1、2014.10.27III-32001234 递推是计算机数值计算中的一个重要算递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单法，可以将复杂的运算化为若干重复的简单运算，运算，以便以便充分发挥计算机长于重复处理的充分发挥计算机长于重复处理的特点特点。通常，使用循环结构来实现重复处理。通常，使用循环结构来实现重复处理。解决此类问题的关键是：分析简单情况，归解决此类问题的关键是：分析简单情况，归纳总结出前后项的关系（通项公式）。纳总结出前后项的关系（通项公式）。递递 推推56#include using namespace std;int main()int N;cout
2、 please input N(N N;int fact;for(int n=1;n=N;n+)if(n=1)fact=1;/起始条件起始条件elsefact=n*fact;/fact_n=n*fact_n_1cout fact(N )=fact endl;return 0;7刀刀刀刀刀刀刀刀8在编程之前要找到规律在编程之前要找到规律分析：分析：令令q(n)q(n)表示切表示切n n刀能分成的块数。从前面的图中可刀能分成的块数。从前面的图中可以找出下列关系：以找出下列关系：q(1)=1+1=2q(1)=1+1=2 q(2)=1+1+2=4 q(2)=1+1+2=4 q(3)=1+1+2+3=7
3、 q(3)=1+1+2+3=7 q(4)=1+1+2+3+4=11 q(4)=1+1+2+3+4=11由于要求最多的块数，所以每刀都是让每两条线都由于要求最多的块数，所以每刀都是让每两条线都有交点。用归纳法不难得到：有交点。用归纳法不难得到：q(0)=1 q(0)=1 -初始条件（边界条件）初始条件（边界条件）q(n)=q(n-1)+n -q(n)=q(n-1)+n -通项公式通项公式9#include using namespace std;int main()int q;for(int n=0;n=100;n+)if(n=0)/起始条件起始条件q=1;elseq=n+q;/q_n=n+q_
4、n_1cout q(100)=q endl;return 0;10数组11数组的定义12VC+6.0:error C2057:expected constant expression13数组中每个元素所在的内存单元，可以通过“数组名位置下标”来访问（赋值、读取）。数组元素的位置下标从 0 开始计数。例如，int a5；定义了一个含有5个整数的数组，各元素的“变量名称”分别为：a0,a1,a2,a3,a4是5个带下标的变量，它们的类型是相同的。该数组的效果与下面的变量定义相同：int a0,a1,a2,a3,a4;数组中元素的“名称”1415所有类型均可以用下面的格式来初始化数组（变量）：所有类
5、型均可以用下面的格式来初始化数组（变量）：vtype_name array_nameN=v1,v2,.,vN;type_name array_nameN=v1,v2,.,vN;其中，其中，v1,v2v1,v2等表示常量表达式。等表示常量表达式。例如：例如：int a5=3,5,4,1,2;char b5=c,h,i,n,a;如果是由字符（char）组成的数组，则还可以使用：vcharchar array_nameN=array_nameN=各种字符各种字符;例如：例如：charchar b6=china;/why 6?b6=china;/why 6?N N必须是字符串长度必须是字符串长度+1+
6、1，其初始化，其初始化结果结果为：为：b0=c;b1=h;b4=a;16#include#include using namespace std;using namespace std;int main()int main()/在定义时设定值，被称为在定义时设定值，被称为“变量初始化变量初始化”char Achar A1010=B,e,i,J,i,=B,e,i,J,i,n,g;n,g;/一共只给出了一共只给出了7 7个字符个字符for(int i=0;ifor(int i=0;i1010;i+);i+)cout Ai cout Ai int(Ai)int(Ai)endl;endl;/强制类型转
7、换，将字符值转换成整数值，即其强制类型转换，将字符值转换成整数值，即其ASCIIASCII码码 /语法格式：语法格式：dst_type(src_value)dst_type(src_value)return 0;return 0;/char_test.cpp/char_test.cpp阅读示例代码阅读示例代码1，注意总结，注意总结1718#include#include using namespace std;using namespace std;int main()int main()/在定义时设定值，被称为在定义时设定值，被称为“变量初始化变量初始化”char Achar A1010=B
8、eiJing;=BeiJing;/一共只给出了一共只给出了7 7个字符个字符for(int i=0;ifor(int i=0;i1010;i+);i+)cout Ai cout Ai int(Ai)int(Ai)endl;endl;/强制类型转换，将字符值转换成整数值，即其强制类型转换，将字符值转换成整数值，即其ASCIIASCII码码 /语法格式：语法格式：dst_type(src_value)dst_type(src_value)return 0;return 0;/char_test_2.cpp/char_test_2.cpp阅读示例代码阅读示例代码2，注意总结，注意总结1920#inc
9、lude#include using namespace std;using namespace std;int main()int main()/在定义时设定值，被称为在定义时设定值，被称为“变量初始化变量初始化”char A=BeiJing;char A=BeiJing;/一共给出了一共给出了7 7个字符个字符 int B=1,2,3,4,5;int B=1,2,3,4,5;/一共给出了一共给出了5 5个整数个整数 for(int i=0;i for(int i=0;i1010;i+);i+)cout Ai cout Ai int(Ai)int(Ai);cout Bi endl;cout
10、Bi endl;return 0;return 0;/char_test_3.cpp/char_test_3.cpp阅读示例代码阅读示例代码3，注意总结，注意总结2122#include#include using namespace std;using namespace std;int main()/int main()/在定义时设定值，被称为在定义时设定值，被称为“变量初始化变量初始化”char charA1=BeiJing;A1=BeiJing;/一共给出了一共给出了7 7个字符个字符 intintB1=1,2,3,4,5;/B1=1,2,3,4,5;/一共给出了一共给出了5 5个整数
11、个整数 cout sizeof(A1)sizeof(A1)endl;cout sizeof(A1)sizeof(A1)endl;cout sizeof(B1)sizeof(B1)endl;cout sizeof(B1)sizeof(B1)endl;char charA210=BeiJing;A210=BeiJing;/一共给出了一共给出了7 7个字符个字符 intintB210=1,2,3,4,5;B210=1,2,3,4,5;/一共给出了一共给出了5 5个整数个整数 cout sizeof(A2)sizeof(A2)endl;cout sizeof(A2)sizeof(A2)endl;cou
12、t sizeof(B2)sizeof(B2)endl;cout sizeof(B2)sizeof(B2)endl;return 0;return 0;/char_test_4.cpp/char_test_4.cpp阅读示例代码阅读示例代码4，猜猜输出，猜猜输出23B eiJ in g 0A124这个结尾处的0字符是编译器自动添加的1.数组变量在“初始化”时（即至少提供了一个初始值），如果提供的初始值数目少于数组元素的个数，则依下标大小顺序，从下标为0的元素开始，逐一设定初始值，缺少初始值的数组元素，将被编译器自动设置成0。以字符串常量方式对字符数组进行“初始化”时，也同样遵循遵循上述规则。2.
13、如果初始化时不设定数组大小（元素数目），则编译器自动根据初始值的数目来设定数组的大小。当以字符串常量方式对字符数组进行初始化时，编译器设定的数组大小是：“字符串常量长度+1”，即不遵循不遵循上述规则！252627这是一个伪命题！这是一个伪命题！所有所有类型的数组变量类型的数组变量均不可以均不可以直接直接赋值赋值30int a5;int a5;char b5;char b5;a=1,2,3,4,5;a=1,2,3,4,5;b=CHINA;b=CHINA;31v单独一个一个进行赋值单独一个一个进行赋值int a5;int a5;a0=1;a3=23;a0=1;a3=23;v使用使用forfor语句
14、，连续赋值语句，连续赋值char a5;char a5;for(int i=0;i5;i+)for(int i=0;i5;i+)ai=A+i;ai=A+i;3233Line 6:error:ISO C+forbids assignment of arrays34strcpy(h,abcdef);35v通过通过cincin操作，对字符数组变量进行操作，对字符数组变量进行“赋值赋值”36v如果是字符数组（变量），则cout会将数组的所有元素一齐输出出来，字符之间无空格。v如果是其他类型的元素组成的数组（变量），则cout只会输出该数组变量的地址，也即数组第一个元素所在内存单元的地址。vcout是如
15、何根据数据类型来决定输出方式的呢？这个问题，将在下学期面向对象程序设计中予以解答。37#includeusing namespace std;int main()char h =tsinghua;h0=a;h1=b;h2=4;h3=7;h4=c;cout h endl;cout h endl;int a=1,2,3,4,5;int a=1,2,3,4,5;a0=79;a1=88;a0=79;a1=88;a2=34;a3=64;a2=34;a3=64;a4=99;a4=99;cout a endl;cout a endl;cout&(a0)=&(a0)endl;cout&(a0)=&(a0)en
16、dl;return 0;38上述结果说明：数组上述结果说明：数组a的第一个元素的地址，与的第一个元素的地址，与a的值相等。的值相等。即即 cout a;与与 cout&(a0);等效。等效。394041424344454647484950这些地方需要修改！这些地方需要修改！515354分析上式分析上式.当当 i=5 时，时，fish i 表示表示 E 醒来所看到的鱼数，醒来所看到的鱼数，该数应满足被整除后余，该数应满足被整除后余，所以初值设为所以初值设为+2.当当 i=5 时，时，fish i-1 表示表示 D 醒来所看到的鱼数，醒来所看到的鱼数，这个数要满足这个数要满足fish 4 =fis
17、h 5 *5/4+1 显然，显然，fish 4 必须必须是整数是整数，所以，所以fish5必须必须满足满足fish 5%4=0 这个结论同样可以用至这个结论同样可以用至 fish 3,fish 2 和和 fish 1 553.按题意要求按题意要求 5 人合伙捕到的人合伙捕到的最少最少鱼数，鱼数，可以从可以从小往大枚举小往大枚举，即：，即：可以先让可以先让 E 所看到的鱼数最少为所看到的鱼数最少为 6 条，即条，即 fish 5 初始化为初始化为 6 来试，之后每次增加来试，之后每次增加 5 再试，直至递再试，直至递推到推到 fish 1 ，均为，均为整数。整数。根据上述思路，我们可以构思如下的
18、程序框图：根据上述思路，我们可以构思如下的程序框图：56定义数组并初始化定义数组并初始化输出计算结果输出计算结果57该图可分为三部分该图可分为三部分(1)是说明部分：包含定义数组是说明部分：包含定义数组 fish6，并初始化为，并初始化为 1 和定义循环控制变量和定义循环控制变量 i，并初始化为，并初始化为 0。(2)是是 do.while 直到型循环，其循环体又含两块：直到型循环，其循环体又含两块：(2.1)是枚举过程中的是枚举过程中的 fish5 的初值设置，一开始的初值设置，一开始 fish5=1+5;以后每次增以后每次增 5。(2.2)是一个是一个 for 循环，循环，i的初值为的初值
19、为 4，终值为，终值为 1，步，步长为长为-1，该循环的循环体是一个分支语句，如果，该循环的循环体是一个分支语句，如果 fishi+1不能被不能被 4 整除，则跳出整除，则跳出 for 循环（使用循环（使用 break 语句语句;）否则，从）否则，从 fishi+1 算出算出fishi。58当当 break 语句让程序退出循环时，意味着某人语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令看到的鱼数不是整数，当然不是所求，必须令fish 5 加加 5 后再试，即重新进入直到型循环后再试，即重新进入直到型循环 do while 的循的循环体。环体。当正常退出当正常退出 fo
20、r 循环时，一定是控制变量循环时，一定是控制变量 i 从从初值初值 4，一步一步执行到终值，一步一步执行到终值 1，每一步的鱼数均为，每一步的鱼数均为整数，最后整数，最后 i=0，表示计算完毕，且也达到了退出，表示计算完毕，且也达到了退出直到型循环的条件。直到型循环的条件。(3)输出计算结果输出计算结果59#include using namespace std;int main()int fish6=1,1,1,1,1,1;/记录每人醒来后看到的鱼数记录每人醒来后看到的鱼数 int i=0;do fish5=fish5+5;/让让E看到的鱼数增看到的鱼数增5。for(i=4;i=1;i-)i
21、f(fishi+1%4!=0)break;/跳出跳出for循环循环elsefishi=fishi+1*5/4+1;/计算第计算第i人看到的鱼数人看到的鱼数 while(i=1);/当当 i=1 继续做继续做do循环循环 /输出计算结果输出计算结果 for(i=1;i=5;i+)cout fishi endl;return 0;6061626331212496199615961276输出结果输出结果64#include using namespace std;int main()int fisher6;/五个人看到的鱼数五个人看到的鱼数 for(int num=6;num+=5)/对各种可能性进
22、行枚举对各种可能性进行枚举 int n;for(n=5;n=1;n-)/对五个人看到的鱼数进行递推对五个人看到的鱼数进行递推 if(n=5)fishern=num;else /fishern+1=(fishern-1)/5*4;if(fishern+1%4!=0)break;/鱼数鱼数num不满足条件，要尝试下一个不满足条件，要尝试下一个num，停止递推，停止递推 else /下式所得下式所得fishern必然满足必然满足 fishern%5=1 fishern=fishern+1*5/4+1;if(n=0)/说明鱼数说明鱼数num满足所有人的条件满足所有人的条件 break;/找到最小鱼数了
23、，停止枚举找到最小鱼数了，停止枚举 /输出各个人看到的鱼数输出各个人看到的鱼数 for(int n=1;n=5;n+)cout fisher n =fishern endl;return 0;第种算法实现第种算法实现65#include using namespace std;int main()int fisher6;/五个人看到的鱼数五个人看到的鱼数 for(int num=6;num+=5)/对各种可能性进行枚举对各种可能性进行枚举 int n;for(n=1;n=5;n+)/对五个人看到的鱼数进行递推对五个人看到的鱼数进行递推 if(n=1)fishern=num;else/下式所得下
24、式所得fishern 必然是整数必然是整数 fishern=(fishern-1-1)/5*4;if(fishern%5!=1)break;/鱼数鱼数num不满足条件，要尝试下一个不满足条件，要尝试下一个num，停止递推，停止递推 if(n=6)/说明鱼数说明鱼数num满足所有人的条件满足所有人的条件 break;/找到最小鱼数了，停止枚举找到最小鱼数了，停止枚举 /输出各个人看到的鱼数输出各个人看到的鱼数 for(int n=1;n=5;n+)cout fisher n =fishern endl;return 0;第种算法实现第种算法实现66#include using namespace
25、 std;bool IsOK(int num,int fisher6)for(int n=1;n=5;n+)/对五个人看到的鱼数进行递推对五个人看到的鱼数进行递推if(n=1)fishern=num;else /下式下式所得所得fishern必然是整数必然是整数fishern=(fishern-1-1)/5*4;if(fishern%5!=1)return false;/鱼数鱼数num不满足条件，停止递推不满足条件，停止递推return true;int main()int fisher6;/五个人看到的鱼数五个人看到的鱼数for(int num=6;num+=5)/对各种可能性进行枚举对各种可能性进行枚举if(IsOK(num,fisher)break;/found/输出各个人看到的鱼数输出各个人看到的鱼数for(int n=1;n=5;n+)cout fisher n =fishern endl;return 0;第种算法实现第种算法实现67思考题：如果不用数组，还能用递推解决这个问题吗？结结 束束69
