wordpress添加边栏,无忧网站优化,东莞做公司网站,软件开发知识第1章 递归函数的设计技巧 数学归纳法 递归函数设计三个重要部分 递归求阶乘 数学(结构)归纳法
验证P(1)成立证明如果P(k)成立#xff0c;那么P(k1)成立联合Step1和Step2,证明P(1)-P(n)成立
递归函数
给递归函数一个明确的语义实现边界条件时的程序逻辑#xff0…第1章 递归函数的设计技巧 数学归纳法 递归函数设计三个重要部分 递归求阶乘 数学(结构)归纳法
验证P(1)成立证明如果P(k)成立那么P(k1)成立联合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(n1)return 1; //边界条件 n1return acm_1_1_diGui_test(n-1)*n; //利用f(n-1)结果计算f(n)的值
}//猴子吃桃
//猴子吃n天桃子的数量
int acm_1_1_diGui_test2(int n){if(n1)return 1;return (acm_1_1_diGui_test2(n-1)1)*2;
}例题
一个小球掉落到一连串弹簧板上每个弹簧板回弹a[i]个距离问小球弹 几次会弹出弹簧板串 5 2 2 3 1 2 2表示会弹2个距离所以是235 到三会弹3个距离,5385 所以弹了两次 f(i)小球从i位置开始被弹出的次数in 时结束f(i)f(ia[i])1 i0
res0
nint(input())
nslist(map(int,input().split( )))
while(in):ins[i]res1
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表示最大 边界条件是jn ,最小值比最大值大的时候 如何按照字典序输出 从小到大进行枚举每个位置的数字就是字典序 如何保证每个位置数字都大于前面的数字 传入一个量标记当前位置的最小值 每个枚举的过程都传入另一个数字这个数字他标记了当前位置最小可以选取的数字 如何输出 int arr[10];
def fn(int i,int j,int n){if (jn) return;for(int kj;kn;k){ //j代表最小值只能输出从j到narr[i]k;//i代表第几个位置 其中arr[j]一定比arr[i]前面的都大print_one_result(i); //输出前i个i表示到了第几个位置fn(i1,j1,n); }
}//输出从arr数组从0到n的元素
void print_one_result(int n){cout n n endl;for(int i0;in;i){if(i){cout ;}cout arr[i];}cout endl;
}
int n;
cin n; //对n进行指数枚举
acm_1_1_diGui_fn3(0,1,n);f(n)的nikarrji01110121 221231 2 332131 32102210132 33103310
结论 in为输出的个数 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,n1):if i:print( ,end)print(arr[i],end)print()def fn3(i,j,n):if(jn): return;for k in range(j,n1):arr[i]kprint_one_result(i)fn3(i1,k1,n);def fn3_Test():nint(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 i0;in;i){if (i) cout ;cout arr[i];}cout endl;
}
void acm_1_1_diGui_fn5(int i,int j,int n,int m){if(im){acm_1_1_print_one_result5(m);return;}for(int kj;kn m-i-1n-k;k){arr[i]k;acm_1_1_diGui_fn5(i1,k1,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)in的时候-》返回输出 //按照字典序输出所有1到n这n个整数的方案
int arr6[10],vis6[10]{0};
void acm_1_1_print_one_result6(int n){for(int i0;in;i){if(i) cout ;cout arr6[i];}cout endl;return;
}
void acm_1_1_diGui_fn6(int i,int n){if(in){//开始输出acm_1_1_print_one_result6(n);return;}for(int k1;kn;k){if(vis6[k])continue; //k被使用过了arr6[i]k;vis6[k]1;acm_1_1_diGui_fn6(i1,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(n1){//当为1级城市的时候直接返回if (s1) x0,y0;else if(s2) x0,y1;else if(s3) x1,y1;else x1,y0;return;}long long L1LL (n-1);long long blockL*L; //每个区域点的数量long long xx,yy;//当前点在第几个区域中if (s block ) { //第一个区域用坐标变换规则x,y-(y,x)acm_1_1_diGui_fn7(n-1,s,xx,yy);xyy,yxx;}else if(s 2*block){ //第二个区域(x,y)-(x,yL)acm_1_1_diGui_fn7(n-1,s-block,xx,yy);xxx,yyyL;}else if(s 3*block){ //第三个区域(x,y)-(xL,yL)acm_1_1_diGui_fn7(n-1,s-2*block,xx,yy);xxxL,yyyL;}else{//第四个区域(x,y)-(2L-y-1 ,L-x-1)acm_1_1_diGui_fn7(n-1,s-3*block,xx,yy);x2*L-yy-1,yL-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
