递归进阶与习题讲解和高精度.ppt

1、递归进阶与习题讲解,问题背景,暴力N重循环生成长度为1的序列: for (int i=1;i=n;+i) cout i endl; 生成长度为2的序列: for (int i=1;i=n;+i) for (int j=1;j=n;+j) cout i j endl; 生成长度为n的序列：需要n重循环？,深度优先搜索入门,n重循环 void dfs(int deep) if (deep n) /check answer else for (i = 1; i = n; i+) dfs(deep + 1); ,搜索过程如下：,H,A,L,I,F,B,C,D,E,J,G,K,S,深度优先搜索示意图,例

2、题：放鸡蛋,想想，鸡蛋的篮子相当于什么？ 然后如何让每个篮子的鸡蛋横向递增。 放鸡蛋的递归模型是什么？,不难看出放鸡蛋问题实质就是n重循环。第几个篮子就相当于第几层循环。然后是纵向搜索，再是横向遍历。同样道理，深搜也是n重循环的体现。,高精度算法,问题背景：当我们遇到的数字超过了unsigned long long时，要如何存储呢？ 比如3200,高精度加法,void add(char s1,char s2,int a,int b,int c) int len1 = strlen(s1); int len2 = strlen(s2); for(int i = len1-1; i=0; i-)a

3、len1-1-i = (int)(s1i-0); for(int i = len2-1; i=0; i-)blen2-1-i = (int)(s2i-0); int tmp = max(len1,len2); for(int i = 0; i=10) ci%=10; ci+1+; ,高精度减法,void decrease(char* a,char* b) int len = strlen(a); int len2 = strlen(b); int tmp210 = 0; for(int i = 0; ilen; i+)reli = (int)(ai-0); for(int k = 0; kle

4、n2; k+)tmpk =(int) (bk-0); for(int i = 0; ilen; i+) reli = reli-tmpi; if(reli0) reli+=10; reli+1-; /printf(%d ,reli); ,高精度乘法,1.高精度*高精度 void multiply( char s1,char s2,int a, int b, int c) int len1 = strlen(s1); int len2 = strlen(s2); for(int i = 0; ilen1; i+) for(int j = 0; jlen2; j+) ci+j +=( ai*bj)

5、; for(int i = 0; ilen1+len2-1; i+) ci+1 += (ci/10); ci = ci%10; ,高精度乘法,高精度*单精度 void multiply(char s1,int a,int c) int len = strlen(s1); for(int i = len-1; i=0; i-) alen-1-i=(int)(s1i-0); for(int i = 0; ilen+4; i+) ci+=(ai*b); for(int i = 0; ilen+4; i+) ci+1+=(ci/10); ci%=10; ,高精度除法,方案一：不断作减法 也就是不多调用高精度的减法，知道做减法的次数与除数相同。,高精度除法,方案二：二分试探商（也是在减法基础上）,#include #include #include using namespace std; int lenth(int n)/求数字长度(位数)函数 int i=0; while(n0) n/=10; i+; return i; int main() char a102; int b; cinab;/输入除数与被除数 /cout1 ,课