ROB Bowden: Ola, eu son Rob Bowden, e imos falar sobre quiz0.
>> Entón, primeira pregunta.
Esta é a pregunta que necesitas para codificar o número
127 nos bulbos binarios.
Se quixese, podería facer a conversión regular
de bi-- ou, de decimal a binario.
Pero iso probablemente vai para ter unha morea de tempo.
Quero dicir, pode descubrir que, OK, un está alí, 2 está aí,
4 está aí, 8 está aí.
Xeito máis doado, é de 128 127 menos un.
Esta lámpada máis á esquerda é o 128 bits.
Así, 127 é realmente só todo das outras lámpadas,
xa que é o máis á esquerda lámpada menos 1.
Isto é todo para esta pregunta.
>> Pregunta dun.
Así, con 3 bits que poida representan 8 valores distintos.
Por que, entón, é de 7 a maior non-negativo enteiro decimal pode representar?
Ben, se só podemos representan 8 valores distintos,
entón o que nós imos ser representando é de 0 a 7.
0 leva-se un dos valores.
>> Pregunta dous.
Con n bits, cantas distinta valores que poden representar?
Así, con n bits, ten 2 os valores posibles para cada bit.
Polo tanto, temos dous valores posibles para o primeiro bit, dous valores posibles
para a segunda, 2 posible para o terceiro.
E de xeito que é 2 veces 2 veces 2, e en definitiva, a resposta é de 2 a n.
>> Pregunta tres.
Que é 0x50 en binario?
Entón lembre de que ten un hexadecimal moi conversión simple de binario.
Entón aquí, nós só necesitamos mirar para a 5 e a 0 de forma independente.
Entón, cal é 5 en binario?
0101, que é o 1 bit eo bit 4.
Cal é 0 en binario?
Non complicado.
0000.
Entón, só tes que poñer-los xuntos, e que é o número total de binario.
01.010.000.
E se quixese podería despegar que máis á esquerda cero.
É irrelevante.
>> Entón, en alternativa, o que é 0x50 en decimal?
Se quixese, ten could-- se está máis cómodo co binario,
podería tomar esta resposta binaria e convertelo en decimal.
Ou podemos só recordar que hexadecimal.
Así que 0 é o 0 º lugar, e a 5 é, no 16 para o primeiro lugar.
Entón, aquí temos 5 veces 16 a en primeiro lugar, ademais de 16 0 veces para a cero,
é 80.
E se mirou para o título para a pregunta,
era CS 80, que era unha especie de Consello para a resposta a este problema.
>> Pregunta cinco.
Temos este guión cero, o que é repetindo 4 veces manteiga de cacahuete marmelada.
Así como nós agora o código que en C?
Ben, temos aqui-- a parte en negra é a única parte que tiña de aplicar.
Polo tanto, temos un 4 loop que é looping 4 veces, -ing printf Peanut Butter Jelly,
coa nova liña que o problema pide.
>> Pregunta seis, outro problema do risco.
Vemos que estamos en un loop para sempre.
Estamos dicindo que a variable i e logo, incrementando i por un.
Agora queremos facelo en C. Hai múltiples formas que poderiamos ter feito isto.
Aquí pasou para codificar o para sempre como un lazo while (true).
Así, declaramos a variable i, só como tivemos i variable no scratch.
Declare a variable i, e para sempre while (true), nós dicimos que a variable i.
Entón printf% i-- ou podería usar% d.
Dicimos que variable e entón incrementa-lo, i ++.
>> Pregunta sete.
Agora, queremos facer algo moi semellante Mario punto c do problema definido.
Queremos imprimir estas hashtags, queremos imprimir un cinco
por tres rectángulo destes hashes.
Entón, como é que imos facer isto?
Ben, nós dámoslle un todo chea de código, e só
ten que cubrir a función de reixa de impresión.
>> Entón, o que PrintGrid parece?
Ben, vostede é pasado o anchura e altura.
Polo tanto, temos un exterior 4 loop, que é looping
ao longo de todas as liñas do presente reixa que queremos imprimir.
Entón temos a 4 circuíto inter-nested, esa é a impresión sobre cada columna.
Así, para cada liña, nós imprimir para cada columna, un único hash.
Entón, ao final da liña que imprime un soa liña nova para ir á seguinte liña.
E iso por toda a rede.
>> Pregunta oito.
Unha función como PrintGrid dise ter un efecto colateral, pero non un retorno
valor.
Explique a distinción.
Entón, iso depende de ti lembrar o que é un efecto colateral é.
Ben, un retorno value-- sabemos PrintGrid non
ten valor de retorno, xa que aquí se di baleiro.
Entón, todo o que volve void realmente non retorna nada.
Entón, cal é o efecto colateral?
Ben, un efecto colateral é algo que tipo de persistir
despois do remate da función que non era só retornou,
e non foi só a partir dos insumos.
>> Así, por exemplo, podemos cambiar unha variable global.
Iso sería un efecto colateral.
Neste caso particular, unha efectos secundarios moi importante
está imprimindo en pantalla.
Así que é un efecto colateral PrintGrid que ten.
Nós imprimir estas cousas para a pantalla.
E pode pensar que como efectos secundarios,
xa que é algo que persiste tras esa función remata.
Isto é algo fóra do alcance desta función que, en definitiva
está a ser alterado, o contido da pantalla.
>> Pregunta nove.
Considero o programa a continuación, para que os números de liña
foron engadidos para a causa da discusión.
Polo tanto, neste programa estamos só chamando GetString, almacenando-o
Nesta variable s, e despois imprimir esta variable s.
Está ben.
Así, explicar por que unha liña está presente.
#include CS50 punto h.
Por que necesitamos de #include CS50 dot h?
Ben, nós estamos chamando a Función GetString,
e GetString defínese na biblioteca CS50.
Entón, se non tivésemos #include CS50 punto h,
teriamos que declaración implícita do erro da función GetString
do compilador.
Entón, necesitamos incluír o library-- necesitamos incluír o arquivo de cabeceira,
ou o compilador non vai recoñecer que hai GetString.
>> Explique por que a liña dous está presente.
Así estándar dot h io.
É exactamente o mesmo como o problema anterior,
excepto no canto de xestionar GetString, estamos falando printf.
Entón, se nós non dixemos que necesitamos para incluír estándar io punto h,
entón non sería capaz para utilizar a función printf,
xa que o compilador non saber sobre el.
>> Para entendermos que o que é o significado de anular en liña de catro?
Polo tanto, temos aquí int main (void).
Isto é só dicindo que nós non están a recibir calquera liña de comandos
argumentos para inicio.
Lembre que poderiamos dicir int principais soportes int argc argv corda.
Entón aquí só dicir baleiro de dicir que están ignorando os argumentos de liña de ordes.
>> Explique, no que se refire á memoria, exactamente o que GetString en liña seis retorno.
GetString está retornando dun bloque de memoria, unha matriz de caracteres.
É realmente de volver punteiro para o primeiro carácter.
Lembre que unha cadea é unha estrela de char.
Así, s é un punteiro para o primeiro personaxe en calquera que sexa a secuencia é
que o usuario inseriu no teclado.
E que a memoria pasa a ser malloced, para que a memoria está no heap.
>> Pregunta 13.
Considero o programa a continuación.
Entón, todo isto programa está facendo é printf-ing 1 dividido por 10.
Entón, cando compilado e executado, este programa
saídas 0.0, a pesar de 1 dividido por 10 é de 0,1.
Entón por que é 0.0?
Ben, iso é porque da división enteira.
Así, é un número enteiro de 1, 10 é un número enteiro.
Entón, 1 dividido por 10, todo é tratado como números enteiros,
e no C, cando facemos a división enteira, nós truncar calquera punto decimal.
Entón, 1 dividido por 10 é 0, e entón nós estamos intentando
para imprimir que, como unha boia, de xeito cero, impreso como un float é de 0,0.
E é por iso que temos 0,0.
>> Considero o programa a continuación.
Agora estamos imprimindo 0.1.
Polo tanto, non hai división de enteiros, estamos só a impresión de 0,1,
pero estamos de imprimir lo 28 casas decimais.
E temos esa 0,1000, un grupo enteiro de ceros, 5 5 5, bla bla bla.
Polo tanto, a cuestión aquí é por iso que o fai imprimir que, no canto de exactamente 0.1?
>> Así, a razón é aquí agora punto flotante imprecisión.
Lembre que un float é de só 32 bits.
Por iso, só pode representar un número finito de valores de punto flotante cos 32
Bits.
Así, hai, en última instancia infinitamente moitos valores de punto flotante,
e hai infinitamente moitos flotante valores puntuais en entre 0 e 1,
e estamos obviamente poder representan aínda máis valores que iso.
Entón temos que facer sacrificios para poder representar a maioría dos valores.
>> Así, un valor como 0,1, aparentemente non é seguro que exactamente.
Entón, en vez de representar 0,1 nós facemos o mellor que podemos representar este 0.100000 5 5
5.
E iso é moi preto, pero para unha serie de aplicacións
ten que preocuparse punto flotante imprecisión,
porque simplemente non pode representar todos os puntos flotantes exactamente.
>> Pregunta 15.
Considero o código de abaixo.
Estamos só a impresión 1 máis 1.
Polo tanto, non hai ningún truco aquí.
1 máis 1 avalía a 2, e entón nós estamos imprimindo iso.
Isto só imprime 2.
>> Pregunta 16.
Agora estamos imprimindo o carácter 1 máis o carácter 1.
Entón, por que iso non fai imprimir o mesmo?
Ben, o personaxe 1 máis o carácter 1, o personaxe ten un valor ASCII 49.
Entón, iso realmente está dicindo 49 máis 49, e en definitiva, que vai imprimir 98.
Polo tanto, este non imprime 2.
>> Pregunta 17.
Completar a implantación de impar baixo de tal xeito
que a función devolve true se n é estraño e falso se n é par.
Esta é unha gran propósito ao operador mod.
Entón, tomamos noso argumento n, se n mod 2 é igual a 1, así
é dicir que n dividido por 2 tiña un resto.
Se n dividido por 2 tiña un remanente, que significa que n é impar, entón volvemos verdade.
Outra cousa que volver falso.
Tamén podería ter feito n mod 2 é igual a cero, voltar falso, senón retornar certo.
>> Considere a función recursiva continuación.
Así, se n é inferior ou igual a 1, de regreso 1,
else return n veces f de n menos un.
Entón, cal é esa función?
Ben, este é só o función factorial.
Isto está moi ben representado como n factorial.
>> Así cuestión 19 agora, queremos asumir esta función recursiva.
Queremos facelo interactivo.
Entón, como imos facelo?
Ben para o persoal solución, e de novo hai
varias formas que podería facer que, comezamos con este producto int
é igual a 1.
E ao longo deste loop for, imos
multiplicarse produto para finalmente acabar co factorial completo.
Así, para int i é igual a 2, i é inferior ou igual a n, i ++.
>> Podes estar se pregunta por que eu é igual a 2.
Ben, lembre que aquí temos que facer que o noso caso base é correcto.
Así, se n é menor ou igual 1, nós estamos só retornando unha.
Entón, aquí, comezan a i é igual a 2.
Ben, se eu fose un, entón as-- ou se n fose 1, entón o loop
non sería executado en todo.
E así teriamos só produto de retorno, que é 1.
Do mesmo xeito, se n fose nada menos que 1--
se fose 0, 1 negativo, whatever-- aínda estariamos volvendo 1,
que é o que o versión recursiva está facendo.
>> Agora, se n é maior que 1, entón nós imos
facer polo menos un iteración deste circuíto.
Entón, digamos que n é 5, entón nós estamos fará veces de produtos é igual a 2.
Polo tanto, agora o produto é 2.
Agora nós imos facer é igual a 3 veces produtos.
Agora é 6.
Produto veces é igual a 4, agora é 24.
Produto é igual a 5 veces, agora é de 120.
Entón, en definitiva, estamos volvendo 120, que é correctamente 5 factorial.
>> Pregunta 20.
Este é aquel en que ten que cubrir nesta táboa con calquera algoritmo,
algo que xa vimos, que encaixa nestes prazo algorítmica
veces estes tempos de execución asintótica.
Entón, o que é un algoritmo que omega é de 1, pero gran O de n?
Polo tanto, non podería ser infinitamente moitas respostas aquí.
O que vimos, probablemente, máis frecuentemente é só busca lineal.
>> Así, no mellor dos casos escenario, o elemento que estamos
buscando está no inicio da lista
e así en omega de 1 pasos, o primeiro que comprobar,
nós só retornar inmediatamente que atopamos o elemento.
No peor dos casos, o produto é, ao final,
ou o elemento non está na lista de todo.
Entón, temos que buscar toda a lista, todo n
elementos, e é por iso que é o de n.
>> Polo tanto, agora é algo que é á vez omega de log n n, e gran O de n log n.
Ben, a cousa máis relevante nós vimos aquí é merge sort.
Entón, merge sort, lembre, é, en definitiva teta
de n log n, onde teta defínese se ambos omega e gran O son os mesmos.
Ambos n log n.
>> Que é algo que é omega de n, e O de n ao cadrado?
Ben, unha vez máis hai varias respostas posibles.
Aquí pasar a dicir bubble sort.
Ordenación por inserción tamén funcionaría aquí.
Lembre que bubble sort ten que optimización, onde,
se vostede é capaz de obter toda a lista
sen necesidade de facer calquera swaps, entón, ben,
podemos volver inmediatamente que a lista foi clasificada para comezar.
Así, no mellor dos casos, é só omega de n.
Se non é só un ben lista para comezar con ordenados,
entón temos O de n ao cadrado swaps.
E, finalmente, temos a selección especie para n ao cadrado, ambos omega e gran O.
>> Pregunta 21.
O que hai de integer overflow?
Ben de novo, semellante á anterior, temos só un número finito de anacos
para representar un número enteiro, Entón, talvez 32 bits.
Imos dicir que temos un completo asinado.
Logo, en definitiva, a maior número positivo que pode representar
é de 2 a 31 menos 1.
Entón o que ocorre se intentamos entón incrementar ese número enteiro?
Ben, nós estamos indo a ir de 2 a 31 menos 1, todo o camiño para negativa 2
a 31.
Polo tanto, este é integer overflow cando manter o incremento,
e, finalmente, non se pode máis alto e el só
implica toda a maneira para tras en torno a un valor negativo.
>> Que tal un buffer overflow?
Así, un tapón de overflow-- lembre que é un buffer.
É só unha peza de memoria.
Algo así como unha matriz é un buffer.
Entón, un buffer overflow é cando intenta acceder á memoria
ademais do final do array.
Entón, se ten un matriz de tamaño 5 e
tentar acceder ao soporte de matriz 5 ou 6 soporte ou apoio 7,
ou algo alén do final, ou mesmo nada
soporte de matriz below-- negativo 1-- todos estes son estourido de buffer.
Está tocando memoria en malos camiños.
>> Pregunta 23.
Entón, nun presente que precisa para aplicar strlen.
E nós lles dicimos que pode asumir s non será nulo,
así que non ten que facer calquera comprobación para nulo.
E hai moitas maneiras podería ter feito isto.
Aquí só tomar o simple.
Comezamos cun contador, n. n é contar cantos caracteres existen.
Entón, imos comezar con 0, e entón nós iterado sobre a lista enteira.
>> S é igual a 0 soporte da carácter terminador nulo?
Lembre que estamos a buscar o carácter terminador nulo
para determinar canto tempo a nosa cadea é.
Isto vai acabar calquera secuencia correspondente.
Entón é s soporte 0 igual ao terminador nulo?
Se non é, entón imos mirar s franxa 1, s 2 soporte.
Seguimos ata que atopar o terminador nulo.
Xa que atopamos, entón n contén a lonxitude total da cadea,
e podemos voltar só iso.
>> Pregunta 24.
Polo tanto, este é aquel en que Ten que facer o trade off.
Entón, unha cousa é boa nun xeito, pero de que xeito é malo?
Entón, aquí, merge sort tende a ser máis rápido bubble sort.
Dito isso-- ben, non varias respostas aquí.
Pero o principal é que bubble sort é omega de n para unha lista ordenada.
>> Lembre que a táboa que acabamos de ver antes.
Entón burbulla clasifica omega de n, o mellor escenario
é que é capaz de ir un pouco máis lista xa, determinar
hey iso xa é clasificadas e retorno.
Merge sort, non importa o que fai, é omega de log n n.
Así, por lista ordenada, burbulla tipo será máis rápido.
>> Agora que sobre listas ligadas?
Así, unha lista ligada pode medrar e encoller para caber tantos elementos como sexa necesario.
Dito así que-- normalmente a comparación directa
será un conectado lista con un array.
Así, aínda que as matrices poden facilmente aumentar e diminuír
para caber tantos elementos que corresponda, unha lista ligada
en comparación con un un array-- matriz ten acceso aleatorio.
Podemos índice en calquera nomeadamente elemento da matriz.
>> Así, para unha lista ligada, non podemos só tes que ir ata o quinto elemento,
temos que percorrer desde o inicio ata chegar ao quinto elemento.
E iso vai impedir de facer algo como busca binaria.
Falando de busca binaria, busca binaria tende a ser máis rápido que a procura lineal.
Dito que-- así, unha cousa posible
é que non pode facer binario buscar en listas ligadas,
só se pode facelo en arrays.
Pero, probablemente, máis importante aínda, non pode facer busca binaria
nunha matriz que non está clasificada.
Upfront pode ter para clasificar a matriz, e só entón pode
fai a procura binaria.
Polo tanto, se a súa cousa non é ordenada, para comezar,
logo busca lineal pode ser máis rápido.
>> Pregunta 27.
Por iso, considero o programa a continuación, que será o próximo foto.
E este é o único onde estamos Vai querer declarar explicitamente
os valores para varias variables.
Entón, imos ollar para iso.
>> Entón liña un.
Temos int x é igual a 1.
Esa é a única cousa que pasou.
Así, na liña dun vemos na nosa táboa, que y, a, b, e son todos tmp
apaguei.
Entón, o que é x?
Ben, nós só configure-lo igual a 1.
E despois a liña dous, ben, vemos que y defínese como 2,
e a táboa xa está cuberto para nós.
Así, x é 1 e y é 2.
>> Agora, a liña de tres, estamos agora dentro da función de intercambio.
O que nós pasamos para intercambiar?
Pasamos comercial x para un e comercial y de b.
Onde o problema anteriormente afirmou que a dirección de x
é 0x10, e a dirección de y é 0x14.
Así, a e b son iguais aos 0x10 e 0x14, respectivamente.
>> Agora a liña de tres, que son xe y?
Ben, nada cambiou preto de x e y neste punto.
Aínda que sexan dentro dun marco de pila principal,
eles aínda teñen o mesmo valores que facían antes.
Non modificou ningunha memoria.
Así, x é 1, y é 2.
Todo correcto.
Entón, agora nós dixemos int tmp igual para protagonizar un.
Así, na liña de catro, todo é o mesmo, excepto para tmp.
Non cambiamos os valores de calquera cousa, excepto para tmp.
Estamos creando tmp igual para protagonizar un.
¿Que é unha estrela?
Ben, algúns puntos de x, Entón protagonizar un vai x igual, o que é un.
Entón, todo se copia abaixo, e tmp defínese como 1.
>> Agora, a seguinte liña.
Estrela un é igual a estrela b.
Entón por liña five-- ben de novo, todo é o mesmo, só que quere unha estrela é.
¿Que é unha estrela?
Ben, nós só dixemos estrela é un x.
Entón, nós estamos cambiando x a igual estrela b.
¿Que é a estrela b? y. b apunta y.
Así estrela b é y.
Entón, nós estamos definindo x igual a y, e todo o resto é o mesmo.
Así, podemos ver na seguinte liña que x é agora 2, eo resto son só copiados abaixo.
>> Agora, na seguinte liña, estrela b é igual tmp.
Ben, nós só dixemos estrela b é y, por iso, estamos definindo y igual a tmp.
Todo o resto é o mesmo, polo tanto, todo é copiado para abaixo.
Estamos definindo y igual a tmp, que é un, e todo o resto é o mesmo.
>> Agora, por fin, a liña sete.
Estamos de volta na función principal.
Estamos detrás de intercambio está rematado.
Perdemos a, b, e tmp, pero en definitiva,
non modificar os valores de nada neste momento,
nós só copiar x e y abaixo.
E vemos que x e y son 1 e 2 agora, en vez de 1 e 2.
O intercambio ten executado correctamente.
>> Pregunta 28.
Supoña que atopa as mensaxes de erro
a continuación, durante o horario de expediente o próximo ano, como CA ou TF.
Aconsellar como corrixir cada un destes erros.
Referencia, de xeito indefinido para GetString.
Por que se pode ver iso?
Ben, se un alumno está a usar GetString no seu código,
eles correctamente hash incluído CS50 dot h para incluír a biblioteca CS50.
>> Ben, o que eles fan Debe corrixir este erro?
Precisan facer unha lcs50 trazo no liña de comandos cando se está compilando.
Entón, se eles non pasan clang lcs50 trazo, son
non terá o real código que aplica GetString.
>> Pregunta 29.
Implicitamente declarando función da biblioteca strlen.
Ben, iso agora, eles non teñen feito o hash correcto incluír.
Neste caso particular, o ficheiro de cabeceira precisan incluír é string punto h,
e incluíndo secuencia punto h, agora o student-- agora o compilador
ten acceso ao declaracións de strlen,
e el sabe que o seu código Está a utilizar strlen correctamente.
>> Pregunta 30.
Máis conversións por cento que argumentos de datos.
Entón, o que é iso?
Bo lembrar que estes cento signs-- como son relevantes para printf.
Así, en printf podemos percent-- podemos imprimir algo
como por cento i barra invertida n.
Ou podemos imprimir como i por cento, espazo, i por cento, espazo, i por cento.
Así, para cada un destes sinais de porcentaxe, necesitamos
pasar unha variable ao final do printf.
>> Entón, se nós dicimos paren printf cento i barra invertida paren n próximos,
ben, dicimos que estamos vai imprimir un número enteiro,
pero entón non pasar printf un número enteiro de realmente imprimir.
Entón aquí máis por cento conversións que argumentos datos?
Isto é dicir que temos unha morea de porcentaxes,
e non temos variables suficientes para realmente cubrir estes porcentuais.
>> E, a continuación, en definitiva, á pregunta 31, definitivamente perdeu 40 bytes nun bloques.
Polo tanto, este é un erro Valgrind.
Isto quere dicir que nalgún lugar no seu código,
ten unha asignación que é de 40 bytes grande para que malloced 40 bytes,
e nunca liberou-o.
O máis probable é que só precisa atopar algún escape de memoria,
e descubrir que precisa liberar este bloque de memoria.
>> E pregunta 32, write válido de tamaño 4.
De novo este é un erro Valgrind.
Isto non ten que ver con perdas de memoria agora.
É dicir, a maioría likely-- quero dicir, é algún tipo de dereitos de memoria incorrectos.
E probablemente iso é algún tipo de buffer overflow.
Onde ten unha matriz, quizais unha matriz de enteiros, e imos
din que é de tamaño 5, e tentar tocar soporte matriz 5.
Entón, se tentar escribir para que valor, que non é unha peza de memoria
que realmente ten acceso e así que está indo para obter ese erro,
dicindo gravación válido de tamaño 4.
Valgrind vai recoñecer que é intentando tocar de memoria de forma inadecuada.
>> E iso por quiz0.
Estou Rob Bowden, e este é CS50.