本文主要是介绍第1章递归函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第1章 递归函数的设计技巧
数学归纳法
递归函数设计三个重要部分
递归求阶乘
数学(结构)归纳法
- 验证P(1)成立
- 证明如果P(k)成立，那么P(k+1)成立
- 联合Step1和Step2,证明P(1)->P(n)成立
递归函数
- 给递归函数一个明确的语义
- 实现边界条件时的程序逻辑（p(1)）
- 假设递归函数调用返回结果是正确的，实现本层函数逻辑 ( p(k) )
//递归 n的阶乘
//1.acm_1_1_diGui_test6代表n的阶乘的结果
int acm_1_1_diGui_test(int n){if(n==1)return 1; //边界条件 n==1return acm_1_1_diGui_test(n-1)*n; //利用f(n-1)结果计算f(n)的值
}//猴子吃桃
//猴子吃n天桃子的数量
int acm_1_1_diGui_test2(int n){if(n==1)return 1;return (acm_1_1_diGui_test2(n-1)+1)*2;
}
例题
一个小球，掉落到一连串弹簧板上，每个弹簧板回弹a[i]个距离，问小球弹 几次会弹出弹簧板串
5
2 2 3 1 2
2表示会弹2个距离，所以是2+3==5 ，
到三会弹3个距离,5+3=8>5
所以弹了两次
- f(i)小球从i位置开始被弹出的次数
- i>=n 时结束
- f(i)=f(i+a[i])+1
i=0
res=0
n=int(input())
ns=list(map(int,input().split(" ")))
while(i<n):i+=ns[i]res+=1
print(res)
例题：
输出n的指数型枚举
in:
3
out:
1
1 2
1 2 3
1 3
2
2 3
3分析：
f(i,j,n) ,i表示第i个位置，j表示最小，n表示最大
边界条件是j>n ,最小值比最大值大的时候
- 如何按照字典序输出？
从小到大进行枚举每个位置的数字就是字典序
- 如何保证每个位置数字都大于前面的数字？
传入一个量，标记当前位置的最小值
每个枚举的过程都传入另一个数字，这个数字他标记了当前位置最小可以选取的数字
- 如何输出？
int arr[10];
def fn(int i,int j,int n){if (j>n) return;for(int k=j;k<=n;k++){ //j代表最小值，只能输出从j到narr[i]=k;//i代表第几个位置， 其中arr[j]一定比arr[i]前面的都大print_one_result(i); //输出前i个，i表示到了第几个位置fn(i+1,j+1,n); }
}//输出从arr数组从0到n的元素
void print_one_result(int n){cout << "n" << n << endl;for(int i=0;i<=n;i++){if(i){cout << " ";}cout << arr[i];}cout << endl;
}
int n;
cin >> n; //对n进行指数枚举
acm_1_1_diGui_fn3(0,1,n);
| f(n)的n==i | k | arr | j | i |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 0 |
| 1 | 2 | 1 2 | 2 | 1 |
| 2 | 3 | 1 2 3 | 3 | 2 |
| 1 | 3 | 1 3 | 2 | 1 |
| 0 | 2 | 2 | 1 | 0 |
| 1 | 3 | 2 3 | 3 | 1 |
| 0 | 3 | 3 | 1 | 0 |
结论：
i==n为输出的个数
k为最后一个元素值
结束条件：j用来限定输出最小值，j永远不超过3
因为是递归，所以看k的值可以看出来属于哪一层递归
1
2 3
3
2
3
3
arr=[0]*10
def print_one_result(n):for i in range(0,n+1):if i:print(" ",end="")print(arr[i],end="")print()def fn3(i,j,n):if(j>n): return;for k in range(j,n+1):arr[i]=kprint_one_result(i)fn3(i+1,k+1,n);def fn3_Test():n=int(input())fn3(0,1,n)
fn3_Test()
例题：
递归实现组合型枚举
in:
3 2
out:
1 2
1 3
2 3
- 如何按照字典序输出所有方案？
枚举每个位置直接从小到大
当前位置可以选取的最小值是什么–设置变量
怎么输出？
if i ==m，就
f(i,j,n) 第i个位置的最小值j和最大值n
边界是是否有足够多数
void acm_1_1_print_one_result5(int n){for(int i=0;i<n;i++){if (i) cout << " ";cout << arr[i];}cout << endl;
}
void acm_1_1_diGui_fn5(int i,int j,int n,int m){if(i==m){acm_1_1_print_one_result5(m);return;}for(int k=j;k<=n && m-i-1<=n-k;k++){arr[i]=k;acm_1_1_diGui_fn5(i+1,k+1,n,m);}return;
}
void acm_1_1_diGui_test5(){int n,m; //n代表输入是几 ，m代表每次输出几个数cin >> n >> m;acm_1_1_diGui_fn5(0,1,n,m);//0 代表第几个位置//1 代表当前位置最小可以选择的值//n 代表当前位置最大可以选择的值//m 最多枚举多少倍
}
例题：
按照字典序列，输出所有1到n这n个整数的所有方案
- 递归函数长什么样？----f(i,n)
- i==n的时候-》返回输出
//按照字典序输出所有1到n这n个整数的方案
int arr6[10],vis6[10]={0};
void acm_1_1_print_one_result6(int n){for(int i=0;i<n;i++){if(i) cout << " ";cout << arr6[i];}cout << endl;return;
}
void acm_1_1_diGui_fn6(int i,int n){if(i==n){//开始输出acm_1_1_print_one_result6(n);return;}for(int k=1;k<=n;k++){if(vis6[k])continue; //k被使用过了arr6[i]=k;vis6[k]=1;acm_1_1_diGui_fn6(i+1,n);vis6[k]=0; //回收k}
}
void acm_1_1_diGui_test6(){int n; //n代表输入是几 ，m代表每次输出几个数cin >> n;acm_1_1_diGui_fn6(0,n);//0 代表第几个位置//1 代表当前位置最小可以选择的值//n 代表当前位置最大可以选择的值//m 最多枚举多少倍
}
acm_1_1_diGui_test6();
例题：
239不规则的街道
分形系统：
同样的一个图形通过固定的变换到一个更大的图形，-继续更大的图形
//分形图形
void acm_1_1_diGui_fn7(long long n,long long s,long long &x,long long &y){//递归函数，求n级城市中，房子编号为s的房子坐标并将坐标存储在(x,y)变量中if(n==1){//当为1级城市的时候，直接返回if (s==1) x=0,y=0;else if(s==2) x=0,y=1;else if(s==3) x=1,y=1;else x=1,y=0;return;}long long L=1LL << (n-1);long long block=L*L; //每个区域点的数量long long xx,yy;//当前点在第几个区域中if (s <= block ) { //第一个区域，用坐标变换规则：（x,y）->(y,x)acm_1_1_diGui_fn7(n-1,s,xx,yy);x=yy,y=xx;}else if(s <= 2*block){ //第二个区域，(x,y)->(x,y+L)acm_1_1_diGui_fn7(n-1,s-block,xx,yy);x=xx,y=yy+L;}else if(s <= 3*block){ //第三个区域，(x,y)->(x+L,y+L)acm_1_1_diGui_fn7(n-1,s-2*block,xx,yy);x=xx+L,y=yy+L;}else{//第四个区域，(x,y)->(2L-y-1 ,L-x-1)acm_1_1_diGui_fn7(n-1,s-3*block,xx,yy);x=2*L-yy-1,y=L-xx-1;}return;}
void acm_1_1_diGui_test7(){long long t,n,s,d;scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&n,&s,&d);long long sx,sy,dx,dy;acm_1_1_diGui_fn7(n,s,sx,sy);acm_1_1_diGui_fn7(n,d,dx,dy);printf("%.0lf\n",10*sqrt(S(sx-dx)+S(sy-dy)));}
}
void acm_1_1_diGui_test7(){long long t,n,s,d;scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&n,&s,&d);long long sx,sy,dx,dy;acm_1_1_diGui_fn7(n,s,sx,sy);acm_1_1_diGui_fn7(n,d,dx,dy);printf("%.0lf\n",10*sqrt(S(sx-dx)+S(sy-dy)));}
}
- 完成2024.3.5
| by cry |
|---|
这篇关于第1章递归函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
