ROB BOWDEN: Hola, soy Rob Bowden, y vamos a hablar de quiz0. Por lo tanto, la primera pregunta. Esta es la pregunta donde que necesitabas para codificar el número 127 en los bulbos binarios. Si quisieras, podrías hacer la conversión normal desde bi-- o, de decimal a binario. Pero eso probablemente va que tomar un montón de tiempo. Quiero decir, usted podría darse cuenta de que, Aceptar, 1 es de allí, 2 es allí, 4 es ahí, 8 es en allí. Manera más fácil, 127 es 128 menos uno. Esa bombilla más a la izquierda es la de 128 bits. Así que 127 es realmente todo de las otras bombillas, ya que es el más a la izquierda bombilla menos 1. Eso es todo por esta pregunta. 

Pregunta uno. Así que con 3 bits que pueda representar 8 valores distintos. ¿Por qué, entonces, es la más grande de 7 no negativo entero decimal se puede representar? Bueno, si sólo podemos representar 8 valores distintos, entonces lo que vamos a ser que representa es de 0 a 7. 0 ocupa uno de los valores. 

Pregunta dos. Con n bits, ¿cuántos distinta valores pueden representarlo? Así, con n bits, tiene 2 los valores posibles para cada bit. Así que tenemos dos valores posibles para el primer bit, 2 valores posibles para el segundo, 2 posible para la tercera. Y por lo que es 2 veces 2 veces 2, y en última instancia, la respuesta es 2 a la n. 

Pregunta tres. ¿Qué es 0x50 en binario? Así que recuerde que tiene una muy hexadecimal conversión directa a binario. Así que aquí, sólo tenemos que mirar el 5 y el 0 independiente. Así que lo que es 5 en binario? 0101, que es el bit 1 y el 4 bits. Lo que es 0 en binario? No es complicado. 0000. Así que sólo hay que poner juntos, y ese es el número completo en binario. 01.010.000. Y si quisieras podrías despegue que más a la izquierda de cero. Es irrelevante. 

Así que, alternativamente, lo que es 0x50 en decimal? Si usted quisiera, usted could-- si estás más cómodo con el binario, usted podría tomar esa respuesta binaria y convertir eso en decimal. O podríamos recordar que hexadecimal. Así que 0 está en el lugar 0 º, y el 5 es en el 16 al primer lugar. Así que aquí, tenemos 5 veces 16 a la primero, plus 0 veces 16 a la cero, es 80. Y si uno mira en la el título de la pregunta, era CS 80, que era una especie de alusión a la respuesta a este problema. 

Pregunta cinco. Tenemos este script Scratch, que es repetir 4 veces la mantequilla de maní jalea. Entonces, ¿cómo ahora el código que en C? Bueno, tenemos aquí-- la parte en negrita es la única parte que había que poner en práctica. Así que tenemos un bucle de 4 que está en bucle 4 veces, la mantequilla de maní jalea ing-printf, con la nueva línea que el problema pide. 

Pregunta seis, otro problema de Scratch. Vemos que estamos en un bucle para siempre. Estamos diciendo que la variable i y luego incrementar i en 1. Ahora queremos hacer que en C. Hay múltiples formas en las que podríamos haber hecho esto. Aquí pasamos a codificar el para siempre como un bucle while (true). Así que declaramos la variable i, sólo como teníamos i variable en scratch. Declare la variable i, y para siempre while (true), decimos que la variable i. Así printf% yo-- o que podría haber utilizado% d. Nosotros decimos que la variable, y luego incrementarlo, i ++. 

Pregunta siete. Ahora queremos hacer algo muy similar Mario punto c del problema planteado uno. Queremos imprimir estos hashtags, queremos imprimir un cinco por tres rectángulo de estos hashes. Entonces, ¿cómo vamos a hacer eso? Bueno, te damos un todo montón de código, y que acaba de tiene que llenar en la función de impresión de cuadrícula. 

Así que lo que se ve como PrintGrid? Pues estás más allá de la anchura y la altura. Así que tenemos un exterior 4 lazo, eso es un bucle sobre todo de las filas de este cuadrícula que queremos imprimir. Luego tenemos el bucle anidado entre 4, esa es la impresión sobre cada columna. Así que para cada fila, imprimimos para cada columna, un solo hash. Luego, al final de la fila es la impresión de un línea de nuevo sencillo para ir a la siguiente fila. Y eso es todo por toda la red. 

Pregunta ocho. Una función como PrintGrid se dice que tener un efecto secundario, pero no un retorno valor. Explicar la distinción. Así que esto se basa en que recordar lo que es un efecto secundario es. Bueno, un retorno value-- sabemos PrintGrid no lo hace tienen valor de retorno, ya que aquí se dice sin efecto. Así que cualquier cosa que devuelve void en realidad no devolver nada. Entonces, ¿cuál es el efecto secundario? Bueno, un efecto secundario es nada ese tipo de persiste después de los extremos de la función que no era acabamos de volver, y que no era sólo de los insumos. 

Así, por ejemplo, podríamos cambiar una variable global. Eso sería un efecto secundario. En este caso particular, un efecto secundario muy importante se imprime en la pantalla. Así que es un efecto secundario que tiene PrintGrid. Imprimimos estas cosas a la pantalla. Y usted puede pensar en que como un efecto secundario, ya que eso es algo que persiste después de que termine esta función. Eso es algo que está fuera del alcance de esta función que en última instancia está siendo cambiado, la contenido de la pantalla. 

Pregunta nueve. Considere el siguiente programa, a la que los números de línea se han añadido para En aras de la discusión. Así que en este programa sólo somos llamando GetString, almacenándolo en esta variable s, y luego la impresión de que la variable s. Okay. Así que explicar por qué la línea uno está presente. #include punto CS50 h. ¿Por qué necesitamos a #include CS50 punto h? Bueno estamos llamando a la Función GetString, y GetString se define en la biblioteca CS50. Así que si no teníamos #include punto CS50 h, que iba a conseguir que la declaración implícita de la función de error GetString del compilador. Así que tenemos que incluir la library-- tenemos que incluir el archivo de cabecera, o de lo contrario el compilador no lo hará reconocen que existe GetString. 

Explique por qué la línea dos está presente. Así estándar punto h io. Es exactamente la misma como el problema anterior, excepto que en lugar de tratar con GetString, estamos hablando de printf. Así que si no decimos lo que necesitamos para incluir estándar de punto io h, entonces nosotros no podríamos utilizar la función printf, porque el compilador no saberlo. 

Qué-- cuál es el significado de pleno derecho en la línea de cuatro? Así que aquí tenemos int main (void). Eso es justo decir que no están recibiendo ninguna línea de comandos argumentos a principal. Recuerde que nosotros podríamos decir int principales soportes de cadena argv argc int. Así que aquí nos limitamos a decir nula decir que están haciendo caso omiso de los argumentos de línea de comandos. 

Explicar, con respecto a la memoria, exactamente lo GetString en línea de seis vueltas. GetString está volviendo un bloque de memoria, una gran variedad de personajes. Es realmente un regreso puntero al primer carácter. Recuerde que una cadena es una estrella de carbón. Así que s es un puntero a la primera personaje en cualquiera que sea la cadena es que el usuario entró en el teclado. Y que la memoria pasa a ser malloced, por lo que la memoria está en el montón. 

Pregunta 13. Considere el siguiente programa. Así que todo este programa está haciendo se printf-ing 1 dividido por 10. Así que cuando se compila y ejecutado, este programa salidas 0.0, a pesar de que 1 dividido por 10 es 0,1. Así que ¿por qué es 0.0? Bueno, esto se debe a de la división entera. Así que es un número entero 1, 10 es un número entero. Así que 1 dividido por 10, todo se trata como números enteros, y en C, cuando hacemos la división entera, truncamos cualquier punto decimal. Así que 1 dividido por 10 se 0, y entonces estamos tratando para imprimir que como un flotador, por lo cero impresa como un flotador es 0.0. Y es por eso que obtenemos 0.0. 

Considere el siguiente programa. Ahora estamos imprimiendo 0.1. Así que no hay división entera, sólo estamos imprimiendo 0,1, pero estamos imprimirlo a 28 cifras decimales. Y obtenemos este 0,1000, un montón de ceros, 5 5 5, bla, bla, bla. Así que la pregunta aquí es ¿por qué lo hace imprimir que, en lugar de exactamente 0,1? 

Así que la razón aquí es ahora punto imprecisión flotante. Recuerde que un flotador está a sólo 32 bits. Así que sólo podemos representar un número finito de valores de punto flotante con los 32 Bits. Bueno, hay, en última instancia infinitamente muchos de los valores de punto flotante, y hay infinitamente muchos flotante los valores de punto de entre 0 y 1, y estamos obviamente capaz de representar incluso más valores que eso. Así que tenemos que hacer sacrificios para ser capaz de representar a la mayoría de los valores. 

Así como un valor de 0,1, al parecer, no podemos representar eso exactamente. Así que en lugar de representar el 0,1 hacemos la Lo mejor que podemos representar este 0.100000 5 5 5. Y eso es bastante estrecha, pero para una gran cantidad de aplicaciones usted tiene que preocuparse acerca de punto imprecisión flotante, porque simplemente no podemos representar todos flotante puntos exactamente. 

Pregunta 15. Considere el código de abajo. Estamos imprimiendo 1 más 1. Así que no hay truco aquí. 1 más 1 evalúa a 2, y entonces estamos imprimiendo eso. Esto sólo imprime 2. 

Pregunta 16. Ahora estamos imprimiendo el carácter 1 más el carácter 1. Así que ¿por qué esto no imprimir la misma cosa? Bueno, el personaje 1 más el carácter 1, el personaje tiene un valor ASCII 49. Así que esto realmente está diciendo 49, más 49, y en última instancia, esto va a imprimir 98. Así que esto no imprime 2. 

Pregunta 17. Completar la aplicación de impar a continuación de tal manera que la función devuelve verdadero si n es impar y false si n es par. Este es un gran propósito para el operador mod. Así que nos tomamos nuestro argumento n, si n mod 2 es igual a 1, así eso significa que n divide por 2 tenía un resto. Si n dividido por 2 tenía un resto, que significa que n es impar, por lo que volver realidad. Otras ventas volvemos falsa. También podría haber hecho n mod 2 iguales cero, return false, de lo contrario devuelve true. 

Considere la función recursiva a continuación. Así que si n es menor que o igual a 1, devuelve 1, o regrese n veces f de n menos 1. Entonces, ¿qué es esta función? Bueno, esto es sólo el función factorial. Esto está muy bien representado como n factorial. 

Así que ahora la pregunta 19, queremos aprovechar esta función recursiva. Queremos que sea iterativo. Entonces, ¿cómo hacemos eso? Bueno para el personal solución, y de nuevo no es múltiples formas en las que podría haber hecho que, comenzamos con este producto int es igual a 1. Y en todo este bucle for, vamos multiplicarse producto a última instancia terminar con el factorial completo. Así que para int i es igual a 2, i es menos de o igual a n, i ++. 

Tal vez se pregunte por qué i es igual a 2. Bueno, recuerde que aquí tenemos que asegurarse de que nuestro caso base es correcta. Así que si n es menor que o igual a 1, sólo estamos volviendo 1. Así que aquí, empezamos a i es igual a 2. Bueno, si yo fuera 1, entonces el-- o si n era 1, entonces el bucle for no ejecutar en absoluto. Y así lo haríamos sólo producto de vuelta, que es 1. Del mismo modo, si n eran nada menos que 1-- si fuera 0, 1 negativo, whatever-- todavía estaríamos regresando 1, que es exactamente lo que el versión recursiva está haciendo. 

Ahora, si n es mayor que 1, entonces vamos hacer al menos un iteración de este bucle. Así que digamos que n es 5, entonces estamos va a hacer veces de productos es igual a 2. Así que ahora el producto es de 2. Ahora vamos a hacer veces de productos es igual a 3. Ahora es el 6. Tiempos de producto es igual a 4, ahora es el 24. Tiempos de producto es igual a 5, ahora es el 120. Así que, en última instancia, estamos volviendo 120, que es correctamente 5 factorial. 

Pregunta 20. Esto es en la que usted tiene que llenar en esta tabla con cualquier algoritmo dado, nada de lo que hemos visto, que encaja estos algorítmica plazo veces estos tiempos de ejecución asintótica. Entonces, ¿qué es un algoritmo que es el omega de 1, pero gran O de n? Así que podría ser infinitamente muchas respuestas aquí. La que hemos visto probablemente más con frecuencia es sólo búsqueda lineal. 

Así, en el mejor de los casos escenario, el tema que estamos buscando está en el principio de la lista y así en omega de pasos de 1, lo primero que comprobamos, acabamos de regresar de inmediato que encontramos el artículo. En el peor de los casos, el artículo está en el extremo, o el artículo no está en la lista en absoluto. Así que tenemos que buscar toda la lista, todos los n elementos, y es por eso que es o de n. 

Así que ahora es algo que a la vez omega de n log n, y gran O de n log n. Bueno, la cosa más relevante que hemos visto aquí es fusionar especie. Así fusionar especie, recordar, es en última instancia, Theta de n log n, donde se define theta si ambos omega y grande O son los mismos. Tanto n log n. 

¿Qué es algo que es omega de N, y O del cuadrado n? Bueno, de nuevo hay múltiples respuestas posibles. Aquí nos toca decir burbuja especie. Inserción especie también trabajaría aquí. Recuerde que la burbuja de tipo tiene que la optimización donde, si usted es capaz de obtener a través de toda la lista sin necesidad de hacer cualquier swaps, entonces, bueno, podemos volver inmediatamente que la lista se solucionó para empezar. Así que en el mejor de los casos, es sólo el omega de n. Si no se trata sólo de un bien lista para empezar ordenados, entonces tenemos O de n al cuadrado swaps. Y por último, tenemos la selección especie para n al cuadrado, tanto omega y gran O. 

Pregunta 21. ¿Qué hay desbordamiento de entero? Bien de nuevo, similar a la anterior, sólo tenemos un número finito de bits de para representar un número entero, por lo que tal vez 32 bits. Digamos que tenemos un entero con signo. A continuación, en última instancia, el más alto número positivo podemos representar es 2 a la 31 menos 1. Entonces, ¿qué sucede si tratamos de a continuación, incrementar ese entero? Bueno, vamos a ir de 2 a la 31 menos 1, todo el camino hasta negativo 2 a la 31. Así que este desbordamiento de enteros es cuando sigues incrementando, y en última instancia, no se puede conseguir más arriba y que sólo envuelve todo el camino de vuelta alrededor a un valor negativo. 

¿Qué pasa con un desbordamiento de búfer? Así un tampón overflow-- recuerda lo que un buffer es. Es sólo una parte de la memoria. Algo así como una matriz es un tampón. Así que un desbordamiento de búfer es cuando intenta acceder a memoria más allá del final de la matriz. Así que si usted tiene una matriz de tamaño 5 y usted tratar de acceder a soporte de matriz 5 o 6 el soporte o el soporte 7, o cualquier cosa más allá de la extremo, o incluso nada soporte de serie aquí a continuación, negativo 1-- todos esos son desbordamientos de búfer. Estás tocando de memoria en los malos caminos. 

Pregunta 23. Así que en éste lo que necesita para implementar strlen. Y les decimos que se puede asumen s no será nulo, por lo que no tiene que hacer cualquier cheque por nulo. Y hay varias maneras que podría haber hecho esto. Aquí sólo tomamos el sencillo. Empezamos con un contador, n. n es contando el número de caracteres que hay. Así que empezamos a 0, y luego iterar sobre la lista completa. 

Es s igual a 0 soporte de la carácter terminador nulo? Recuerden que estamos buscando el carácter terminador nulo para determinar cuánto tiempo nuestra cadena es. Eso va a terminar cualquier cadena correspondiente. Así que es soporte de s 0 igual para el terminador nulo? Si no es así, entonces vamos a mirar s soporte 1, s 2 soporte. Seguimos camino hasta que encontrar el terminador nulo. Una vez que hemos encontrado, entonces n contiene la longitud total de la cadena, y sólo podemos devolver ese. 

Pregunta 24. Así que este es el uno en el que tener que hacer la compensación. Así que una cosa es buena en uno manera, pero ¿de qué manera es malo? Así que aquí, fusionar especie tiende a ser más rápido que la burbuja especie. Habiendo dicho que-- así, hay son múltiples respuestas aquí. Pero la principal es que la burbuja especie es omega de n para una lista ordenada. 

Recuerde que la tabla que acabamos de ver antes. Así burbuja ordena omega de n, el mejor de los casos es que es capaz de ir más la lista una vez, determinar bueno esto ya es ordenados, y retorno. Ordenamiento por mezcla, sin importar lo que usted lo hace, es el omega de n log n. Así que para la lista ordenada, burbuja especie que va a ser más rápido. 

Ahora ¿qué pasa vinculada listas? Así que una lista enlazada puede crecer y encoger para adaptarse a tantos elementos como sea necesario. Dicho así que-- por lo general la comparación directa va a ser un vinculado una lista con una matriz. Así que a pesar de que las matrices pueden aumentar y reducir fácilmente para adaptarse a tantos elementos según sea necesario, una lista enlazada en comparación con un un array-- matriz tiene acceso aleatorio. Nos puede indexar en cualquier en particular elemento de la matriz. 

Así que para una lista enlazada, no podemos sólo tiene que ir al quinto elemento, tenemos que recorrer desde el principio hasta llegar al quinto elemento. Y eso va a impedirnos hacer algo como búsqueda binaria. Hablando de búsqueda binaria, búsqueda binaria tiende a ser más rápida que la búsqueda lineal. Habiendo dicho que-- así, una cosa posible es que no se puede hacer binario buscar en listas enlazadas, sólo puede hacerlo en matrices. Pero, probablemente, lo más importante, no se puede hacer la búsqueda binaria en una matriz que no está ordenada. Upfront puede que tenga que ordenar la matriz, y sólo entonces puede que haces de búsqueda binaria. Así que si lo tuyo no es ordenada, para empezar, entonces la búsqueda lineal podría ser más rápido. 

Pregunta 27. Así que considere el programa a continuación, que estarán en la siguiente diapositiva. Y esto es en la que estamos va a querer declarar explícitamente los valores para distintas variables. Así que echemos un vistazo a eso. 

Así que la línea uno. Tenemos int x es igual a 1. Esa es la única cosa que ha pasado. Así que en la línea uno, que vemos en nuestra mesa, y que, a, b, y tmp son todos tachado. Entonces, ¿qué es x? Bueno apenas fijamos que igual a 1. Y a continuación, la línea dos, bueno, vemos que y se establece en 2, y la tabla ya está cumplimentado para nosotros. Así que x es 1 ey es 2. 

Ahora, la línea de tres, ahora estamos dentro de la función de intercambio. ¿Qué hicimos pasar a intercambiar? Pasamos signo x para una, y símbolo de unión y de b. Cuando el problema anterior declaró que la dirección de x es 0x10, y la dirección de y es 0x14. Así que a y b son iguales a 0x10 y 0x14, respectivamente. 

Ahora en línea de tres, ¿cuáles son xey? Bueno, nada ha cambiado acerca de x e y en este punto. A pesar de que son dentro de un marco principal de pila, todavía tienen la misma los valores que tenían antes. No hemos modificado ninguna memoria. Así que x es 1, y es 2. Bien. Así que ahora hemos dicho int tmp igual a protagonizar una. Así que en la línea de cuatro, todo es el mismo excepto por tmp. No hemos cambiado ningún valor de nada, excepto para tmp. Estamos estableciendo tmp igual a protagonizar una. ¿Qué es una estrella? Bueno, unos puntos a X, por lo protagonizan un va a igualdad de x, que es 1. Así que todo se copia abajo, y tmp se establece en 1. 

Ahora la siguiente línea. Estrella es igual a una estrella b. Así por línea five-- bien de nuevo, todo que es lo mismo, excepto que sea una estrella es. ¿Qué es una estrella? Bueno, acabamos de decir una estrella es x. Así que estamos cambiando x a la igualdad de estrellas b. ¿Cuál es la estrella b? y. b puntos a y. Así estrella b es y. Así que estamos estableciendo x igual a y, y todo lo demás es igual. Así que nos vemos en la siguiente fila que x es ahora 2, y el resto son simplemente copió. 

Ahora, en la siguiente línea, estrella b es igual a tmp. Bueno, acabamos de decir estrella b es y, por lo que estamos estableciendo y igual a tmp. Todo lo demás es lo mismo, así que todo se copia abajo. Estamos estableciendo y igual a TMP, que es uno, y todo lo demás es igual. 

Ahora, por fin, la línea siete. Estamos de vuelta en la función principal. Estamos después de swap se terminó. Hemos perdido a, b, y tmp, pero en última instancia, nos no se cambia ningún valor de nada en este momento, que acabamos de copiar x e y hacia abajo. Y vemos que x e y son ahora 2 y 1 en lugar de 1 y 2. El canje se ha ejecutado con éxito. 

Pregunta 28. Supongamos que te encuentras los mensajes de error a continuación en horario de oficina el año que viene como una CA o TF. Asesorar cómo solucionar cada uno de estos errores. Así referencia indefinida a GetString. ¿Por qué puede usted ver esto? Bueno, si un estudiante está usando GetString en su código, se han incluido correctamente hash CS50 punto h para incluir la biblioteca CS50. 

Bueno, ¿qué es lo que que tenga que corregir este error? Tienen que hacer un guión al lcs50 línea de comandos cuando se está compilando. Así que si no pasan lcs50 guión sonido metálico, que son no va a tener la real código que implementa GetString. 

Pregunta 29. Implícitamente declarar función de biblioteca strlen. Bueno esto ahora, que no tiene hecho el hash apropiado incluir. En este caso particular, el archivo de cabecera que necesitan para incluir es la cadena de puntos h, e incluyendo cadena dot h, ahora la student-- ahora el compilador tiene acceso a la declaraciones de strlen, y se sabe que su código está usando strlen correctamente. 

Pregunta 30. Más por ciento de las conversiones que los argumentos de datos. Entonces, ¿qué es esto? Bueno recordar que estos ciento signs-- cómo son relevantes para printf. Así que en printf podríamos ciento-- podríamos imprimir algo como ciento i barra invertida n. O podemos imprimir como ciento i, espacio, i por ciento, el espacio, i por ciento. Así que para cada uno de los signos de porcentaje, que necesitan pasar una variable al final de printf. 

Así que si decimos que paren printf ciento i barra invertida n cerca paren, así, decimos que estamos va a imprimir un número entero, pero entonces no pasamos printf un entero para imprimir en realidad. Así que aquí más por ciento conversiones que los argumentos de datos? Eso es mucho decir que tenemos un montón de porcentajes, y no tenemos suficientes variables para llenar realmente en esos porcentajes. 

Y entonces, sin duda, para la pregunta 31, definitivamente perdido 40 bytes en un bloques. Así que esto es un error de Valgrind. Esto es decir que en algún lugar de su código, usted tiene una asignación que es 40 bytes grande, así que malloced 40 bytes, y nunca se liberó. Lo más probable es que usted sólo tiene encontrar alguna pérdida de memoria, y encontrar donde usted necesita liberar este bloque de memoria. 

Y la pregunta 32, escritura no válida de tamaño 4. Una vez más se trata de un error de Valgrind. Esto no tiene que ver con pérdidas de memoria ahora. Esto es, más likely-- Quiero decir, es algún tipo de derechos de memoria no válida. Y lo más probable es que esto es cierto tipo de desbordamiento de búfer. Cuando usted tiene una matriz, tal vez una matriz de enteros, y vamos a dicen que es de tamaño 5, y usted tratar de tocar matriz soporte 5. Así que si se intenta escribir en esa valor, eso no es un pedazo de la memoria que en realidad se tiene acceso a, y por lo que vamos a conseguir este error, diciendo escritura no válida de tamaño 4. Valgrind va a reconocer que eres tratando de tocar la memoria de forma inapropiada. 

Y eso es todo por quiz0. Estoy Rob Bowden, y esto es CS50.