Antes de abordar os problemas, assista às aulas 7 a 8 , leia e aprofunde-se nos “ Materiais adicionais da terceira semana ”. Eles são dedicados a algoritmos de busca (linear e binário), classificação (há muitos deles!), bem como ao trabalho de um depurador (a capacidade de trabalhar com um depurador para depurar programas é uma habilidade extremamente importante!). Se tudo correu como deveria com as aulas teóricas e teóricas, você poderá facilmente responder às questões do teste:
Por que a pesquisa binária requer um array classificado?
Por que a classificação por bolha é estimada em O(n2)?
Por que a estimativa da classificação por inserção é Ω (n)?
Como funciona a classificação por seleção? Descreva em três frases (ou menos).
Qual é o limite superior (pior caso) de quanto tempo a classificação por mesclagem pode ser executada?
O depurador GDB permite depurar um programa. E se você formular mais especificamente, o que exatamente isso permite que você faça?
Metas
Aprenda a trabalhar com projetos que contêm vários arquivos
Aprenda a ler o código-fonte de outra pessoa
Compreenda vários algoritmos e funções recursivas
A maioria destes objectivos é praticamente impossível de avaliar formalmente. Portanto, do ponto de vista da verificação formal dos problemas, há pouca coisa que lhe pareça difícil. Porém, lembramos: você só pode aprender programação através da prática constante! Portanto, encorajamos você não apenas a resolver as tarefas, mas também a gastar tempo e esforço adicionais e implementar todos os algoritmos que foram discutidos esta semana. Avançar!
Começar
Lembre-se de que, para os problemas práticos das semanas um e dois, você escreveu programas do zero e criou seus próprios diretórios pset1 e pset2 usando o comando mkdir . Para a tarefa prática da terceira semana, você precisa baixar a distribuição (ou “distro”, como a chamamos) que escrevemos e adicionar suas próprias linhas de código a ela. Primeiro, leia nosso código e tente entendê-lo. A habilidade mais importante desta semana é aprender a ler o código de outras pessoas. Portanto, faça login em cs50.io e execute o comando update50 em uma janela de terminal para garantir que a versão do espaço de trabalho esteja atualizada. Se você fechou acidentalmente a janela do terminal e não consegue encontrá-la, vá ao menu Exibir e certifique-se de que a opção Console esteja marcada (marque se não estiver). Clique em (+), dentro do círculo verde na moldura da janela do terminal, selecione Novo Terminal . Depois disso, execute o comando cd ~/workspace e certifique-se de estar dentro do diretório do espaço de trabalho (este é o seu diretório). Depois disso, execute o comando: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip para baixar o arquivo ZIP do livro de problemas em sua área de trabalho (wget é o comando de download do Linux). Se tudo estiver bem, você verá a seguinte frase na linha: 'pset3.zip' saved Certifique-se de que você realmente baixou o pset3.zip executando o comando: ls e depois execute unzip pset3.zip para descompactar o arquivo. Se você executar o comando ls novamente , também verá o diretório pset3 . Acesse-o executando o comando cd pset3 e solicite a visualização do conteúdo do diretório novamente: ls você verá que existem dois subdiretórios neste diretório: fifteen find Já intrigante!
Procurar
Vamos agora mergulhar em um desses subdiretórios. Para fazer isso, executaremos o comando: cd ~/workspace/pset3/find Se você exibir o conteúdo desta pasta na tela (provavelmente já se lembra de como fazer isso), é isso que você deverá ver: helpers.c helpers.h Makefile find.c generate.c Nossa, são muitos arquivos. Mas não se preocupe, vamos lidar com eles agora. O arquivo generate.c contém código para um programa que usa um "gerador de números pseudo-aleatórios" (gerado pela função drand48 ) para gerar um grande número de números aleatórios (na verdade, pseudo-aleatórios, os computadores não conseguem lidar com aleatoriedade pura!) e coloque-os um de cada vez na linha. Compile o programa: make generate Agora execute-o executando o comando: ./generate O programa fornecerá a seguinte mensagem: Usage: generate n [s] Isso significa que o programa espera um ou dois argumentos de linha de comando. n, é obrigatório; este número significa quantos números pseudoaleatórios você deseja criar. O parâmetro s é opcional, conforme indicado entre colchetes. O número s pode ser chamado de "semente" para o gerador de números pseudoaleatórios. Por "semente" queremos dizer os dados de entrada para o gerador de números pseudoaleatórios que afetam sua saída. Por exemplo, se você estiver usando drand48, primeiro chamando srand48 (outra função cujo objetivo é "semear" drand48) com um argumento de, digamos, 1, e então, chamando drand48 três vezes, drand48 pode retornar 2728, depois 29785 e depois 54710. Se você, em vez do anterior, usando drand48, primeiro chamar srand48 com um argumento de, digamos, 2, e depois usar drand48 novamente três vezes, drand48 pode retorne 59797, depois 10425 e depois 37569. Mas se você ver novamente drand48 chamando srand48 novamente com um argumento de 1, o resultado das próximas três chamadas para drand48 você obterá 2728 novamente, depois 29785 e depois 54710! Veja, tudo acontece por uma razão. Execute o programa novamente, desta vez, digamos n=10, conforme mostrado abaixo; você verá uma lista de 10 números pseudo-aleatórios. ./generate 10 Vamos executar o programa uma terceira vez com o mesmo valor de n; você deverá ver outra lista de 10 números. Agora tente executar o programa com dois parâmetros. Vamos considerar s = 0 conforme mostrado abaixo. ./generate 10 0 Agora execute o mesmo comando novamente: ./generate 10 0 você nem pode discutir: você viu a mesma sequência “aleatória” de dez dígitos novamente. Isto é o que acontece se você não alterar as sementes do gerador de números pseudoaleatórios. Agora vamos dar uma olhada no próprio programa generate.c(lembra como?). Os comentários no início deste arquivo explicam a funcionalidade geral do programa. Mas parece que esquecemos de comentar o próprio código. Leia o código com atenção e leia-o até entender o significado de cada linha. Em seguida, comente este código para nós, substituindo cada TODO por uma frase que descreve o propósito ou funcionalidade da linha ou linhas de código correspondentes. (nota: unsigned int é um int “unsigned”, o que significa que não pode ser negativo). Para obter mais informações sobre rand ou srand, execute: man drand48 ou man srand48 Depois de comentar o máximo que puder em generate.c, recompile o programa para ter certeza de que não quebrou nada: make generate Se generate não compilar mais, corrija o que você quebrado: )! Como lembrete, o comando make automatiza a compilação de código, então você não precisa executar o comando clang inserindo manualmente um monte de opções. Mas, na verdade, make simplesmente simplifica nossa entrada, mas, na verdade, o mesmo ruído com os parâmetros que precisamos está oculto por trás dele. Entretanto, à medida que seus programas ficam maiores, o make não consegue mais descobrir, a partir do contexto, como compilar o código. Neste caso, você terá que informar ao make como compilar os programas, especialmente se eles envolverem o uso de arquivos de origem diferentes (como .c). Para resolver este problema usaremos arquivos de configuração (Makefiles) que informam ao make exatamente o que fazer. Como o comando make sabia como deveríamos compilar e gerar? Na verdade, a equipe usou um arquivo de configuração que já havíamos escrito. Este arquivo é chamado Makefile e está localizado no mesmo diretório que generate.c . Makefile é uma lista de regras que especificam como criar o arquivo generate a partir de generate.c. No arquivo você encontrará, em particular, as linhas relevantes: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c A primeira linha informa ao make que um "target" chamado generate deve ser criado chamando o comando da segunda linha. Além disso, a primeira linha informa ao make que generate depende de generate.c, o que significa que o make só reconstruirá o generate nas execuções subsequentes se o arquivo tiver sido alterado. Não é um truque ruim para economizar tempo, certo? Na verdade, execute o comando abaixo novamente se você não alterou generate.c . make generate Você será informado que o generate já foi atualizado para a versão atual. Nota : O recuo no início da segunda linha não é uma sequência de espaços, mas sim um caractere de tabulação. Infelizmente, make exige que os comandos sejam precedidos por tabulações, então tome cuidado para não alterá-los para espaços ou você encontrará erros estranhos! O sinalizador -Werror informa ao comando clangtrate os avisos (ruins) como erros (pior ainda), para que você seja forçado (de uma forma boa e educacional!) a corrigi-los. Agora vamos dar uma olhada no arquivo find.c. Observe que este programa espera um argumento de linha de comando: "iglu", que deve ser encontrado em um "palheiro" de valores. Depois disso, revise o código e compile o programa executando o comando abaixo. make find make basicamente nos deu o seguinte: clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Preste atenção! Você acabou de compilar um aplicativo que consiste em um, mas dois arquivos: helpers.c e find.c . Como você soube disso? Para entender isso, abra o Makefile novamente para ver o que realmente está acontecendo lá. As linhas relevantes estão abaixo. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm O que queremos dizer com dependência (depois dos dois pontos) é que quaisquer alterações em find.c , helpers.c ou helpers.h forçarão o make a reconstruir o find na próxima vez que for chamado para esses propósitos. Agora execute este programa fazendo, por exemplo, o seguinte: ./find 13 Depois disso, você será solicitado a fornecer uma determinada pilha (isto é, números inteiros) e alimentá-los com um canudo de cada vez. Quando você se cansar de digitar números, pressione a combinação de teclas Ctrl-D . Esta combinação enviará ao programa um caractere de fim de arquivo (EOF). O símbolo forçará a função GetInt da biblioteca CS50 a retornar a constante INT_MAX , e esta, por sua vez, em find.c forçará find a parar de digitar "stack". O programa irá agora procurar a agulha no palheiro que você forneceu e, eventualmente, informará se ela foi encontrada. Resumindo, o programa procura algum valor em um array. Pelo menos deveria, mas o problema é que ela ainda não encontrará nada! Mas aqui você vem para o resgate! Falaremos sobre a importância do seu papel um pouco mais tarde. Na verdade, o processo de fornecer um palheiro pode ser automatizado, pelo menos "mesclando" a saída de generate com find como entrada. Por exemplo, o comando abaixo passa 1000 números pseudoaleatórios para find, que então pesquisa entre esses valores por 42. ./generate 1000 | ./find 42 Observe que quando generate passa os dados brutos para find, você não verá o número de geração, mas verá find em execução . Alternativamente, você pode "redirecionar" a saída de generate para um arquivo com um comando como este: ./generate 1000 > numbers.txt O conteúdo deste arquivo pode ser redirecionado para a entrada de find com o comando: ./find 42 < numbers.txt Vamos dar outra olhada no código no Makefile e observar o seguinte linha: all: find generate Isso significa que você pode construir, gerar e localizar executando o seguinte comando: make all Além disso, o comando abaixo desta linha é equivalente ao comando acima dela, já que make constrói a primeira entrada no Makefile por padrão. make Se você pudesse resumir todas essas tarefas práticas em um comando! Mas - infelizmente! Por fim, preste atenção nessas últimas linhas do Makefile: clean: rm -f *.o a.out core find generate Esta entrada permite remover todos os arquivos que terminam em .o ou são chamados de core (explicaremos isso em um momento!), e também executar o find ou gerar programas de forma simples. executando a linha: Se você quiser make clean experiment , então aqui está algo para ter cuidado: não adicione, digamos, *.c à última linha do Makefile! (por quê?) Todas as linhas que começam com o sinal # são apenas comentários.
Tarefa 1: Pesquisa
É hora de algo interessante! Observe que find.c chama search , uma função declarada em helpers.h . Infelizmente, esquecemos de implementar esta função completamente em helpers.c ! (Deve-se notar que poderíamos colocar o conteúdo de helpers.h e helpers.c em um find.c . Mas às vezes é melhor separar os programas em vários arquivos. Especialmente se algumas funções, ou melhor, funções utilitárias, puderem ser úteis para outros programas. Como as funções da biblioteca CS50, por exemplo. Dê uma olhada em helpers.c e você verá que a pesquisa sempre retorna falso, independentemente de o valor fornecido estar em valores. Reescreva a pesquisa para que ela use pesquisa linear, retornando verdadeiro , se o valor estiver em valores e falso se o valor não estiver em valores. Tome cuidado para retornar falso imediatamente se n não for positivo. Quando estiver pronto para verificar a validade, tente chamar o seguinte comando: Como um dos números ./generate 1000 50 | ./find 127 impressos com generate quando 50 foi propagado é 127, seu código deve encontrar a agulha! Para contraste, tente este comando: ./generate 1000 50 | ./find 128 Como 128 não está no conjunto de números gerados por generate quando 50 foi propagado, seu código não deve encontrar a "agulha" . Execute outros testes executando generate com alguma semente, analisando a saída e procurando a agulha que deveria estar no palheiro. Observe que main em find.c é escrito de tal forma que find retorna 0 se a "agulha" for encontrada, caso contrário, retorna 1. Você pode verificar o chamado "código de saída" que main retorna quando executado após executar algum outro comandos echo $? . Por exemplo, se sua implementação de pesquisa estiver correta, se você executar ./generate 1000 50 | ./find 127 echo $? verá 0, enquanto 127 está entre os 1000 números gerados por gerar com uma semente de 50, portanto, a pesquisa que você escreveu deve retornar verdadeiro. Neste caso, main (escrito por nós) deve retornar 0 (ou seja, exit). Se você fornecer o seguinte input ./generate 1000 50 | ./find 128 echo $? , verá 1 porque 128 não está entre os 1000 números que foram gerados por generate com uma semente de 50. Nesse caso, search (escrito por você) retornará false, e main (escrito por nós ) retornará 1 (e então terminará o trabalho). Você entende a lógica? Quando tudo estiver pronto para ser verificado usando check50, execute o seguinte comando: check50 2015.fall.pset3.find helpers.c A propósito, você não deve se acostumar a testar seu código usando check50 antes de testá-lo você mesmo. Afinal, check50 realmente não existe, então executar o código com suas próprias amostras de entrada, comparando a saída real com a saída esperada, é o melhor hábito que você pode adquirir neste momento. É verdade, não fique viciado! Se você estiver interessado em brincar com a implementação de find dos assistentes cs50, execute este comando: ~cs50/pset3/find
Ordenação
A busca linear não é algo realmente impressionante, mas desde as primeiras palestras (e na sétima repetimos esse truque novamente!) você lembra que pode encontrar uma agulha no palheiro muito mais rápido. Mas primeiro precisamos arrumar nosso palheiro. Observe que find.c chama sort , uma função declarada em helpers.h . Infelizmente, “esquecemos” de implementar totalmente esse recurso em helpers.c ! Dê uma olhada em helpers.c e você verá que sort retorna instantaneamente, mesmo que a função principal de find realmente passe para ele o array real. Agora lembre-se da sintaxe de declaração do array. Você não apenas especifica o tipo de elemento dessa matriz, mas também especifica seu tamanho entre colchetes. Isto é o que fazemos para o palheiro em find.c : int haystack [MAX]; mas ao percorrer um array, você especifica apenas seu nome. E fazemos exatamente da mesma maneira quando passamos pelo palheiro para fazer sort em find.c : sort (haystack, size); (Adivinhe por que passamos o tamanho desse array separadamente?) Quando declaramos uma função que usa um array unidimensional como argumento, não precisamos especificar o tamanho do array. Da mesma forma, não fizemos isso quando declaramos sort em helpers.h (e helpers.c): void sort (int values [] int n); Implemente sort para que a função realmente classifique o array de números de pequeno para grande. Ele precisa de um tempo de execução igual a O(n 2 ), onde n é o tamanho do array. Você provavelmente desejará implementar classificação por bolha, classificação por seleção ou classificação por inserção, conforme aprendemos sobre isso na terceira semana. Porém, é importante ressaltar: não existe uma forma “correta” de implementar esses algoritmos. Há um grande número de variações. Na verdade, você sempre pode melhorá-los se achar adequado, desde que sua implementação convirja para O(n2 ) . Entretanto, deixe a experimentação para o corpo da função e, para simplificar os testes, não altere nossa declaração de classificação. Deveria ficar assim: void sort (int values [] int n); Como a função retorna um valor nulo, ela não deve retornar um array ordenado. Em vez disso, ele deve classificar "destrutivamente" o array real pelo qual está "percorrendo", movendo seus elementos. Na quarta semana discutiremos que arrays são passados por referência e não por valor. Ou seja, sort não receberá cópias do array, mas sim o próprio array original. Embora não seja possível alterar nossa declaração de classificação, você sempre pode definir sua própria função em helpers.c, que pode então ser chamada a partir da classificação. Decida por si mesmo a melhor forma de testar sua implementação de classificação. Não esqueça que printf e GDB irão te ajudar! E não se esqueça de que você pode criar a mesma sequência de números pseudoaleatórios repetidamente, especificando explicitamente os valores iniciais para gerar.
Pesquisa binária, dicas
A primeira coisa que você precisa entender sobre a função find é que já escrevemos o código (distribuição). Estamos simplesmente preenchendo algumas lacunas no código existente. O programa find.c solicita a entrada de números (ou seja, para preencher uma "pilha") e, a pedido do usuário, procura uma "agulha" nela, usando funções de classificação e pesquisa definidas em helpers.c . Então, find já está escrito, precisamos escrever helpers . Então aqui está o que precisamos fazer:
Implementar pesquisa. Esta função deve retornar verdadeiro se o valor for encontrado na pilha e falso se não estiver lá.
Implemente sort, uma função que classifica uma matriz de valores.
Inicialmente, a busca foi implementada como linear. Mas você pode fazer melhor. O algoritmo de pesquisa linear é executado em tempo O(n) . Sua tarefa é escrever um algoritmo de busca binária. Seu tempo de execução é O(log n) . No entanto, o problema é que ele precisa de dados classificados como entrada, caso contrário não funcionará. Você se lembra do exemplo do livro rasgado e provavelmente sabe por que isso acontece. Se você fez uma pesquisa binária pelos elementos e não há mais deles (ou seja, simplesmente não há “agulha” nesta “pilha”), você precisa que a função retorne falso. A pesquisa binária pode ser implementada de forma iterativa ou recursiva (David Malan falou sobre recursão na oitava palestra).
Depois disso, execute o comando 
GO TO FULL VERSION