Departamento de Ciência da
Computação - IME - USP
I make mistakes. I always have, and I probably always will. But I like
to think that I learn something, every time I go astray.
D.E. Knuth
"Literate Programming"
Este primeiro exercício-programa é simples e serve para irmos aquecendo os motores.
Escreva um programa em C que recebe uma sequência de n números inteiros x0,x1,...,xn-1, e encontra índices l,r, com l ≤ r, tais que a soma xl + xl+1 +...+ xr seja máxima.
Por exemplo, dada a sequência
1, -3, 6, -4, 2, -5, 1, 8, -4, 2, 3, -1, 2, -3, 1, 3, -5, 3 , -3, 4,
seu programa deve devolver os índices 6 e 15, pois o segmento
Um 'esqueleto' do programa é dado. O arquivo esqueleto.c pode ser copiado daqui. A única coisa que você deve fazer nesse esqueleto é acrescentar uma função de nome segmax. No esqueleto é mostrado onde você deve escrever a função e a sua espeficação está em em comentário antes dela.
Para tornar o desafio de fazer seu programa mais interessante, será fornecido a você um programa executável que, além de resolver o problema acima, imprime o tempo gasto (em segundos).
Para cronometrar o tempo de execução o arquivo esqueleto.c contém o seguinte trecho de código:
clock_t t0, tf;
double tempo_gasto;
...
/* Leitura de dados */
...
t0 = clock();
...
/* ache um segmento de soma máxima */
...
tf = clock();
tempo_gasto = ( (double) (tf - t0) ) / CLOCKS_PER_SEC;
...
printf("Tempo gasto: %lf s\n", tempo_gasto);
O tipo clock_t e a constante CLOCKS_PER_SEC
já estão definidos na biblioteca time.h.
Desse modo, você pode comparar o desempenho do seu programa com o que vamos fornecer.
O seu programa deve ler a sequência de números a partir de um arquivo cujo nome é fornecido pelo usuário através da linha de comando. Isto já está feito no arquivo esqueleto.c. O arquivo é binário (hmmm, isto não é usual), e na primeira posição contém o número de elementos da sequência e depois a sequência propriamente dita:
Para gerar os dados você pode usar o programa gera.c, mas sugiro que antes você teste seu programa com arquivos textos de sequências pequenas de números.
O programa deve aceitar valores de n entre 1 e 500M (500 milhões ... arquivos de 500Mb ... é muito ?). Para a leitura de arquivos binários o esqueleto.c utiliza as funções fopen e fread disponíveis na biblioteca de funções do C. Você pode ver a utilização dessas funções no esqueleto.c e no programa gera.c.
Como saída, seu programa deve imprimir:
meu_prompt> segmax seq100M O arquivo de entrada "seq100M" contem 100000000 numeros. Foi encontrada uma subsequencia de soma maxima com Inicio: 48658259 Final: 61583411 Soma: 2204931 Tempo: 0.140000 s (nao incluido tempo com leitura)A saída do programa com um arquivo de 500M foi
meu_prompt> segmax seq500M O arquivo de entrada "seq500M" contem 500000000 numeros. Foi encontrada uma subsequencia de soma maxima com Inicio: 118875343 Final: 388708744 Soma: 12636316 Tempo: 0.720000 s (nao incluido tempo com leitura)Teste seu programa (sua função) com sequencias grandes, mas inicialmente teste com arquivos bem pequenos. De preferência arquivos textos com uma sequência pequena como a mostrada no início deste enunciado.
O executável segmax resolve o problema. Compare os resultados obtidos pelo seu programa com o do executável fornecido.
A propósito, dados experimentais só fazem sentido especificando-se o computador usado. As especificações do computador que geraram as saídas acima são
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz cpu MHz : 1596.000 cache size : 4096 KB MemTotal : 3354708 kB
Mudando de assunto, apesar de vocês não serem obrigados a encherem os seus programas de comentários, está na hora de começar a aprender a escrevê-los.
''Antes de cada função [e bloco] diga o que a função [e bloco] faz. Procure responder as perguntas que um usuário faria: que dados essa função recebe? que suposições faz sobre esses dados? que resultados devolve? Não perca tempo tentando dizer como a função faz o que ela faz.'' (Paulo Feofiloff)
Se o tamanho de suas funções é razoavelmente pequeno, como devem ser, o conselho é extremamente útil. Leia mais sobre documentação na página Documentação do sítio de Projeto de Algoritmos em C de Paulo Feofiloff.
Os programas entregues também devem ter uma boa endentação ou leiaute. Leia sobre isto na página Leiaute do sítio de Projeto de Algoritmos em C de Paulo Feofiloff.