[Powered by Google Translate] [Seção 3 - Mais Confortável]
[Rob Bowden - Harvard University]
>> [Esta é CS50. - CS50.TV]
>> Então, a primeira pergunta é estranhamente formulada.
GDB permite "depurar" um programa, mas, mais especificamente, o que é que vamos fazer?
Eu vou responder essa, e eu não sei o que é exatamente o esperado,
então eu estou supondo que é algo ao longo das linhas de ele permite que você passo a passo
andar através do programa, interagir com ele, as variáveis ​​de mudança, fazer todas essas coisas -
basicamente controlar completamente a execução de um programa
e inspeccionar qualquer determinada parte da execução do programa.
Então, esses recursos permitem que você depurar as coisas.
Okay.
Por que a busca binária requer que uma matriz ser classificados?
Quem quer responder a isso?
[Aluno] Porque ele não funciona se não for classificado. Sim >>. [Risos]
Se não for resolvido, então é impossível para dividi-lo ao meio
e saber que tudo para a esquerda é menos e tudo à direita
é maior do que o valor médio.
Por isso, precisa ser ordenada.
Okay.
Por que é uma espécie de bolha em O de n ao quadrado?
Alguém primeiro quero dar uma muito rápida visão geral de alto nível de que tipo bolha é?
[Aluno] Você basicamente passar por cada elemento e você verificar os elementos primeiros.
Se eles estão fora de onde você trocá-los, depois de verificar os elementos seguintes, e assim por diante.
Quando você chegar ao fim, então você sabe que o maior elemento é colocado no final,
assim você ignorar que um, então você continuar passando,
e cada vez que você tem que verificar um elemento menos até que você não fazer alterações. Sim >>.
É chamado espécie de bolha, porque se você virar a matriz de lado assim que é de cima para baixo, vertical,
em seguida, os grandes valores que vão para o fundo e os pequenos valores vai borbulhar até o topo.
É assim que tem o seu nome.
E sim, você acabou de passar.
Você continua passando pela matriz, trocando o valor maior
para obter os maiores valores para o fundo.
>> Por que é O de n ao quadrado?
Primeiro, alguém quer dizer por isso que é O de n ao quadrado?
[Aluno] Porque para cada corrida ele vai n vezes.
Você só pode ter certeza de que você tenha tido o maior elemento de todo o caminho,
então você tem que repetir que para tantos elementos. Sim >>.
Portanto, tenha em mente o que significa e grande O que significa Omega grandes.
O O grande é como o limite superior sobre o quão lento ele pode realmente ser executado.
Então, dizendo que é O de n ao quadrado, não é O de n ou então ele seria capaz de executar
no tempo linear, mas é de O n cubed
porque é delimitada por O de n em cubos.
Se ele é limitado por O de n ao quadrado, então é limitada também pelo n cubos.
Por isso, é n ao quadrado e, no pior caso absoluta que não pode fazer melhor do que n ao quadrado,
é por isso que é O de n ao quadrado.
Então, para ver de matemática discreta em como ele vem a ser n ao quadrado,
se temos cinco coisas em nossa lista, a primeira vez que o número de swaps poderíamos potencialmente precisa fazer
a fim de obter isso? Vamos realmente apenas -
Quantos swaps que vamos ter que fazer na primeira corrida da espécie de bolha através da matriz?
[Aluno] n - 1. Sim >>.
>> Se existem 5 elementos, vamos precisar fazer n - 1.
Em seguida, no segundo quantas swaps que vamos ter que fazer?
[Estudante] n - 2. Sim >>.
E o terceiro vai ser n - 3, e em seguida para a conveniência vou escrever os dois últimos
como então vamos precisar fazer dois swaps e um de swap.
Eu acho que o último pode ou não pode realmente precisam acontecer.
É uma troca? Eu não sei.
Portanto, estas são as quantidades totais de swaps ou pelo menos comparações que você tem que fazer.
Mesmo se você não trocar, você ainda precisa comparar os valores.
Então, existem n - 1 comparações na primeira corrida através da matriz.
Se você reorganizar essas coisas, vamos realmente fazer seis coisas assim que as coisas se comportam bem,
e então eu vou fazer 3, 2, 1.
Então, basta reorganizar estes montantes, que queremos ver quantas comparações fazemos
no algoritmo inteiro.
Então, se nós trazemos esses caras aqui em baixo,
então ainda estamos apenas somando comparações no entanto eram.
Mas se resumir estes e somamos estes e somamos estes,
ainda é o mesmo problema. Nós apenas somar esses grupos particulares.
>> Então agora estamos somando 3 n da. Não é apenas de 3 n.
É sempre vai ser n / 2 n é.
Então, aqui acontece que temos 6.
Se tivéssemos 10 coisas, então nós poderíamos fazer isso de agrupamento para 5 pares diferentes de coisas
e acabar com n + n + n + n + n.
Então, você está sempre indo para obter n / 2 n, e assim por isso, vamos anotar-lo para n ao quadrado / 2.
E por isso mesmo que é o fator de metade, o que acontece a entrar em
devido ao fato de que em cada iteração sobre a matriz compararmos um a menos
então é assim que temos a mais de 2, mas ainda é n ao quadrado.
Nós não nos importamos com o fator constante de um meia.
Então, um monte de coisas O grande como este se baseia em apenas um tipo de fazer esse tipo de matemática,
fazer contas de aritmética e outras coisas série geométrica,
mas a maioria deles neste curso são bastante simples.
Okay.
Por que é tipo de inserção no Omega de n? O que o ômega significa?
[Dois alunos falam ao mesmo tempo - ininteligíveis] sim. >>
Omega você pode pensar como o limite inferior.
>> Portanto, não importa o quão eficiente o seu algoritmo de ordenação por inserção é,
independentemente da lista que é transmitido, ele sempre tem que comparar pelo menos n coisas
ou tem que iterar n coisas.
Por que isso?
[Aluno] Porque se a lista já está classificado, em seguida, através iteração o primeiro
você só pode garantir que o primeiro elemento é o mínimo,
ea segunda iteração você só pode garantir os dois primeiros são
porque você não sabe o que o resto da lista é ordenada. Sim >>.
Se você passar em uma lista completamente classificados, no mínimo você tem que passar por cima de todos os elementos
para ver que nada precisa ser movimentados.
Então, passando por cima da lista e dizer oh, isso já está classificado,
é impossível para você saber que está classificada até que você verifique cada elemento
para ver que eles estão em ordem de classificação.
Assim, o limite inferior é Omega tipo de inserção de n.
Qual é o pior caso de tempo de funcionamento merge sort,
O pior caso de ser grande de novo?
Assim, no pior caso, como é que merge sort correr?
[Estudante] N log n. Sim >>.
Os mais rápidos algoritmos de classificação geral são n log n. Você não pode fazer melhor.
>> Há casos especiais, e se tivermos tempo de hoje - mas provavelmente won't -
podemos ver um que faz melhor do que n log n.
Mas, no caso geral, você não pode fazer melhor do que n log n.
E merge sort acontece a ser o que você deve saber para este curso que é n log n.
E assim nós vamos realmente ser de execução que hoje.
E, finalmente, em não mais que três frases, como funciona o tipo de seleção?
Alguém quer responder, e eu vou contar suas frases
porque se você passar por cima de 3 -
Alguém se lembra tipo de seleção?
Tipo de seleção é geralmente bastante fácil de lembrar apenas do nome.
Você só iterar sobre a matriz, encontrar o que o maior valor é o menor ou -
ordem que está classificando dentro
Então, vamos dizer que estamos classificação da menor para a maior.
Você iterar sobre a matriz, olhando para o que o elemento mínimo é,
selecioná-lo, e depois é só trocá-lo o que está em primeiro lugar.
E então, na segunda passagem sobre a matriz, procure o elemento mínimo de novo,
selecioná-lo, e depois trocá-lo com o que está na segunda posição.
Então, estamos apenas escolhendo os valores mínimos
e inserindo-os na frente da matriz até que seja ordenada.
Perguntas sobre isso?
>> Isto inevitavelmente aparecem nas formas que você tem que preencher quando você está enviando o pset.
Esses são, basicamente, as respostas a esses.
Ok, então agora codificação problemas.
Eu já enviado através de e-mail - Será que ninguém obter esse e-mail? Okay.
Eu já enviou por e-mail o espaço que vamos utilizar,
e se você clicar no meu nome - então eu acho que vou estar no fundo
por causa do r para trás - mas se você clicar no meu nome que você vai ver duas revisões.
Revisão 1 vai ser eu já copiou e colou o código em espaços
para a coisa de pesquisa você vai ter que implementar.
Revisão 2 e será a coisa tipo que vamos implementar depois disso.
Assim, você pode clicar no meu Revisão 1 e trabalhar a partir daí.
E agora queremos implementar busca binária.
>> Alguém quer apenas dar uma explicação de alto nível pseudocódigo
de que nós vamos ter que fazer para pesquisas? Sim.
[Estudante] Você acabou de tomar a meio da matriz e ver se o que você está procurando
é menor do que ou maior do que isso.
E se for menos, você vai para a metade que é menos,
e se é mais, você vai para a metade que é mais e você repetir isso até você, é só pegar uma coisa.
[Bowden] Yeah.
Observe que a nossa matriz de números já está classificado,
e assim que significa que podemos tirar proveito disso e podemos verificar primeiro,
bem, eu estou olhando para o número 50.
Então eu posso ir para o meio.
Médio é difícil de definir quando é um número par de coisas,
mas vamos apenas dizer que nós sempre truncar para o meio.
Portanto, temos aqui oito coisas, de modo que o meio seria 16.
Estou à procura de 50, de modo que 50 é maior que 16.
Então agora eu posso tratar a minha matriz basicamente como estes elementos.
Eu posso jogar fora tudo de mais 16.
Agora a minha matriz é apenas estes quatro elementos, e repito.
Então eu quero encontrar o meio novamente, o que vai ser 42.
42 é menor que 50, então eu posso jogar fora esses dois elementos.
Esta é a minha matriz restante.
Eu vou encontrar o meio novamente.
Eu acho que 50 foi um mau exemplo, porque eu estava sempre jogando fora as coisas para a esquerda,
mas pela mesma medida, se eu estou procurando algo
e é menos do que o elemento Atualmente estou olhando,
então eu vou jogar fora tudo para a direita.
Então agora precisamos implementar isso.
Observe que temos de passar de tamanho.
Não podemos também precisa duro código de tamanho.
Então, se livrar desse # define -
Okay.
Como posso muito bem imaginar o que o tamanho da matriz de números, atualmente, é?
>> Quantos elementos estão na matriz de números?
[Aluno] Números, suportes. Comprimento?
[Bowden] Isso não existe em C.
Precisa. Comprimento.
Matrizes não têm propriedades, por isso não há propriedade de comprimento de matrizes
que só vai dar-lhe o tempo que passa a ser.
[Estudante] Ver a quantidade de memória que tem e dividir por quanto - Sim. >>
Então, como podemos ver quanta memória ele tem? >> [Aluno] Sizeof. >> Sim, sizeof.
Sizeof é o operador que vai retornar o tamanho da matriz de números.
E isso vai ser inteiros no entanto, existem muitas vezes o tamanho de um inteiro
já que é a quantidade de memória que está realmente tomando-se.
Então, se eu quiser que o número de coisas na matriz,
então eu vou querer dividir com o tamanho de um inteiro.
Okay. Assim que me permite passar em tamanho aqui.
Por que eu preciso passar em tamanho a todos?
Por que eu não posso simplesmente fazer aqui int tamanho = sizeof (palheiro) / sizeof (int)?
Por que isso não funciona?
[Aluno] Não é uma variável global.
[Bowden] Haystack existe e estamos passando em números como palheiro,
e esta é uma espécie de prenúncio do que está por vir. Sim.
[Aluno] Haystack é apenas a referência a ele, por isso seria voltar como grande referência que é.
Sim.
Eu duvido que na palestra que você já viu a pilha ainda muito, certo?
Acabamos de falar sobre isso.
Assim, a pilha é onde todas as suas variáveis ​​vão ser armazenados.
>> Qualquer memória que está alocado para as variáveis ​​locais vai na pilha,
e cada função recebe o seu próprio espaço na pilha, seu quadro de pilha própria é o que é chamado.
Então principal tem seu quadro de pilha, e dentro dele vai existir essa matriz de números,
e que vai ser de tamanho sizeof (números).
Vai ter o tamanho de números separados por tamanho dos elementos,
mas que todas as vidas dentro do quadro principal de pilha.
Quando chamamos de busca, pesquisa recebe o seu quadro de pilha própria,
seu próprio espaço para armazenar todas as suas variáveis ​​locais.
Mas esses argumentos - assim palheiro não é uma cópia desta matriz inteira.
Nós não passamos em toda a matriz como uma cópia em pesquisa.
Ele só passa uma referência para essa matriz.
Então pesquisa pode acessar estes números através desta referência.
Ainda está acessando as coisas que vivem dentro da estrutura principal da pilha,
mas, basicamente, quando chegarmos aos ponteiros, que deve ser em breve,
isto é o que os ponteiros estão.
Os ponteiros são apenas referências a coisas, e você pode usar ponteiros para acessar as coisas
que estão em quadros de outras coisas "pilha.
Assim, mesmo que os números é local para o principal, que ainda pode acessá-lo através deste ponteiro.
Mas já que é apenas um ponteiro e é apenas uma referência,
sizeof (palheiro) retorna apenas o tamanho da própria referência.
Ele não retorna o tamanho da coisa que está apontando.
Ele não retorna o tamanho real dos números.
E isso não vai funcionar como queremos que ele.
>> Perguntas sobre isso?
Ponteiros será ido em em detalhes significativamente mais sangrento na semana que vem.
E é por isso que um monte de coisas que você vê, coisas de busca mais ou coisas de classificação,
eles estão quase todos indo a necessidade de ter o tamanho real da matriz,
porque em C, não temos idéia do que o tamanho da matriz é.
Você precisa manualmente passá-lo dentro
E você não pode manualmente passar em toda a matriz, porque você está só de passagem na referência
e não pode obter o tamanho da referência.
Okay.
Então, agora queremos implementar o que foi explicado antes.
Você pode trabalhar com ele por um minuto,
e você não tem que se preocupar em obter tudo perfeitamente 100% funcionando.
Basta escrever o pseudocódigo metade para como você acha que ele deve funcionar.
Okay.
Não há necessidade de ser feito completamente com isso ainda.
Mas será que alguém se sinta confortável com o que têm, até agora,
como algo que pode trabalhar em conjunto?
Alguém quer ser voluntário? Ou eu vou escolher aleatoriamente.
Ele não tem de estar certo por qualquer medida, mas algo que pode modificar em um estado de trabalho.
[Aluno] Claro. Ok >>.
Então você pode salvar a revisão clicando no ícone Salvar pouco.
Você é Ramya, certo? >> [Estudante] Yeah. >> [Bowden] Okay.
Então agora eu posso ver a sua revisão e todos podem puxar para cima a revisão.
E aqui nós temos - Certo.
Então Ramya foi com a solução recursiva, que é definitivamente uma solução válida.
Há duas maneiras que você pode fazer este problema.
Você pode fazê-lo de forma iterativa ou recursivamente.
A maioria dos problemas que você encontrar o que pode ser feito recursivamente também pode ser feito de forma iterativa.
Então aqui nós temos feito isso de forma recursiva.
>> Será que alguém quer definir o que significa fazer uma função recursiva?
[Estudante] Quando você tem uma função chamar a si mesma
e depois chamar-se até que ele sai com verdade e verdade. Sim >>.
Uma função recursiva é apenas uma função que chama a si mesmo.
Há três coisas grandes que uma função recursiva deve ter.
O primeiro é, obviamente, ele chama a si mesmo.
O segundo é o caso base.
Então, em algum ponto, a função precisa parar de chamar-se,
e é isso que o caso base é para.
Então aqui nós sabemos que devemos parar, devemos dar-se em nossa busca
quando começo iguala final - e nós falaremos sobre o que isso significa.
Mas, finalmente, a última coisa que é importante para funções recursivas:
as funções de alguma forma abordar o caso base.
Como se você não está realmente atualizar qualquer coisa quando você faz a segunda chamada recursiva,
se você está literalmente apenas chamando a função novamente com os mesmos argumentos
e não variáveis ​​globais mudaram ou qualquer coisa,
você nunca vai chegar ao caso base, caso em que isso é ruim.
Será uma recursão infinita e um estouro de pilha.
Mas aqui vemos que a atualização está acontecendo desde o início, estamos atualizando + final / 2,
estamos atualizando o argumento final aqui, estamos atualizando o argumento start aqui.
Assim, em todas as chamadas recursivas estamos atualizando algo. Okay.
Você quer andar conosco através de sua solução? >> Claro.
Estou usando SearchHelp de modo que cada vez que faço esta chamada de função
Eu tenho o início de onde eu estou procurando na matriz e no final
de onde eu estou olhando a matriz.
>> A cada passo onde ele está dizendo que é o elemento do meio, que é de início + final / 2,
é que igual ao que nós estamos procurando?
E se é, então, que encontramos, e eu acho que é passado até os níveis de recursão.
E se isso não for verdade, então vamos verificar se esse valor médio da matriz é muito grande,
caso em que se olha para a parte esquerda da matriz, indo desde o início até o índice médio.
E caso contrário, fazer a meia final.
[Bowden] Okay.
É uma boa idéia.
Ok, então um par de coisas, e na verdade, isso é uma coisa muito alto nível
que você nunca vai precisar saber para este curso, mas é verdade.
Funções recursivas, você sempre ouve que eles são um mau negócio
porque se você recursivamente chamar-se muitas vezes, você tem de estouro de pilha
uma vez que, como eu disse antes, cada função recebe o seu quadro de pilha própria.
Então, cada chamada da função recursiva obtém sua estrutura própria pilha.
Então, se você fizer mil chamadas recursivas, você recebe 1.000 quadros de pilha,
e rapidamente você levar a ter quadros de pilha demais e as coisas simplesmente quebrar.
É por isso que funções recursivas são geralmente ruim.
Mas há um subconjunto agradável de funções recursivas chamado rabo-recursivas funções,
e este passa a ser um exemplo de um que se o compilador percebe isso
e que deveria, penso eu - em Clang se você passar a O2-bandeira
em seguida, ele vai perceber isso é rabo recursiva e fazer as coisas bem.
>> Ele vai reutilizar o quadro de pilha, uma e outra vez para cada chamada recursiva.
E assim desde que você está usando o quadro de pilha mesmo, você não precisa se preocupar com
nunca empilhe transbordando, e, ao mesmo tempo, como você disse antes,
onde uma vez você retornar verdadeiro, então ele tem que voltar-se todos estes quadros de pilha
ea chamada 10 a SearchHelp tem que voltar para o 9, tem que voltar para o 8.
De modo que não precisa acontecer quando funções são cauda recursiva.
E então o que torna esta cauda função recursiva é aviso de que, para um dado convite para searchHelp
a chamada recursiva que ele está fazendo é o que ele está retornando.
Assim, em primeira chamada para SearchHelp, que quer retornar imediatamente falso,
retornar imediatamente verdadeira, ou fazemos uma chamada recursiva para SearchHelp
onde o que está retornando é o que essa chamada está retornando.
E não poderia fazer isso se fizemos algo como int x = SearchHelp retorno, x * 2,
apenas alguma alteração aleatória.
>> Então, agora chamada esta recursiva, esta int x = SearchHelp chamada recursiva,
já não é cauda recursiva porque na verdade não tem que devolver
de volta para um quadro de pilha anterior de modo a que a chamada anterior para a função
pode, então, fazer algo com o valor de retorno.
Então isso não é cauda recursiva, mas o que tinha antes, é bem cauda recursiva. Sim.
[Aluno] não deve o caso base segundo ser verificada primeiro
porque pode haver uma situação em que, quando você passar o argumento
você começar = fim, mas eles são o valor da agulha.
A questão foi que não podemos correr para o caso em que o valor final é de agulha
ou iniciar = fim, apropriadamente, começar final =
e você realmente não tenho verificado que um valor particular, no entanto,
em seguida, iniciar + final / 2 é apenas vai ser o mesmo valor.
Mas nós já retornou falso e nós nunca realmente verificado o valor.
Então, no mínimo, em primeira convocação, se o tamanho é 0, então queremos voltar falso.
Mas se o tamanho é 1, então de início não vai acabar igual,
e nós vamos pelo menos verificar a um elemento.
Mas eu acho que você está certo em que pode acabar em um caso onde começar + final / 2,
início acaba sendo o mesmo que de início + final / 2,
mas nós nunca realmente verificado esse elemento.
>> Então, se nós primeiro verificar se o elemento do meio o valor que está procurando,
então podemos retornar imediatamente verdadeiro.
Mais se eles são iguais, então não há sentido em continuar
já que estamos indo só para atualizar a um caso em que estamos em uma matriz de elemento único.
Se esse elemento único não é o que estamos procurando,
então está tudo errado. Sim.
[Estudante] O problema é que uma vez que o tamanho é realmente maior do que o número de elementos na matriz,
já existe um deslocamento - >> Então vai tamanho -
[Aluno] Dizer se a matriz foi tamanho 0, então o SearchHelp vai realmente verificar palheiro de 0
na primeira chamada.
A matriz tem tamanho 0, de modo que o 0 é - >> Yeah.
Há outra coisa que - que poderia ser bom. Vamos pensar.
Então, se a matriz tinha 10 elementos e um meio que vamos verificar é o índice de 5,
por isso estamos verificando 5, e vamos dizer que o valor é menor.
Então, nós estamos jogando tudo fora de 5 em diante.
Então comece a + final / 2 vai ser o nosso novo fim,
Então, sim, ele sempre vai ficar para além do fim da matriz.
Se é um caso se era par ou ímpar, então poderíamos verificar, por exemplo, 4,
mas ainda estamos jogando fora -
Então, sim, o fim é sempre vai ser além do fim real da matriz.
Assim, os elementos que estamos focando, final é sempre vai ser o um depois.
E assim se faz sempre começo final igual, estamos em uma matriz de tamanho 0.
>> A outra coisa que eu estava pensando é que estamos atualizando início para começar a ser + final / 2,
por isso este é o caso que eu estou tendo problemas com onde começar + final / 2
é o elemento que estamos verificando.
Vamos dizer que nós tivemos essa matriz de 10 elementos. Qualquer que seja.
Então comece a + final / 2 vai ser algo como este,
e se isso não é o valor, digamos que deseja atualizar.
O valor é maior, por isso queremos olhar para esta metade da matriz.
Então, como estamos atualizando início, estamos atualizando início para agora ser esse elemento.
Mas isso ainda pode trabalhar, ou pelo menos, você pode fazer start + final / 2 + 1.
[Aluno] Você não precisa ser começar final + [inaudível] >> Yeah.
Nós já verificada este elemento e sei que não é o que estamos procurando.
Portanto, não é necessário atualizar início para ser esse elemento.
Nós podemos simplesmente ignorá-lo e atualizar começar a ser este elemento.
E há sempre um caso, vamos dizer, que este fosse final,
assim, então começar seria isso, inicie + final / 2 seria este,
começar a final + - Sim, eu acho que ele pode acabar em recursão infinita.
Vamos dizer que é apenas uma matriz de tamanho 2 ou uma matriz de tamanho 1. Eu acho que isso vai funcionar.
Assim, atualmente, é que início e fim elemento é um além.
Assim, o elemento que vamos verificar é este,
e então, quando nós atualizamos início, estamos atualizando início para ser 0 + 1/2,
que vai acabar nos de volta com partida sendo este elemento.
>> Então, nós estamos verificando o mesmo elemento e outra vez.
Portanto, este é o caso em que cada chamada recursiva deve realmente atualizar alguma coisa.
Então, nós precisamos fazer start + final / 2 + 1, ou então há um caso
onde não estamos realmente atualizar início.
Todo mundo vê isso?
Okay.
Alguém tem perguntas sobre esta solução ou comentários mais?
Okay. Alguém tem uma solução iterativa que todos nós podemos olhar?
Será que todos nós fazemos isso recursivamente?
Ou eu também acho que se você abrir o seu, então você pode ter substituído o seu anterior.
Será que salvar automaticamente? Eu não sou positivo.
Alguém tem iterativo?
Podemos caminhar com ele junto, se não.
A ideia de que vai ser o mesmo.
Solução iterativa.
Nós vamos querer fazer basicamente a mesma idéia
onde queremos acompanhar o novo fim da matriz e do novo começo da matriz
e fazer isso mais e mais.
E se o que estamos mantendo o controle de como o início eo fim nunca se cruzam,
então nós não encontrá-lo e podemos retornar falso.
Então, como posso fazer isso? Alguém tem sugestões ou código para me puxar para cima?
[Aluno] Faça um loop while. Sim >>.
Você vai querer fazer um loop.
>> Será que você tem o código que eu poderia puxar para cima, ou o que você estava indo para sugerir?
[Aluno] Eu acho que sim. >> Tudo bem. Isso torna as coisas mais fáceis. Qual era o seu nome?
[Aluno] Lucas.
Revisão 1. Okay.
Baixo é o que chamamos de começar antes.
Se não é o que nós chamamos final antes.
Na verdade, o fim está agora dentro da matriz. É um elemento que devemos considerar.
Tão baixa é 0, se for o tamanho da matriz - 1,
e agora estamos looping, e estamos verificando -
Eu acho que você pode andar por ela.
Qual foi o seu pensamento por isso? Ande nos através do seu código.
[Aluno] Claro. Veja o valor palheiro no meio e compará-lo com agulha.
Então, se é maior do que a agulha, então você quer - oh, na verdade, que deve ser para trás.
Você vai querer jogar fora a metade direita, e então sim, que deve ser o caminho.
[Bowden] Portanto, este deve ser menos? É isso que você disse? >> [Estudante] Yeah.
[Bowden] Okay. Menos.
Então, se o que estamos vendo é menor do que o que nós queremos,
então sim, nós queremos jogar fora a metade esquerda,
o que significa que estamos atualizando tudo o que estamos considerando
movendo baixo à direita da matriz.
Este parece ser bom.
Eu acho que tem o mesmo problema que nós dissemos que o anterior,
onde se baixa é 0 e se for 1, então baixa-se + / 2 vai definir até ser a mesma coisa de novo.
>> E mesmo se esse não é o caso, é ainda mais eficiente no mínimo
apenas para jogar fora o elemento que apenas olhou para que sabemos que é errado.
Então baixo + cima / 2 + 1 - >> [aluno], que deveria ser o contrário.
[Bowden] Ou este deve ser - 1 e o outro deve ser + 1.
[Aluno] E não deve ser um duplo sinal de igual. >> [Bowden] Yeah.
[Estudante] Yeah.
Okay.
E, finalmente, agora que temos este 1 + - 1 coisa,
é - não pode ser - é sempre possível para baixo para acabar com um valor maior do que para cima?
Eu acho que a única maneira que pode acontecer - É possível? >> [Aluno] não sei.
Mas se ele fica truncado e em seguida, recebe menos que 1 e depois - >> Yeah.
[Aluno] Seria possivelmente ficar confuso.
Eu acho que deve ser bom só porque
para que ele acabe menor que teria que ser igual, eu acho.
Mas se eles são iguais, então não teria feito o loop while para começar
e nós só teria devolvido o valor. Então, eu acho que estamos bem agora.
Note-se que, embora este problema já não é recursivo,
o mesmo tipo de ideias aplicar onde podemos ver como isso tão facilmente se presta
a uma solução recursiva pelo fato de que nós estamos apenas atualização dos índices e outra vez,
estamos tornando o problema cada vez menor, estamos nos concentrando em um subconjunto da matriz.
[Estudante] Se baixo é 0 e se for 1, ambos estariam 0 + 1/2, que iria para 0,
e, em seguida, um seria + 1, pode-se ser - 1.
[Aluno] Onde estamos verificando a igualdade?
Como se o meio é realmente agulha?
Nós não estamos fazendo atualmente isso? Oh!
Se isto é -
Sim. Não podemos simplesmente fazer o teste aqui porque vamos dizer que a primeira metade -
[Aluno] É realmente como não jogar fora o limite.
Então, se você jogar fora o salto, você tem que verificar primeiro ou o que quer.
Ah. Sim. >> [Estudante] Yeah.
Portanto, agora temos jogado fora o que nós atualmente olhou,
o que significa que nós agora precisamos também ter
if (palheiro [(+ baixo para cima) / 2] == agulha), então podemos retornar true.
E se eu colocar mais ou apenas se, significa literalmente a mesma coisa
porque este teria retornado verdade.
Então, eu vou colocar mais se, mas isso não importa.
>> Então, mais se isso, mais isso, e isso é uma coisa comum que eu faço
onde até mesmo se for o caso, onde tudo é bom aqui,
como baixo nunca pode ser maior do que se, não é o raciocínio que vale a pena saber se isso é verdade.
Assim, pode também dizer enquanto baixo é menor do que ou igual a
ou enquanto baixo é inferior a
por isso, se eles são sempre iguais ou baixa acontece a passar-se,
então podemos quebrar este ciclo.
Perguntas, preocupações, comentários?
Okay. Este parece ser bom.
Agora nós queremos fazer tipo.
Se formos a minha segunda revisão, vemos esses mesmos números,
mas agora eles não estão mais em ordem de classificação.
E nós queremos implementar ordenação usando qualquer algoritmo em O de n log n.
Assim que o algoritmo que você acha que deve implementar aqui? >> [Aluno] tipo Merge.
[Bowden] Yeah. Merge sort é O (n log n), de modo que é o que vamos fazer.
E o problema vai ser bastante semelhante,
onde se presta facilmente a uma solução recursiva.
Nós também podemos chegar a uma solução iterativa, se quisermos,
mas recursão será mais fácil aqui e nós devemos fazer a recursividade.
Acho que vamos caminhar por merge sort primeiro,
embora haja um vídeo bonito em merge sort já. [Risos]
Então, merge sort existem - Eu estou perdendo muito deste trabalho.
Oh, há apenas uma esquerda.
Então, se fundem.
Oh, 1, 3, 5.
Okay.
Merge leva duas matrizes distintas.
Individualmente as duas matrizes são ambos classificadas.
Então, essa matriz, 1, 3, 5, classificados. Esta matriz, 0, 2, 4, classificados.
Agora, o que deve fazer é mesclar combiná-los em uma única matriz que é em si classificados.
Então, nós queremos uma matriz de tamanho 6, que vai ter esses elementos dentro dele
em ordem de classificação.
>> E assim podemos tirar vantagem do fato de que essas duas matrizes são classificadas
fazer isso em tempo linear,
significado de tempo linear se essa matriz é x tamanho e este é y tamanho,
então o algoritmo total deve ser O (x + y). Okay.
Assim sugestões.
[Aluno] Poderíamos começar a partir da esquerda?
Então você vai colocar a 0 para baixo primeiro e depois a 1 e, em seguida, aqui você está no 2.
Então é tipo de como você tem um guia que está se movendo para a direita. >> [Bowden] Yeah.
Para ambas as matrizes se concentrar apenas no elemento mais à esquerda.
Porque ambas as matrizes são classificadas, sabemos que esses dois elementos
são os mais pequenos elementos em um array.
Então isso significa que um desses dois elementos deve ser o menor elemento em nossa matriz resultante da fusão.
O que acontece é que o menor é o do tempo este direito.
Então, tomamos 0, insira-o à esquerda porque 0 é menor que 1,
assim que tomar 0, inseri-lo em nossa primeira posição, e depois atualizar esta
para se concentrar em primeiro elemento.
E agora vamos repetir.
Então agora nós comparar 2 e 1. 1 é menor, por isso vamos inserir uma.
Nós atualizar este ponteiro para apontar para esse cara.
Agora vamos fazer isso de novo, então 2. Isto irá atualizar, comparar estes 2, 3.
Isso atualiza, depois 4 e 5.
De modo que é de mesclagem.
>> Que deve ser bastante óbvio que é o tempo linear, uma vez que basta ir em cada elemento de uma vez.
E esse é o maior passo para a implementação de merge sort está fazendo isso.
E não é tão difícil.
Algumas coisas para se preocupar é vamos dizer que foram fusão 1, 2, 3, 4, 5, 6.
Neste caso, vamos acabar no cenário onde este vai ser menor,
então nós atualizamos este ponteiro, este vai ser menor, atualizar esta,
este é menor, e agora você tem que reconhecer
quando você realmente ficar sem elementos para comparar com.
Uma vez que já utilizaram este matriz inteira,
tudo nesta matriz é agora apenas inserido aqui.
Então, se nós nunca correr para o ponto onde uma de nossas matrizes é completamente fundidas já,
então simplesmente tomar todos os elementos da matriz que não e inseri-las no fim do array.
Assim, podemos apenas inserir 4, 5, 6. Okay.
Isso é uma coisa a observar.
De aplicação que deve ser o passo 1.
Mesclar classificar, então com base nisso, que é duas etapas, duas etapas de bobos.
Vamos dar essa matriz.
Então, merge sort, etapa 1 é recursivamente quebrar a matriz em metades.
Então, dividir essa matriz em metades.
Temos, agora, 4, 15, 16, 50 e 8, 23, 42, 108.
E agora nós fazê-lo novamente e nós dividimos estas em metades.
Eu só vou fazer isso deste lado.
Então, 4, 15 e 16, 50.
Gostaríamos de fazer a mesma coisa aqui.
E agora nós dividi-lo em duas metades novamente.
E nós temos 4, 15, 16, 50.
Então, esse é o nosso caso base.
Uma vez que as matrizes são de tamanho 1, então vamos parar com a divisão em duas metades.
>> Agora o que vamos fazer com isso?
Vamos acabar isto também se dividem em 8, 23, 42 e 108.
Então, agora que estamos neste momento, agora o segundo passo de merge sort é apenas fusão pares para as listas.
Então, nós queremos unir estes. Nós apenas chamar fundir.
Sabemos fusão voltará estes em ordem de classificação.
4, 15.
Agora, queremos juntar essas, e que vai retornar uma lista com aqueles em ordem de classificação,
16, 50.
Combinamos aqueles - Eu não posso escrever - 8, 23 e 42, 108.
Portanto, temos pares incorporadas uma vez.
Agora só fundir novamente.
Observe que cada uma dessas listas é classificada em si,
e então nós podemos apenas mesclar essas listas para obter uma lista de tamanho 4, que é classificada
e mesclar essas duas listas para obter uma lista de tamanho 4, que está classificada.
E, finalmente, podemos mesclar essas duas listas de tamanho 4 para obter uma lista de tamanho 8, que está classificada.
Então, para ver que este é global n log n, já vimos que mesclagem é linear,
Então, quando estamos lidando com a junção destes, assim como o custo global de fusão
para estas duas listas é apenas 2 porque -
Ou bem, é O de n, mas n aqui é apenas esses dois elementos, por isso é 2.
E estes dois será 2 e estes dois será 2 e estes 2 vai ser 2,
assim em todas as fusões que temos de fazer, acabamos fazendo n.
Como 2 + 2 + 2 + 2 é de 8, que é n,
de modo que o custo de fusão neste conjunto é n.
E então a mesma coisa aqui.
Vamos juntar essas duas, então estes dois e, individualmente, esta fusão terá quatro operações,
esta fusão terá quatro operações, mas, mais uma vez, entre todos eles,
acabamos fusão n coisas totais, e por isso este passo leva n.
E assim cada nível tem n elementos a serem reunidos.
>> E quantos são os níveis?
Em cada nível, a nossa matriz cresce tamanho 2.
Aqui nossas matrizes são de tamanho 1, aqui eles são de tamanho 2, aqui eles são de tamanho 4,
e, finalmente, eles são de tamanho 8.
Então, uma vez que está dobrando, não vão ser um total de log n desses níveis.
Assim, com o registro de n níveis, cada nível individual, tendo n total de operações,
temos um log n n algoritmo.
Perguntas?
Já as pessoas já fizeram progressos sobre como implementar isso?
Será que alguém já em um estado onde eu só posso puxar para cima o seu código?
Eu posso dar um minuto.
Este vai ser mais longo.
Eu recomendo se repetem -
Você não tem que fazer recursão para fusão
porque para fazer recursão para mesclagem, você vai ter que passar por um monte de diferentes tamanhos.
Você pode, mas é irritante.
Mas recursão para classificar-se é muito fácil.
Você só literalmente chamar espécie na metade esquerda, tipo na metade direita. Okay.
Alguém tem alguma coisa que eu posso puxar para cima ainda?
Ou então eu vou dar um minuto.
Okay.
Alguém tem algo que podemos trabalhar?
Ou então nós vamos trabalhar com isso e, em seguida, expandir a partir daí.
>> Alguém tem mais do que isso que eu posso puxar para cima?
[Estudante] Yeah. Você pode puxar a minha. >> Tudo bem.
Sim!
[Aluno] Havia uma série de condições. >> Oh, atirar. Você pode -
[Estudante] Eu tenho que salvá-lo. Sim >>.
Então nós fizemos a fusão separadamente.
Ah, mas não é tão ruim assim.
Okay.
Então tipo é em si apenas chamando mergeSortHelp.
Explique-nos o que mergeSortHelp faz.
[Aluno] MergeSortHelp praticamente faz as duas etapas principais,
que é o de classificar cada metade da matriz e, em seguida, para fundir os dois.
[Bowden] Ok, então me dê um segundo.
Eu acho que isso - >> [aluno] eu preciso -
Sim. Eu estou sentindo falta de alguma coisa.
Na fusão, eu percebo que eu preciso para criar uma nova matriz
porque eu não poderia fazê-lo no lugar. Sim >>. Você não pode. Corrigir.
[Estudante] Então eu criar uma nova matriz.
Esqueci-me no final de fundir a re-mudar.
Okay. Precisamos de uma nova matriz.
Em merge sort, isso é quase sempre verdadeiro.
Parte do custo de um algoritmo de melhor em termos de tempo
é quase sempre a necessidade de usar a memória um pouco mais.
Então, aqui, não importa como você fazer merge sort,
você inevitavelmente precisa usar um pouco de memória extra.
Ele ou ela criou uma nova matriz.
E então você diz, no final, só precisa copiar nova matriz para a matriz original.
[Estudante] Eu acho que sim.
Eu não sei se isso funciona em termos de contagem de referência ou o que for -
Sim, ele vai funcionar. >> [Aluno] Okay.
Será que você tente executar isso? >> [Aluno] Não, ainda não. Ok >>.
Tente executá-lo, e então eu vou falar sobre isso por um segundo.
[Aluno] Eu preciso ter todos os protótipos de função e tudo, certo?
Os protótipos de função. Ah, você quer dizer como - Sim.
Ordenar está chamando mergeSortHelp.
>> Então, para que tipo de chamar mergeSortHelp, mergeSortHelp deve ter sido definido
antes tipo ou só precisamos do protótipo. Basta copiar e colar isso.
E da mesma forma, mergeSortHelp está chamando fundir,
mas mesclagem não foi definido ainda, então nós podemos apenas deixar mergeSortHelp saber
que é isso que vai fundir a aparência, e que é isso.
Então mergeSortHelp.
Nós temos um problema aqui, onde temos nenhum caso base.
MergeSortHelp é recursiva, então qualquer função recursiva
vai precisar de algum tipo de caso base para saber quando parar de chamar recursivamente si.
O que é o nosso caso base vai ser aqui? Sim.
[Estudante] Se o tamanho for 1? >> [Bowden] Sim.
Então, como se viu ali, paramos matrizes de divisão
uma vez que temos em matrizes de tamanho 1, que inevitavelmente são classificados si.
Então, se o tamanho é igual a 1, sabemos que a matriz já está classificado,
para que possamos retornar apenas.
>> Observe que é vazio, de modo que não retornar nada especial, apenas retornar.
Okay. Então, esse é o nosso caso base.
Eu acho que o nosso caso base também poderia ser se acontecer de ser fusão de uma matriz de tamanho 0,
nós provavelmente quer parar em algum ponto,
assim, podemos dizer tamanho inferior a 2 ou inferior ou igual a 1
de modo que isso vai funcionar para qualquer matriz agora.
Okay.
Então, esse é o nosso caso base.
Agora se você quer andar conosco através fusão?
O que todos esses casos significa?
Até aqui, nós estamos apenas fazendo a mesma idéia, o -
[Estudante] Eu preciso estar passando tamanho, com todas as chamadas mergeSortHelp.
Eu adicionei tamanho como uma primária adicional e que não está lá, como o tamanho / 2.
[Bowden] Oh, tamanho / 2, tamanho / 2. >> [Estudante] É, e também na função acima, bem.
[Bowden] Aqui? >> [Aluno] Apenas o tamanho. >> [Bowden] Oh. Tamanho, tamanho? >> [Estudante] Yeah.
[Bowden] Okay.
Deixe-me pensar por um segundo.
Não nos deparamos com um problema?
Estamos sempre tratar a esquerda como 0. >> [Aluno] Não.
Isso é errado também. Desculpe. Deve ser partida. Sim.
[Bowden] Okay. Eu gosto que melhor.
E fim. Okay.
Então agora você quer andar conosco através fusão? >> [Aluno] Okay.
Eu só estou passando esta nova matriz que eu criei.
O seu tamanho é o tamanho da parte da matriz que queremos ser classificados
e tentando encontrar o elemento que eu deveria colocar na etapa nova matriz.
Então, para fazer isso, primeiro eu estou verificando se a metade esquerda da matriz continua a ter mais elementos,
e se isso não acontecer, então você vai para baixo para que a condição mais, que apenas diz
Tudo bem, ele deve estar no direito de matriz, e vamos colocar isso no índice atual de newArray.
>> E então, de outra forma, eu estou verificando se o lado direito da matriz também está terminado,
caso em que eu só colocar na esquerda.
Isso pode não ser realmente necessário. Não tenho a certeza.
Mas de qualquer forma, a verificação de outros dois qual dos dois são menores na esquerda ou na direita.
E também, em cada caso, estou incrementando o que eu incrementar espaço reservado.
[Bowden] Okay.
Isso parece bom.
Alguém tem comentários ou questões ou perguntas?
Assim, os quatro casos que temos de trazer as coisas em apenas sendo - ou parece que cinco -
mas temos que considerar se a matriz de esquerda não tem mais coisas que precisamos fundir,
se o direito de matriz não tem mais coisas que precisamos unir -
Estou apontando para o nada.
Então, se a matriz de esquerda não tem mais coisas ou o direito de matriz não tem mais coisas.
Esses são dois casos.
Precisamos também de um caso trivial de se a coisa esquerdo é menor que a coisa certa.
Então, nós queremos escolher a coisa esquerdo.
Esses são os casos.
Então isso era certo, então é isso.
Matriz esquerda. É 1, 2, 3. Okay. Então, sim, essas são as quatro coisas que pode querer fazer.
E nós não vamos passar por cima de uma solução iterativa.
Eu não recomendaria -
Fundir tipo é um exemplo de uma função que é ao mesmo tempo não a cauda recursiva,
não é fácil fazer com que a cauda recursiva,
mas também não é muito fácil fazê-lo interativo.
Isto é muito fácil.
Esta implementação do merge sort,
fundem, não importa o que você faça, você está indo para a construção de mesclagem.
>> Então, merge sort construída em cima de mesclar recursivamente é apenas essas três linhas.
Iterativamente, é mais chato e mais difícil de se pensar.
Mas note que não é cauda recursiva desde mergeSortHelp - quando se chama a si mesma -
ele ainda precisa fazer as coisas após esta chamada retorna recursivas.
Portanto, este quadro de pilha deve continuar a existir mesmo depois de chamar isso.
E então, quando você chama isso, o quadro de pilha deve continuar a existir
porque, mesmo depois que a chamada, ainda precisamos mesclar.
E isso não é trivial para fazer este rabo recursiva.
Perguntas?
Tudo bem.
Então, voltando a classificar - oh, há duas coisas que eu quero mostrar. Okay.
Voltando ao tipo, vamos fazer isso rapidamente.
Ou pesquisa. Tipo? Ordenar. Sim.
Voltando aos primórdios da espécie.
Queremos criar um algoritmo que ordena a matriz usando qualquer algoritmo
em O de n.
Então, como isso é possível? Alguém tem qualquer tipo de -
Sugeri antes em -
Se estamos prestes a melhorar a partir de n log n a O de n,
temos melhorado o nosso algoritmo em termos de tempo,
o que significa que vamos precisar fazer para compensar isso?
[Aluno] Espaço. Sim >>. Nós vamos estar usando mais espaço.
E nem mesmo apenas mais espaço, é exponencialmente mais espaço.
Então eu acho que esse tipo de algoritmo é algo pseudo, pseudo polynom -
pseudo - Eu não me lembro. Pseudo algo.
Mas é porque precisamos usar tanto espaço
que isso pode ser conseguido, mas não realista.
>> E como vamos conseguir isso?
Podemos alcançar isso se garantir que algum determinado elemento da matriz
é inferior a um determinado tamanho.
Então vamos apenas dizer que o tamanho é de 200,
qualquer elemento de uma matriz é abaixo do tamanho 200.
E isso é realmente muito realista.
Você pode muito facilmente ter uma matriz que você sabe tudo na mesma
vai ser menor do que um número.
Como se você tiver algum vetor absolutamente enorme ou algo
mas você sabe que tudo vai ser entre 0 e 5,
em seguida, ele vai ser muito mais rápido para fazer isso.
E o limite de qualquer um dos elementos é de 5,
assim que este limite, que é a quantidade de memória que você vai estar usando.
Assim, o limite é de 200.
Em teoria, há sempre um limite desde um inteiro só pode ser de até 4 bilhões,
mas isso é irreal, desde então, estaria usando o espaço
da ordem de 4000 milhões. Então, isso é irreal.
Mas aqui vamos dizer que nosso limite é 200.
O truque para fazê-lo em O de n é que fazer uma outra matriz chamada conta de tamanho VINCULADO.
Então, na verdade, este é um atalho para - Eu realmente não sei se Clang faz isso.
Mas no GCC, no mínimo - Clang assumindo estou faz isso também -
isso só vai inicializar a matriz inteira para ser 0s.
Então, se eu não quiser fazer isso, então eu poderia fazer separadamente for (int i = 0;
i <BOUND, i + +) e conta [i] = 0;
Então, agora tudo é inicializado com 0.
Eu iterar sobre minha matriz,
eo que eu estou fazendo é que eu estou contando o número de cada um - Vamos descer aqui.
Temos 4, 15, 16, 50, 8, 23, 42, 108.
O que eu estou contando é o número de ocorrências de cada um desses elementos.
Vamos realmente adicionar mais um par aqui com algumas repetições.
Assim, o valor que temos aqui, o valor do que vai ser array [i].
Então val poderia ser 4 ou 8 ou o que seja.
E agora eu estou contando quantos de que o valor que eu vi,
para a contagem [val] + +;
Depois de feito isso, conta vai para algo parecido com 0001.
Vamos fazer a contagem [val] - VINCULADO + 1.
>> Agora isso é só para explicar o fato de que estamos começando do 0.
Então, se 200 vai ser a nossa maior número,
então 0-200 é 201 coisas.
Então, conta, ele vai olhar como 00001 porque temos um 4.
Então nós vamos ter 0001, onde vamos ter um 1 no índice de 8 de contagem.
Nós vamos ter a 2 no índice 23 da contagem.
Nós vamos ter a 2 no índice 42 da contagem.
Assim, podemos usar contagem.
Então num_of_item = contagem [i].
E assim se num_of_item é 2, isso significa que nós queremos inserir o número 2 de i
em nossa matriz de classificação.
Portanto, temos de manter o controle de quanto estamos longe na matriz.
Então index = 0.
Array - Eu só vou escrever.
Conta -
array [index + +] = i;
É isso o que eu quero? Eu acho que é o que eu quero.
Sim, isso parece bom. Okay.
Assim que todo mundo entende o que o propósito da minha conta é a matriz?
É contando o número de ocorrências de cada um desses números.
Então eu estou interagindo sobre essa matriz conta,
e a posição ith na matriz contagens
é o número de i é que deve aparecer na minha matriz de classificação.
É por isso que a contagem de 4 vai ser um
e contagem de 8 vai ser 1, as contagens de 23, vai ser 2.
Então é assim que muitos deles eu quero inserir no meu array ordenado.
Então eu só fazer isso.
Estou inserindo num_of_item i é a minha matriz de classificação.
>> Perguntas?
E assim mais uma vez, este é o tempo linear uma vez que estamos apenas interagindo sobre isso uma vez,
mas também é linear em que este número se encontrar,
e por isso depende muito do que o seu limite é.
Com um limite de 200, que não é tão ruim.
Se o seu limite vai ser de 10.000, então isso é um pouco pior,
mas se o seu limite vai ser 4 bilhões, que é completamente irrealista
e essa matriz vai ter que ser de tamanho 4 bilhões, o que é irreal.
Então é isso. Perguntas?
[Resposta do aluno inaudível] >> Okay.
Eu percebi uma coisa, quando estávamos passando.
Acho que o problema estava em Lucas e, provavelmente, cada um que já vimos.
Eu esqueci completamente.
A única coisa que eu queria comentar é que quando você está lidando com coisas como índices,
você nunca realmente ver isso quando você está escrevendo um loop,
mas, tecnicamente, sempre que você está lidando com esses índices,
você deve quase sempre lidar com números inteiros sem sinal.
A razão para isso é quando você está lidando com números inteiros assinados,
por isso, se você tem dois inteiros assinados e adicioná-los juntos
e eles acabam muito grande, então você acaba com um número negativo.
Então é isso que é estouro de inteiro.
>> Se eu adicionar 2 bilhões e 1 bilhão, eu acabar com negativo 1 bilhão.
É assim que funciona em computadores inteiros.
Assim, o problema com o uso -
Isso é bom, exceto se baixo passa a ser 2 bilhões e se passa a ser 1 bilhão,
então isso vai ser negativo 1 bilhão e, em seguida, vamos dividir esse por dois
e acabar com negativo de 500 milhões.
Portanto, este é apenas um problema se acontecer de você estar procurando por uma matriz
de bilhões de coisas.
Mas se + baixo para cima acontece a transbordar, então isso é um problema.
Assim que torná-los sem sinal, então 2 bilhões, mais 1 bilhão é 3 bilhões.
3.000 milhões dividido por dois é de 1,5 bilhões.
Assim, logo que eles estão sem sinal, tudo é perfeito.
E por isso é também um problema quando você está escrevendo o seu loops,
e realmente, ele provavelmente faz isso automaticamente.
Será realmente apenas gritar com você.
Portanto, se esse número é muito grande para ser em apenas um inteiro, mas que caberia em um inteiro não assinado,
ela vai gritar com você, é por isso que você nunca correr para a questão.
Você pode ver que um índice nunca vai ser negativo,
e assim, quando você está interagindo sobre uma matriz,
você quase sempre pode dizer unsigned int i, mas você realmente não precisa.
As coisas estão indo para o trabalho praticamente tão bem.
Okay. [Sussurra] Que horas são?
A última coisa que eu queria mostrar - e eu vou fazê-lo muito rápido.
Você sabe como nós # define para que possamos # define MAX como 5 ou algo assim?
Não vamos fazer MAX. # Define limite como 200. Isso é o que fizemos antes.
Que define uma constante, que só vai ser copiado e colado
onde quer que aconteça para escrever VINCULADO.
>> Assim, podemos realmente fazer mais com # define.
Podemos # define funções.
Eles não são realmente funções, mas vamos chamá-los de funções.
Um exemplo seria algo como MAX (x, y) é definida como (x <y y:? X). Okay.
Portanto, você deve se acostumar a sintaxe do operador ternário,
mas é menor que x y? Retornar y, outro retorno x.
Assim você pode ver que você pode fazer esta função um separado,
ea função poderia ser como bool MAX leva 2 argumentos, devolva este.
Este é um dos mais comuns que eu vejo feito como este. Nós os chamamos de macros.
Esta é uma macro.
Esta é apenas a sintaxe para isso.
Você pode escrever uma macro para fazer o que quiser.
Você freqüentemente ver macros para depurar printfs e outras coisas.
Assim, um tipo de printf, existem constantes especiais em C, como sublinhado LINHA sublinhado,
2 underscores LINHA sublinhado,
e há também acho que 2 underscores FUNC. Isso pode ser isso. Algo assim.
Estas coisas será substituído com o nome da função
ou o número da linha que você está.
Freqüentemente, você escreve printfs depuração que aqui eu poderia então apenas escrever
DEBUG e ele será impresso o número da linha e função que acontecer de eu estar no
que encontrou que a declaração DEBUG.
E você também pode imprimir outras coisas.
Então, uma coisa que você deve observar é se acontecer de eu # define DOUBLE_MAX
como algo como 2 * y e 2 * x.
Assim, por razão alguma, acontecer de você fazer isso muito.
Então faça uma macro.
Esta é realmente quebrado.
Eu diria que é, fazendo algo como DOUBLE_MAX (3, 6).
Então, o que deve ser devolvido?
[Estudante] 12.
Sim, 12 devem ser devolvidos, e 12 é devolvido.
3 é substituído por x, 6 é substituído por y, e voltamos 2 * 6, que é 12.
Agora, o que sobre isso? O que deve ser devolvido?
[Estudante] 14. >> Idealmente, 14.
A questão é que, como define o trabalho de hash, lembre-se que é uma cópia literal e colar
de praticamente tudo, então o que é que isto vai ser interpretado como
3 é inferior a 1, mais 6, 2 vezes 1 mais 6, 2 vezes 3.
>> Assim, por esta razão, você quase sempre embrulhar tudo entre parênteses.
Qualquer variável que quase sempre embrulhe em parênteses.
Há casos em que você não tem que, como eu sei que eu não preciso fazer isso aqui
porque menos do que é praticamente sempre vai funcionar,
apesar de que pode até não ser verdade.
Se há algo ridículo como DOUBLE_MAX (1 == 2),
então que vai ficar substituído por 3 é igual a menos de 1 é igual a 2,
E então ele vai fazer 3 menor que 1, isso igual a 2,
o que não é o que queremos.
Portanto, a fim de evitar quaisquer problemas de precedência de operadores,
sempre embrulhe em parênteses.
Okay. E é isso, 5:30.
Se você tem alguma dúvida sobre o pset, avise-nos.
Deve ser divertido, ea edição hacker também é muito mais realista
do que a edição hacker do ano passado, por isso esperamos que um monte de você tentar.
No ano passado, foi muito grande.
>> [CS50.TV]