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: Mon, 15 Jan 2024 14:00:56 -0300 Organization: A noiseless patient Spider Lines: 99 Message-ID: <87bk9mzg3b.fsf@example.com> References: <87sf37ajzn.fsf@example.com> <87y1cy8z8u.fsf@example.com> <87v881z5qs.fsf@brilhante.top> <87a5pd6kuv.fsf@yaxenu.org> <8734v3ztrz.fsf@brilhante.top> <877cke4ny3.fsf@example.com> <87y1cujtsk.fsf@brilhante.top> <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> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Info: dont-email.me; posting-host="9ec70f55fb8ac0a0db61477606cc8189"; logging-data="1064880"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1930CI9MNWb3QaIEcvCSH62J6LyZfhBWxo=" Cancel-Lock: sha1:a2Ree9LZeLC08mcmAejSHYa4Go4= sha1:7CHr2RuUUcTex+2hrvN2kVelFC8= Xref: csiph.com pt.comp.programacao:165 Daniel Cerqueira writes: > Patricia Ferreira writes: > >>> Patricia Ferreira writes: >>> >>>> Daniel Cerqueira writes: >>>> >>>>> Patricia Ferreira 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.)