递推算法经典例题详解
递推算法经典例题详解
递推在C语言学习中是一个十分关键的思想，我们最初的递推可以源于数学的全排列，递推规律（数列）甚至脑筋急转弯（高考题中也有递推的数列题（emm，概率和统计那块（全国卷为例））），而这里整理了一些递推 经典题，目的是帮助读者理清递推的思路。
经典例题1：爬楼梯
题目描述
欧老师爬楼梯，他可以每次走 1 级或者 3 级，输入楼梯的级数，求不同的走法数。
输入格式
输入包含若干行，每行包含一个正整数 N，代表楼梯级数，1<=N<=30。
输出格式
不同的走法数，每一行输入对应一行输出。
样例
输入
1
3
5
输出
1
2
4
解题思路
这道题的递推式为 F(n) = F(n-1) + F(n-3)。因为到达第 n 级楼梯有两种方式：从第 n-1 级跨一步，或从第 n-3 级跨三步。
代码实现
//递推爬楼梯
#include<stdio.h>
int oy(int n)
{
if(n==1 || n==2) // 特殊情况处理
return 1;
if(n==3)
return 2;
else
return oy(n-1) + oy(n-3);
}
int main()
{
int a[1000], i=0;
while(scanf("%d", &a[i]) != EOF)
{
a[i] = oy(a[i]);
i++;
}
for(int j=0; j<i; j++)
{
printf("%d\n", a[j]);
}
return 0;
}
例题2：全排列
题目描述
输入一个数 N，求 1 到 N 的全排列。
输入格式
输入一个 N，N<12。
输出格式
输出 N 的全排列，每个数字占 4 个位置。
样例
输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
解题思路
使用深度优先搜索（DFS）算法来生成全排列。DFS是一种常见的图搜索算法，从根节点开始，沿着一条路径一直搜索下去，直到到达最深的节点或无法继续搜索为止，然后回溯到上一个节点，继续搜索其他路径，直到所有节点都被访问过为止。
代码实现
#include<stdio.h>
int p[10000]={0}, l[1000]={0};
int k;
void oy(int n)
{
if(n==k+1)
{
for(int i=1; i<=k; i++)
printf("%d ", p[i]);
printf("\n");
return;
}
for(int i=1; i<=k; i++)
{
if(l[i]==0)
{
p[n] = i;
l[i] = 1;
oy(n+1);
l[i] = 0;
}
}
return;
}
int main()
{
scanf("%d", &k);
oy(1);
return 0;
}
例题三：成群的奶牛
题目描述
现有 n 只奶牛在一片宽广的草地上吃草，草地有一些小路，可以去到其他草场。这些小路都是单向的。每个草场有 2 条小路可以去到其他草场，但是只有 1 条小路可以到达这个草场。奶牛从其中一个草场开始，每遇到一个草场，奶牛们会精确地分成两群，这两群奶牛数量之差的绝对值为 k，分别从两条路去到下一个草场（如果数量不满足要求就不会再分裂）。当来到一个草场而该奶牛群已不可再分割时，奶牛们就会停下来在这里吃草。现给出 n 和 k，求奶牛最终会分成多少群。
输入格式
一行，分别是 n 和 k，用空格隔开。
输出格式
一个正整数，表示最终奶牛会分成多少群。
样例
输入
50 4
输出
2
数据规模与约定
0<n≤10000
0<k<n
解题思路
每次分裂后的两个数为 (n-k)/2 和 (n+k)/2，不满足的条件要么现在这个数比 k 小，要么分解后是分数（这个怎么去表示？（分数用相加不等于原数表示））。
代码实现
//成群的奶牛
#include<stdio.h>
int a, b;
int o=1;
void oy(int n)
{
int p=(n-b)/2;
int l=(n+b)/2;
if(p+l != n)
return;
o++;
if(p > b)
oy(p);
if(l > b)
oy(l);
}
int main()
{
scanf("%d %d", &a, &b);
oy(a);
printf("%d", o);
return 0;
}
例四：初级快速幂训练
题目描述
请你计算 a 的 n 次方是多少，由于答案可能会很大，所以你只需要输出答案和 b 取余数的结果。
输入格式
多组输入，EOF 结束。每组一行，输入三个非负整数分别表示 a, n, b，(a, b, n 均在 int 范围内)。
输出格式
对于每一组输入，在新的一行输出结果。
样例
输入
2 10 10
3 3 5
输出
4
2
解题思路
使用二分法递归快速幂算法，本质上是分治算法。
代码实现
//初级快速幂（分治或者递归思想）
#include<bits/stdc++.h>
using namespace std;
long long oy(long long a, long long n, long long b)
{
if (n <= 1)
{
if (n == 0)
return 1 % b;
else
return a % b;
}
long long half = n / 2;
long long tem = oy(a, half, b);
if (n % 2 == 0)
{
return (tem * tem) % b;
}
else
{
return (tem * oy(a, half + 1, b)) % b;
}
}
int main()
{
long long int a, n, b, i=0, o[100000];
while (scanf("%lld %lld %lld", &a, &n, &b) != EOF)
{
o[i] = oy(a, n, b);
i++;
}
for(int j=0; j<i; j++)
{
printf("%d\n", o[j]);
}
return 0;
}
例五：分型三角形
题目描述
有一些少数民族的图腾是分形三角形，你能画出来吗？
输入格式
一个整数 n，表示图腾的大小。
输出格式
若干行，表示图腾的样子。
样例
输入
3
输出
/\
/__\
/\ /\
/__\/__\
/\ /\
/__\ /__\
/\ /\ /\ /\
/__\/__\/__\/__\
数据规模与约定
1≤n≤10
解题思路
分型三角形的绘制可以通过递归实现，每次将一个三角形分为四个更小的三角形。
代码实现
#include <stdio.h>
#include <string.h>
void draw_triangle(int n, int row, int col, char triangle[20][40])
{
if (n == 0)
return;
// Draw the top triangle
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 2 * n - 1; j++)
{
if (j >= col - i && j <= col + i)
triangle[row + i][col - i + j] = (j % 2 == 0) ? '/' : '\\';
}
}
// Draw the bottom left triangle
draw_triangle(n - 1, row + n, col - n, triangle);
// Draw the bottom right triangle
draw_triangle(n - 1, row + n, col + n, triangle);
}
int main()
{
int n;
scanf("%d", &n);
char triangle[20][40];
memset(triangle, ' ', sizeof(triangle));
draw_triangle(n, 0, 2 * n - 1, triangle);
for (int i = 0; i < 2 * n - 1; i++)
{
for (int j = 0; j < 4 * n - 3; j++)
{
printf("%c", triangle[i][j]);
}
printf("\n");
}
return 0;
}
例六：超级楼梯
题目描述
有一楼梯共 M 级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第 M 级，共有多少种走法？
输入格式
输入数据首先包含一个整数 N，表示测试实例的个数，然后是 N 行数据，每行包含一个整数 M（1<=M<=40），表示楼梯的级数。
输出格式
对于每个测试实例，请输出不同走法的数量。
样例
输入
2
2
3
输出
1
2
解题思路
这道题的递推式为 F(n) = F(n-1) + F(n-2)。因为到达第 n 级楼梯有两种方式：从第 n-1 级跨一步，或从第 n-2 级跨两步。
代码实现
//超级楼梯
#include<stdio.h>
int oy(int n)
{
if(n==1)
return 1;
if(n==2)
return 1;
else
return oy(n-1) + oy(n-2);
}
int main()
{
int i, a, b[10000];
scanf("%d", &a);
for(i=0; i<a; i++)
{
scanf("%d", &b[i]);
b[i] = oy(b[i]);
}
for(int j=0; j<i; j++)
{
printf("%d\n", b[j]);
}
return 0;
}