quinta-feira, 18 de fevereiro de 2010

SICP - Exercício 1.12 - Triângulo de Pascal

O padrão de números abaixo é denominado triângulo de Pascal.
    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1
   ...

Os números nas "arestas" do triângulo são todos 1, e cada número dentro do triângulo é a soma dois dois números sobre ele. Escreva um procedure que compute elementos do triângulo de pascal por meio de um processo recursivo.

Solução: Veja que o enunciado dá todas as dicas para a elaboração de um processo recursivo. O que faremos é uma simples tradução das propriedades enunciadas. Primeiramente, vamos definir que (pascal n p) representa o número na linha n e na coluna p do triângulo. Ambas as contagens começam do zero. Com essa convenção, (pascal n p) é igual à combinação de n elementos, tomados p a p.

Definida a nossa convenção, é só traduzir as regras. Os números das "arestas" são aqueles na primeira coluna ou na última coluna. Portanto, são os que obedecem à condição (or (= p 0) (= p n)). Para os demais, temos (em notação matemática, pascal(n,p) = pascal(n - 1, p - 1) + pascal(n - 1, p). Temos, portanto, o código:

Lembrando que, no "mundo real", deveríamos checar se os argumentos para a função pascal fazem sentido.

2 comentários:

  1. Fala Berabinha. Eu interpretei o enunciado de maneira diferente. Achei que o autor queria afunção f(n), onde n seria apenas a ordem do elemento desejado respeitando o triângulo de Pascal. Ou seja, o triângulo fornecido por ele seria apenas para explicar como a série funciona. Aí ficou um pouco mais suga pq eu tinha que calcular x e y dado o n.

    (define (pascal-triangle n)
    (define (pascal-iter x y)
    (cond ((or (<= x 0) (= x y)) 1)
    ((> x y) (pascal-iter (- x y 1) (+ y 1)))
    (else (+
    (pascal-iter (- x 1) (- y 1))
    (pascal-iter x (- y 1))))))
    (pascal-iter (- n 1) 0))

    Obviamente que se fosse levar em conta que em geral usamos o triângulo para calcular os coefiecientes do binômio de Newton, aí seria muito mais bizu trabalhar em termos de linha e colunas =D

    Quem diria eu estar metendo Gaga parnasiano em um domingo, ainda mais em LISP!

    Vlw pelas dicas.

    ResponderExcluir
    Respostas
    1. É... Realmente fica mais difícil mesmo...
      Agora, estou impressionado com o seu gagá de fim de semana. Eu to tirando uns dias pra descansar... To aqui em Uberaba, meu Raspberry Pi finalmente em mãos e eu nem mexi no bichinho... Depois do Natal acho que a boa vontade volta. Para você que está com disposição de sobra, ótimos estudos.

      Excluir