Path: csiph.com!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Patricia Ferreira Newsgroups: pt.comp.programacao Subject: Re: Lisp, um mapa de trajeto Date: Sat, 20 Jan 2024 11:42:44 -0300 Organization: A noiseless patient Spider Lines: 113 Message-ID: <87wms4f4m3.fsf@example.com> References: <87ttni48z9.fsf@example.com> <87r0im428v.fsf@brilhante.top> <87edem3yds.fsf@example.com> <87edel4avz.fsf@brilhante.top> <874jfhvwb9.fsf@example.com> <87a5p83yxq.fsf@brilhante.top> <87mst8rpjj.fsf@example.com> <87o7dn3636.fsf@brilhante.top> <874jff1dbm.fsf@yaxenu.org> <87a5p638mt.fsf@brilhante.top> <87bk9mzg3b.fsf@example.com> <87bk9l9mki.fsf@brilhante.top> <87r0ign4zd.fsf@yaxenu.org> <87h6jcj6uh.fsf@brilhante.top> <87wms6khgu.fsf@yaxenu.org> <87cytyjzhb.fsf@brilhante.top> <87v87qike6.fsf@example.com> <874jfajvgc.fsf@brilhante.top> <878r4mfjiw.fsf@example.com> <87v87oi0pw.fsf@brilhante.top> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: dont-email.me; posting-host="62ee3c425ded30f299d326f65aa702e0"; logging-data="3905997"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/eNc2x01xpzQ75aLSyrrxNRM6WRbq4/vU=" Cancel-Lock: sha1:1oWgFaKtOJlM3Rz/h8MWl8O4wWE= sha1:kwMwpXd/h8vxK6EVu9s+XfMbfOk= Xref: csiph.com pt.comp.programacao:183 Daniel Cerqueira writes: > Patricia Ferreira writes: > >> Daniel Cerqueira writes: >> >>> Como resolverias este exercício? :-) >> >> (defun find-path (src dst graph) >> (cond >> ((eq src dst) (cons src nil)) >> (t >> (let ((subsolution (find-path/list (neighbors src graph) dst graph))) >> (if subsolution >> (cons src subsolution) >> nil))))) >> >> (defun find-path/list (ns end graph) >> (cond >> ((null ns) nil) >> (t (let ((subsolution (find-path (car ns) end graph))) >> (if subsolution >> subsolution >> (find-path/list (cdr ns) end graph)))))) >> >> CL-USER> (find-path 'A 'G sample-graph) >> (A B E F G) >> CL-USER> (find-path 'C 'D sample-graph) >> (C D) >> CL-USER> (find-path 'C 'A sample-graph) >> NIL >> >> Solucionado. > > Estou (e passei estes últimos dias) a olhar espantado quanto ao > maravilhoso engenho deste algoritmo.... Somos dois. Mas me parece mais adequado observá-lo nesta forma: (defun find-path/list (ns end graph) (cond ((null ns) nil) (t (or (find-path (car ns) end graph) (find-path/list (cdr ns) end graph))))) (defun find-path (src dst graph) (cond ((eq src dst) (cons src nil)) (t (and (find-path/list (neighbors src graph) dst graph) (cons src (find-path/list (neighbors src graph) dst graph)))))) > Isto deve ser o que Stallman quer dizer com "playful cleverness" (que é > o significado real da palavra "hacker"). > > Ainda estou a analisar cuidadosamente os algoritmos. Por serem > regenerativos (acho que é assim o nome), parecem que tem por base ar > puro, isto é, nada em concreto. E funcionam :-) É uma solução > maravilhosa........ Como traduzimos isso? Não apoio ``regenerativo'', não, porque essa palavra sugere uma coisa que foi destruída e então recuperou-se. Já ``generativa'' sugere a geração de alguma coisa, que é o que ocorre em qualquer recursão. Entretanto, a recursão que é obviamente menor que a anterior é chamada de recursão estrutural ou recursão natural. Essa é a impressão que tenho. Nunca achei muito fácil definir recursão natural, estrutura e recursão generativa. >> (*) Epílogo >> >> Esse é o processo ensinado pelo HtDP. Mas não é fácil usar isso. Não >> diria que realmente compreenda esse processo. Os autores anunciam >> também --- especialmente nesses casos de recursão ``generativa'', que é >> como eles chama esse tipo, o código muitas vezes exige um certo insight. >> >> Em retrospectiva, posso fazer as seguintes observações. Observe que pra >> escrever find-path/list, precisamos de find-path. Pra escrever >> find-path, precisamos de find-path/list. Em outras palavras, temos uma >> recursão mútua aí. Isso é comum de ocorrer em árvores. Por exemplo, >> como se faz pra descer um sistema de arquivos? Dessa forma. Esse grafo >> não é nada senão uma árvore. Ele não possui ciclos. Então é preciso >> trabalhar de forma mais sistemática --- observando essas coisas. Como >> diz Frederick P. Brooks, é preciso prestar atenção à estrutura de dados >> primeiro. Os algoritmos em si serão óbvios depois. Essa noção está >> explicitamente explorada pelo HtDP. >> >> ``Representation Is the Essence of Programming. Much more often, >> strategic breakthrough will come from redoing the representation of >> the data or tables. This is where the heart of a program lies. Show >> me your flowcharts and conceal your tables, and I shall continue to be >> mystified. Show me your tables, and I won’t usually need your >> flowcharts; they’ll be obvious.'' -- ``The Mythical Man-Month'', >> expanded anniversary edition (2nd edition), 1995, Addison-Wesley, ISBN >> 0-201-83595-9. Página 102. > > Ótima citação. Parece que o HtDP tem muito a oferecer. É. Não é um livro que deveríamos ignorar, já que não enxergamos essas técnicas com naturalidade. Tem outras coisas que não devemos ignorar, mas fica pra outro momento. >> (*) Novo problema >> >> Encontremos todos os caminhos. Parece moleza. Experimenta. > > Vou demorar algum tempo a resolver este último problema. Primeiro quero > entender melhor a solução que des-te. > > E vou resolver sim esse novo problema ;-) Tem uma solução que julgo mais ou menos óbvia, mas me pergunto se é uma solução natural aí no caso. Vou deixar você trabalhar por aí antes de apresentar. Torço pra que você encontre a solução que eu acho que deveria existir e não consigo encontrar.