Ahhh, fato. Só depois de ler sua resposta, e reler o problema do Albert, é que vi que o problema pergunta a respeito da distância mais curta!
Abraço! Bruno -- Bruno FRANÇA DOS REIS msn: [email protected] skype: brunoreis666 tel: +55 11 9961-7732 http://brunoreis.com http://brunoreis.com/tech (en) http://brunoreis.com/blog (pt) GPG Key: http://brunoreis.com/bruno-public.key e^(pi*i)+1=0 2011/5/20 Pedro Cardoso <[email protected]> > Opa, Bruno, o processo que você descreveu certamente faz o nadador achar > uma das margens. > Mas o Bouskela quer mais - ele quer saber a melhor maneira (que faz o > nadador nadar menos) > de se achar uma das margens. > > Acho que isso cai para uma área da matemática que os matemáticos "puros" > não estudam muito > - a área de algoritmos. E esse problema tem a maior cara de *busca > exponencial*. > > ----------------------------------------------------------------------- > > Imagine que o nadador está a uma distância N de uma das margens. > Ele deve fazer o seguinte... > > > x <- 1 > Enquanto não achar a margem, repita: > [1] Nada x metros pra frente. Volta. Nada 2x metros para trás. Volta. > [2] Nada x metros pra esquerda. Volta. Nada 2x metros pra direita. Volta. > x <- 4x > > As noções de "frente" e "esquerda" estão erradas no máximo 45 graus. Assim, > na pior das hipóteses o nadador vai ter que nadar sqrt(2)*N metros em uma > das direções > (agora, até fazer isso, ele nadou nessa direção várias vezes). > > Note que [1] e [2] são processos independentes. > > Quanto ele nada em função de N? Pense um pouco pra ver que é C*N, onde C é > uma constante. > > Ignorando constantes, essa é a melhor maneira, já que mesno enxergando ele > teria que nadar 1*N > metros. > > > 2011/5/19 Bruno França dos Reis <[email protected]> > >> Em aberto? >> >> Se o nadador estivesse nadando paralelo ao rio, é só ele fazer uma curva >> mínima, e continuar até chegar às margens. >> >> Caso o nadador não saiba a direção em que estava nadando (suponhamos uma >> briga com os peixes, que o deixou desorientado, antes de ter seus olhos >> devorados), ele poderia nadar seguindo uma "espiral", aí certamente >> encontrará a margem, não? O algoritmo seria: >> >> n <- 1 >> Enquanto não achar a margem, repita: >> - dar n braçadas para frente >> - virar 90 graus para a esquerda >> - dar n braçacas para frente >> - virar 90 graus para a esquerda >> - n <- n + 1 >> >> Como a largura é finita, e a espiral cresce de tamanho em todas as >> direções, esse algoritmo certamente termina em um tempo finito! >> >> Tem alguma falha que eu não vi nesse processo? >> >> Abraço! >> Bruno >> >> >> -- >> Bruno FRANÇA DOS REIS >> >> msn: [email protected] >> skype: brunoreis666 >> tel: +55 11 9961-7732 >> >> http://brunoreis.com >> http://brunoreis.com/tech (en) >> http://brunoreis.com/blog (pt) >> >> GPG Key: http://brunoreis.com/bruno-public.key >> >> e^(pi*i)+1=0 >> >> >> >> 2011/5/19 Albert Bouskela <[email protected]> >> >>> Olá a todos, >>> >>> >>> >>> Uma curiosidade: – Parece-me que o problema abaixo (tão simples!) >>> permanece em aberto. >>> >>> >>> >>> Um nadador está nadando (o que mais pode fazer um nadador?) em um ponto >>> qualquer de um rio horizontal, retilíneo, com correnteza desprezível, >>> comprimento infinito e largura finita. >>> >>> >>> >>> Subitamente, peixes extremamente vorazes devoram os olhos do malfadado >>> nadador, ou, com menos drama, cai a noite absolutamente escura. >>> >>> >>> >>> Qual é a trajetória que o nadador deve trilhar, i.e., nadar, para atingir >>> – seguramente – uma das margens, nadando a menor distância possível? >>> >>> >>> >>> Obs.: – O malfadado nadador tem, implantado em sua cabeça, um sistema de >>> navegação que lhe informa, continuamente, a sua posição em relação ao ponto >>> inicial (o ponto no qual os peixes devoraram os seus olhos). >>> >>> >>> >>> Saudações, >>> >>> Albert Bouskela >>> >>> [email protected] >>> >>> >>> >> >> >
