ROB BOWDEN: Oi, eu sou Rob Bowden, e vamos falar sobre quiz0. Então, primeira pergunta. Esta é a pergunta que você precisava para codificar o número 127 nos bulbos binários. Se você quisesse, você poderia fazer a conversão regular de bi-- ou, de decimal para binário. Mas isso provavelmente vai para ter um monte de tempo. Quero dizer, você pode descobrir que, OK, um está lá, 2 está lá, 4 está lá, 8 está lá. Maneira mais fácil, é de 128 127 menos um. Essa lâmpada mais à esquerda é o 128-bit. Assim, 127 é realmente apenas tudo das outras lâmpadas, já que é o mais à esquerda lâmpada menos 1. Isso é tudo para essa pergunta. 

Pergunta um. Assim, com 3 bits que puder representam 8 valores distintos. Por que, então, é de 7 a maior não-negativo inteiro decimal pode representar? Bem, se só podemos representam 8 valores distintos, então o que nós vamos ser representando é de 0 a 7. 0 leva-se um dos valores. 

Pergunta dois. Com n bits, quantas distinta valores que podem representar? Assim, com n bits, você tem 2 os valores possíveis para cada bit. Portanto, temos dois valores possíveis para o primeiro bit, dois valores possíveis para o segundo, 2 possível para a terceira. E de modo que é 2 vezes 2 vezes 2, e em última análise, a resposta é de 2 a n. 

Pergunta três. O que é 0x50 em binário? Então lembre-se de que tem um hexadecimal muito conversão simples de binário. Então aqui, nós só precisamos olhar para a 5 e a 0 de forma independente. Então, qual é 5 em binário? 0101, que é o 1 bit eo bit 4. Qual é 0 em binário? Não complicado. 0000. Então, basta colocá-los juntos, e que é o número total de binário. 01.010.000. E se você quisesse você poderia decolar que mais à esquerda zero. É irrelevante. 

Então, em alternativa, o que é 0x50 em decimal? Se você quisesse, você could-- se você estiver mais confortável com o binário, você poderia tomar essa resposta binária e convertê-lo em decimal. Ou podemos apenas lembrar que hexadecimal. Assim que 0 é no 0 º lugar, e a 5 é, no 16 para o primeiro lugar. Então, aqui, temos 5 vezes 16 para o em primeiro lugar, além de 16 0 vezes para a zero, é 80. E se você olhou para o título para a pergunta, era CS 80, que era uma espécie de dica para a resposta a este problema. 

Pergunta cinco. Temos este roteiro zero, o que é repetindo 4 vezes manteiga de amendoim geléia. Assim como nós agora o código que em C? Bem, nós temos aqui-- a parte em negrito é a única parte que você tinha de implementar. Portanto, temos um 4 loop que é looping 4 vezes,-ing printf Peanut Butter Jelly, com a nova linha que o problema pede. 

Pergunta seis, outro problema do risco. Nós vemos que estamos em um loop para sempre. Nós estamos dizendo que a variável i e, em seguida, incrementando i por um. Agora nós queremos fazer isso em C. Há múltiplas formas que poderíamos ter feito isto. Aqui nós aconteceu para codificar o para sempre como um laço while (true). Assim, declaramos a variável i, apenas como tivemos i variável no Scratch. Declare a variável i, e para sempre while (true), nós dizemos que a variável i. Então printf% i-- ou você poderia ter usado% d. Dizemos que variável e então incrementá-lo, i ++. 

Pergunta sete. Agora, queremos fazer algo muito semelhante Mario ponto c do problema definido. Queremos imprimir estas hashtags, queremos imprimir um cinco por três retângulo destes hashes. Então, como é que vamos fazer isso? Bem, nós damos-lhe um todo monte de código, e você só tem que preencher a função de grade de impressão. 

Então, o que PrintGrid parece? Bem, você é passado o largura e a altura. Portanto, temos um exterior 4 loop, que é looping ao longo de todas as linhas do presente grade que queremos imprimir. Então nós temos a 4 circuito inter-nested, essa é a impressão sobre cada coluna. Assim, para cada linha, nós imprimimos para cada coluna, um único hash. Então, no final da linha que imprime um única linha nova para ir para a próxima linha. E é isso por toda a rede. 

Pergunta oito. Uma função como PrintGrid é dito ter um efeito colateral, mas não um retorno valor. Explique a distinção. Então, isso depende de você lembrar o que é um efeito colateral é. Bem, um retorno value-- sabemos PrintGrid não tem valor de retorno, uma vez que aqui se diz vazio. Então, qualquer coisa que retorna void realmente não retorna nada. Então, qual é o efeito colateral? Bem, um efeito colateral é qualquer coisa que tipo de persistir após o término da função que não era apenas retornou, e não foi só a partir dos insumos. 

Assim, por exemplo, podemos alterar uma variável global. Isso seria um efeito colateral. Neste caso particular, uma efeito colateral muito importante está imprimindo na tela. Assim que é um efeito colateral PrintGrid que tem. Nós imprimir essas coisas para a tela. E você pode pensar que como um efeito colateral, já que é algo que persistir após essa função termina. Isso é algo fora do escopo desta função que, em última análise está sendo alterado, o conteúdo da tela. 

Pergunta nove. Considere o programa abaixo, para que os números de linha foram adicionados para a causa da discussão. Portanto, neste programa estamos apenas chamando GetString, armazenando-o Nesta variável s, e depois imprimir essa variável s. Está bem. Assim, explicar por que uma linha está presente. #include CS50 ponto h. Por que precisamos de #include CS50 dot h? Bem, nós estamos chamando a Função GetString, e GetString é definida na biblioteca CS50. Então, se não tivéssemos #include CS50 ponto h, teríamos que declaração implícita do erro da função GetString do compilador. Então, precisamos incluir o library-- precisamos incluir o arquivo de cabeçalho, ou então o compilador não vai reconhecer que existe GetString. 

Explique por que a linha dois está presente. Assim padrão dot h io. É exatamente o mesmo como o problema anterior, exceto em vez de lidar com GetString, estamos falando de printf. Então, se nós não dissemos que precisamos para incluir padrão io ponto h, então não seria capaz para usar a função printf, porque o compilador não saber sobre ele. 

Para entendermos que o que é o significado de anular em linha de quatro? Portanto, temos aqui int main (void). Isso é apenas dizendo que nós não estão recebendo qualquer linha de comando argumentos para principal. Lembre-se que nós poderíamos dizer int principais suportes int argc argv corda. Então aqui nós apenas dizer vazio de dizer que estão ignorando os argumentos de linha de comando. 

Explique, no que diz respeito à memória, exatamente o que GetString em linha seis retornos. GetString está retornando de um bloco de memória, uma matriz de caracteres. É realmente de voltar a ponteiro para o primeiro caractere. Lembre-se que uma string é uma estrela de char. Assim, s é um ponteiro para o primeiro personagem em qualquer que seja a seqüência é que o usuário digitou no teclado. E que a memória passa a ser malloced, para que a memória está no heap. 

Pergunta 13. Considere o programa abaixo. Então, tudo isso programa está fazendo é printf-ing 1 dividido por 10. Então, quando compilado e executado, este programa saídas 0.0, apesar de 1 dividido por 10 é de 0,1. Então por que é 0.0? Bem, isso é porque da divisão inteira. Assim, é um número inteiro de 1, 10 é um número inteiro. Então, 1 dividido por 10, tudo é tratada como números inteiros, e no C, quando fazemos a divisão inteira, nós truncar qualquer ponto decimal. Então, 1 dividido por 10 é 0, e então nós estamos tentando para imprimir que, como uma bóia, de modo zero, impresso como um float é de 0,0. E é por isso que temos 0,0. 

Considere o programa abaixo. Agora estamos imprimindo 0.1. Portanto, não há divisão de inteiros, estamos apenas a impressão de 0,1, mas estamos de imprimi-lo 28 casas decimais. E temos essa 0,1000, um grupo inteiro de zeros, 5 5 5, blá blá blá. Portanto, a questão aqui é por isso que o faz imprimir que, em vez de exatamente 0,1? 

Assim, a razão é aqui agora ponto flutuante imprecisão. Lembre-se que um float é de apenas 32 bits. Por isso, só pode representar um número finito de valores de ponto flutuante com os 32 BITS. Bem, há, em última instância infinitamente muitos valores de ponto flutuante, e há infinitamente muitos flutuante valores pontuais em entre 0 e 1, e estamos, obviamente, capaz de representam ainda mais valores do que isso. Então nós temos que fazer sacrifícios para ser capaz de representar a maioria dos valores. 

Assim, um valor como 0,1, aparentemente não podemos garantir que exatamente. Então, ao invés de representar 0,1 nós fazemos o melhor que podemos representar este 0.100000 5 5 5. E isso é muito perto, mas para uma série de aplicações você tem que se preocupar com ponto flutuante imprecisão, porque nós simplesmente não pode representar todos os pontos flutuantes exatamente. 

Pergunta 15. Considere o código abaixo. Estamos apenas a impressão 1 mais 1. Portanto, não há nenhum truque aqui. 1 mais 1 avalia a 2, e então nós estamos imprimindo isso. Isso só imprime 2. 

Pergunta 16. Agora estamos imprimindo o caráter 1 mais o caráter 1. Então, por que isso não faz imprimir a mesma coisa? Bem, o personagem 1 mais o caráter 1, o personagem tem um valor ASCII 49. Então, isso realmente está dizendo 49 mais 49, e em última análise, isso vai imprimir 98. Portanto, este não imprime 2. 

Pergunta 17. Completar a implementação de impar abaixo de tal maneira que a função retorna true se n é estranho e falso se n é par. Esta é uma grande propósito para o operador mod. Então, tomamos nosso argumento n, se n mod 2 é igual a 1, bem que significa que n dividido por 2 tinha um resto. Se n dividido por 2 tinha um remanescente, que significa que n é ímpar, então voltamos verdade. Outra coisa que retornar falso. Você também poderia ter feito n mod 2 é igual a zero, retornar falso, senão retornar verdadeiro. 

Considere a função recursiva abaixo. Assim, se n é inferior ou igual a 1, de regresso 1, else return n vezes f de n menos um. Então, qual é essa função? Bem, este é apenas o função fatorial. Isso está muito bem representado como n fatorial. 

Assim questão 19 agora, queremos assumir esta função recursiva. Queremos torná-lo interativo. Então, como vamos fazer isso? Bem para o pessoal solução, e novamente há várias maneiras que você poderia ter feito que, começamos com este produto int é igual a 1. E ao longo deste loop for, vamos se multiplicar produto para finalmente acabar com o fatorial completo. Assim, para int i é igual a 2, i é inferior ou igual a n, i ++. 

Você pode estar se perguntando por que eu é igual a 2. Bem, lembre-se que aqui temos que fazer com que o nosso caso base está correto. Assim, se n for menor ou igual 1, nós estamos apenas retornando uma. Então, aqui, começamos a i é igual a 2. Bem, se eu fosse um, então as-- ou se n fosse 1, então o loop não seria executado em tudo. E assim teríamos apenas produto de retorno, que é 1. Da mesma forma, se n fosse nada menos do que 1-- se fosse 0, 1 negativo, whatever-- nós ainda estaríamos voltando 1, que é exatamente o que o versão recursiva está fazendo. 

Agora, se n for maior que 1, então nós vamos fazer pelo menos um iteração deste circuito. Então, digamos que n é 5, então nós estamos vai fazer vezes de produtos é igual a 2. Portanto, agora o produto é 2. Agora nós vamos fazer é igual a 3 vezes produtos. Agora é 6. Produto vezes é igual a 4, agora é 24. Produto é igual a 5 vezes, agora é de 120. Então, em última análise, estamos voltando 120, que é corretamente 5 fatorial. 

Pergunta 20. Este é aquele em que você tem que preencher nesta tabela com qualquer algoritmo, qualquer coisa que já vimos, que se encaixa nesses prazo algorítmica vezes esses tempos de execução assintótica. Então, o que é um algoritmo que omega é de 1, mas grande O de n? Portanto, não poderia ser infinitamente muitas respostas aqui. O que temos visto, provavelmente, mais freqüentemente é apenas busca linear. 

Assim, no melhor dos casos cenário, o item que estamos procurando está no início da lista e assim em omega de 1 passos, a primeira coisa que verificar, nós apenas retornar imediatamente que encontramos o item. Na pior das hipóteses, o produto é, no final, ou o item não está na lista de todo. Então, temos que procurar toda a lista, tudo n elementos, e é por isso que é o de n. 

Portanto, agora é algo que é ao mesmo tempo omega de log n n, e grande O de n log n. Bem, a coisa mais relevante nós vimos aqui é merge sort. Então, merge sort, lembre-se, é, em última análise teta de n log n, onde teta é definida se ambos omega e grande O são os mesmos. Ambos n log n. 

O que é algo que é omega de n, e O de n ao quadrado? Bem, mais uma vez há várias respostas possíveis. Aqui nós acontecer a dizer bubble sort. Ordenação por inserção também funcionaria aqui. Lembre-se que bubble sort tem que optimização, onde, se você é capaz de obter toda a lista sem a necessidade de fazer quaisquer swaps, então, bem, podemos voltar imediatamente que a lista foi classificada para começar. Assim, na melhor das hipóteses, é apenas omega de n. Se ele não é apenas um bem lista para começar com ordenados, então nós temos O de n ao quadrado swaps. E, finalmente, temos a seleção espécie para n ao quadrado, ambos omega e grande O. 

Pergunta 21. O que há de integer overflow? Bem de novo, semelhante à anterior, temos apenas um número finito de pedaços para representar um número inteiro, Então, talvez 32 bits. Vamos dizer que temos um inteiro assinado. Em seguida, em última análise, a maior número positivo que pode representar é de 2 a 31 menos 1. Então o que acontece se tentarmos então incrementar esse número inteiro? Bem, nós estamos indo para ir de 2 a 31 menos 1, todo o caminho para negativa 2 a 31. Portanto, este é integer overflow quando você manter o incremento, e, finalmente, você não pode obter mais alto e ele só envolve toda a maneira para trás em torno de um valor negativo. 

Que tal um buffer overflow? Assim, um tampão de overflow-- lembre-se que é um buffer. É apenas um pedaço de memória. Algo como uma matriz é um buffer. Então, um buffer overflow é quando você tenta acessar a memória além do final do array. Então, se você tem um matriz de tamanho 5 e você tentar acessar o suporte de matriz 5 ou 6 suporte ou suporte 7, ou qualquer coisa além do final, ou mesmo nada suporte de matriz below-- negativo 1-- todos esses são estouros de buffer. Você está tocando memória em maus caminhos. 

Pergunta 23. Então, em um presente que você precisa para implementar strlen. E nós lhes dizemos que você pode assumir s não será nulo, assim você não tem que fazer qualquer verificação para nulo. E existem várias maneiras você poderia ter feito isso. Aqui nós apenas tomar o simples. Começamos com um contador, n. n é contar quantos caracteres existem. Então, vamos começar com 0, e então nós iterar sobre a lista inteira. 

S é igual a 0 suporte do caractere terminador nulo? Lembre-se que estamos procurando o caractere terminador nulo para determinar quanto tempo a nossa cadeia é. Isso vai terminar qualquer seqüência relevante. Então é s suporte 0 igual para o terminador nulo? Se não é, então vamos olhar para s faixa 1, s 2 suporte. Continuamos até que encontrar o terminador nulo. Uma vez que nós encontramos, então n contém o comprimento total da cadeia, e podemos retornar apenas isso. 

Pergunta 24. Portanto, este é aquele em que você tem que fazer o trade off. Então, uma coisa é boa em um maneira, mas de que maneira é ruim? Então, aqui, merge sort tende a ser mais rápido do bubble sort. Dito isso-- bem, não várias respostas aqui. Mas o principal é que bubble sort é omega de n para uma lista ordenada. 

Lembre-se que a tabela que acabamos de ver antes. Então bolha classifica omega de n, o melhor cenário é que é capaz de ir um pouco mais lista uma vez, determinar hey isso já é classificadas e retorno. Merge sort, não importa o que você faz, é omega de log n n. Assim, por lista ordenada, bolha tipo vai ser mais rápido. 

Agora que sobre listas ligadas? Assim, uma lista ligada pode crescer e encolher para caber tantos elementos como necessário. Dito assim que-- normalmente a comparação directa vai ser um ligado lista com um array. Assim, mesmo que as matrizes podem facilmente aumentar e diminuir para caber tantos elementos conforme necessário, uma lista ligada em comparação com um um array-- matriz tem acesso aleatório. Podemos índice em qualquer nomeadamente elemento da matriz. 

Assim, para uma lista ligada, não podemos basta ir até o quinto elemento, temos que percorrer desde o início até chegarmos ao quinto elemento. E isso vai nos impedir de fazer algo como busca binária. Falando de busca binária, busca binária tende a ser mais rápido do que a busca linear. Dito que-- assim, uma coisa possível é que você não pode fazer binário pesquisar em listas ligadas, você só pode fazê-lo em arrays. Mas, provavelmente, mais importante ainda, você não pode fazer busca binária em uma matriz que não está classificada. Upfront você pode precisar para classificar a matriz, e só então pode você faz a busca binária. Portanto, se sua coisa não é ordenada, para começar, em seguida, busca linear pode ser mais rápido. 

Pergunta 27. Por isso, considero o programa abaixo, que será no próximo slide. E este é o único onde estamos vai querer declarar explicitamente os valores para várias variáveis. Então, vamos olhar para isso. 

Então linha um. Temos int x é igual a 1. Essa é a única coisa que aconteceu. Assim, na linha um, vemos em nossa tabela, que y, a, b, e são todos tmp apaguei. Então, o que é x? Bem, nós apenas configurá-lo igual a 1. E depois a linha dois, bem, vemos que y é definido como 2, e a tabela já está preenchido para nós. Assim, x é 1 e y é 2. 

Agora, a linha de três, estamos agora dentro da função swap. O que nós passamos para trocar? Passamos comercial x para um e comercial y de b. Onde o problema anteriormente afirmado que o endereço de x é 0x10, e o endereço de y é 0x14. Assim, a e b são iguais aos 0x10 e 0x14, respectivamente. 

Agora a linha de três, que são x e y? Bem, nada mudou cerca de x e y neste ponto. Mesmo que sejam dentro de um quadro de pilha principal, eles ainda têm o mesmo valores que faziam antes. Nós não modificou nenhuma memória. Assim, x é 1, y é 2. Tudo certo. Então, agora nós dissemos int tmp igual para estrelar um. Assim, na linha de quatro, tudo é o mesmo, exceto para tmp. Nós não mudamos os valores de qualquer coisa, exceto para tmp. Estamos criando tmp igual para estrelar um. O que é uma estrela? Bem, alguns pontos de x, Então estrelar um vai x igual, o que é um. Então, tudo se copia para baixo, e tmp é definido como 1. 

Agora, a próxima linha. Estrela um é igual a estrela b. Então por linha five-- bem novamente, tudo é o mesmo, exceto que quer uma estrela é. O que é uma estrela? Bem, nós apenas dissemos estrela é um x. Então, nós estamos mudando x para igual estrela b. O que é a estrela b? y. b aponta para y. Assim estrela b é y. Então, nós estamos definindo x igual a y, e tudo o resto é o mesmo. Assim, vemos na próxima linha que x é agora 2, eo resto são apenas copiados para baixo. 

Agora, na próxima linha, estrela b é igual tmp. Bem, nós apenas dissemos estrela b é y, por isso, estamos definindo y igual a tmp. Tudo o resto é o mesmo, portanto, tudo é copiado para baixo. Estamos definindo y igual a tmp, que é um, e tudo o resto é o mesmo. 

Agora, finalmente, a linha sete. Estamos de volta na função principal. Estamos atrás de swap está terminado. Perdemos a, b, e tmp, mas em última análise, não alterar quaisquer valores de nada neste momento, nós apenas copiar x e y para baixo. E vemos que x e y são 1 e 2 agora, em vez de 1 e 2. O swap tem executado com sucesso. 

Pergunta 28. Suponha que você encontrar as mensagens de erro abaixo, durante o horário de expediente no próximo ano, como CA ou TF. Aconselhar como corrigir cada um desses erros. Referência, de modo indefinido para GetString. Por que você pode ver isso? Bem, se um aluno está usando GetString em seu código, eles corretamente hash incluído CS50 dot h para incluir a biblioteca CS50. 

Bem, o que eles fazem precisa corrigir esse erro? Eles precisam fazer uma lcs50 traço no linha de comando quando se está compilando. Então, se eles não passam clang lcs50 traço, eles são não vai ter o real código que implementa GetString. 

Pergunta 29. Implicitamente declarando função da biblioteca strlen. Bem, isso agora, eles não têm feito o hash correto incluir. Neste caso particular, o arquivo de cabeçalho eles precisam incluir é string ponto h, e incluindo seqüência ponto h, agora o student-- agora o compilador tem acesso ao declarações de strlen, e ele sabe que o seu código está usando strlen corretamente. 

Pergunta 30. Mais conversões por cento do que argumentos de dados. Então, o que é isso? Bom lembrar que estes cento signs-- como eles são relevantes para printf. Assim, em printf podemos percent-- podemos imprimir algo como por cento i barra invertida n. Ou podemos imprimir como i por cento, espaço, i por cento, espaço, i por cento. Assim, para cada um desses sinais de porcentagem, precisamos passar uma variável no final do printf. 

Então, se nós dizemos paren printf cento i barra invertida paren n próximos, bem, dizemos que estamos vai imprimir um número inteiro, mas então nós não passar printf um número inteiro de realmente imprimir. Então aqui mais por cento conversões do que argumentos dados? Isso é dizer que temos um monte de porcentagens, e não temos variáveis ​​suficientes para realmente preencher esses percentuais. 

E, em seguida, definitivamente, para a pergunta 31, definitivamente perdeu 40 bytes em um blocos. Portanto, este é um erro Valgrind. Isto é dizer que em algum lugar no seu código, você tem uma atribuição que é de 40 bytes grande para que você malloced 40 bytes, e você nunca libertou-o. O mais provável é que você só precisa encontrar algum vazamento de memória, e descobrir onde você precisa libertar este bloco de memória. 

E pergunta 32, write inválido de tamanho 4. Novamente este é um erro Valgrind. Isso não tem a ver com vazamentos de memória agora. Isto é, a maioria likely-- eu quero dizer, é algum tipo de direitos de memória inválidos. E provavelmente isso é algum tipo de buffer overflow. Onde você tem uma matriz, talvez uma matriz de inteiros, e vamos dizem que é de tamanho 5, e você tentar tocar suporte matriz 5. Então, se você tentar escrever para que valor, que não é um pedaço de memória que você realmente tem acesso e assim que você está indo para obter esse erro, dizendo gravação inválido de tamanho 4. Valgrind vai reconhecer que você é tentando tocar de memória de forma inadequada. 

E é isso por quiz0. Estou Rob Bowden, e este é CS50.