Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pt.comp.programacao > #169
| From | Patricia Ferreira <pferreira@example.com> |
|---|---|
| Newsgroups | pt.comp.programacao |
| Subject | Re: Lisp, um mapa de trajeto |
| Date | 2024-01-16 22:06 -0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <87r0ign4zd.fsf@yaxenu.org> (permalink) |
| References | (16 earlier) <87o7dn3636.fsf@brilhante.top> <874jff1dbm.fsf@yaxenu.org> <87a5p638mt.fsf@brilhante.top> <87bk9mzg3b.fsf@example.com> <87bk9l9mki.fsf@brilhante.top> |
Daniel Cerqueira <dan.list@brilhante.top> writes: > Patricia Ferreira <pferreira@example.com> writes: > >> Daniel Cerqueira <dan.list@brilhante.top> writes: >> >>> Patricia Ferreira <pferreira@example.com> writes: >>> >>>>> Patricia Ferreira <pferreira@example.com> writes: >>>>> >>>>>> Daniel Cerqueira <dan.list@brilhante.top> writes: >>>>>> >>>>>>> Patricia Ferreira <pferreira@example.com> writes: >>>>>>> >>>>>>>> Muito bom! Agora acreditamos em falta de atenção no anterior. Um nome >>>>>>>> melhor pra esse procedimento seria /merge/. Com ele você implementa o >>>>>>>> seu /ordenar/ --- que se chama /merge sort/, um respeitoso algoritmo. >>>>>>>> >>>>>>>> (*) Exercício 3 >>>>>>>> >>>>>>>> Considere a lista abaixo como uma representação pra um grafo >>>>>>>> direcionado. >>>>>>>> >>>>>>>> (defparameter sample-graph >>>>>>>> '((A (B E)) >>>>>>>> (B (E F)) >>>>>>>> (C (D)) >>>>>>>> (D ()) >>>>>>>> (E (C F)) >>>>>>>> (F (D G)) >>>>>>>> (G ()))) >>>>>>>> >>>>>>>> Os vertices são o que você espera --- A, B, C, ..., G. A lista >>>>>>>> associada a um vértice /v/ representa os outros vértices a que /v/ tem >>>>>>>> acesso. Por exemplo, A tem aresta pra B, mas B não tem aresta pra A. >>>>>>>> Escreva um procedimento chamado /find-path/ tal que >>>>>>>> >>>>>>>> (find-path 'C 'D sample-graph) produza '(C D) >>>>>>>> (find-path 'E 'D sample-graph) produza '((E F D) (E C D)) >>>>>>>> (find-path 'C 'G sample-graph) produza nil >>>>>>>> >>>>>>>> Quando terminar de fazer, veja o tempo que levou. >>>>>>> >>>>>>> É para resolver usando Common Lisp, ou o Lisp simples (como do último >>>>>>> exercício)? Tens de me dizer isso. >>>>>>> >>>>>>> Também é para criar apenas uma função? Recursiva? Ou posso usar >>>>>>> quaisquer outras funções? >>>>>> >>>>>> Como primeira versão, use apenas recursão, cons, cond, car, cdr e essas >>>>>> coisas. Vamos dar uma olhada no algoritmo primeiro de uma forma pura. >>> >>> Está-me a faltar uma mensagem. Não a encontro. Vou responder assim, aqui. >>> >>> Se é para apenas usar uma função recursiva, com as funções primitivas de >>> Lisp, parece-me mais díficil. >> >> É mais difícil. (Estamos fazendo um diagnóstico.) >> >>> Principalmente porque: >>> >>> (find-path 'C 'D sample-graph) produz '(C D) e não '((C D)) >> >> Pode assumir que seja '((C D)) porque é trivial transformá-la pra >> definição do problema. (O objetivo do exercício não está aí.) (Um >> segundo procedimento colapsa listas unitárias pro /car/ delas.) >> >>> (find-path 'E 'D sample-graph) produz '((E F D) (E C D)) e não >>> '((E C D) (E F D)) >> >> Okay, façamos uma simplificação então. Faça com que find-path encontre >> apenas um caminho entre os vértices, ou seja, ou ela produz (E F D) ou >> ela produz (E C D) para /sample-graph/. >> >> Mais fácil assim. >> >>> Outra pergunta: >>> O segundo argumento de /find-path/ tem de sempre ter os vértices como >>> NIL? Para este grafo, só o 'D e o 'G podem ficar no segundo argumento? >> >> O segundo argumento é um vértice de destino. Qualquer destino pode >> entrar lá. Se o caminho não existir, /find-path/ produz nil. (Se o >> destino nem existir, pode retornar nil também, mas pode assumir que >> origem e destino sempre existem.) >> >>> Consegues dar mais exemplos, para além de: >>> >>> (find-path 'C 'D sample-graph) produza '(C D) >>> (find-path 'E 'D sample-graph) produza '((E F D) (E C D)) >>> (find-path 'C 'G sample-graph) produza nil >>> >>> ? >> >> (find-path 'C 'D sample-graph) produza '(C D) >> (find-path 'E 'D sample-graph) produza (or '(E F D) '(E C D)) >> (find-path 'C 'G sample-graph) produza nil >> (find-path 'A 'D sample-graph) produza >> (or '(A B F G) (A B E F G) (A E F G)) >> (find-path 'A 'Z sample-graph) produza nil >> (find-path 'Z 'B sample-graph) produza nil >> >> Pode assumir que origem e destino sempre existem. (Ignore exemplos como >> os dois últimos, A -> Z e Z -> B.) > > Mesmo assim. Não estou a ver maneira de isso ser possível, dado eu só > poder fazer uma função, com o cond, car, cdr, eq, atom, cons, etc.. Você pode (e deve) fazer várias funções. > Não consigo fazer tal função. Não é muito fácil. Isso é ensinado no HtDP. O propósito dos exercícios é diagnosticar isso. Devemos ler o livro ou não? Parece que devemos. Você pode olhar a solução deles, capítulo 29, parte V. Mas não creio que você aprecie muito a apresentação deles se você não estiver bem treinado no método de raciocínio que eles usam. Uma sugestão é a gente voltar um pouco e trabalhar num exercício mais fácil. Por exemplo, capítulo 19, parte IV, exercício 313 --- tendo lido o capítulo 19 todo, o que não demora. Está bem relacionado com /find-path/, mas é mais fácil. O próprio avisa isso no capítulo 29. Ou então insistimos em /find-path/, o que não recomendo. Diga-me o que pensas.
Back to pt.comp.programacao | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-08 10:44 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-08 13:05 -0300
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline dirk@orka.cs.kuleuven.be. (Dirk Craeynest) - 2024-01-09 09:53 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Patricia Ferreira <pferreira@example.com> - 2024-01-09 09:31 -0300
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-10 13:18 +0000
Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline Ninguém <usenet@rasparta.org> - 2024-01-10 15:18 +0000
fiat lux! (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:57 -0300
Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:42 +0000
Re: fiat lux! Ninguém <usenet@rasparta.org> - 2024-01-11 22:21 +0000
Re: fiat lux! Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 14:23 +0000
Re: fiat lux! "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-16 14:05 +0000
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-16 11:45 -0300
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:24 -0300
Re: fiat lux! Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:02 -0300
Lisp (was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-10 16:00 +0000
Re: Lisp Patricia Ferreira <pferreira@example.com> - 2024-01-10 17:00 -0300
Re: Lisp Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 16:30 +0000
Lisp, um mapa de trajeto (Was: Re: Ada-Europe conference - 31 Jan Journal Track Extended Deadline) Patricia Ferreira <pferreira@example.com> - 2024-01-10 16:37 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-11 17:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 11:37 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 18:22 +0000
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-12 18:51 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:29 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:27 -0300
E-mail (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 10:34 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 17:02 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:07 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:39 -0300
Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:51 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:27 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:21 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:24 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:23 +0000
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:33 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 17:01 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-12 22:26 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-12 20:50 -0300
Re: Lisp, um mapa de trajeto "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-13 11:04 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 09:46 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-13 13:32 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-13 16:59 -0300
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 10:11 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:01 -0300
Re: Lisp, um mapa de trajeto Ninguém <usenet@rasparta.org> - 2024-01-14 14:18 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 11:33 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 12:02 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-14 10:51 -0300
Encriptação (was: Re: Lisp, um mapa de trajeto) "Nuno Silva" <nunojsilva@invalid.invalid> - 2024-01-14 15:44 +0000
Re: Encriptação Patricia Ferreira <pferreira@example.com> - 2024-01-14 13:30 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-14 22:25 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 00:25 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-15 15:43 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-15 14:00 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-16 18:10 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-16 22:06 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 14:10 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 18:03 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:47 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-17 15:51 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 08:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 17:57 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 15:09 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-18 19:24 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-18 17:56 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-19 10:39 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-19 08:38 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-20 13:38 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-01-20 11:42 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-01-23 17:29 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 11:19 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 09:29 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 13:14 +0000
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-05 15:43 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-05 18:50 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 10:55 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-06 18:13 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-06 11:11 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 14:52 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-03 18:09 +0000
Re: Lisp, um mapa de trajeto Patricia Ferreira <pferreira@example.com> - 2024-02-03 20:48 -0300
Re: Lisp, um mapa de trajeto Daniel Cerqueira <dan.list@brilhante.top> - 2024-02-04 11:42 +0000
csiph-web