算法竞赛--递归

发表于 更新于 分类于 阅读次数：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

递归边界:返回最简单底层的结果。

递归式:减少数据规模,并向下一层递归。

1.计算N的阶乘

样例输入:

1
3

样例输出:

1
6

递归边界:

1
F(0)=1;

递归式:

1
F(n)=F(n-1)*n;

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int F(int n)
{
	if(n==0)
		return 1;
	else
		return F(n-1)*n;
}
int main()
{
	int N;
	scanf("%d",&N);
	printf("%d\n",F(N));
	return 0;
}

2.求Fibonacci数列的第n项。

样例输入:

1
4

样例输出:

1
5

递归边界:

1
2
ff(0)=1;
ff(1)=1;

递归式:

1
ff(n)=ff(n-1)+ff(n-2);

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int ff(int N)
{
	if(N==0||N==1)
		return 1;
	else
		return ff(N-1)+ff(N-2);
}
int main()
{
	int N;
	scanf("%d",&N);
	printf("%d",ff(N));
	return 0;
}

3.全排列

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
bool H[10]={false};
int P[10],n;
void g(int index)
{
	if(index==n+1)
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d",P[i]);
		}
		printf("\n");
		return;
	}
	for(int x=1;x<=n;x++)
	{
		if(H[x]==false)
		{
			P[index]=x;
			H[x]=true;
			g(index+1);
			H[x]=false;
		}
	}
}
int main()
{
	n=3;
	g(1);
	return 0;
}

4.吃糖果

名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。

妈妈告诉名名每天可以吃一块或者两块巧克力。

假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。

例如：

如果N=1，则名名第1天就吃掉它，共有1种方案；

如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；

如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；

如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。

现在给定N，请你写程序求出名名吃巧克力的方案数目。

输入信息:

输入只有1行，即整数N。

输出信息:

可能有多组测试数据，对于每组数据，
输出只有1行，即名名吃巧克力的方案数。

样例输入:

1
2
3
1
2
4

样例输出:

1
2
3
1
2
5

思路:该题与斐波那切数列类似，第一天吃一颗，第二天就剩N-1颗，第一天吃两颗，第二天就剩N-2颗。ff(n)=ff(n-1)+ff(n-2);

注意:多组输入的判断，while(scanf(“%d”,&n))输出超限0。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
int ff(int n)
{
	if(n==0||n==1)
		return 1;
	else
		return ff(n-1)+ff(n-2);
}
int main()
{
	int n;
	while(scanf("%d",&n)==1)
		printf("%d\n",ff(n));
	return 0;
}

5.数列

编写一个求斐波那契数列的递归函数，输入n 值，使用该递归函数，输出如下图形（参见样例）。

输入信息:

输入第一行为样例数m，接下来有m行每行一个整数n，n不超过10。

输出信息:

对应每个样例输出要求的图形(参见样例格式)。
输出只有1行，即名名吃巧克力的方案数。

样例输入:

1
2
1
6

样例输出:

1
2
3
4
5
6
          0
        0 1 1
      0 1 1 2 3
    0 1 1 2 3 5 8
  0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34 55

思路:该题利用斐波那切数列解题，输出m行数，每行从第0项开始，总共2m-1个数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
int ff(int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else
		return ff(n-1)+ff(n-2);
}
int main()
{
	int n,m;
	while(scanf("%d",&n)==1)		//测试样例数
	{
		for(int k=0;k<n;k++)
		{
			scanf("%d",&m);		//输入m
			for(int i=1;i<=m;i++) 	//输出m行
			{
				for(int j=0;j<2*(m-i);j++)//输出空格
					printf(" ");
				for(int j=0;j<2*i-1;j++)	//输出数字
				{
					printf("%d",ff(j));
					if(j<2*(i-1))
						printf(" ");	
				}
				printf("\n");
			}
		}	
	}
	return 0;
}

6.神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入信息:

输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出信息:

输出不同的选择物品的方式的数目。

样例输入:

1
2
3
4
5
6
7
2
12
28
3
21
10
5

样例输出:

1
2
1
0

思路:从0开始,思路是用40减去good[0]，然后用余数继续与后面数组中的元素相减，看结果是否为0，若为0，表示这样排列满足条件，count++。若不为0，则继续往下走，直到余数小于0或者数组中的数已经全部读完，这样一次查找就完成了，接着需要回退到上一步去继续寻找下一个包含good[0]的可能组合。就比如进行到40-good[0]-good[1]时发现余数为0满足条件，count+1，然后回退到40-good[0]，跳过good[1]，去检查40-good[0]-good[2]是否满足条件，如此往复，直到检查到40-good[0]-good[n-1]为止

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
int good[25];
int count,r=40,n;
void g(int index)
{
	if(r<0)
		return;
	else if(r==0)
	{
		count++;
		return;
	}
	if(index==n)
		return;
	for(int x=index;x<n;x++)
	{
		r=r-good[x];
		g(x+1);
		r=r+good[x];
	}	
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		count=0;
		for(int i=0;i<n;i++)
			scanf("%d",&good[i]);	//输入物体的体积
		g(0);						//递归开始
		printf("%d\n",count);
	}
	return 0;
}
小礼物走一个哟
0%