《程序是怎样练成的.ppt》由会员分享，可在线阅读，更多相关《程序是怎样练成的.ppt（76页珍藏版）》请在三一办公上搜索。
1、计算机系创新实践基地系列讲座之,程序是怎样练成的,邬晓钧 2006年12月28日,A:Fibonacci数列求和,求Fibonacci前n项的和，n=20算法Step1:计算出fi，1=i=20Step2:循环(读入n)Step3:n是0，退出Step4:求和Step5:输出,Step0,#include using namespace std;int main()return 0;,#include using namespace std;int main()const int MAX_N=20;/定义常数/Step1:先计算好所有可能fi值 int fMAX_N+1=0,1,1;for(i
2、nt i=3;i=MAX_N;i+)fi=fi-1+fi-2;/Step25 return 0;,int n;while(cin n)/Step2:读入n if(n=0)/Step3:n是0，退出 break;int sum=0;/Step4:求和 for(int i=1;i=n;i+)sum+=fi;cout sum endl;/Step5:输出,B:加法器,2+2345+913-3=算法Step1:读入第一个数Step2:循环(读入下一个符号)Step3:如果是=，输出Step4:否则，读入下一个数Step5:进行相应计算,Step0,#include using namespace st
3、d;int main()return 0;,int s=0;cin s;/Step1:读入第一个数char c;while(cin c)/Step2:循环读入下一符号 if(c=)/Step3:是等号，输出 cout i;/Step4:读入下一个数 if(c=+)/Step5:进行相应计算 s+=i;else s-=i;,C:序列元素交换,算法：Step1:准备好输入输出文件Step2:读入数据组数，for(组数)Step3:读入N和MStep4:读入N个序列元素Step5:读入M次交换信息，并交换Step6:输出,Step0,#include using namespace std;int
4、main()return 0;,Step1,#include#include using namespace std;int main()/准备好输入输出文件 ifstream fin(swap.in);ofstream fout(swap.out);return 0;,int t;fin t;/Step2:读入数据组数for(int i=0;i N M;/Step3:读入N和M int s10001;/Step4:读入N个序列元素 for(int j=1;j sj;for(int j=1;j x y;/Step5:读入信息 int temp=sx;/交换 sx=sy;sy=temp;for(
5、int j=1;j=N;j+)/Step6:输出 fout sj endl;,D:明智消费者,算法：Step1:读数据Step2:计算Step3:输出,Step0,#include using namespace std;int main()return 0;,Step1:读数据,输入数据第一行是两个数n m，表示有n个超市和m个该买的商品。(1 n m;接下来是nXm的矩阵Aij，其中第i行第j列表示i号超市中j商品的价格int A51101;for(int i=1;i Aij;,Step2:计算,需要记录第i号商品该在哪号超市中购买 定义：int min101=0;int shop101=
6、0;计算for(int j=1;j=m;j+)for(int i=1;i=n;i+)if(Aij!=0,Step3:输出,for(int j=1;j=m;j+)cout shopj;,E:数字三角形,最直接的方法已知n=10在程序中写10个函数，分别打印n=110在main中用switchcase调用相应的函数For example，n=4void print4()cout“1”endl;cout“2 9”endl;cout“3 10 8”endl;cout“4 5 6 7”endl;,不用直接打印的方法,关键是用具有可操作性的话语描述填写过程从1开始，向下填n个数字向右填n-1个数字向左上填
7、n-2个数字向下填n-3个数字向右填n-4个数字向下/右/左上填1个数字,1 N=52 123 13 114 14 15 105 6 7 8 9,关键是方向和填多少个数字,算法设计,把数字存储在二维数组中再打印用一个变量表示填写的方向，是一个循环 下 右 左上 可以分别用1/2/3表示填写的个数从n递减至1填写的数字从1递增,算法设计,Step1：读入nStep2：填写的准备工作Step3：填写Step4：输出,#include using namespace std;int main()int n;cin n;/Step1:读入n/Step2:做填写准备 int s1111;/存储所填写的数
8、字 int steps=n;/第一步要填n个数字 int direction=1;/第一步方向是“下”int num=1;/当前所填写的数字 int x=0,y=1;/当前要填写位置的前一位置/Step3:填写 for(int i=1;i=n;i+)for(int j=1;j=i;j+)cout sij;cout endl;/Step4:输出 return 0;,while(steps 0)switch(direction)case 1:/向下填写 direction=2;/转向右 break;case 2:/向右填写 direction=3;/转向左上 break;case 3:/向左上填写
9、 direction=1;/转向下 break;steps-;,for(int i=0;i steps;i+)x+;sxy=num;num+;,for(int i=0;i steps;i+)y+;sxy=num;num+;,for(int i=0;i steps;i+)x-;y-;sxy=num;num+;,F:命题逻辑,如何判断是重言式或矛盾式？枚举命题变元的所有可能取值，统计真假情况变元数目不定，如何枚举？用递归函数用数的二进制表示有些地方还没想清楚？没关系。我们的程序已经可以开始写了,Step0,#include using namespace std;int main()return
10、0;,根据题目说明读数据,输入数据第一行是两个整数n、m（1 n m;从第二行开始，依次描述A0,A1,Am-1，并严格依照以下格式：输入格式比较复杂，项比较多先定义一个结构来表示Ai,逻辑表达式的表示,struct Yunsuan char type;/逻辑运算符 char left;/左操作数，X或P或A int i;/左操作数下标 char right;/右操作数，P或A int j;/右操作数下标 bool value;/真假的取值;Yunsuan A10;/所有表达式bool P4;/命题变元,读入表达式,char c;for(int i=0;i c c Ai.left Ai.i A
11、i.type Ai.right Ai.j;,准备工作做完了，要面对真正的问题了,枚举命题变元的所有可能取值,for(int i=0;i 枚举总次数;i+)/利用数的二进制表示得到命题变元的取值 if(i/这里进行计算,/计算枚举总次数int Times=1;for(int i=0;i n;i+)Times*=2;,如果命题变元数量很多怎么办？,用递归函数枚举,void SetP(int n)if(n 0)/进行计算 else Pn=true;SetP(n-1);Pn=false;SetP(n-1);,试用这一思路，输出AZ的全排列,计算Ai的值,for(int j=0;j:Aj.value=!
12、Aj的左项取值|Aj的右项取值 break;case:Aj.value=Aj的左项取值,可以用函数来减少重复程序,bool LeftValue(Yunsuan a)/a的左项取值if(a.left=A)return Aa.i.value;elsereturn Pa.i;bool RightValue(Yunsuan a)/a的右项取值if(a.right=A)return Aa.j.value;elsereturn Pa.j;,判断重言式,int TrueTimes=0;/取真的次数for(int i=0;i 枚举总次数;i+)/枚举命题变元的值/计算Aj if(Aj.value)TrueTi
13、mes+;if(TrueTimes=0)cout-1 endl;else if(TrueTimes=枚举总次数)cout 1 endl;else cout 0 endl;,A:超级重复串,根据题意枚举从最大可能长度枚举枚举每一个可能的位置,XXXXXXXXXXXXXXXXXXXXXXX,长度L,长度L,相同字符,算法设计,Step1：读入字符串Step2：for 最大可能长度L;L 0;L-Step3：for 每一个可能位置 Step4：检查是否是重复串 Step5：如果是，输出2L，退出程序Step6：必然没有重复串，输出0,把算法设计写成程序框架,Step0,#include#includ
14、e using namespace std;int main()return 0;,int main()char s101=0;/Step1:读入串 cin s;int n=strlen(s);for(int L=最大可能长度;L 0;L-)/Step2:尝试所有可能的长度 for(int i=0;最大可能位置;i+)/Step3:尝试每一个位置/Step4:检查是否是重复串 if(是)cout L*2 endl;return 0;/Step5:输出2L cout 0 endl;/Step6:输出0 return 0;,最大长度显然是n/2,显然也需要一个循环,for(int L=n/2;L
15、0;L-)/Step2:尝试所有可能的长度 for(int i=0;最大可能位置;i+)/Step3:尝试每一个位置 bool bFound=true;for(int j=0;j L;j+)/比较串中每一个字符 if(si+j!=si+j+L)bFound=false;break;/只要有一个字符不等，不必再比 if(bFound)cout L*2 endl;return 0;/Step5:输出2L,这里有一些最基本的技巧,如何确定循环边界？,for(int i=0;最大可能位置;i+)/尝试每一个位置 bool bFound=true;for(int j=0;j L;j+)/比较串中每一个字
16、符 if(si+j!=si+j+L),设最大位置为x，则i最大可能取值为xj的最大可能取值为L-1i+j+L的最大可能取值为n-1即x+(L-1)+L=n-1得到x=n 2L所以循环边界条件为：i=n 2*L(如不放心，可在纸上写几个例子验证一下),int main()char s101=0;/Step1:读入串 cin s;int n=strlen(s);for(int l=n/2;l 0;l-)/Step2:尝试所有可能长度 for(int i=0;i n-l-l+1;i+)/Step3:尝试每一个位置 bool bFound=true;/Step4:检查是否是重复串 for(int j=
17、0;j l;j+)/比较串中每一个字符 if(si+j!=si+j+l)bFound=false;break;if(bFound)/Step5:输出2L cout l+l endl;return 0;cout 0 endl;/Step6:输出0 return 0;,B:快乐的跳跃者,数列a1,a2,aN，有ci=|ai+1-ai|，c1,c2,cN-1按从小到大排序，能得到序列b1,b2,bN-1满足bi=i判断输入序列是否满足条件,分析,bi=i c1,c2,cN-1正好是1N-1的某种排列算法Step1:读入aiStep2:计算ciStep3:判断c1,c2,cN-1是否1N-1的某种排列
18、Step4:根据Step3的判断结果输出,程序,Step0,#include using namespace std;int main()return 0;,#include using namespace std;int main()/Step1:读入a1aN int N;/考虑int类型够不够存下N？cin N;int a1001;/N最大是1000，可能有a1000/考虑int类型是否能存下可能的取值 for(int i=1;i ai;,/Step2:计算c1cN-1 int c1000;/考虑int类型是否能存下可能的取值 for(int j=1;j=N-1;j+)cj=aj+1-aj
19、;if(cj 0)cj=-cj;/Step3:判断c1cN-1是否是1N-1的某种排列 bool bYes=true;./Step4:输出 if(bYes)cout Im happy!endl;else cout Im unhappy!endl;return 0;,判断ci是否1N-1的某种排列,如果ck=x，则x出现在ci中如果1N-1中每一个数x都出现，则ci正好是某一种排列,/判断c1cN-1是否是1N-1的某种排列bool bYes=true;bool bList1000;/初始化bListfor(int i=1;i=N-1;i+)bListi=false;for(int i=1;i=
20、N-1;i+)if(ci=N-1)/防止数组下标越界 bListci=true;for(int i=1;i=N-1;i+)if(!bListi)bYes=false;,程序的优化,ai前期有用，后期无用，能不用数组吗？ci计算出来后只用一次，能不用数组吗？如果ciN-1，其实已经可以下结论了如果考查ck时发现它已出现在ci中，即当i=k时，发现bListci=true，其实已经可以知道1N-1中至少会缺一个数，已经可以下结论了,C:Cantor表,1/1 1/2 1/3 1/4 1/5.2/1 2/2 2/3 2/4.3/1 3/2 3/3.4/1 4/2.5/1,1个,2个,3个,4个,5个
21、,第i条斜线有i个数i是奇数：分子i1 分母1ii是偶数：分子1i 分母i1,算法,Step1：计算第n个数在哪一列，即i=?Step2：输出分子和分母 如何判断i是奇数还是偶数？,细化Step1,有1+2+i=n,int n;cin n;int sum=0,i=0;while(sum n)i+;sum+=i;,细化Step2（i是奇数）,1/1 1/2 1/3 1/4 1/5.2/1 2/2 2/3 2/4.3/1 3/2 3/3.4/1 4/2.5/1,假设这是第n个,这是第sum个,总结分子分母的数值规律,分子分母的数值规律（i是奇数）,1/1 1/2 1/3 1/4 1/5.2/1 2
22、/2 2/3 2/4.3/1 3/2 3/3.4/1 4/2.5/1,是线性关系！,分子=a(sum n)+b1)当sum=n时，分子为11=b2)当sum=n+i 1时，分子为ii=a(i-1)+1a=1所以，分子=sum n+1类似可计算分母，以及i为偶数时,程序的优化,我们有公式可以计算1+2+k，能不能不用循环，直接计算得出i?,D:矩阵乘法,Step1：读入矩阵Step2：做乘法Step3：输出,Step1：读入矩阵,int N,M;cin N M;int a3030;for(int i=0;i aij;,Step2：做乘法,M0什么意义？单位矩阵矩阵元素的取值范围是多少？做1次乘法
23、，即读入元素，每个不超过10做2次乘法，每个元素不超过10*10*10=1000做3次乘法，每个元素不超过10,00,00做4次乘法，每个元素不超过10,00,00,00做5次乘法，每个元素不超过10,00,00,00,00做n次乘法，每个元素不超过102n-1做5次乘法，小于230，32位的int类型够了,Step2.1：准备单位矩阵,int b3030;/初始化单位矩阵for(int i=0;i N;i+)for(int j=0;j N;j+)bij=0;bii=1;,Step2.2：做M次乘法,for(int m=0;m M;m+)/乘M次 int c3030;for(int i=0;i
24、 N;i+)for(int j=0;j N;j+)/cij=Sum(bik*akj)cij=0;for(int k=0;k N;k+)cij+=bik*akj;for(int i=0;i N;i+)for(int j=0;j N;j+)bij=cij;,Step3：输出,for(int i=0;i N;i+)for(int j=0;j N;j+)cout bij;cout endl;,思考,如果M值很大，程序需要如何改变？数值范围的变化能减少矩阵乘法的次数吗？,E:如何判断矩形重叠？,技巧1：对输入的矩形顶点坐标规格化例如：总是用左下和右上顶点的坐标表示矩形技巧2：不失一般性，假设矩形A的左下
25、顶点不低于矩形B的左下顶点对于处理后的矩形A、B，如何判断矩形不重叠？B在A左，B在A右，B在A上,重叠部分的面积计算,考虑横坐标，有4种情况B的右下角在A内部B的左下角在A内部A在B的内部B在A的内部共同点重叠部分是个矩形左下和右上顶点的坐标都是“中间值”左下：(Max(Ax1,Bx1),Max(Ay1,By1)右上：(Min(Ax2,Bx2),Min(Ay2,By2),更一般化的思想,先不管两个矩形的位置关系和是否重叠，直接计算左下(Max(Ax1,Bx1),Max(Ay1,By1)右上(Min(Ax2,Bx2),Min(Ay2,By2)如果不满足位置关系，则实际不重叠if(Min(Ax2
26、,Bx2)Max(Ax1,Bx1)if(Min(Ay2,By2)Max(Ay1,By1),其它考虑,用double比用float能得到更大的数据表示范围，得到更高的精度用double比用float计算会慢一些，但是本题计算量极小，体现不出来因此，本题用double更保险,F:完美的代价,如何判断可能性？显然，出现次数为奇数的字符最多有一个如何只用最少的交换次数？所谓的交换，不就像冒泡排序一样吗？要保证最少的交换次数，也就是要保证排序过程中，只进行“正确”的冒泡操作如何保证正确？只要规定某种排序准则,把左边的A移到对称位置2，和把右边的A移到对称位置1，交换次数是一样的,把左边的A移到对称位置1
27、，和把右边的A移到对称位置2，交换次数是一样的,对于相同的字符，任选一个确定其对称位置即可选A或选B来确定对称位置并移动都可以因此，可以假设串左边就是正确的字符串顺序，只要将右边移成对称的形状，反之也对最后一对字符或最后一个字符怎么办？移好前一对后，自然同时到位,如果某个字符出现奇数次，怎么办？“最中心”的那个字符，只有唯一对称位置那就以串另一边的字符为准如果串另一边也是该字符怎么办？那正好，不用移了,算法设计,Step1：读入字符串Step2：判断是否可能变成回文串（可同时知道哪个字符出现奇数次）Step3：移动，记录交换次数Step4：输出结果,#include using namespa
28、ce std;int main()int N;cin N;/Step1 char s8001=0;cin s;/Step2 int cnt26=0;/统计每个字符出现次数 for(int i=0;i 1)cout Impossible endl;else int change=0;/Step3 cout change endl;return 0;,Step3,Step3.1：for串左边的每一个字符Step3.2：if是奇数字符Step3.3：以对称位置字符为准 将该位置以右的第一个同样 字符移到该位置Step3.4：else将对称位置以左的第一个 同样字符移到对称位置,交换操作的次数，即移动
29、前后的下标之差,int change=0;for(int i=0;i i;k-)/实现交换移动 sk=sk-1;si=sN-i-1;else int j=0;for(j=N-i-1;j=i;j-)/从对称位置向左查找 if(sj=si)break;change+=N-i-1-j;for(int k=j;k N-i-1;k+)/实现交换移动 sk=sk+1;sN-i-1=si;/end of for,估算移动次数,最坏情况是什么样？aabbccddee假设串长度为2n，需要移动(2n-2)+(2n-4)+2=2 1+2+(n-1)=n(n 1)当2n不超过8000时，int类型可以存储总的移动次数如果字符出现次数大于2，实际移动会少一点,程序是怎样练成的？,由简及繁、由易及难练习用可操作性的语言描述算法将可操作性的语言变成程序语言程序不是从第一行顺序写到最后一行的！一次只专心做一件事：写一段程序，实现一步操作，完成一项功能积累经验：见多识广，熟能生巧,祝你早日练成：写程序就像说话一样自然！,
