2章 二分法递归 ........................................................................................................... 3
一、分治法 ............................................................................................................ 3 4、 多边形法（王晓东算法设计与分析教材上的实现，比较费解，比较牛逼） . 6 2章 整数划分，递归 .................................................................................................... 7 2章 整数划分，分治 .................................................................................................... 8 2章 大数乘法，分治 .................................................................................................... 9 2章 大整数乘法，递归 .............................................................................................. 11 2章 汉诺塔，递归,非递归 .......................................................................................... 12 2章 循环赛日程表，分治算法 ................................................................................... 13 2章 循环赛日程表，递归 ........................................................................................... 16 3章 独立任务最优调度，动态规划 ............................................................................ 17 3章 汽车加油行驶问题，动态规划 ............................................................................ 18 3章 最优时间表问题，动态规划 ................................................................................ 23 3，4章 石子合并问题，动态规划，贪心算法............................................................ 25
1.动态规划算法 .................................................................................................... 25 2 .贪心算法 .......................................................................................................... 27 3，4章 大币找零钱问题，动态规划，贪心算法 ........................................................ 28
1.动态规划 ........................................................................................................... 28 2.贪心算法 ........................................................................................................... 30 3，4章 最大K乘积问题，动态规划，贪心算法 ....................................................... 32
1.动态规划 ........................................................................................................... 32 2. 贪心算法 ......................................................................................................... 34 4章 会场安排，贪心算法 ........................................................................................... 35 4章 磁带最优存储，贪心算法 ................................................................................... 35 4章 磁盘文件最优存储，贪心算法 ............................................................................ 36 4章 汽车加油问题，贪心算法 ................................................................................... 37 5章 装载问题改进，回溯法 ....................................................................................... 37 5章 N色方柱问题，回溯法 ....................................................................................... 38 5章 排列宝石问题，回溯法 ....................................................................................... 42 5，6章 运动员最佳配对问题，回溯法，分支界限法 ................................................. 44
1.回溯法 ............................................................................................................... 44 2.分支界限法 ....................................................................................................... 45 5，6章 HYPERLINK \\l _Toc32666 最佳调度问题，回溯法，分支界限法 .............. 47 1.回溯法................................................................................................................. 47
2.分支限界法 ....................................................................................................... 48 5，6章 最小重量机器设计，回溯法，分支界限法 .................................................... 50
1.回溯法 ............................................................................................................... 50 2.分支界限法 ....................................................................................................... 51 5，6章 工作分配问题，回溯法，分支限界法 ..................... 54
1.回溯法 ............................................................................................................... 54 2.分支限界法 ....................................................................................................... 55 5，6章 最小长度电路板排列问题，回溯法，分支界限法 ......................................... 57
1.回溯法 ............................................................................................................... 58 2.分支限界算法 .................................................................................................... 60
1
5，6章 布线问题，回溯法，分支界限法 ................................................................... 62
1.回溯法 ............................................................................................................... 62 2.分支界限法 ....................................................................................................... 63 5，6章 无优先级预算问题，回溯法，分支界限法 .................................................... 65
1.回溯法 ............................................................................................................... 66 2.分支界限法 ....................................................................................................... 67 5，6章 世界名画陈列馆问题，回溯法，分支界限法 ................................................. 70
1.回溯法 ............................................................................................................... 70 2.分支界限法 ....................................................................................................... 71 5，6章 子集（空间）树问题，回溯法，分支界限法 ................................................. 74
1.回溯法 ............................................................................................................... 75 2.分支界限法 ....................................................................................................... 76 5，6章 0-1背包问题，回溯法，分支界限法 ............................................................. 79
1.回溯法 ............................................................................................................... 79 2.分支界限法 ....................................................................................................... 81 6章 N后问题，分支界限法 ....................................................................................... 88
2
2章 二分法递归
int search(int t,int x[],int n) {
int low=(n-1)/2;
if( x > x+n ) return -1; if( t > x[low] ) {
return search(t,x+low+1,n-low-1)+low+1; }
else if( t < x[low] ){
return search(t,x,low); } else
return low; }
问题描述：有n个运动员进行循环赛，要求设计满足一下要求的日程表 1、 每两人必须比赛一次且只比赛一次 2、 每个选手每天只能比赛一次
3、 要求比赛时间尽可能短（即n为偶数时比赛n-1天，n为奇数时比赛n天）
一、分治法
算法思想，先算n/2的日程表，然后将循环赛日程表左上复制到右下，左下复制到右上，得到n的日程表，递归实现 实现代码： //循环赛日程表 #include
inline bool odd(int n) {
return n & 1; }
void copy(int n)//将左上角抄到右下角，将右上角加n/2后抄到左下角，将左下角抄到右上角 {
int m=n/2; int i,j;
for(i=1;i<=m;++i) for(j=1;j<=m;++j) {
a[i][j+m]=a[i][j]+m;//将左上角抄到右下角
3
a[i+m][j]=a[i][j+m];//将右上角加n/2后抄到左下角 a[i+m][j+m]=a[i][j];//将左下角抄到右上角 } }
void copyodd(int n)//n/2为奇数时的复制，让轮空选手与下一个为参赛选手进行比赛 {
int m=n/2; int i,j;
for(i=1;i<=m;++i) {
b[i]=m+i; b[m+i]=b[i]; }
for(i=1;i<=m;++i) {
for(j=1;j<=m+1;++j) {
if(a[i][j]>m) {
a[i][j]=b[i];
a[m+i][j]=(b[i]+m)%n; } else
a[m+i][j]=a[i][j]+m; }
for(j=2;j<=m;++j) {
a[i][m+j]=b[i+j-1]; a[b[i+j-1]][m+j]=i; } } }
void makecopy(int n) {
if(n/2>1 && odd(n/2)) copyodd(n); else copy(n); }
void tour(int n) {
if(n==1) {
a[1][1]=1; return;
4
}
if(odd(n)) {
tour(n+1);//当n为奇数，就设置一个虚拟的n+1，然后就有偶数个人了。。。。和一休的那个分马很像啊 return; }
tour(n/2); makecopy(n); }
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)//当比赛日程是与那位虚拟出来的n+1号选手比赛时，输出0，代表轮空
printf(\ else
printf(\ }
printf(\ } }
int main() {
int n;
while(scanf(\ {
tour(n); out(n); }
5