/* ************************************************************ */ /* Nome do aluno: Danilo R. Vieira Número USP: 5653262 */ /* Curso: Bach. em Oceanografia Data: 03/11/2007 */ /* MAC-115 Introdução à Computação */ /* Exercício Programa número 3 */ /* ************************************************************ */ #include /* Declaração de constantes */ #define COMPNOME 31 /* Tamanho máximo (em caracteres) do * nome de um arquivo */ #define MAX_PROD 50 /* Número máximo de produtos */ /* Na declaração de vetores, usa-se MAX_PROD+1 como tamanho máximo * do vetor, pois foram descartados elementos de índice zero. * Dessa forma, mantemos correspondência entre o número do produto * e seu índice. */ /* Cabecalhos de funcoes */ void custo_quilo (int n, float q[], float ct[], float cq[]); void ordena (int n, int num[], float cq[]); int enche_mochila (float capm, int n, float q[], int num[], float *qultp, float *ptm); float custo_mochila (int np, float custo_ult, float ct[], int num[]); void bubble_sort_adaptado (float v_f[], int n, int v_i[]); int main () { /* Declaração de variáveis */ FILE *arqentra, /* Arquivo de entrada */ *arqsai; /* Arquivo de saida */ int n, /* Número de produtos no problema atual */ i, /* Contador */ num_prob, /* Número do problema atual */ num[MAX_PROD+1], /* Contem os números dos produtos, * ordenados de acordo com o custo * por quilo */ n_prod; /* Numero de produtos colocados na mochila */ float m, /* Capacidade máxima da mochila */ quant[MAX_PROD+1], /* Armazena a quantidade total * de cada produto */ custot[MAX_PROD+1], /* Armazena o custo total de * cada produto */ cusquilo[MAX_PROD+1], /* Armazena o custo por quilo * de cada produto */ qultp, /* Quantidade do último produto * colocado na mochila */ ptm; /* Peso total dos produtos * na mochila */ char nomearq[COMPNOME]; /* Armazena o nome de um arquivo * (de entrada ou de saida, * dependendo do momento) */ printf ("Digite o nome (maximo %d caracteres)" " do arquivo de entrada :\n", COMPNOME-1); scanf ("%s", nomearq); arqentra = fopen (nomearq, "r"); if (arqentra == NULL) { printf ("ERRO: nao foi possivel abrir arquivo %s\n", nomearq); return 1; } printf ("Digite o nome (maximo %d caracteres) do" " arquivo de saida :\n", COMPNOME-1); scanf ("%s", nomearq); arqsai = fopen (nomearq, "w"); if (arqsai == NULL) { printf ("ERRO: nao foi possivel criar arquivo %s\n", nomearq); return 2; } /* Imprime o cabeçalho do arquivo */ fprintf(arqsai, "*****************************" "*****************************\n" "* Nome do aluno: Danilo R. Vieira " "Numero USP: 5653262 *\n" "*****************************" "*****************************"); num_prob = 1; while (!feof (arqentra)) { fscanf (arqentra, "%d %f ", &n, &m); /* Processa o problema de número num_prob */ fprintf(arqsai, "\n\n" "Problema %d\n" "\n" "Numero de produtos : %d\n" "Capacidade da mochila (em quilos) : %.2f\n" "\n" " Produto Quantidade " "Preco Preco\n" " (numero) (quilos) " "total (quilo)\n" "\n", num_prob, n, m); for (i = 1; i <= n; i++) { fscanf (arqentra, "%f %f ", &quant[i], &custot[i]); num[i] = i; } custo_quilo(n, quant, custot, cusquilo); for (i = 1; i <= n; i++) { fprintf(arqsai, "%8d %13.2f %16.2f %15.2f\n", i, quant[i], custot[i], cusquilo[i]); } ordena(n, num, cusquilo); n_prod = enche_mochila(m, n, quant, num, &qultp, &ptm); if (n_prod == 1) fprintf(arqsai, "\n" "Foi colocado 1 produto na mochila:\n" "\n" " Produto Quantidade\n" " (numero) (quilos)\n" "\n"); else fprintf(arqsai, "\n" "Foram colocados %d produtos na" " mochila, na seguinte ordem:\n" "\n" " Produto Quantidade\n" " (numero) (quilos)\n" "\n", n_prod); for(i = 1; i < n_prod; i++) fprintf(arqsai,"%9d %15.2f\n", num[i], quant[num[i]]); fprintf(arqsai, "%9d %15.2f\n", num[n_prod], qultp); if (n_prod == 1) fprintf(arqsai, "\n" "Peso total do produto na mochila : %.2f (quilos)\n" "Custo total do produto na mochila : %.2f\n", ptm, custo_mochila (n_prod, cusquilo[n_prod]*qultp, custot, num)); else fprintf(arqsai, "\n" "Peso total dos produtos na mochila : %.2f (quilos)\n" "Custo total dos produtos na mochila : %.2f\n", ptm, custo_mochila (n_prod, cusquilo[n_prod]*qultp, custot, num)); fprintf(arqsai, "\n" "-------------------------------" "-------------------------------"); num_prob++; } fclose (arqentra); fclose (arqsai); return 0; } /* Definicoes das funcoes */ /* função custo_quilo(n, q, ct, cq) * Recebe um inteiro n e dois vetores reais q e ct contendo, * respectivamente, a quantidade e o custo total de cada um dos * n produtos. * Determina o vetor real cq, armazenando o custo por quilo de * cada um dos n produtos. */ void custo_quilo (int n, float q[], float ct[], float cq[]) { int cont; /* Contador */ for (cont = 1; cont <= n; cont++) cq[cont] = ct[cont] / q[cont]; } /* função ordena(n, num, cq) * Recebe um inteiro n, um vetor inteiro num com os números dos * n produtos, e um vetor real cq contendo o custo por quilo de * cada um dos n produtos. * Coloca os n números no vetor cq em ordem decrescente, * alterando, respectivamente, o vetor num. */ void ordena (int n, int num[], float cq[]) { int cont, /* Contador */ aux_i[MAX_PROD]; /* Vetor auxiliar */ float aux_f[MAX_PROD]; /* Vetor auxiliar */ /* Ordena cq em ordem crescente e altera a ordem dos * elementos de num de modo que mantenham a correspondência */ bubble_sort_adaptado(cq, n, num); /* Copia os elementos de num e de cq para vetores auxiliares * (em ordem inversa) */ for (cont = 1; cont <= n; cont++){ aux_i[cont] = num[n-cont+1]; aux_f[cont] = cq[n-cont+1]; } /* Copia os elementos dos vetores auxiliares de volta a num * e cq. Assim, o vetor cq ficará ordenado em ordem decrescente * e os elementos de num manterão a correspondedência com * elementos de cq. */ for (cont = 1; cont <= n; cont++){ num[cont] = aux_i[cont]; cq[cont] = aux_f[cont]; } } /* função enche_mochila(capm, n, q, num, *qultp, *ptm) * Recebe um número real capm e um inteiro n, que representam, * respectivamente, a capacidade total (em quilos) de uma * mochila e o número total de produtos. Recebe, também, o * vetor q, contendo a quantidade (em quilos) de cada produto; * e o vetor num, contendo os números dos produtos, ordenados * de acordo com o custo por quilo (ou seja, o primeiro número * no vetor num é o número de um produto com maior custo por * quilo). * A função devolve em *qultp a quantidade (em quilos) do * último produto colocado na mochila, pois pode não ter * colocado toda a quantidade; e em *ptm o peso total dos * produtos na mochila. * A função deve determinar e devolver o número total de * produtos colocados na mochila */ int enche_mochila (float capm, int n, float q[], int num[], float *qultp, float *ptm) { int cont; /* Contador */ cont = 1; *ptm = 0; while ((capm > *ptm) && (cont <= n)) { if (capm-*ptm >= q[num[cont]]) *qultp = q[num[cont]]; else *qultp = capm - *ptm; *ptm += *qultp; cont++; } return cont - 1; } /* função custo_mochila(np, custo_ult, ct, num) * Recebe um inteiro np que representa o número total de * produtos na mochila; e um número real custo_ult com o custo * total do último produto colocado na mochila. Recebe também * o vetor ct, contendo o custo total de cada produto; e o * vetor num, contendo os números dos produtos, ordenados de * acordo com o custo por quilo (em ordem decrescente). * A função deve determinar e devolver o custo total dos * produtos na mochila. */ float custo_mochila (int np, float custo_ult, float ct[], int num[]) { int cont; /* Contador */ float custo_total; /* Custo total dos produtos na mochila */ custo_total = 0; for (cont = 1; cont < np; cont++) custo_total += ct[num[cont]]; custo_total += custo_ult; return custo_total; } /* função bubble_sort_adaptado(v_f, n, v_i) * Recebe o vetor de reais v_f, um inteiro n e o vetor de * inteiros v_i. * Ordena o vetor v_f em ordem crescente e organiza os * elementos correspondentes em v_i. */ void bubble_sort_adaptado (float v_f[], int n, int v_i[]) { int i, j, aux_i; float aux_f; for (i = 1; i <= n; i++) { aux_f = v_f[i]; aux_i = v_i[i]; j = i - 1; while ((j >= 0) && (aux_f < v_f[j])){ v_f[j+1] = v_f[j]; v_i[j+1] = v_i[j]; j--; } v_f[j+1] = aux_f; v_i[j+1] = aux_i; } }