编程知识 cdmana.com

Algorithme | hannotta et frog jump Step Problem

Préface

Je crois que beaucoup de petits amis sont comme moi,La méthode de récursion fonctionnelle n'a pas toujours été bien maîtrisée,Je ne sais toujours pas comment utiliser cette méthode de récursion de fonction,Je ne sais pas quand utiliser cette méthode.

Aujourd'hui, je vais jeter un coup d'oeil au sujet classique de la récursion de deux fonctions.

Le problème de hanota et le problème du saut de grenouille.

Conseils chaleureux:L'algorithme d'aujourd'hui estCMise en oeuvre linguistique Oh.

La question de hanota

Insérer la description de l'image ici

Le titre signifie probablement:
C'est tout.3Colonne racinaire,Parmi euxALes colonnes ont des disques creux,Les chaînes de disques sontADans les colonnes,Et le rayon du disque augmente de bas en haut.Un seul disque peut être déplacé à la fois,Et finalement faire toutes les chaînes de disques dansCDans les colonnes et le rayon du disque augmente de bas en haut.

Tout le monde peut y réfléchir.

L'analyse est la suivante::

Commençons par une situation simple,S'il n'y a qu'un seul disque, C'est une question très simple. , Il suffit de mettre le disque directement à partir de ADéplacer versCC'est tout..
Insérer la description de l'image ici

Si vous avez deux disques , Il est facile de penser à la méthode à ce moment - là. , Nous pouvons Numéroter le disque ci - dessus comme suit: 1, Le numéro de disque suivant est 2,Nous devons juste mettre1 Disque n° 1 BAllez.,Encore2 Disque n° 1 CAllez.,Et enfin1 Disque n° 1 CIl suffit de monter.
Insérer la description de l'image ici
QuandA Depuis le début. 3 Sur les disques , Nous pouvons également numéroter de haut en bas 1、2、3,On peut faire ça.:D'abord.1Et2 Trouver un moyen de mettre BAllez.,- Oui.3Mets - le.CAllez.,Et ensuite,1Et2Dans l'ensembleCAllez..
Les étapes spécifiques sont les suivantes:1Mets - le.CMoyenne,2Mets - le.BMoyenne,1Mets - le.BMoyenne,3Mets - le.CMoyenne,1Mets - le.AMoyenne,2Mets - le.CMoyenne,1Mets - le.CMoyenne.

Insérer la description de l'image ici
Insérer la description de l'image ici
La même chose., Quand le disque a 4Oui., On peut aussi commencer. 1、2、3Comme un tout, Mettez ça dans son ensemble. BMoyenne,Et mettre4Mets - le.CMoyenne,- Oui.1、2、3 C'est tout. CMoyenne.Alors...1、2、3 C'est tout. B Dans ce processus , Peut être démonté et transformé en 1Et2 Pour l'ensemble et 3La question de.Voilà., Nous réalisons que les problèmes complexes se transforment en problèmes simples .

Il y a une idée très importante. :Les choses tournent mal..

Et c'est l'idée principale de la récursion .

Les codes spécifiques sont les suivants::

//La question de hanota
// Résoudre par récurrence 
#include<stdio.h>

void hannuota(int n ,char A ,char B,char C)
{
    
	// S'il n'y a qu'une seule couche , Alors il suffit d'aller directement de ADéplacer versCC'est tout.
	if (1 == n) 
	{
    
		printf("%c -> %c\n", A, C);
	}
	else
	{
    
		// S'il y a plus d'une couche , On va commencer par le haut. n-1 Couche à couche BAllez., Encore une fois, AMets - le.CMoyenne
		// Prends le reste. n-1 L'ensemble de BDéplacer versC
		hannuota(n-1,A, C, B);
		printf("%c -> %c\n", A, C);
		hannuota(n - 1, B, A, C);


	}

}

int main()
{
    
	int n = 0;
	// Saisissez le nombre de couches du bloc de Hanovre 
	scanf("%d", &n);

	hannuota(n,'A','B','C');// Appelez la fonction et mettez le nombre de couches nPasser à la fonction,A,B,C Représente trois colonnes .

	return 0;
}

C'est le Code pour résoudre ce problème. , Où le contenu imprimé représente , De droite à gauche ,Par exempleA -> CDeADans les colonnes, Prenez la couche supérieure. ,Mets - le.CMoyenne.

Les gars peuvent tester le Code eux - mêmes. .

Les grenouilles sautent sur les marches

Le problème est à peu près le suivant: : Une Grenouille. , Un pas à la fois ,Vous pouvez aussi sauter deux marches,S'il y en a maintenantnUn pas, Combien de sauts moyens cette grenouille a - t - elle? ?
Insérer la description de l'image ici

Analyse:

Supposons que le nombre de couches soit N,f(N) Combien de sauts de mi - parcours y a - t - il? .

S'il n'y a qu'une seule marche , La petite grenouille n'a qu'un seul saut. , C'est un saut à la fois. .
En ce momentn = 1,f(N) = 1.

S'il y a deux marches , La petite grenouille a deux façons de sauter. , Ou deux sauts à la fois , Une seule fois. ; Ou deux sauts. , Une couche à la fois .
En ce momentn = 2,f(N) = 2.

S'il y a trois marches , Donc nous regardons en arrière du troisième étage , La façon de sauter au troisième étage est de sauter du deuxième étage au troisième étage , Vous pouvez également sauter du premier étage au troisième étage .À ce moment - là, Sauter au troisième niveau est un saut qui peut sauter au premier niveau plus un saut qui peut sauter au deuxième niveau .

La même chose., S'il y a quatre marches , Donc nous regardons en arrière du quatrième étage , La façon de sauter au quatrième étage est de sauter du deuxième étage au quatrième étage , Vous pouvez également sauter du troisième au quatrième étage .À ce moment - là, Sauter au quatrième niveau est un saut qui peut sauter au deuxième niveau plus un saut qui peut sauter au troisième niveau .

En ce moment,f(N) = f(N - 1)+ f(N -2).

Le Code est implémenté comme suit: :

//Les grenouilles sautent sur les marches

#include<stdio.h>

int func(int n)
{
    
	if (1 == n)
		return 1;
	else if (2 == n)
		return 2;
	else
		return func(n - 1) + func(n - 2);

}

int main()
{
    
	int n = 0;
	// Entrez le nombre total de marches 
	scanf("%d", &n);

	int ret = func(n);

	printf("Oui.%d Au niveau des marches ,C'est tout.%d Méthode du saut de graines \n", n, ret);

	return 0;
}

C'est le Code qui résout le problème de la grenouille sautant sur les marches. , Les gars, on peut essayer. ~

Par l'analyse des deux questions ci - dessus , J'espère approfondir la compréhension de la récursion des fonctions par les partenaires. ~

Conclusion

Cette fois, partager,C'est fini ici!

La création n'est pas facile,Si tout le monde pense que c'est bien,,J'espère que ça ira.、Cache - toi.、Fais gaffe.~~

Votre soutien est ma plus grande motivation pour créer!!

En raison de mes capacités limitées,En cas d'erreur,J'espère que la correction!!

S'il y a une meilleure façon ou une meilleure idée,Les commentaires sont les bienvenus~

Insérer la description de l'image ici

版权声明
本文为[Ersansui]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211538505s.html

Scroll to Top