Récursion des bosses 1: formule récursive

Mon grand trésor est le plus mignon. 2022-07-23 17:06:58 阅读数:701

cursiondesbossesformulecursive

1. Formule récursive

Preuve f ( n ) = 5 n + 3 f(n)=5^n+3 f(n)=5n+3Peut être4Effacer
Regardez d'abord quelques détailscase,Pour voir si on peut4Effacer

n n n f ( n ) = 5 n + 3 f(n)=5^n+3 f(n)=5n+3
n = 1 n=1 n=1 f ( 1 ) = 5 1 + 3 = 8 f(1)=5^1+3=8 f(1)=51+3=8
n = 2 n=2 n=2 f ( 2 ) = 5 2 + 3 = 28 f(2)=5^2+3=28 f(2)=52+3=28
n = 3 n=3 n=3 f ( 3 ) = 5 3 + 3 = 128 f(3)=5^3+3=128 f(3)=53+3=128

J'ai regardé plusieurscaseLa découverte peut être faite par4Divisible,Comment prouver l'un ou l'autrenTout va bien. 5 n + 3 5^n+3 5n+3Par4Et la Division??Les données réelles montrent quen=3Quand on peut être4Divisible,Alorsn=4Peut être4Diviser?
f ( 4 ) = 5 4 + 3 = 5 × 5 3 + 3 = 4 × 5 3 + 5 3 + 3 = 4 × 5 3 + f ( 3 ) \begin{aligned} f(4) & =5^4+3\\ & =5\times 5^3+3\\ &=4\times 5^3+5^3+3\\ &=4\times 5^3+f(3) \end{aligned} f(4)=54+3=5×53+3=4×53+53+3=4×53+f(3)

On peut le découvrir. 4 × 5 3 4\times 5^3 4×53Peut être4Effacer,Et f ( 3 ) f(3) f(3)Peut aussi être4Divisible,Donc, f ( 4 ) f(4) f(4)Peut être4Effacer. Plus généralement, il y a des formules récursives
f ( k + 1 ) = 5 k + 1 + 3 = 5 × 5 k + 3 = 4 × 5 k + 5 k + 3 = 4 × 5 k + f ( k ) \begin{aligned} f(k+1) & =5^{k+1}+3\\ & =5\times 5^k+3\\ &=4\times 5^k+5^k+3\\ &=4\times 5^k+f(k) \end{aligned} f(k+1)=5k+1+3=5×5k+3=4×5k+5k+3=4×5k+f(k)

Nous avons écrit la formule récursive ,Vous pouvez voir si f ( k ) f(k) f(k)Peut être4Effacer,Alors f ( k + 1 ) f(k+1) f(k+1) Pour être sûr d'être 4Effacer.De1Début du calcul

  • 1Peut être4Effacer,Il doit y avoir2Peut être4Effacer
  • 2Peut être4Effacer,Il doit y avoir3Peut être4Effacer

Continuez à tour de rôle., C'est - à - dire que n'importe quel entier peut correspondre .

2. Comment résoudre n ! n! n!

Encore une question. ,Comment résoudre n ! n! n!, La question est aussi très simple ,Nous allons directement de1 Commencez à multiplier jusqu'à nJe l'aurai.

res = 1
for i in range(1,n+1):
res *= i

On peut penser à la récursion ici , Il suffit de trouver la formule récursive , Nous avons aussi commencé par le plus simple n=1Début du calcul

n n n f ( n ) = n ! f(n)=n! f(n)=n!
n = 1 n=1 n=1 f ( 1 ) = 1 f(1)=1 f(1)=1
n = 2 n=2 n=2 f ( 2 ) = 1 ∗ 2 f(2)=1*2 f(2)=12
n = 3 n=3 n=3 f ( 3 ) = 1 ∗ 2 ∗ 3 f(3)=1*2*3 f(3)=123
n = 4 n=4 n=4 f ( 4 ) = 1 ∗ 2 ∗ 3 ∗ 4 f(4)=1*2*3*4 f(4)=1234
n = 5 n=5 n=5 f ( 5 ) = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 f(5)=1*2*3*4*5 f(5)=12345

Les formules plus générales de récurrence sont
f ( n ) = f ( n − 1 ) ∗ n f(n)=f(n-1)*n f(n)=f(n1)n

Ce qui veut dire que je veux résoudre f ( n ) f(n) f(n), Alors j'ai juste besoin de mettre f ( n − 1 ) f(n-1) f(n1) C'est tout. , Mais pour résoudre f ( n − 1 ) f(n-1) f(n1),Je dois mettre f ( n − 2 ) f(n-2) f(n2)Résoudre, Parler franchement, c'est continuer à faire des imbéciles .Un simple coup d'oeil f ( 6 ) f(6) f(6)Comment calculer
f ( 6 ) = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 = f ( 5 ) ∗ 6 = f ( 4 ) ∗ 5 ∗ 6 = f ( 3 ) ∗ 4 ∗ 5 ∗ 6 = f ( 2 ) ∗ 3 ∗ 4 ∗ 5 ∗ 6 = f ( 1 ) ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6 = 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ 6   \begin{aligned} f(6)&=1*2*3*4*5*6\\ &=f(5)*6\\ &=f(4)*5*6\\ &=f(3)*4*5*6\\ &=f(2)*3*4*5*6\\ &=f(1)*2*3*4*5*6\\ &=1*2*3*4*5*6\ \end{aligned} f(6)=123456=f(5)6=f(4)56=f(3)456=f(2)3456=f(1)23456=123456 

Honnêtement, c'est comme enlever son pantalon et péter. , Mieux vaut partir directement de 1 Commencez à multiplier directement n,C'estcaseIl n'y a pas de problème,Mais plus tardcase Plus c'est compliqué. , Et plus vous approchez de la récursion . On va d'abord l'écrire Récursivement.

def f(n):
if n == 1:return 1
return f(n-1)*n

3. Comment résoudre x n x^n xn

La question est aussi très simple , Nous pouvons encore le faire en boucle.

def f(x,n):
res = 1
for _ in range(n):
res *= x
return res

Vous pouvez également écrire des formules récursives
f ( n ) = f ( n − 1 ) ∗ x f(n)=f(n-1)*x f(n)=f(n1)x
Écrivez sa méthode récursive

def f(x,n):
if n == 0:
return 1
return f(x,n-1)*x

Encore une foiscase C'est aussi enlever son pantalon et péter , Pourquoi envisager d'utiliser la récursion? ? Parce qu'il y a une solution ingénieuse , Changeons la formule récursive
f ( n ) = { f 2 ( ⌊ n 2 ⌋ ) n % 2 = = 0 f 2 ( ⌊ n 2 ⌋ ) ∗ x n % 2 = = 1 f(n)= \begin{cases} f^2(\lfloor \frac{n}{2}\rfloor) & n\%2==0 \\ f^2(\lfloor \frac{n}{2}\rfloor)*x & n\%2==1 \end{cases} f(n)={ f2(⌊2n⌋)f2(⌊2n⌋)xn%2==0n%2==1
Ce n'est pas ce que j'ai trouvé , Mais j'ai trouvé ça très ingénieux. .Voyons voir. f ( 13 ) f(13) f(13)Comment demander.

f ( 13 ) f(13) f(13) f 2 ( 6 ) ∗ x f^2(6)*x f2(6)x 13 % 2 = 1 13 \% 2=1 13%2=1
f ( 6 ) f(6) f(6) f 2 ( 3 ) f^2(3) f2(3) 6 % 2 = 0 6 \% 2=0 6%2=0
f ( 3 ) f(3) f(3) f 2 ( 1 ) ∗ x f^2(1)*x f2(1)x 3 % 2 = 1 3 \% 2=1 3%2=1
f ( 1 ) f(1) f(1) f 2 ( 0 ) ∗ x f^2(0)*x f2(0)x 1 % 2 = 1 1 \% 2=1 1%2=1
f ( 0 ) f(0) f(0) 1 1 1base

C'est - à - dire, Il suffit de résoudre f ( 1 ) , f ( 3 ) , f ( 6 ) , f ( 13 ) f(1),f(3),f(6),f(13) f(1),f(3),f(6),f(13)Il suffit de résoudre4 Et le résultat sera , Et si le cycle est utilisé , Nous devons résoudre 13Une fois,Un juge de haut rang.
C'estcaseÇa explique un problème, Différentes formules de récurrence , Vous obtenez une complexité de résolution différente .IcicaseMoyenne, La formule récursive conventionnelle réduit l'échelle de résolution du problème étape par étape ,C'est - à - dire obtenir f ( n ) f(n) f(n)Et f ( n − 1 ) f(n-1) f(n1)La relation entre, Et puis à chaque fois 1 Pour réduire l'ampleur du problème , Mais ce qu'il en résulte, c'est que f ( n ) f(n) f(n)Et f ( n / / 2 ) f(n//2) f(n//2)La relation entre,À chaque fois. n / / 2 n//2 n//2 Réduction exponentielle de l'échelle du problème .

4. Série Fibonacci

1、 Questions relatives aux escaliers : Une échelle de nNiveau, Au début, les gens étaient 1Niveau, Si vous ne pouvez traverser qu'un ou deux niveaux à la fois ,Pour aller à lanNiveau,Combien de façons de marcher?
S'il y a5Escalier de marche, On a codé chaque escalier 1,2,3,4,5.Du plus simplecaseÇa commence à compter
Quandn=1Heure,Il n'y a qu'une seule façon
Quandn=2Heure, On peut sauter pas à pas , Vous pouvez aussi sauter directement 1-2,2
Quandn=3Heure, Sautez pas à pas , Ou sautez d'abord sur deux étages , Et monte un autre étage. , Ou peut - être qu'il y en a un et deux. 1-2-3,1-3,2-3

Vous verrez que c'était très compliqué. , Cette question peut être examinée plus loin. .Comme quandn=4Heure, Si vous voulez sauter ,Seulement à partir de2Et3 Deux pas en haut , f ( 2 ) = 2 , f ( 3 ) = 3 f(2)=2,f(3)=3 f(2)=2,f(3)=3,Alors Sautez à4 Il y a des marches f ( 4 ) = f ( 2 ) + f ( 3 ) = 5 f(4)=f(2)+f(3)=5 f(4)=f(2)+f(3)=5Comment?. Une question que j'ai toujours examinée , Pourquoi les deux méthodes s'additionnent - elles? , Pourquoi ne pas multiplier ou combiner d'autres façons? ? J'ai dessiné l'arbre récursif. , La valeur dans chaque cercle est le nom de cette étape ,0 Indique le sol , Chaque chemin est une façon de sauter . Par exemple, le chemin le plus à gauche 0-1-2-4-5,

  • Sautez d'abord.1Pas à pas1Allez - y.,
  • Et sautez. 1Pas à pas2Allez - y.,
  • Et sautez. 2 Le Ministère a sauté 4Allez - y.,
  • Enfin, sautez. 1 Sautez vers 5Allez - y..

Vous pouvez voir le noeud supérieur 4Oui.5Chemins,Noeud3Oui.3Chemins,Donc les noeuds5Au total.3+5=8Chemins, Donc C'est la relation Additive
Insérer la description de l'image ici
Selon l'analyse ci - dessus, il est facile d'écrire une formule récursive
f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2)

Peut être facilement écrit Récursivement

def f(n):
if n == 1:return 1
if n == 2:return 2
return f(n-1)+f(n-2)

Si vous utilisez la récursion ,Vous trouverez un problème, C'est que beaucoup de noeuds sont comptés à plusieurs reprises. , Considérez donc l'utilisation directe du cycle pour résoudre

def f(n):
fn1 = 1
fn2 = 2
fn = 0
for i in range(3,n+1):
fn = fn1+fn2
fn2 = fn1
fn1 = fn

2、 Problèmes de couverture rectangulaire :Avec1×2 Petite couverture rectangulaire de 2×nGrand rectangle de,Combien de méthodes y a - t - il au total??
C'est le même problème que Fibonacci. , C'est aussi très facile à comprendre .Sin=5, Si vous voulez remplir tout ,Il y a deux façons, L'un d'eux est de mettre en place 4 Terminé. , Un dernier. , Ou juste avant 3 Terminé. , Il en faut deux.
Insérer la description de l'image ici

5. Petit résumé

Le problème de récurrence ci - dessus , L'essence est de réduire l'ampleur du problème. ,Exigences f ( n ) f(n) f(n), Trouvez d'abord le plus petit f ( n − 1 ) , f ( n / / 2 ) f(n-1),f(n//2) f(n1),f(n//2)Attendez un peu!,Alors..., Le plus important est d'analyser le problème pour obtenir une formule récursive .

Copyright:Cet article est[Mon grand trésor est le plus mignon.]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2022/204/202207231359540429.html