Classical questions of function recursion

1、 The hanotta problem

The game is on a copper device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate ( Here's the picture ). The goal of the game : hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules : Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .

analysis : For such a question , No one can write every step of moving the plate directly , But we can use the following methods to solve . Set the number of moving plates to n, To put this n A plate from A The rod moves to C rod , You can do the following three steps :

(1) With C The rod is the intermediary , from A Rod will 1 to n-1 Disk No. moved to B rod ;

(2) take A The remaining third in the rod n Disk No. moved to C rod ;

(3) With A The rod is the intermediary ; from B Rod will 1 to n-1 Disk No. moved to C rod . 

------------------------------------------------------------------------------------

Ideas ： There is an intermediary , With the help of the target rod , First the （n-1） Put a plate on the intermediary , Put another plate on the target pole ;

namely ： that （n-1） A plate is a recursive object .

-------------------------------------------------------------------------------------

Code ：

// The hanotta problem --  Find how many times you need to move 
//n-1  null ： Move （2^(n-1)）-1  Time 

#include<stdio.h>
#include<math.h>

int ToH(int n)
{
	if (n > 0)
	{
		return (1 + 2 * ToH(n - 1));
	}
	return (pow(2.0,(double)(n-1.0))-1);
}
int main()
{
	int n = 0;
	printf(" Please enter the number of plates n：\n");
	scanf("%d", &n);
	// Hanoi 
	int ret = ToH(n);
	printf("ToH(%d)=%d\n", n, ret);
	return 0;
}

-------------------------------------------------------------------------------------

2、 The problem of frog jumping on the steps

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 level . Ask the frog to jump on one n How many jumps are there in the steps （ Different results are calculated according to different order ）.

----------------------------------------------------------------------------

Ideas ： It is also divided into the first step and the rest （n-1） Step problem , Repeat the same work --- recursive

 

-----------------------------------------------------------------------------

Code ：

// The problem of frog jumping on the steps ： Find the number of methods 
// except 0 1 2 Outside the steps are all Fibonacci sequences 

#include<stdio.h>
int Stage(int n)
{
	if (0 == n)
	{
		return 0;
	}
	else if (1 == n)
	{
		return 1;
	}
	else if (2 == n)
	{
		return 2;
	}
	else
	{
		return (Stage(n - 1) + Stage(n - 2));
	}
}
int main()
{
	int n = 0;
	printf(" Please enter the number of steps n：\n");
	scanf("%d", &n);
	// recursive 
	int ret = Stage(n);
	printf("Kind(%d)=%d\n", n, ret);
	return 0;
}

---------------------- All a person's anger comes from the pain of his incompetence .-------------------------