程序设计与算法研讨.doc

《程序设计与算法研讨.doc》由会员分享，可在线阅读，更多相关《程序设计与算法研讨.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1009可怜的毅毅【P1】时间限制(普通/Java):1000MS/10000MS 运行内存限制:65535KByte总提交:1219 测试通过:349描述 毅毅刚刚上小学三年级。有一天，老师给他出了一道十进制数的加法题目，11=几。结果毅毅做错了，老师很不高兴，罚毅毅回家做N道大整数的加法（最大有80位）。可怜的毅毅需要你的帮助输入本题有多组测试数据，每组测试数据有两行，分别表示两个非负整数。输出对每组测试数据输出一行，表示两数之和。样例输入11123456样例输出2579提示Leadingzerosshouldbeignored.+参考源码01.#include 02. 03.int re

2、verse(char * str, int f); 04. 05.int main(void) 06. 07. char a100, b100, sum100; 08. int i, tmp, c100 = 0; 09. 10. while(scanf(%s %s, a, b) = 2) 11. 12. reverse(a, 1); 13. reverse(b, 1); 14. for(i = 0; i 100; i+) 15. ci = 0; 16. i = 0; 17. while(ai != /0 & bi != /0) 18. 19. tmp = ai - 0 + bi - 0 + c

3、i; 20. if(tmp 10) 21. sumi = tmp + 0; 22. else 23. 24. sumi = tmp - 10 + 0; 25. ci + 1 = 1; 26. 27. i+; 28. 29. while(ai != /0) 30. 31. tmp = ai - 0 + ci; 32. if(tmp 10) 33. sumi = tmp + 0; 34. else 35. 36. sumi = tmp - 10 + 0; 37. ci + 1 = 1; 38. 39. i+; 40. 41. while(bi != /0) 42. 43. tmp = bi - 0

4、 + ci; 44. if(tmp 10) 45. sumi = tmp + 0; 46. else 47. 48. sumi= tmp - 10 + 0; 49. ci + 1 = 1; 50. 51. i+; 52. 53. if(ci != /0) 54. 55. sumi = ci + 0; 56. i+; 57. 58. sumi = /0; 59. reverse(sum, 0); 60. printf(%s/n, sum); 61. 62. return 0; 63. 64. 65.int reverse(char * str, int f) 66. 67. int i, j,

5、n; 68. char ch; 69. 70. if(f) 71. 72. n = 0; 73. while(strn != /0) 74. n+; 75. if(str0 = 0) 76. 77. i = 1; 78. while(stri = 0) 79. i+; 80. if(i = n) 81. str1 = /0; 82. else 83. 84. j = 0; 85. while(stri != /0) 86. strj+ = stri+; 87. strj = /0; 88. 89. 90. 91. i = 0; 92. while(stri != /0) 93. i+; 94.

6、 for(j = 0; j 1 but 0;xi=yj max cij-1,ci-1j I,j 0;xi=yj 在具体的算法设计中，以序列X= x1,x2,x3,xm 和Y= y1,y2,y3,ym作为输入。输出三个数组c,b,temp。其中cij存储Xi和Yj的公共子序列的长度，bij记录cij的值是由哪一个子问题的解得到的，这在构造最长公共子序列时要用到。问题得最优解，即X和Y得最长公共子序列记录在temph中。 二、源代码 下面是在Microsoft Visual C+ 6.0中编写的求最长公共子序列的源程序，程序定义了最大得字符串长度为99，是将p48页的动态规划算法改写而来的。 #i

7、nclude #include #define MAX 99 /typedef char MM; void main() int i,j,m,n,h=0; char xMAX= , ,yMAX= , ,bMAXMAX= ; int cMAXMAX=0; char tempMAX= ; cout *本程序可以求得字符数在99以内的任意两个字符串的最大公共子序列*n ; cout m; cout 请输入第一个字符串(“回车”结束)n如果输入的字符数超过m,则会出错!nx m = ; for(i=1;i xi; /键盘输入x和y cout n; cout 请输入第二个字符串ny n = ; for(

8、i=1;i yi; for(i=1;i =m;i+)ci0=0; /动态规划开始 for(i=1;i =n;i+)c0i=0; for(i=1;i =m;i+) for(j=1;j =cij-1) cij=ci-1j; bij= ; elsecij=cij-1; bij= - ; /动态规划结束 cout cmn中的内容：n ; for(i=0;i =m;i+) for(j=0;j =n;j+) cout cij; cout endl; cout bmn中的内容：n ; for(i=1;i =m;i+) for(j=1;j =n;j+) cout bij; cout endl; i=m,j=n

9、; while(1) if(i=0j=0) break; if(bij= ) temph+=xi; /反序记录最长公共子序列到temp中 i=i-1,j=j-1; else if(bij= ) i=i-1; else j=j-1; cout nx m 和y n =0;i-) /格式化输出最长公共子序列 if(i=h-1) if(h=1) cout LCS: tempi ; else cout LCS: tempi; else if(i=0) cout , tempi ; else cout , tempi; cout n endl; 1199怪的电梯 时间限制(普通/Java):1000MS/

10、3000MS 运行内存限制:65536KByte总提交:84 测试通过:22描述呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki(0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？输入共有二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200, 1A,BN)，第

11、二行为N个用空格隔开的正整数，表示Ki。输出仅一行，即最少按键次数,若无法到达，则输出-1。样例输入51533125样例输出3+奇怪的电梯【广度优先搜索】呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1=i=N)上有一个数字Ki (0=Ki=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失 灵。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要 按几次按钮呢？输入文件共有

12、二行，第一行为三个用空格隔开的正整数，表示N,A,B(1N200, 1A,BN)，第二行为N个用空格隔开的正整数，表示Ki。输出文件仅一行，即最少按键次数,若无法到达，则输出-1。input：5 1 53 3 1 2 5output：3广搜，只有注意上下的扩散，不用管开关的，要注意开始时就是当前层。代码：type node=recorddep,pr:longint;end;var n,i,j,x,y,head,tail,p:longint;list:array1.4000of node;a:array1.200of longint;b:array1.200of boolean;bo:boole

13、an;beginwhile not eof do beginreadln(n,x,y);for i:=1 to n do read(ai);if (x=y) then begin writeln(0);halt;end;/ 开始时就是当前层fillchar(b,sizeof(b),true); bx:=true;list1.dep:=x; list1.pr:=0;head:=1; tail:=1;bo:=false;while head=tail do beginp:=listhead.dep+alisthead.dep;if (p=1)and bp thenbegininc(tail);li

14、sttail.dep:=p;listtail.pr:=listhead.pr+1;bp:=false;if p=y then begin bo:=true; break; end;end;inc(head);end;if bo then writeln(listtail.pr)else writeln(-1);end;end.链表：program problem1029;typeteamtype=teamnode;teamnode=recorddata:integer;deep:integer;next:teamtype;end;varvisited:array1.200 of boolean

15、;k:array1.200 of integer;n,a,b:integer;procedure init;vari:integer;beginreadln(n,a,b);for i:=1 to n do read(ki);fillchar(visited,sizeof(visited),false);end;procedure bfs(root:integer);varhead,tail,temp:teamtype;i,x,y,deep:integer;beginnew(head);tail:=head;head.data:=root;head.deep:=0;head.next:=nil;

16、while headnil dobeginx:=head.data;deep:=head.deep;temp:=head;head:=head.next;dispose(temp);visitedx:=true;if x=b thenbeginwriteln(deep);halt;end;for i:=1 to 2 dobegincase i of1:y:=x+kx;2:y:=x-kx;end;if (1=y) and (y=n) and (not visitedy) thenif head=nil thenbeginnew(head);tail:=head;head.data:=y;head

17、.deep:=deep+1;head.next:=nil;endelsebeginnew(temp);temp.data:=y;temp.deep:=deep+1;temp.next:=nil;tail.next:=temp;tail:=temp;end;end;end;writeln(-1);end;beginwhile not eof do begininit;bfs(a);end;end. +1063Fibonacci 数列 【P17】时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte总提交:800 测试通过:207描述在Fibonacci 数列中

18、,F0= 0,F1= 1, andFn=Fn 1+Fn 2forn 2. 比如, 前10个Fib数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, .现在给你一个整数n, 你需要计算出Fn. 的最后4位数字输入The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 n 1,000,000,000). The end-of-file is denoted by a single line contai

19、ning the number 1.输出For each test case, print the last four digits ofFn. If the last four digits ofFnare all zeros, print 0; otherwise, omit any leading zeros (i.e., printFnmod 10000).样例输入09-1样例输出0346266875【最长公共子序列】【递归】#include#include#define N 1000Int dpN-1N+1;Char str1N.str2N;Int max(int a,int b)r

20、eturn (ab?a:b);Int LSCL(int len1,int len2) Int I,j; Int len=max(len1,len2); For(i=0;i=len;i+) dpi0=0;dp0i=0; For(i=1;i=len1;i+) For(j=0;j=len2;j+) if(str1i-1=str2j-1) Dpi=dpi-1j-1+1; Else Dpij=max(dpi-1j,dpij-1);rerurn dplen1len2;Int main() While(scanf(“%s%s”,str1,str2) Intl len1=strlen(str1);int len2=strlen(str2);printf(“%dn”,LSCL(len1,len2);return 0;