Aucune idée comment résoudre l'exercice SICP 1.11

https://stackoverflow.com/questions/2365993

23-09-2019
|

Question

A f de fonction est définie par la règle selon laquelle si f(n) = n n < 3 et f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) si n > 3. Ecrire une procédure qui calcule f au moyen d'un processus récursif. Ecrire une procédure qui calcule f au moyen d'un processus itératif.

La mise en œuvre est assez simple récursive. Mais je ne pouvais pas comprendre comment le faire de manière itérative. J'ai essayé la comparaison avec l'exemple donné Fibonacci, mais je ne savais pas comment l'utiliser comme une analogie. Donc, j'ai abandonné (honte sur moi) et googlé une explication , et je trouve ceci:

(define (f n)
   (if (< n 3)
       n
       (f-iter 2 1 0 n)))

(define (f-iter a b c count)
   (if (< count 3)
       a
       (f-iter (+ a (* 2 b) (* 3 c))
               a
               b
               (- count 1))))

Après l'avoir lu, je comprends le code et comment il fonctionne. Mais ce que je ne comprends pas le processus nécessaire pour obtenir de la définition récursive de la fonction à ce sujet. Je ne comprends pas comment le code aurait pu se former dans la tête de quelqu'un.

Pouvez-vous expliquer le processus de réflexion nécessaire pour arriver à la solution?

La solution

Vous devez saisir l'état dans certains accumulateurs et mettre à jour l'état à chaque itération.

Si vous avez de l'expérience dans un langage impératif, imaginer écrire une boucle while et des informations de suivi dans les variables lors de chaque itération de la boucle. Quelles sont les variables auriez-vous besoin? Comment qualifieriez-vous les mettre à jour? C'est exactement ce que vous devez faire pour un ensemble itérative (récursif queue) des appels dans le schéma.

En d'autres termes, il pourrait aider à commencer à penser à cela comme une boucle while au lieu d'une définition récursive. Finalement, vous serez assez couramment avec récursives -. Transformations> itératives que vous ne aurez pas besoin d'aide supplémentaire pour commencer

Pour cet exemple, vous devez examiner de près les trois appels de fonction, car il est pas immédiatement clair comment les représenter. Cependant, voici le processus de pensée probable: (en Python pseudo-code pour mettre l'accent sur l'impérativité)

Chaque étape récursive garde la trace de trois choses:

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)

Je besoin de trois morceaux de l'état pour suivre le courant, la dernière et les valeurs de l'avant-dernier f. (C'est f(n-1), f(n-2) and f(n-3).) Appelez-les a, b, c. Je dois mettre à jour ces pièces à l'intérieur de chaque boucle:

for _ in 2..n:
    a = NEWVALUE
    b = a
    c = b
return a

Alors, quel est NEWVALUE? Eh bien, maintenant que nous avons des représentations de f(n-1), f(n-2) and f(n-3), il est juste l'équation récursive:

for _ in 2..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

Maintenant, tout ce qui reste est de comprendre les valeurs initiales de a, b and c. Mais c'est facile, puisque nous savons que f(n) = n if n < 3.

if n < 3: return n
a = 2 # f(n-1) where n = 3
b = 1 # f(n-2)
c = 0 # f(n-3)
# now start off counting at 3
for _ in 3..n:
    a = a + 2 * b + 3 * c
    b = a
    c = b
return a

C'est encore un peu différent du schéma version itérative, mais je l'espère, vous pouvez voir le processus de pensée maintenant.

Autres conseils

Je pense que vous demandez comment on peut découvrir l'algorithme naturellement, en dehors d'un « modèle de conception ».

Il a été utile pour moi de regarder l'expansion du f (n) à chaque valeur n:

f(0) = 0  |
f(1) = 1  | all known values
f(2) = 2  |

f(3) = f(2) + 2f(1) + 3f(0)
f(4) = f(3) + 2f(2) + 3f(1)
f(5) = f(4) + 2f(3) + 3f(2)
f(6) = f(5) + 2f(4) + 3f(3)

regardant de plus près f (3), nous voyons que nous pouvons calculer immédiatement à partir des valeurs connues. Que devons-nous calculer f (4)?

Nous devons calculer au moins f (3) + [le reste]. Mais comme on calcule f (3), on calcule f (2) et f (1), ainsi que nous Happen besoin pour calculer [le reste] de f (4).

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)

Ainsi, pour un nombre quelconque n, je peux démarrer en calculant f (3), et réutiliser les valeurs I utiliser pour calculer f (3) pour calculer f (4) ... et le motif continue ...

f(3) = f(2) + 2f(1) + 3f(0)
            ↘       ↘
f(4) = f(3) + 2f(2) + 3f(1)
            ↘       ↘
f(5) = f(4) + 2f(3) + 3f(2)

Puisque nous allons les réutiliser, permet de leur donner un un nom, b, c. indicée par l'étape nous sommes, et traverser un calcul de f (5):

  Step 1:    f(3) = f(2) + 2f(1) + 3f(0) or f(3) = a₁ + 2b₁ +3c₁

où

a ₁ = f (2) = 2,

b ₁ = f (1) = 1,

c ₁ = 0

puisque f (n) = n, pour n <3.

Ainsi:

f (3) = a ₁ + 2b ₁ + 3c ₁ = 4

  Step 2:  f(4) = f(3) + 2a₁ + 3b₁

a ₂ = f (3) = 4 (calculée ci-dessus à l'étape 1),

b ₂ = a ₁ = f (2) = 2,

c ₂ = b ₁ = f (1) = 1

Ainsi:

f (4) = 4 + 2 * 2 * 1 + 3 = 11

  Step 3:  f(5) = f(4) + 2a₂ + 3b₂

a ₃ = f (4) = 11 (calculé ci-dessus à l'étape 2),

b ₃ = a ₂ = F (3) = 4,

c ₃ = b ₂ = f (2) = 2

Ainsi:

f (5) = 11 + 2 * 4 + 2 = 3 * 25

Tout au long du calcul ci-dessus, nous Capturer l'état dans le calcul précédent et le faire passer à l'étape suivante, particularily:

a _étape = résultat de l'étape - 1

b _étape = a _{étape - 1}

c _étape = b _{étape -1}

Une fois que je voyais cela, alors à venir avec la version itérative était simple.

Depuis le poste vous décrit lié à beaucoup de choses sur la solution, je vais essayer de ne donner des informations complémentaires.

Vous essayez de définir une fonction récursive dans le schéma ici, étant donné une (non-queue) définition récursive.

Le cas de base de la récursion (f (n) = n si n <3) est traitée par deux fonctions. Je ne suis pas sûr de savoir pourquoi l'auteur fait cela; la première fonction pourrait être simplement:

(define (f n)
   (f-iter 2 1 0 n))

La forme générale serait:

(define (f-iter ... n)
   (if (base-case? n)
       base-result
       (f-iter ...)))

Note Je ne remplissez pas les paramètres pour f-iter encore, parce que vous devez d'abord comprendre quel état doit être passé d'une itération à l'autre.

Maintenant, regardons les dépendances de la forme récursive de f (n). Il fait référence f (n - 1), f (n - 2), et f (n - 3), nous avons donc besoin de garder autour de ces valeurs. Et bien sûr, nous avons besoin de la valeur de n lui-même, afin que nous puissions arrêter itérer dessus.

Alors voilà comment vous venez avec l'appel récursif queue: on calcule f (n) à utiliser comme f (n - 1), faites pivoter f (n - 1) à f (n - 2) et f (n - 2) à f (n -. comptage 3), et décrément

Si cela ne fonctionne pas, s'il vous plaît essayer de poser une question plus précise. - il est vraiment difficile de répondre lorsque vous écrivez: « Je ne comprends pas » donné une explication relativement approfondie déjà

Je vais venir à cela dans une approche légèrement différente des autres réponses ici, porté sur la façon de style de codage peut faire le processus de pensée derrière un algorithme comme celui-ci plus facile à comprendre.

Le problème avec approche de Bill , cité dans votre question , est que ce n'est pas immédiatement clair que signifie est véhiculée par les variables d'état, a, b et c. Leurs noms véhiculent aucune information, et le poste de projet de loi ne décrit pas une règle invariable ou autre qu'ils obéissent. Je trouve plus facile à la fois de formuler et de comprendre les algorithmes itératifs si les variables d'état obéissent à certaines règles documentées décrivant leurs relations les uns aux autres.

Dans cet esprit, considérer cette autre formulation du même algorithme exact, qui diffère de Bill qu'en ayant des noms de variables plus significatives pour a, b et c et une variable compteur incrémenter au lieu d'un décrémentation un:

(define (f n)
    (if (< n 3)
        n
        (f-iter n 2 0 1 2)))

(define (f-iter n 
                i 
                f-of-i-minus-2
                f-of-i-minus-1
                f-of-i)
    (if (= i n)
        f-of-i
        (f-iter n
                (+ i 1)
                f-of-i-minus-1
                f-of-i
                (+ f-of-i
                   (* 2 f-of-i-minus-1)
                   (* 3 f-of-i-minus-2)))))

Tout à coup, la justesse de l'algorithme - et le processus de pensée derrière sa création - est simple à voir et à décrire. Pour calculer f(n):

Nous avons une variable compteur i qui commence à 2 et grimpe à n, incrémente de 1 sur chaque appel à f-iter.
A chaque étape le long du chemin, nous gardons une trace de f(i), f(i-1) et f(i-2), ce qui est suffisant pour nous permettre de calculer f(i+1).
Une fois i=n, nous fait.

A f de fonction est définie par la règle selon laquelle f(n) = n, if n<3 et f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), if n > 3. Ecrire une procédure qui calcule f au moyen d'un processus récursif.

est déjà écrit:

f(n) = n,                                  (* if *)  n < 3
     = f(n - 1) + 2f(n - 2) + 3f(n - 3),   (* if *)  n > 3

Croyez-le ou non, il y avait une fois une telle langue . Pour écrire cela dans une autre langue est juste une question de syntaxe. Et par ailleurs, la définition que vous (més) cites il a un bug, qui est maintenant très évident et clair.

Ecrire une procédure qui calcule f au moyen d'un processus itératif.

va avant ( il y a votre explication) plutôt que d'aller de la récursion en arrière dans un premier temps:

f(n)   =  f(n - 1) + 2f(n - 2) + 3f(n - 3) 
       =  a        + 2b        + 3c
f(n+1) =  f(n    ) + 2f(n - 1) + 3f(n - 2)
       =  a'       + 2b'       + 3c'          a' = a+2b+3c, b' = a, c' = b
......

Il décrit ainsi les transitions d'état du problème

 (n, a, b, c)  ->  (n+1, a+2*b+3*c, a, b)

On peut coder comme

g (n, a, b, c) = g (n+1, a+2*b+3*c, a, b)

mais bien sûr, il ne jamais arrêter. Nous devons donc avoir lieu

f n = g (2, 2, 1, 0)
  where
  g (k, a, b, c) = g (k+1, a+2*b+3*c, a, b),    (* if *) k < n
  g (k, a, b, c) = a,                           otherwise

et ce qui est déjà exactement comme le code vous a demandé, à la syntaxe.

En comptant n est plus naturel ici, suite à notre paradigme de « aller de l'avant », mais compte à rebours 0 le code que vous citez n'est bien sûr entièrement équivalent.

Les cas d'angle et possible hors par une erreur sont laissés comme ~~exercice~~ aspects techniques non intéressants.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow