return 0; }
4、 多边形法（王晓东算法设计与分析教材上的实现，比较费解，比较牛逼）
#include
inline bool odd(int n) {
return n & 1; }
void init() {
int i;
for(i=0;i void tour(int n) { a[n][1]=n; if(n==1) return; int m=odd(n) ? n : n-1; int i,j,k,r; for(i=1;i<=m;++i) { a[i][1]=i; b[i]=i+1; b[m+i]=i+1; } for(i=1;i<=m;++i) { a[1][i+1]=b[i]; a[b[i]][i+1]=1; for(j=1;j<=m/2;++j) { k=b[i+j]; r=b[i+m-j]; a[k][i+1]=r; a[r][i+1]=k; } } 6 } void out(int n) { if(n==1) { printf(\ return; } int i,j; int m; if(odd(n)) m=n+1; else m=n; for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { if(a[i][j]>n) printf(\ else printf(\ } printf(\ } } int main() { int n; init(); while(scanf(\ { tour(n); out(n); } return 0; } 2章 整数划分，递归 #include int x,i,sum,t,temp;//x是待划分的数 i来做1:x个对x进行划分的数 sum记录划分总数 t是每个划分数能划分x的方法数 temp记录上一次的划分数 7 temp=0; printf(\请输入要划分的数\sum=0; scanf(\for(i=1;i<=x;i++){ t=q(x,i); printf(\对%d的划分有%d种\\n\ sum+=t-temp; temp=t; } printf(\共有%d种划分方发\\n\} int q(int n,int m){ if((n<1||(m<1)))return 0; if((n==1)||(m==1))return 1; if(n 2章 整数划分，分治 int split(int n)//此程序用m记录划分种数并返回m值，并且在函数体内输出了各种划 分//种类，n在int范围内皆可处理，处理时间小于1秒 { int i, j, m = 0, x, t; for(i = 1;(i*(i+1)/2)<=n; i++) { t = n - i*(i-1)/2; x = t / i; if(x <= 0) break; if(t % i == 0) { printf(\ for(j = 1; j < i; j++) printf(\ printf(\ m++; } } return m; 8 2章 大数乘法，分治 1. #include 6. #define N 7200 //做72xx位的整数乘法 7. int max(int a,int b,int c) 8. { 9. int d = (a >b)?a:b; 10. return (d>c)?d:c; 11. } 12. int initarray(int a[]) 13. { 14. int q,p,i; 15. q = N + random(100); 16. if(q%3 ==0) 17. p =q/3; 18. else 19. p =q/3+1; 20. for(i=0;i 21. a[i] = random(1000); 22. if(q%3 ==0) 23. a[0] = 100+random(900); 24. if(q%3 == 2) 25. a[0] = 10 + random(90); 26. if(q%3 == 1) 27. a[0] = 1 + random(9); 28. return p; 29. } 30. void write(int a[],int l) 31. { 32. int i; 33. char string[10]; 34. for(i=1;i 36. itoa(a[i],string,10); 37. if(strlen(string)==1) 38. fprintf(fp,\); 39. if(strlen(string)==2) 40. fprintf(fp,\); 41. fprintf(fp,\,string); 9 42. if((i+1)% == 0) 43. fprintf(fp,\); 44. } 45. fprintf(fp,\); 46. fprintf(fp,\); 47. } 48. FILE * fp; 49. 50. int main() 51. { 52. int a[5000]={0},b[5000]={0},k[10001]={0}; 53. unsigned long c,d,e;//申明作累加用的无符号长整数变量 54. int i,j,la,lb,ma,mi,p,q,t; 55. randomize();//初始化随机数 56. 57. la = initarray(a);//被乘数 58. lb = initarray(b);//乘数 59. 60. if(la < lb)//如果被乘数长度小于乘数，则交换被乘数与乘数 61. { 62. p = (lb > la)?lb:la; 63. for(q=0;q 64. t=a[q],a[q]=b[q],b[q]=t; 65. t =la,la=lb,lb =t; 66. } 67. c=d=0; 68. for(i=la+lb-2;i>=0;i--)//累加斜线间的数，i位横纵坐标之和 69. { 70. c=d;//将前一位的进位标志存入累加变量C 71. ma =max(0,i-la+1,i-lb+1);//求累加的下限 72. mi = (i > la)?(la-1):i;//求累加的上限 73. for(j=ma;;j<=mi;j++) 74. { 75. c+=a[j]b[i-j]; 76. } 77. d=c/1000;//求进位标志 78. if(c>999) 79. c%=1000;//取c的后3位 80. k[i] = c;//保存至表示乘积的数组k[] 81. 82. } 83. e = k[0] + 1000*d;//求出乘积的最高位 84. fp = fopen(\,\); 85. fprintf(fp,\,a[0]);//打印被乘数的最高位 10