求24点游戏的编程，python计算机视觉编程给你4个任意数，你自己通过输进去运算，如果可以则算正确否则算失败
点击联系发帖人
时间：2017-12-25 16:48
24点游戏计算器 （简单四则运算）（c++）
时间： 16:35:59
&&&& 阅读：90
&&&& 评论：
&&&& 收藏：0
标签：24点游戏计算器 （简单四则运算）（c++）:https://github.com/liuxinig/cpp_1001/blob/master/24dian_siZeIN.txt
1 //24点统计
3 #include &iostream&
4 #include &cmath&
5 using namespace
6 #define N 14
7 //a数组存四个数字
8 int cixu[3],fuHao[3],p[N],sum = 0;
9 float a0[4],a[4],b[4],b0[4];
10 float zuhe[24][4];
12 各数组代表含义
13 cixu 记录运算符调用次序
15 a数组存初始的四个数
17 fuHao 存整合后的运算符顺序
19 b数组存整合后的数的计算次序
21 b0数组为用户输入的四个数
23 P数组各下标位置所代表的含义:
24 0,1,2,3:四个数是否需要阶乘（1），导数（2），或不变（0）
25 4，5,6：三个运算符
26 7,10:括号1位置
27 8,9:括号2位置
28 11:括号1是否需要阶乘或求导
29 12：括号2是否需要阶乘或求导
32 float qiuZhi(float x,float y,int f)
switch (f)
return x +
return x -
return x *
if(y == 0)
return -1;
return x /
if(x == 0)
return -1;
return y /
return y -
55 bool jiSuan()
int i,w = 0;
float b1,b2;
for(i = 0;i & 3;i++)
if(i == 0)
b1 = qiuZhi(b[w],b[w + 1],fuHao[0]);
if(b1 == -1)
return false;
if(abs(cixu[0] - cixu[1]) == 1)
b1 = qiuZhi(b1,b[w],fuHao[i]);
if(b1 == -1)
return false;
b2 = qiuZhi(b[2],b[3],fuHao[1]);
if(b2 == -1)
return false;
b1 = qiuZhi(b1,b2,fuHao[2]);
if(b1 == 24)
return true;
return false;
93 //返回除数与被除数的顺序，是左边为除数还是右边为除数
4代表左边为除数，3代表右边为除数
94 int fuHaoPD(int t1,int t2)
int t = p[t1 + 3];
if(t == 0 || t == 2)
else if(t == 3)
if(t2 != 0 && cixu[t2] & cixu[t2 - 1] && abs(cixu[0] - cixu[1]) != 2)
else if(t == 1)
if(t2 != 0 && cixu[t2] & cixu[t2 - 1] && abs(cixu[0] - cixu[1]) != 2)
113 //构造表达式 （根据找到的计算次序构造出从左到右的计算式）
114 void zhengHe()
int w1 = 0,w2 = 0;
for(int i = 0;i & 3;i++)
switch (cixu[i])
if(a[0] != -1)
b[w1] = a[0];
a[0] = -1;
if(a[1] != -1)
b[w1] = a[1];
a[1] = -1;
fuHao[w2] = fuHaoPD(1,i);
if(a[1] != -1)
b[w1] = a[1];
a[1] = -1;
if(a[2] != -1)
b[w1] = a[2];
a[2] = -1;
fuHao[w2] = fuHaoPD(2,i);
if(a[2] != -1)
b[w1] = a[2];
a[2] = -1;
if(a[3] != -1)
b[w1] = a[3];
a[3] = -1;
fuHao[w2] = fuHaoPD(3,i);
179 //查找计算顺序（即三个运算符的运算次序
类似123 213 321 ...）
180 void ciXu()
int i,j,k,l,w = 0;
//若有括号
if(p[8] != 0 || p[7] != 0)
if(p[8] != 0)
//如果有括号1
cixu[w] = p[8];
//第一计算次序为括号1的表达式
if(p[7] != 0)
//如果还有括号2
if(p[10] - p[7] & 1)
//如果括号2为大括号
{//大括号中没在小括号的运算符为第二计算次序
if(p[7] == p[8])
//如果两括号起始位置相同，则第二运算次序为小括号加一
cixu[w] = p[8] + 1;
//否则为减一
cixu[w] = p[8] - 1;
//如果括号2为小括号
cixu[w] = p[7];
cixu[w] = 6 - cixu[0] - cixu[1];
//最后一个没在括号中的运算符
运算符顺序分别为 1,2,3 和为6
最后一个为 6 - （第一个） - （第二个）
//如果没有括号2
if(cixu[0] == 2)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 1;
cixu[1] = 1;
cixu[2] = 3;
else if(cixu[0] == 1)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 3;
if(p[4] & 1)
cixu[1] = 1;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 1;
//如果只有大括号
for(i = p[7] - 1;i & p[10] - 1;i++)//括号中
if(p[4 + i] & 1)
cixu[w] = i + 1;
for(i = p[7] - 1;i & p[10] - 1;i++)//括号中
if(p[4 + i] & 2)
cixu[w] = i + 1;
if(p[7] == 1)
cixu[w] = 3;
cixu[w] = 1;
// 没有括号
for(i = 0;i & 3;i++)
if(p[4 + i] & 1)
cixu[w] = i + 1;
if(w == 0)
cixu[0] = 1;
cixu[1] = 2;
cixu[2] = 3;
else if(w == 1)
if(cixu[0] == 2)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 1;
cixu[1] = 1;
cixu[2] = 3;
else if(cixu[0] == 1)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 3;
if(p[4] & 1)
cixu[1] = 1;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 1;
else if(w == 2)
cixu[w] = 6 - cixu[1] - cixu[0];
334 //判断某表达式是否符合
335 bool panDuan()
zhengHe();
if(jiSuan() == true)
return true;
return false;
344 void chuShiHua()
for(i = 0;i & 3;i++)
cixu[i] = 0;
a[i] = a0[i];
a[i] = a0[i];
355 //输出表达式到文件
356 void outPut()
for(i = 0;i & 4;i++)
if(p[7] == i + 1)
cout&&"(";
if(p[8] == i + 1)
cout&&"(";
cout&&a0[i];
if(p[9] == i + 1)
cout&&")";
if(p[10] == i + 1)
cout&&")";
if(i != 3)
switch (p[i + 4])
cout&&‘+‘;break;
cout&&‘-‘;break;
cout&&‘*‘;break;
cout&&‘/‘;break;
cout&&"=24"&&
394 void chuLi()
int i,i1,i2,i3,i4,l1,l2,l3,l4,m,n,q,r,t;
for(i = 0;i & N;i++)
//初始化p数组为0
for(l1 = 0;l1 & 4;l1++)
for(l2 = 0;l2 & 4;l2++)
for(l3 = 0;l3 & 4;l3++)
p[4] = l1;
p[5] = l2;
p[6] = l3;
for(m = 0;m & 4;m++)
if(m == 1)
else if(m == 2)
else if(m == 3)
for(n = 0;n & 4;n++)
if(n == 1 && m != 3)
p[10] = 3;
else if( n == 2 && m != 1)
p[10] = 4;
else if(n == 3 && m == 1)
p[10] = 4;
else if(n == 0)
p[10] = 0;
chuShiHua();
if(panDuan() == true)
475 bool chongZhi(int &w)
for(i = 0;i &i++)
flag = true;
for(j = 0;j & 4;j++)
if(zuhe[i][j] != zuhe[w][j])
flag = false;
if(flag == true)
return true;
return false;
491 void zuHe()
int i,j,k,l,w = 0,s;
for(i = 0;i & 4;i++)
for(j = 0;j & 4;j++)
for(k = 0;k & 4;k++)
for(l = 0;l & 4;l++)
if(i != j && i != k && i != l && j != k && j != l && k != l)
zuhe[w][0] = b0[i];
zuhe[w][1] = b0[j];
zuhe[w][2] = b0[k];
zuhe[w][3] = b0[l];
if(chongZhi(w) == true)
for(s = 0;s & 4;s++)
a0[s] = zuhe[w][s];
517 void main()
cout&&"请输入四个数：";
cin&&b0[0]&&b0[1]&&b0[2]&&b0[3];
cout&&"共"&&sum&&"种"&&
24dian_siZe
&标签：原文地址：http://www.cnblogs.com/liuxinig/p/5874947.html
&&国之画&&&& &&&&chrome插件&&
版权所有 京ICP备号-2
迷上了代码！扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
有一种玩24点的游戏，给你4个数-2,3,4,6，可通过加减乘除运算符号将这4个数写成一个算式（每个数只能使用一次，且必须用一次）使计算结果等于24，你能写出几个式子？试一试求解答，在线等！！！快！
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
3*6+4-(-2)=24
还在吗？这种我写了，请问还有吗？我写了你这种还有（-2+3）*4*6=24
[6+(-2)+4]*3=24
为您推荐：
扫描下载二维码全国青少年信息学奥林匹克联赛培训习题与解答-共享资料网
全国青少年信息学奥林匹克联赛培训习题与解答
全国青少年信息学奥林匹克联赛培训习题与解答
（中学高级本）
目录
习题篇 与 解析篇
第一章 回溯法
1.1 马拦过河卒
1.2 出栈序列统计
1.3 算24点
1.4 冗余依赖
1.5 走迷宫
单向双轨道
1.7 组合的输出
1.8 售货员的难题
1.9 驾车旅游
关路灯
第二章 递规与递推
2.1 遍历问题
2.2 产生数
2.3 出栈序列统计
2.4 计数器
2.5 诸侯安置
2.6 括号序列
2.7 新汉诺塔
2.8 排序集合
2.9 青蛙过河
编码
第三章 贪心法
3.1 排队接水
3.2 智力大冲浪
3.3 取火柴游戏
3.4 加工生产调度
3.5 最大乘积
3.8 马拉松接力赛
3.9 线性存储问题
扇区填数
第四章
4.1 取余运算
4.2 地毯填补问题
4.3 平面上的最接近点对
4.4 求方程的根
4.5 小车问题
4.6 黑白棋子的移动
4.7 麦森数（NOIP2003）
4.8 旅行家的预算(NOIP1999)
4.9 飞行计划
第五章 图
5.1 医院设置
5.2 工程规划
5.3 服务器储存信息问题
5.4 间谍网络(AGE)
5.5 宫廷守卫
5.6 K-联赛
5.7 机器调度
5.8 公路修建
5.9 速度限制
第六章
6.1 排序二叉树
6.2 树的重量
6.3 信号放大器
6.4 “访问”术馆
6.5 聚会的快乐
6.6 重建道路
6.7 有线电视网
第七章
7.1 最多因子数
7.2 黑白棋游戏
7.3 纵横填字游戏
7.4 魔术数字游戏
7.6 三维扫描
7.7 拼字游戏
7.8 公路修建
7.9 单词游戏
第八章
尼克的任务
三角形牧场
分组
第九章 数学问题
9.1 多项式展开系数
9.3 盒子与球
9.4 取数游戏
9.5 磁盘碎片整理
9.6 欧几里德的游戏
9.7 百事世界杯之旅
9.9 班级聚会
第十章
10.2 木棍加工
10.3 三角形
10.4 多边形面积
10.5 网线切割
10.6 最接近的分数
10.7 切孔机
10.8 栓狗方案
10.9 城市街道交通费系统
回溯法
1.1
马拦过河卒
源程序名
knight.???（pas, c, cpp）
可执行文件名
knight.exe
输入文件名
knight.in
输出文件名
knight.out
【问题描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
【输入】
一行四个数据，分别表示B点坐标和马的坐标。
【输出】
一个数据，表示所有的路径条数。
【样例】
knight.out
6
【算法分析】
从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。
1.2 出栈序列统计
stack1.???（pas, c, cpp）
可执行文件名
stack1.exe
输入文件名
stack1.in
输出文件名
stack1.out
【问题描述】
栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两?种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
【输入】
一个整数n（1&=n&=15）
【输出】
一个整数，即可能输出序列的总数目。
【样例】
stack1.out
5
【算法分析】
先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
1.3 算24点
point24.???（pas, c, cpp）
可执行文件名
point24.exe
输入文件名
point24.in
输出文件名
point24.out
【问题描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。
【输入】
只有一行，四个1到9之间的自然数。
【输出】
如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。
如果没有解则输出“No answer!”
【样例】
point24.in
point24.out
21+3=24
【算法分析】
计算24点主要应用四种运算．开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少(只有三层)，所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。
1.4 冗余依赖
redund.???（pas, c, cpp）
可执行文件名
redund.exe
输入文件名
redund.in
输出文件名
redund.out
【问题描述】
在设计关系数据库的表格时，术语“函数依赖”（FD）被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号X-&Y被用来表示当集合X中的域被赋值后，集合Y的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（S）、“姓名”（N）、“地址”（A）、“电话”（P）的域，并且每个人都与某个特定的互不相同的S值相对应，根据域S就可以确定域N、A、P的值。这就记作S-&NAP。
写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖A-&B、B-&C和A-&C，那么第三个依赖是冗余的，因为域C可以用前两个依赖得到（域A确定了域B的值，同样域B确定了域C的值)。在A-&B、B-&C、C-&A、A-&C、C-&B和B-&A中，所有的依赖都是冗余的。
现在要求你编写一个程序，从给定的依赖关系中找出冗余的。
【输入】
输A的文件第一行是一个不超过100的整数n，它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复，每行包含用字符“-”和“&”隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A-&A）。虽然文件中没有对函数依赖编号，但其顺序就是编号1到n。
【输出】
每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD，然后是依赖函数号，接着是&is redundant using FDs：”最后是说明的序列号。
如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“No redundant FDs”信息。
【样例1】
redund.out
redund.out
FD 3 is redundant using FDs: 1 2
FD 3 is redundant using FDs: 1
{即C可以通过1、2得到}
FD 5 is redundant using FDs: 4 6 2
【算法分析】
一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a-&b”，先找出所有形式为“a-&*”的依赖，再由*开始找相关依赖，直到出现“#-&b”为止(这里a、b、*、#都表示任意一个域名)。
如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。
1.5 走迷宫
maze.???（pas, c, cpp）
可执行文件名
maze.exe
输入文件名
maze.in
输出文件名
maze.out
【问题描述】
有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
【输入】
第一行是两个数m，n(1&m，n&15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
【输出】
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一&”表示方向。
如果没有一条可行的路则输出-1。
【样例】
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
maze.out
(1,2)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(3,4)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(3,4)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
【算法分析】
用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
对应的位置为：(x-1, y)，(x, y+1)，(x+1, y)，(x, y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。
这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}
for i:＝1 to 4 do{分别对4个点进行试探}
先记住当前点的位置，已走过的情况和走过的路；
如果第i个点(xl，y1)可以走，则走过去；
如果已达终点，则输出所走的路径并置有路可走的信息，
否则继续从新的点往下查找search(xl，y1，b1，p1)；
end；
【思考与提高】
该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想――换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。
有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”――明显无用的节点可以先行“剪掉”，从而提高搜索速度。
1.6 单向双轨道
track.???（pas, c, cpp）
可执行文件名
track.exe
输入文件名
track.in
输出文件名
track.out
【问题描述】
如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。
从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新位置。或者输出‘NO’表示不能完成这样的调度。
【输入】
一个数n(1&n&27)及由n个小写字母组成的字符串。
【输出】
可以调度则输出最短的调度序列，不可以调度时则输出‘NO’。
【样例】
c B D
【算法分析】
这是一道类似于栈的操作题目，只不过是有两个栈B和C可以操作，而对于A序列里的元素，既可以进入B，也可以进入C，或直接到D。解决问题可以从D序列出发反过来看，当前要到D的字符在哪里，如果在A，再看它前面有没有字符，如果有，先让它们进栈(B或C)，否则直接到D；如果在B，看是否是栈顶元素，如果是，直接到D，否则将上面的字符进C；如果在C，看是否是栈顶元素，如果是，直接到D，否则无法进行操作，因为只能向右不能向左，这时要回溯。如果所有的情况都检测过，某个字符不能进行到D的操作，则输出无解信息。
由于A里的非直接进入D的字符可以进入B或C，可以跟二进制建立起对应关系，将所有情况列举一遍，再找出其中步骤最少的输出。
1.7 组合的输出
track.???（pas, c, cpp）
可执行文件名
track.exe
输入文件名
track.in
输出文件名
track.out
【问题描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r&＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
3 4 5
【输入】
一行两个自然数n、r(1&n&21，1&＝r&＝n)。
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【样例】
compages.in
compages.out
3 4 5
【算法分析】
如果通过循环加递归来实现回溯比较简单，相应程序为：
const max=20;
var a:array[0..max]
n,r:1..
procedure compages(k:integer);{选取第k个元素}
begin
{当前所选元素最小为前一个元素加1，最大为n-(r-k)，因为后面还有(r-k)个元素要选取，至少为每次选取留一个}
for i:=a[k-1]+1 to n-(r-k) do begin
{选取一个元素}
if k=r then begin
for j:=1 to r do write(a[j]:3);
else compages(k+1);
readln(n,r);
compages(1);
{从第一个元素开始选取给合数}
end.
本题要求不用递归来实现回溯，关键要定好回溯的条件。如果选取第i个元素时选择了a[i]，根据输出条件应有a[i]-i&＝n-r，如果不满足这个条件说明当前第i个元素已再无数可取，要进行回溯，将其值减1，退到上一步将上一步原来的值再增加1，重复上述过程。当全部选取完时，i回到了0，a[0]的值增加1后变为1，这是整个选取过程结束的条件。
1.8 售货员的难题
salesman.???（pas, c, cpp）
可执行文件名
salesman.exe
输入文件名
salesman.in
输出文件名
salesman.out
【问题描述】
某乡有n个村庄(1&n&40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0&s&1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
【输入】
村庄数n和各村之间的路程(均是整数)。
【输出】
最短的路程。
【样例】
salesman.in
salesman.out
{村庄1到各村的路程}
{村庄2到各村的路程}
{村庄3到各村的路程}
【算法分析】
题目给定的村庄数不多(≤40)，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。
用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果step＝n，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的村庄号)。
1.9 驾车旅游
tour.???（pas, c, cpp）
可执行文件名
tour.exe
输入文件名
tour.in
输出文件名
tour.out
【问题描述】
如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价(如3.25元/L)。驾车者一般都有以下的习惯：
（1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；
（2）在第一个停下的加油站总是将油箱加满；
（3）在加油站加油的同时，买快餐等吃的东西花去20元。
（4）从起始城市出发时油箱总是满的。
（5）加油站付钱总是精确到0.1元(四舍五入)。
（6）驾车者都知道自己的汽车每升汽油能够行驶的里程数。
现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。
【输入】
第一行是一个实数，是从出发地到目的地的距离(单位：km)。
第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量(单位：I。)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用(单位元)；一个整数是1到50间的数，表示从出发地到目的地线路上加油站的数目。
接下来n行都是两个实数，第一个数表示从出发地到某一个加油站的距离(单位：km)；第二个实数表示该加油站汽油的价格(单位：元)。
数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。
【输出】
就一个数据，是精确到0.1元的最小的加油和吃饭费用
【样例】
365
【算法分析】
驾车者从出发地出发后对于每个加油站都可能有两种操作，一是进去加油买食品，二是不进去继续前行(如果当前汽车的余油可以的话)，这样有n个加油站最多可能有2n种选择。由于加油站数目不太多，可以采用回溯的算法来解决问题。从第一个加油站开始，依次选择所要停下的下一个加油站，从而找出总费用最少的方案，加油站数目最多为50，这样回溯不会进行得很深。在选择下一个要停下的加油站时比较麻烦，不能完全一个一个地试过去，这样时间太长。可以用这样的方法：先找出第一个要停下的加油站，判断其后面的加油站是否可以到达，如果不可到达就必须在这里停下来加油；否则就找出可以到达但如果只用一半汽油则无法到达的所有加油站，依次进行停靠。
1.10关路灯
power.???（pas, c, cpp）
可执行文件名
power.exe
输入文件名
power.in
输出文件名
power.out
【问题描述】
某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
【输入】
文件第一行是两个数字n(0&n&50，表示路灯的总数)和c(1&＝c&=n老张所处位置的路灯号)；
接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。
【输出】
一个数据，即最少的功耗(单位：J，1J＝1W?s)。
【样例】
{此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序}
8 10
【算法分析】
设老张开始所在位置为c，以起始点c为分界点，算出左右两部分总的功率p_left和p_right，再来分别看向左与向右的情况。
向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_left+w[i])*t，增加的功为p_right*2t。
向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_righ+w[i])*t，增加的功为p_left*2t。
比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，但不能求出所有情况下最佳的解。
对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变化都跟上面所述一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左与向右的情况，在所有可能的情况中找出最优解。
【思考与提高】
上面的程序运算的范围很有限，当n比较大时就会栈溢出，如n&30时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：
最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种；
最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。
如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。
第二章 递规与递推
2.1 遍历问题
travel.???（pas, c, cpp）
可执行文件名
travel.exe
输入文件名
travel.in
输出文件名
travel.out
【问题描述】
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
【输入】
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。
【输出】
输出可能的中序遍历序列的总数，结果不超过长整型数。
【样例】
trave1.out
bca
【算法分析】
根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。
设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况：
根结点的左子树结点个数为n-1，右子树结点的个数为0；
根结点的左子树结点个数为n-2，右子树结点的个数为1；
……
根结点的左子树结点个数为n-i，右子树结点的个数为i-1；{0&＝i&=n-1)；
……
根结点的左子树结点个数为0，右子树结点的个数为n-1。
根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个数为i-l(0&＝i&＝n-1)，先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。
结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：
Function count (先序结果first，后序结果last : string) :
Len:=遍历结果的长度；
如果len为0或1，则返回结果即count:=l
t为当前统计后符合条件的数目，初值为0；
分类统计for i:=len-1 downto 0 do
在first中取出长度为i的左子树结果LF；
在last中取出长度为i的左子树结果LL；
在first中取出长度为len-1-i的左子树结果RF；
在last中取出长度为len-1-i的右子树结果RL；
如果LF、LL符合基本规则(LF的首字符跟LL的尾字符相同、LF中，所有的
字符在LL中也都有)
并且RF、RL也符合基本规则，那么
t:=t+count(LF，LL)*count(RF，RL);
{分步相乘、分步相加}
{这里count函数中递归调用了count}
返回值为t即count:=t;
其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：
function check(先序字符串F，后序字符串L)：boolean；
如果F的首字符不等于L的尾字符则check:=
从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=
【思考与提高】
上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。
在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：
a
这两种结构的中序遍历结果分别为：ba、ab，有两种。
根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得到总的数目。这也可以理解为一种递推的方法。
从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2n种不同的结果，其中n&＝0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。
递推的程序如下：
Program travel(intput,output);
Var
Total,I,m:
S1,s2:
Assign(input,’travel.in’);
Assign(output,’travel.out’);
Reset(input);
rewrite(output);
Readln(s1);
readln(s2);
For i:=1 to length(s1)-1 do
M:=pos(s1[i],s2);
If m&1 then if s[i+1]=s[m-1] then total:=total*2;
Writeln(total);
close(iinput);
close(output);
2.2 产生数
build.???（pas, c, cpp）
可执行文件名
build.exe
输入文件名
build.in
输出文件名
build.out
【问题描述】
给出一个整数n(n&1030)和m个变换规则(m≤20)。
约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。
现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产生出多少个不同的整数。
【输入】
共m+2行，第一行是一个不超过30位的整数n，第2行是一个正整数m，接下来的m行是m个变换规则，每一规则是两个数字x、y，中间用一个空格间隔，表示x可以变换成y。
【输出】
仅一行，表示可以产生的不同整数的个数。
【样例】
2 3
【算法分析】
如果本题用搜索，搜索的范围会很大(因为n可能有30位!)，显然无法在规定的时间内出解。而我们注意到本题只需计数而不需要求出具体方案，所以我们稍加分析就会发现，可以用乘法原理直接进行计数。
设F[i]表示从数字i出发可以变换成的数字个数(这里的变换可以是直接变换，也可以是间接变换，比如样例中的1可以变换成2，而2又可以变换成3，所以1也可以变换成3；另外自己本身不变换也是一种情况)。那么对于一个长度为m位的整数a，根据乘法原理，能产生的不同的整数的个数为：F[a[1]]*F[a[2]]*F[a[3]]*…*F[a[m]]。
下面的问题是如何求F[i]呢？由于这些变换规则都是反映的数字与数字之间的关系，所以定义一个布尔型的二维数组g[0..9，0..9]来表示每对数字之间是否可以变换，初始时都为False；根据输入的数据，如果数字i能直接变换成数字j，那么g[i，j]置为True，这是通过一次变换就能得到的；接下来考虑那些间接变换可得到的数字对，很明显：如果i可以变为k，k又可以变为j，那么i就可以变为j，即：
for k:=0 to 9 do
for i:=0 to 9 do
for j:=0 to 9 do
g[i,j]＝g[i,j]or(g[i,k] and g[k,j])；
最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。
2.3 出栈序列统计
源程序名
stack.???（pas, c, cpp）
可执行文件名
stack.exe
输入文件名
stack.in
输出文件名
stack.out
【问题描述】
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
【输入】
就一个数n(1≤n≤1000)。
一个数，即可能输出序列的总数目。
【样例】
5
【算法分析】
在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。
从排列组合的数学知识可以对此类问题加以解决。
我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。
出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：
C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*…*(n+2)/n!。
考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。
本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考《组合数学》等书。
【思考与提高】
我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：
（1）将右方的等待进栈的第一个元素进栈；
（2）将栈顶的元素出栈，进入左边的出栈序列。
设此时右方、栈、左方的元素个数分别为a，b，c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。
又由上面的两种移动方法，我们可类似的得到两种状态转移方式：
再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：
边界值：f(0,0)=1。
有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。
2.4 计数器
count.???（pas, c, cpp）
可执行文件名
count.exe
输入文件名
count.in
输出文件名
count.out
【问题描述】
一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中―个页码不含多余的0，如N＝1234时第5页不是0005，只是5。
【输入】
一个正整数N(N≤109)，表示总的页码。
【输出】
共十行：第k行为数字k-1的个数。
【样例】
1
【算法分析】
本题可以用一个循环从1到n，将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1，则count[1]增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：
for i:=1 to n do begin
while j&0 do begin
count[j mod 10]:=count[j mod 10]+1;
j:=j div 10;
当n是整型数据时，程序执行的时间不会太长。而n是长整型范围，就以n是一个9位数为例，当i执行到8位数时，每拆分一次内循环要执行8次，执行完8位数累计内循环执行的次数为：
9*1+90*2+900*3+00*5+++
时间上让人不能忍受。
可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的0的情况，假设从，这一万个连续的数，0到9用到的次数都是相同的，一万个四位数，0到9这十个数字共用了40000次，每个数字使用了4000次。
进一步推广，考虑所有的n位数情况，从n个0到n个9，共10n个n位数，0到9十个数字平均使用，每个数字共用了n*10n-1次。
有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的0的个数。
以n=3657为例：(用count数组来存放0到9各个数字的使用次数)
最高位(千位)为3，从0千、1千到2千，000~999重复了3次，每一次从000到999，每个基本数字都使用了3*102＝300次，重复3次，所以count[0]～count[9]各增加3*300；
另外最高位的0到2作为千位又重复了1000次，count[0]～count[2]各增加1000，3作为千位用了657次(＝n mod 100)，因此count[3]增加657；
接下来对百位6再进行类似的处理，0到9在个位和十位平均重复使用6*20次，所以count[0]～count[9]先各增加6*20，0到5作为百位重复使用了100次，所以count[0]～count[5]再各增加100，6作为百位在这里重复用了57次(＝n mod 100)；因此count[6]增加57；
对十位和个位也进行相同的处理，得出count[0]~count[9]的值；
最后再减去多算的0的个数。
那么0到底多算了多少次呢?
当没有十位及以更高位时，个位的0，只多算了1次；
当没有百位及以更高位时，十位的0，多算了10次；
当没有千位及以更高位时，百位的0，多算了100次；
因此在统计m位数时，0多算了(11……1)这样一个全是1的m位数。
基本算法描述如下：
计算n的位数Len；
将n每一位上的数字存放到数组c里；
计算10的0次方到len-1次方并存放到数组b里；
i控制位数，for i:=len downto 1 do
0到9的使用次数增加平均使用的次数b[i-1]*(i-1)*c[i]；
0到c[i-1]的使用次数增加作为当前位使用的次数b[i-1]；
c[i]的使用次数增加n mod b[i-1]
最后减去多计算的0的个数；
输出结果。
2.5 诸侯安置
empire.???（pas, c, cpp）
可执行文件名
empire.exe
输入文件名
empire.in
输出文件名
empire.out
【问题描述】
很久以前，有一个强大的帝国，它的国土成正方形状，如图2―2所示。
这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图2―3为n＝3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。
国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。
因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。
现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。(n≤l00，k≤2n2-2n+1)
由于方案数可能很多，你只需要输出方案数除以504的余数即可。
【输入】
仅一行，两个整数n和k，中间用一空格隔开。
【输出】
一个整数，表示方案数除以504的余数。
【样例】
empire.out
4
【样例说明】
四种安置方案如图2-4所示。注意：镜面和旋转的情况属于不同的方案。
【算法分析】
重新描述一下问题，其实就是在一个边长为2n-1的正菱形(如上图2-2为n＝3的情形)上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?
看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n，n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n))2*k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。
首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间[a,b]当中，第i个数一定在区间[ai,bi]之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。
因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，n最多可到100，k最多可到50，穷举要进行C(50,100)种方案!
显然无法在规定的时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。
设f[i,j]表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：
不过还要注意，当k≥2n-1时，问题无解。
2.6 括号序列
bracket.???（pas, c, cpp）
可执行文件名
bracket.exe
输入文件名
bracket.in
输出文件名
bracket.out
【问题描述】
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…， 和序列bl，b2，…， ，如果存在一组下标1≤i1&i2&…& ≤m，使得aj＝ 对一切1≤j≤n成立，那么a1，a2…， 就叫做b1，b2，…， 的子列。
【输入】
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
【输出】
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
【样例】
bracket.in
bracket.out
{最多的嵌套层数为1，如层数为2时的一种为()[()]}
【算法分析】
对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0，如果没有相应的括号跟它对应，则保存原子始代码的编号，“[]”分别为-1和1，“()”分别为-2和2。
因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。
查找匹配时，可用这样的方法：
如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0，查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。
从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。
输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。
2.7 新汉诺塔
hanoi.???（pas, c, cpp）
可执行文件名
hanoi.exe
输入文件名
hanoi.in
输出文件名
hanoi.out
【问题描述】
设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。
现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
移动时有如下要求：
?一次只能移一个盘；
?不允许把大盘移到小盘上面。
【输入】
文件第一行是状态中圆盘总数；
第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号；
第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。
【输出】
每行一步移动方案，格式为：move I from P to Q
最后一行输出最少的步数。
【样例】
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to C
7
【算法分析】
要从初始状态到目标状态．就是要把每个圆盘分别移到自己的目标状态。
怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘……直到最小的编号为1的圆盘到目标状态为止。
设计一个移动过程：move(k,w)，表示把编号k的圆盘移到w柱。
2.8 排序集合
sort.???（pas, c, cpp）
可执行文件名
sort.exe
输入文件名
sort.in
输出文件名
sort.out
【问题描述】
对于集合N={1,2,…,n}的子集，定义一个称之为“小于”的关系：
设S1={X1,X2,…,Xi}，（X1&X2&…&Xi），S2={Y1, Y2, …,Yj}，（Y1&Y2&…&Yj），如果存在一个k，（0≤k≤min(i,j)），使得X1=Y1，…，Xk=Yk，且k=i或X(k+1)&Y(k+1)，则称S1“小于”S2。
你的任务是，对于任意的n(n≤31)及k(k&2n)，求出第k小的子集。
【输入】
输入文件仅一行，包含两个用空格隔开的自然数，n和k。
【输出】
输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。
【样例】
1 2 3
【算法分析】
我们知道，n个元素构成的集合有2n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n＝3时，8个集合排序如下：{}&{1}&{l,2}&{l,2,3}&{1,3}&{2}&{2,3}&{3}，你发现规律了吗?具体算法为：先推出第k小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后的结果。
2.9 青蛙过河
源程序名
frog.???（pas, c, cpp）
可执行文件名
frog.exe
输入文件名
frog.in
输出文件名
frog.out
【问题描述】
有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图2―5所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：
(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；
(2)青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D；
(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。
你的任务是对于给出的h，k，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
【样例】
{河中间有2个石礅，3个荷叶}
16 {最多有16只青蛙可以按照规则过河}
【算法分析】
结论为：f(h,k)=2h(k+1)
从具体到一般，推导过程如下：
f(0,k)=k+1;
（如k=3时，有4只青蛙可以过河）
f(1,k)=2(k+1);
（递推思想）
依此类推：f(2,k)=(2*(k+1))*2=22(k+1);
2.10电话号码
源程序名
phone.???（pas, c, cpp）
可执行文件名
phone.exe
输入文件名
phone.in
输出文件名
phone.out
【问题描述】
电话机上每一个数字下面都写了若干个英文字母。分布如下：
现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。
【输入】
第一行为一个正整数N表示单词表中单词的个数(N≤100)；
第二行为一个长度不超过100的数字串，表示密码；
接下来的N行，每行一个长度不超过20的单词，表示单词表。
【输出】
仅一行，表示翻译后的原文，如果密码无法翻译，则输出“No Solutions!”，如果密码有多种翻译方式，则输出任意一种即可。
【样例】
thi shs b boo k
k
【算法分析】
本题可以用递归搜索求解。首先，我们注意到一个数字串对应的单词是不惟一的，而反之，一个单词所对应的数字串却是惟一的!所以，我们一开始就读入一大串的数字密码和一些可以出现的单词，我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的开头开始扫描，得出密码的第一个单词有可能的情况，选择其中一种，得出第一个单词，得到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解，就可以换一种第一个单词的取法，再次试验。如果全是无解，那整个密码也是无解的。另外，首先要判断整个密码串是否是一个单词，避免无限递归。
encode.???（pas, c, cpp）
可执行文件名
encode.exe
输入文件名
encode.in
输出文件名
encode.out
【问题描述】
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。
字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。
你的任务就是对于所给的单词，求出它的编码。
【输入】
仅一行，被编码的单词。
【输出】
仅一行，对应的编码。如果单词不在字母表中，输出0。
【样例】
encode.out
27
【算法分析】
对于输入的字符串，首先检查是否符合编码的条件：全是由小写字母组成并且前面的字母不会比后面的字母大。如果符合条件则进行编码，否则输出0。
编码时如果不找规律，可以根据顺序，从第一个符合条件的单词a开始往后构造，每构造一个，相应的编码增加1，直到构造到输入的字符串。
一个单词的后序单词类似于数字的进位，如十进制中8后面是9，9后面是10――进位的情况，再如99后面是100，199后面是200。而这里单词的规则是一串中后面的字符不比前面的大，所以z后是ab，az后是bc，……两个字符的单词最大的为yz，三个字符最小的为abc，最大的为xyz，……六个字符的单词最小的为abcdef，最大的为uvwxyz。
根据上面的进位规则进行构造，构造到输入的字符串时则输出相应的序号。
由此可以写出程序。
另外可以从数学上寻找递推的规则：
一个字符的单词有26个；
两个字符的单词有：25+24+23+…+1个；
{其中ab~az共25个，bc~bz共24个，cd~cz共23个…，yz共1个}
三个字符的单词有：
(24+23+22+…+1)+(23+22+21+…+1)+…+(2+1)+(1)个
xyz
四个字符的单词有：
((23+22+21+…+1)+(22+21+20+…+1)+…+(2+1)+(1))+
abcd~axyz
((22+21+20+…+1)+(21+20+…+1)+…+(2+1)+(1))+…+…+((1))个
wxyz
以此类推，得到相应的数学公式。
第三章 贪心法
3.1 排队接水
源程序名
water.???（pas, c, cpp）
可执行文件名
water.exe
输入文件名
water.in
输出文件名
water.out
【问题描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
【输入】
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
【输出】
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
【样例】
3 2 7 8 1 4 9 6 10 5
56 12 1 99
291.90
【算法分析】
平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1~n的自然顺序排列的，则这个问题就是求以下公式的最小值：
如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！
其实，我们认真研究一下上面的公式，发现可以改写成如下形式：
这个公式何时取最小值呢？对于任意一种排列k1, k2, k3, …, kn，当 ≤ ≤ ≤…≤ 时，total取到最小值。如何证明呢？方法如下：
假设i&j，而 & ，这是的和为total1，而把ki和kj互换位置，设新的和为total2，则：
我们发现上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。
既然如此，我们就得到了一种最有贪心策略：把接水时间少的人尽可能排在前面。这样一样，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。
3.2 智力大冲浪
源程序名
riddle.???（pas, c, cpp）
可执行文件名
riddle.exe
输入文件名
riddle.in
输出文件名
riddle.out
【问题描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
【输入】
输入文件riddle.in，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
【输出】
输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。
【样例】
riddle.out
4 2 4 3 1 4 6
70 60 50 40 30 20 10
【算法分析】
因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?应该放在第k个时段，因为放在1～k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。
本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。
当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序2。
3.3 取火柴游戏
源程序名
match.???（pas, c, cpp）
可执行文件名
match.exe
输入文件名
match.in
输出文件名
match.out
【问题描述】
输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：
A：(2,2)→(1,2)
{从一堆中取一根}
P：(1,2)→(1,1)
{从另一堆中取一根}
A：(1,1)→(1,0)
P：(1,0)→ (0,0)
如果决定A后取：
P：(2,2)→(2,0)
A：(2,0)→ 0,0)
又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：
P：(1,2,3)→(0,2,3)
A：(0,2,3)→(0,2,2)
A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输
出第一次该如何取。如果是先取必败，则输出“lose”。
【样例1】
{表示第一次从第3堆取4个出来，必胜}
3 6 5 {第一次取后的状态}
【样例2】
{先取必败}
15 22 19 10
【算法分析】
从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后―次取火柴棒的人为胜方。
当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。
但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。然后再对这个数的比k位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。
如n＝3时，三堆火柴棒的数量分别为3，6，9，则3＝(＝(＝(1001)2，最高位之和为1，其中9对应的二进制数的最高位为1，将其变为0，次高位之和也是1，9对应的二进制数的次高位为0，根据证明过程将其变为1，最后二位数字之和均为偶数，无需作任何改变，这样9＝(1001)2被变成了(，显然，3=(=(=(0101)2是一个偶状态。
有了前面的分析，一种贪心算法就出来了。程序中用n个包含16个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如b[i, 0]存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。
【后记】
大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!
有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。
3.4 加工生产调度
源程序名
prod.???（pas, c, cpp）
可执行文件名
prod.exe
输入文件名
prod.in
输出文件名
prod.out
【问题描述】
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【输入】
第一行仅―个数据n(0&n&1000)，表示产品的数量。
接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。
最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。
【输出】
第一行一个数据，表示最少的加工时间；
第二行是一种最小加工时间的加工顺序。
【样例】
3 5 8 7 10
1 5 4 2 3
【算法分析】
本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。
要使总的空闲时间最少，就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。
设计出这样的贪心法：
设Mi＝min{Ai，Bi}
将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，则将它安排在从头开始的已经安排的生产顺序后面，如果Mi＝Bi，则将它安排在从尾开始的已安排的生产顺序前面。
这种安排是否是最少的加工时间，还要通过数学证明。证明如下：
设S＝&J1，J2，…，Jn)，是等待加工的作业序列，如果A车间开始加工S中的产品时，B车间还在加工其他产品，t时刻后B车间就可利用A车间加工过的产品。在这样的条件下，加工S中任务所要的最短时间T(S, t)=min{Ai+T(s-{Ji}，Bi+max{t-Ai, 0})}，其中，Ji∈S。
图3-1是加工作业i时A车间等待B车间的情况：
A等B的情况
图3-2是加工作业i时B车间等待A车间的情形：
B等A的情况
假设最佳的方案中，先加工作业Ji，然后再加工作业Jj，则有：
如果将作业Ji和作业Jj的加工顺序调整，则有：
按照上面的假设，有T&=T’，所以有：
这说是所谓的Johnson公式，也就是说在此公式成立的条件下，优先安排任务Ji在Jj之前可以得到最优解。也就是在A车间加工时间短的安排在前面，在B车间加工时间短的任务安排在后面。
以样例数据为例：
（A1, A2, A3, A4, A5）=（3, 5, 8, 7, 10）
（B1, B2, B3, B4, B5）=（6, 2, 1, 4, 9）
则（m1, m2, m3, m4, m5）=（3, 2, 1, 4, 9）
排序之后为：（m3, m2, m1, m4, m5）
处理m3，因为m3=B3，所以m3安排在后面（，，，，3）；
处理m2，因为m2=B2，所以m2安排在后面（，，，2，3）；
处理m1，因为m1=A1，所以m1安排在前面（1，，，2，3）；
处理m4，因为m4=B4，所以m4安排在后面（1，，4，2，3）；
处理m5，因为m5=B5，所以m5安排在后面（1，5，4，2，3）。
从而得到加工的顺序1，5，4，2，3。计算出最短的加工时间34。
【补充说明】
由于本题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。
3.5 最大乘积
源程序名
maxmul.???（pas, c, cpp）
可执行文件名
maxmul.exe
输入文件名
maxmul.in
输出文件名
maxmul.out
【问题描述】
一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。
现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
【输入】
只一个正整数n，(3≤n≤10000)。
【输出】
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
【样例】
maxmul.out
30
【算法分析】
初看此题，很容易想到用回溯法进行搜索，但是这里的n范围比较大，最多到10000，如果盲目搜索，运行时间比较长，效率很低，对于部分数据可能得到结果，对于大部分数据会超时或栈溢出。
先来看看几个n比较小的例子，看能否从中找出规律：
n 分解方案 最大的乘积
5 2 3 6
6 2 4 8
7 3 4 12
8 3 5 15
9 2 3 4 24
10 2 3 5 30
可以发现，将n分解成a1, a2, a3, a4,…, am这m个自然数，该序列为从2开始的一串由小到大的自然数，如果a1为1，则对乘积没有影响，而且使n减少，没有实际意义，只有特殊情况如n为3、4时才可能用上。
设h&＝5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。证明如下：
将h分为两部分：a，h-a其中2&＝a&h/2，两部分的乘积为a*(h-a)。
a*(h-a)-h＝h*a-a*a-h＝h*(a-1)-a*a
因为h&2*a，所以a*(h-a)-h&2*a*(a-1)-a*a=a*a-2*a=a*(a-2)
又因为a&＝2，所以a*(a-2)&=0，所以a*(h-a)-h&O即a*(h-a)&h。
从上面的证明可以看出，对于指定的正整数，如果其大于等于5，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。因此可以将指定的n，依次拆成a1+a2+a3+a4+…+am，乘积最大。
现在的问题是如何拆分才能保证n＝a1+a2+a3+a4+…+am呢?
可以先这样取：当和不足n时，a1取2，a2取3，…，am-1取m，即从2开始按照自然数的顺序取数，最后剩余的数给am，如果am&=am-1，此时am跟前面的数字出现了重复，则把am从后面开始平均分布给前面的m-1个数。为什么要从后面开始往前呢?同样是考虑数据不出现重复的问题，如果是从前面往后面来平均分配，如2加上1以后变成3，就跟后面的已有的3出现了重复。这样操作到底是否正确、是否能保证乘积最大呢?还要加以证明。证明过程如下：
设两个整数a，b的和为2s，且a&&b，设a＝s-1，则b＝s+1，a*b=(s-1)*(s+1)=s2-1，如果a=s-2，则b＝s+2，a*b＝(s-2)*(s+2)＝s2-4。
a-b的绝对值越小，乘积的常数项越大，即乘积越大，上面的序列a1, a2, a3, a4, …, am正好满足了a-b的绝对值最小。但是还要注意两个特例就是n=3和n=4的情况，它们的分解方案分别为1，2和1，3，乘积分别为2和3。
以n=10为例，先拆分为：10=2+3+4+1，最后一项为1，比4小，将其分配给前面的一项，得到10=2+3+5，所以最大的乘积为2*3*5＝30。
以n=20为例，拆分为：20=2+3+4+5+6，正好是连续自然数的和，所以最大乘积为2*3*4*5*6=720。
再以n=26为例，先拆分为：26=2+3+4+5+6+6，因为最后一项为6，不比最后第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的4项各分到1，笫5项6分到2，最后是26＝3+4+5+6+8，所以最大的乘积为3*4*5*6*8＝2880。
由于n可能大到10000，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。
本题的贪心策略就是：
要使乘积最大，尽可能地将指定的n(n&4)拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。
基本算法描述如下：
（1）拆分过程
拆分的数a先取2；
选择a作为一项；
如果n&0，那么将n从最后一项开始平均分给各项；
如果n还大于0，再从最后一项开始分一次；
（2）求乘积
设置一个数组来存放乘积，初始状态位数为1，结果为1；
将上面拆分的各项依次跟数组各项相乘并考虑进位；
3.6 种树
源程序名
trees.???（pas, c, cpp）
可执行文件名
trees.exe
输入文件名
trees.in
输出文件名
trees.out
【问题描述】
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
* 从trees.in读入数据
* 计算最少要种树的数量和位置
* 把结果写到trees.out
【输入】
第一行包含数据N，区域的个数(0&N≤30000)；
第二行包含H，房子的数目(0&H≤5000)；
下面的H行描述居民们的需要：B E T，0&B≤E≤30000，T≤E-B+1。
【输出】
输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。
【样例】
3 5 2
【算法分析】
不难想到下面的贪心算法：按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边(排序)，可以保证这些树尽可能多地被下面的区间利用到。
扫描需要的时间为O(h)，更新需要的时间为O(n)，所以总的时间复杂度为O(n*h)。
3.7 餐巾
源程序名
napkin.???（pas, c, cpp）
可执行文件名
napkin.exe
输入文件名
napkin.in
输出文件名
napkin.out
【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
(1)购买新的餐巾，每块需p分；
(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f&p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
(3)把餐巾送到慢洗部，洗一块需n天(n&m)，费用需s分(s&f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共3行，第1行为总天数；第2行为每天所需的餐巾块数；第3行为每块餐巾的新购费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。
【输出】
输出文件共n+1行。第1行为最小的费用。下面的n行为从第1天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。
【样例】
napkin.out
3 3 1 2 0 0
10 1 6 2 3
2 1 2 0 1 0
4 0 0 0 2 2
【算法分析】
在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行出最优解。如果从买的角度去思考这个问题，则该问题就变得十分简单。在确定要买的餐巾数之后，显然这些餐巾购买得越早，被反复利用的可能就越大。也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。这就是我
们的贪心思想。
对所要购买的餐巾数进行穷举，开始时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。在确定了购买的餐巾总数后，按上述算法构造出最小费用方案，所有的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组need存放每天需用的餐巾数，数组fromslow记录每天来自慢洗的餐巾数。数组fromfast记录每天来自快洗的餐巾数，数组buy记录每天购买的餐巾数。变量restslow存储当天可供选用的已经慢洗好的餐巾数。这个算法的数量级为O(n)，其中n为所有天中需用的餐巾数之总和。
3.8 马拉松接力赛
源程序名
marathon.???（pas, c, cpp）
可执行文件名
marathon.exe
输入文件名
marath.in
输出文件名
marath.out
【问题描述】
某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。
刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、…、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。
根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑2km速度快，连续跑2km又要比连续跑3km速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。
【输入】
5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、…、10km所用的时间。
【输出】
两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。
【样例】
marath.out
333 700 40 56
300 610 960 12 98 7682
298 612 990 96 96 7654
289 577 890 34 90 9876
312 633 995 34 99 8123
【算法分析】
初看此题，好象是一个排列问题，选取5个10之间的数，共有10*10*10*10*10＝100000种情况，对每一种情况，再看其和是否为25，在和为25的情况下再计算所用的总时间，找出其中最少的。
这种枚举的方法，肯定能找到最优解，但是这样做的效率不高，执行时间长，这里是5个选手还行，如果更多，如15个选手，就要对l015种可能情况进行判定，再快的计算机也要较长的时间来执行。
因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快……也就是说连续跑的路程越长，速度越慢，所以我们可以将每个选手的所跑时间进行分段处理，计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里，先给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时检查各自所跑第二公里所用的时间，哪个用的时间最短就选这个选手继续跑一公里，因为这样做可以保证当前所用的时间最少，这个所手所跑的公里数增加1。下一公里继续用这种方法选，看当前要跑一公里哪个用的时间最短就选谁，选了谁，谁所跑的公里数增加l，下面要检查的时间段就是他的下一段……如此反复直到25公里分配完为止。
对于每个运动员跑各公里所用的时间不一定要单独计算出来，如它跑第5公里所用的时间等于他连续跑完5公里所用的时间减去他连续跑4公里所用的时间。
本题所用的贪心策略就是：
先分配每个运动员跑一公里；剩下的20公里始终选择所有运动员当中下一公里跑的时间最短的，直到分配完。
这样局部的最优保证整体的最优。
3.9 线性存储问题
源程序名
storage.???（pas, c, cpp）
可执行文件名
storage.exe
输入文件名
storage.in
输出文件名
storage.out
【问题描述】
磁带等存储介质存储信息时基本上都是一种线性存储的方式，线性存储方式虽然简单，但查询检索时往往要经过一些其它信息，不象磁盘等存储介质在目录区找到后可直接定位到某一区城，因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点，现在仍然在使用。
如果有n段信息资料要线性存储在某种存储介质上，它们的长度分别是L1，L2，…，Ln，存储介质能够保存下所有这些信息，假设它们的使用(查询检索)的频率分别是F1，F2，…，Fn，要如何存储这些信息资料才能使平均检索时间最短。
你的任务就是编程安排一种平均检索时间最短的方案。
【输入】
第一行是一个正整数n(n&10000)，接下来是n行数据，每行两个整数分别是第1段信息的长度(1到10000之间)和使用的频率(万分比，在0到9000之间)，总的频率之和为10000。
所输入数据均不要判错。
【输出】
依次存储信息段的编号。每个数据之间用一个空格隔开。
【样例】
storage.in
storage.out
12 2500
【算法分析】
根据统计的基本原理，n段信息资料的使用（查询检索）的频率之和应为1，即F1+F2+…+Fn=1，如果总的检索次数为m，第I段信息资料使用的次数为m*Fi，设平均检索速度为v单位长度/单位时间，而它的长度为Li，每次所用的时间为Ti-1+Li/V，其中Ti-1为通过安排在第I个信息段前面的所有信息所要的时间，访问信息段I所有次数总的时间时：
m*Fi*(Ti-1+Li/v)。
因为上表达式中m、v可看作是常数，所以单一访问时间Fi与Li及前面的安排有关，每段信息均是这样，由此我们可采用如下的贪心方法：
根据(频率*长度)进行由大到小的排序，然后根据这个排序安排某一信息段在相应位置，从而得到的总的检索时间最短，也就是平均检索时间最短。
3.10扇区填数
源程序名
fan.???（pas, c, cpp）
可执行文件名
fan.exe
输入文件名
fan.in
输出文件名
fan.out
【问题描述】
有一个圆，当输入一个整数n(1≤n≤6)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。
向各个扇区放入数之后，你可以从单个扇区中选出―个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列，：1，2，3，…，i，你的任务是使i尽可能地大。
【输入】
只一个整数n(1&＝n&＝6)。
【输出】
第一行是最大的i，接下来的几行是所有能达到最大i的填法。
由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从1，开始输出(因为连续数里要有1，所以所填的数中肯定有1)。
【样例】
1
【算法分析】
假设圆已经被分成了n个扇区，并且已经在这n个扇区中填好了数字，先来看看填好数字后最多有多少种选择连续的数字并求和的方法，以N＝4为例：
单独选一个，有n种即1、2、3、4；
选择相邻两个也有n种即12、23、34、41
选择相邻三个也有n种即123、234、341、412；
选择相邻四个只有一种即1234。
总共有n*(n-1)+1种，当n=4时有13种。
如果每一种选择所求的和都不同，那么能够构成的最多有n*(n-1)+1个不同的数。我们当然希望能够达到的最大的连续数就是从1到n*(n-1)+1了，如N=4时就是1到13。
现在的问题是如何保证这n*(n-1)+1个数就是从1到n*(n-1)+1。在填数时首先填1，接下来的n-1个数都保证不同且最小为2，再看其他的取相邻的多个数的情况了。在n&＝6的情况下都能满足这个要求，对于n&6时就不一定了。
从这种最优策略出发，再结合回溯法找出所有可能的情况。
分治
4.1 取余运算
源程序名
mod.???（pas, c, cpp）
可执行文件名
mod.exe
输入文件名
mod.in
输出文件名
mod.out
【问题描述】
输入b，p，k的值，求b p mod k的值。其中b，p，k*k为长整型数。
【样例】
2^10 mod 9=7
【知识准备】
进制转换的思想、二分法。
【算法分析】}
时间： 16:35:59
&&&& 阅读：90
&&&& 评论：
&&&& 收藏：0
标签：24点游戏计算器 （简单四则运算）（c++）:https://github.com/liuxinig/cpp_1001/blob/master/24dian_siZeIN.txt
1 //24点统计
3 #include &iostream&
4 #include &cmath&
5 using namespace
6 #define N 14
7 //a数组存四个数字
8 int cixu[3],fuHao[3],p[N],sum = 0;
9 float a0[4],a[4],b[4],b0[4];
10 float zuhe[24][4];
12 各数组代表含义
13 cixu 记录运算符调用次序
15 a数组存初始的四个数
17 fuHao 存整合后的运算符顺序
19 b数组存整合后的数的计算次序
21 b0数组为用户输入的四个数
23 P数组各下标位置所代表的含义:
24 0,1,2,3:四个数是否需要阶乘（1），导数（2），或不变（0）
25 4，5,6：三个运算符
26 7,10:括号1位置
27 8,9:括号2位置
28 11:括号1是否需要阶乘或求导
29 12：括号2是否需要阶乘或求导
32 float qiuZhi(float x,float y,int f)
switch (f)
return x +
return x -
return x *
if(y == 0)
return -1;
return x /
if(x == 0)
return -1;
return y /
return y -
55 bool jiSuan()
int i,w = 0;
float b1,b2;
for(i = 0;i & 3;i++)
if(i == 0)
b1 = qiuZhi(b[w],b[w + 1],fuHao[0]);
if(b1 == -1)
return false;
if(abs(cixu[0] - cixu[1]) == 1)
b1 = qiuZhi(b1,b[w],fuHao[i]);
if(b1 == -1)
return false;
b2 = qiuZhi(b[2],b[3],fuHao[1]);
if(b2 == -1)
return false;
b1 = qiuZhi(b1,b2,fuHao[2]);
if(b1 == 24)
return true;
return false;
93 //返回除数与被除数的顺序，是左边为除数还是右边为除数
4代表左边为除数，3代表右边为除数
94 int fuHaoPD(int t1,int t2)
int t = p[t1 + 3];
if(t == 0 || t == 2)
else if(t == 3)
if(t2 != 0 && cixu[t2] & cixu[t2 - 1] && abs(cixu[0] - cixu[1]) != 2)
else if(t == 1)
if(t2 != 0 && cixu[t2] & cixu[t2 - 1] && abs(cixu[0] - cixu[1]) != 2)
113 //构造表达式 （根据找到的计算次序构造出从左到右的计算式）
114 void zhengHe()
int w1 = 0,w2 = 0;
for(int i = 0;i & 3;i++)
switch (cixu[i])
if(a[0] != -1)
b[w1] = a[0];
a[0] = -1;
if(a[1] != -1)
b[w1] = a[1];
a[1] = -1;
fuHao[w2] = fuHaoPD(1,i);
if(a[1] != -1)
b[w1] = a[1];
a[1] = -1;
if(a[2] != -1)
b[w1] = a[2];
a[2] = -1;
fuHao[w2] = fuHaoPD(2,i);
if(a[2] != -1)
b[w1] = a[2];
a[2] = -1;
if(a[3] != -1)
b[w1] = a[3];
a[3] = -1;
fuHao[w2] = fuHaoPD(3,i);
179 //查找计算顺序（即三个运算符的运算次序
类似123 213 321 ...）
180 void ciXu()
int i,j,k,l,w = 0;
//若有括号
if(p[8] != 0 || p[7] != 0)
if(p[8] != 0)
//如果有括号1
cixu[w] = p[8];
//第一计算次序为括号1的表达式
if(p[7] != 0)
//如果还有括号2
if(p[10] - p[7] & 1)
//如果括号2为大括号
{//大括号中没在小括号的运算符为第二计算次序
if(p[7] == p[8])
//如果两括号起始位置相同，则第二运算次序为小括号加一
cixu[w] = p[8] + 1;
//否则为减一
cixu[w] = p[8] - 1;
//如果括号2为小括号
cixu[w] = p[7];
cixu[w] = 6 - cixu[0] - cixu[1];
//最后一个没在括号中的运算符
运算符顺序分别为 1,2,3 和为6
最后一个为 6 - （第一个） - （第二个）
//如果没有括号2
if(cixu[0] == 2)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 1;
cixu[1] = 1;
cixu[2] = 3;
else if(cixu[0] == 1)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 3;
if(p[4] & 1)
cixu[1] = 1;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 1;
//如果只有大括号
for(i = p[7] - 1;i & p[10] - 1;i++)//括号中
if(p[4 + i] & 1)
cixu[w] = i + 1;
for(i = p[7] - 1;i & p[10] - 1;i++)//括号中
if(p[4 + i] & 2)
cixu[w] = i + 1;
if(p[7] == 1)
cixu[w] = 3;
cixu[w] = 1;
// 没有括号
for(i = 0;i & 3;i++)
if(p[4 + i] & 1)
cixu[w] = i + 1;
if(w == 0)
cixu[0] = 1;
cixu[1] = 2;
cixu[2] = 3;
else if(w == 1)
if(cixu[0] == 2)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 1;
cixu[1] = 1;
cixu[2] = 3;
else if(cixu[0] == 1)
if(p[6] & 1)
cixu[1] = 3;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 3;
if(p[4] & 1)
cixu[1] = 1;
cixu[2] = 2;
cixu[1] = 2;
cixu[2] = 1;
else if(w == 2)
cixu[w] = 6 - cixu[1] - cixu[0];
334 //判断某表达式是否符合
335 bool panDuan()
zhengHe();
if(jiSuan() == true)
return true;
return false;
344 void chuShiHua()
for(i = 0;i & 3;i++)
cixu[i] = 0;
a[i] = a0[i];
a[i] = a0[i];
355 //输出表达式到文件
356 void outPut()
for(i = 0;i & 4;i++)
if(p[7] == i + 1)
cout&&"(";
if(p[8] == i + 1)
cout&&"(";
cout&&a0[i];
if(p[9] == i + 1)
cout&&")";
if(p[10] == i + 1)
cout&&")";
if(i != 3)
switch (p[i + 4])
cout&&‘+‘;break;
cout&&‘-‘;break;
cout&&‘*‘;break;
cout&&‘/‘;break;
cout&&"=24"&&
394 void chuLi()
int i,i1,i2,i3,i4,l1,l2,l3,l4,m,n,q,r,t;
for(i = 0;i & N;i++)
//初始化p数组为0
for(l1 = 0;l1 & 4;l1++)
for(l2 = 0;l2 & 4;l2++)
for(l3 = 0;l3 & 4;l3++)
p[4] = l1;
p[5] = l2;
p[6] = l3;
for(m = 0;m & 4;m++)
if(m == 1)
else if(m == 2)
else if(m == 3)
for(n = 0;n & 4;n++)
if(n == 1 && m != 3)
p[10] = 3;
else if( n == 2 && m != 1)
p[10] = 4;
else if(n == 3 && m == 1)
p[10] = 4;
else if(n == 0)
p[10] = 0;
chuShiHua();
if(panDuan() == true)
475 bool chongZhi(int &w)
for(i = 0;i &i++)
flag = true;
for(j = 0;j & 4;j++)
if(zuhe[i][j] != zuhe[w][j])
flag = false;
if(flag == true)
return true;
return false;
491 void zuHe()
int i,j,k,l,w = 0,s;
for(i = 0;i & 4;i++)
for(j = 0;j & 4;j++)
for(k = 0;k & 4;k++)
for(l = 0;l & 4;l++)
if(i != j && i != k && i != l && j != k && j != l && k != l)
zuhe[w][0] = b0[i];
zuhe[w][1] = b0[j];
zuhe[w][2] = b0[k];
zuhe[w][3] = b0[l];
if(chongZhi(w) == true)
for(s = 0;s & 4;s++)
a0[s] = zuhe[w][s];
517 void main()
cout&&"请输入四个数：";
cin&&b0[0]&&b0[1]&&b0[2]&&b0[3];
cout&&"共"&&sum&&"种"&&
24dian_siZe
&标签：原文地址：http://www.cnblogs.com/liuxinig/p/5874947.html
&&国之画&&&& &&&&chrome插件&&
版权所有 京ICP备号-2
迷上了代码！扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
有一种玩24点的游戏，给你4个数-2,3,4,6，可通过加减乘除运算符号将这4个数写成一个算式（每个数只能使用一次，且必须用一次）使计算结果等于24，你能写出几个式子？试一试求解答，在线等！！！快！
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
3*6+4-(-2)=24
还在吗？这种我写了，请问还有吗？我写了你这种还有（-2+3）*4*6=24
[6+(-2)+4]*3=24
为您推荐：
扫描下载二维码全国青少年信息学奥林匹克联赛培训习题与解答-共享资料网
全国青少年信息学奥林匹克联赛培训习题与解答
全国青少年信息学奥林匹克联赛培训习题与解答
（中学高级本）
目录
习题篇 与 解析篇
第一章 回溯法
1.1 马拦过河卒
1.2 出栈序列统计
1.3 算24点
1.4 冗余依赖
1.5 走迷宫
单向双轨道
1.7 组合的输出
1.8 售货员的难题
1.9 驾车旅游
关路灯
第二章 递规与递推
2.1 遍历问题
2.2 产生数
2.3 出栈序列统计
2.4 计数器
2.5 诸侯安置
2.6 括号序列
2.7 新汉诺塔
2.8 排序集合
2.9 青蛙过河
编码
第三章 贪心法
3.1 排队接水
3.2 智力大冲浪
3.3 取火柴游戏
3.4 加工生产调度
3.5 最大乘积
3.8 马拉松接力赛
3.9 线性存储问题
扇区填数
第四章
4.1 取余运算
4.2 地毯填补问题
4.3 平面上的最接近点对
4.4 求方程的根
4.5 小车问题
4.6 黑白棋子的移动
4.7 麦森数（NOIP2003）
4.8 旅行家的预算(NOIP1999)
4.9 飞行计划
第五章 图
5.1 医院设置
5.2 工程规划
5.3 服务器储存信息问题
5.4 间谍网络(AGE)
5.5 宫廷守卫
5.6 K-联赛
5.7 机器调度
5.8 公路修建
5.9 速度限制
第六章
6.1 排序二叉树
6.2 树的重量
6.3 信号放大器
6.4 “访问”术馆
6.5 聚会的快乐
6.6 重建道路
6.7 有线电视网
第七章
7.1 最多因子数
7.2 黑白棋游戏
7.3 纵横填字游戏
7.4 魔术数字游戏
7.6 三维扫描
7.7 拼字游戏
7.8 公路修建
7.9 单词游戏
第八章
尼克的任务
三角形牧场
分组
第九章 数学问题
9.1 多项式展开系数
9.3 盒子与球
9.4 取数游戏
9.5 磁盘碎片整理
9.6 欧几里德的游戏
9.7 百事世界杯之旅
9.9 班级聚会
第十章
10.2 木棍加工
10.3 三角形
10.4 多边形面积
10.5 网线切割
10.6 最接近的分数
10.7 切孔机
10.8 栓狗方案
10.9 城市街道交通费系统
回溯法
1.1
马拦过河卒
源程序名
knight.???（pas, c, cpp）
可执行文件名
knight.exe
输入文件名
knight.in
输出文件名
knight.out
【问题描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
【输入】
一行四个数据，分别表示B点坐标和马的坐标。
【输出】
一个数据，表示所有的路径条数。
【样例】
knight.out
6
【算法分析】
从起点开始往下走(只有两个方向可以走)，如果某个方向可以走再继续下一步，直到终点，此时计数。最后输出所有的路径数。这种方法可以找出所有可能走法，如果要输出这些走法的话这种方法最合适了，但是本题只要求输出总的路径的条数，当棋盘比较大时，本程序执行会超时，此时最好能找出相应的递推公式更合适，详见后面的递推章节。
1.2 出栈序列统计
stack1.???（pas, c, cpp）
可执行文件名
stack1.exe
输入文件名
stack1.in
输出文件名
stack1.out
【问题描述】
栈是常用的一种数据结构，有n令元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两?种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
【输入】
一个整数n（1&=n&=15）
【输出】
一个整数，即可能输出序列的总数目。
【样例】
stack1.out
5
【算法分析】
先了解栈的两种基本操作，进栈push就是将元素放入栈顶，栈顶指针上移一位，等待进栈队列也上移一位，出栈pop是将栈顶元素弹出，同时栈顶指针下移一位。
用一个过程采模拟进出栈的过程，可以通过循环加递归来实现回溯：重复这样的过程，如果可以进栈则进一个元素，如果可以出栈则出一个元素。就这样一个一个地试探下去，当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
1.3 算24点
point24.???（pas, c, cpp）
可执行文件名
point24.exe
输入文件名
point24.in
输出文件名
point24.out
【问题描述】
几十年前全世界就流行一种数字游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1~9之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(2*2)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1、2、3、7，则一种可能的解答是1+2+3*7=24。
【输入】
只有一行，四个1到9之间的自然数。
【输出】
如果有解的话，只要输出一个解，输出的是三行数据，分别表示运算的步骤。其中第一行是输入的两个数和一个运算符和运算后的结果，第二行是第一行的结果和一个输入的数据、运算符、运算后的结果；第三行是第二行的结果和输入的一个数、运算符和“=24”。如果两个操作数有大小的话则先输出大的。
如果没有解则输出“No answer!”
【样例】
point24.in
point24.out
21+3=24
【算法分析】
计算24点主要应用四种运算．开始状态有四个操作数，一个运算符对应两个操作数，所以一开始选择两个操作数分别对四个操作符进行循环检测，每一次运算后产生了新的数，两个数运算变成一个数，整体是少了一个操作数，所以四个数最终是三次运算。由于操作的层数比较少(只有三层)，所以可以用回溯的算法来进行检测，当找到一个解时便结束查找。如果所有的情况都找过后仍然没有，则输出无解的信息。
1.4 冗余依赖
redund.???（pas, c, cpp）
可执行文件名
redund.exe
输入文件名
redund.in
输出文件名
redund.out
【问题描述】
在设计关系数据库的表格时，术语“函数依赖”（FD）被用来表示不同域之间的关系。函数依赖是描述一个集合中的域的值与另一个集合中的域的值之间的关系。记号X-&Y被用来表示当集合X中的域被赋值后，集合Y的域就可以确定相应的值。例如，一个数据表格包含“社会治安编号”（S）、“姓名”（N）、“地址”（A）、“电话”（P）的域，并且每个人都与某个特定的互不相同的S值相对应，根据域S就可以确定域N、A、P的值。这就记作S-&NAP。
写一个程序以找出一组依赖中所有的冗余依赖。一个依赖是冗余的是指它可以通过组里的其他依赖得到。例如，如果组里包括依赖A-&B、B-&C和A-&C，那么第三个依赖是冗余的，因为域C可以用前两个依赖得到（域A确定了域B的值，同样域B确定了域C的值)。在A-&B、B-&C、C-&A、A-&C、C-&B和B-&A中，所有的依赖都是冗余的。
现在要求你编写一个程序，从给定的依赖关系中找出冗余的。
【输入】
输A的文件第一行是一个不超过100的整数n，它表示文件中函数依赖的个数。从第二行起每一行是一个函数依赖且互不重复，每行包含用字符“-”和“&”隔开的非空域列表。列表月包含大写的字母，函数依赖的数据行中不包括空格和制表符，不会出现“平凡”冗余依赖（如A-&A）。虽然文件中没有对函数依赖编号，但其顺序就是编号1到n。
【输出】
每一个冗余依赖，以及其他依赖的一个序列以说明该依赖是冗余的，先是一个FD，然后是依赖函数号，接着是&is redundant using FDs：”最后是说明的序列号。
如果许多函数依赖的序列都能被用来说明一个依赖是冗余的，则输出其中最短的证明序列。如果这些函数依赖中不包含冗余依赖，则输出“No redundant FDs”信息。
【样例1】
redund.out
redund.out
FD 3 is redundant using FDs: 1 2
FD 3 is redundant using FDs: 1
{即C可以通过1、2得到}
FD 5 is redundant using FDs: 4 6 2
【算法分析】
一个依赖冗余，就是说它可以由其他依赖推导出来。如何判断一个依赖能否被其他依赖推导出来呢？假设判断的依赖为“a-&b”，先找出所有形式为“a-&*”的依赖，再由*开始找相关依赖，直到出现“#-&b”为止(这里a、b、*、#都表示任意一个域名)。
如何实现这种查找呢？可以通过筒单的回溯来完成。只是找出冗余(如果有的话)还不说明工作就已结束，要到找出所有的能够推导出b的依赖序列，选出其中长度最短的(最短的也可能并不惟一，因此本题答案有可能并不惟一)，最短的证明序列中一定不存在多余的依赖，如果不是最短的证明序列，那么该证明序列中就有可能还有冗余依赖。
1.5 走迷宫
maze.???（pas, c, cpp）
可执行文件名
maze.exe
输入文件名
maze.in
输出文件名
maze.out
【问题描述】
有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。
【输入】
第一行是两个数m，n(1&m，n&15)，接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。
【输出】
所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一&”表示方向。
如果没有一条可行的路则输出-1。
【样例】
1 0 0 1 0 1
1 1 1 1 1 1
0 0 1 1 1 0
1 1 1 1 1 0
1 1 1 0 1 1
maze.out
(1,2)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(3,4)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(2,4)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(3,4)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(3,4)-&(2,4)-&(2,5)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(3,4)-&(3,5)-&(4,5)-&(5,5)-&(5,6)
(1,1)-&(2,1)-&(2,2)-&(2,3)-&(3,3)-&(4,3)-&(4,4)-&(4,5)-&(5,5)-&(5,6)
【算法分析】
用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
对应的位置为：(x-1, y)，(x, y+1)，(x+1, y)，(x, y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。
这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路}
for i:＝1 to 4 do{分别对4个点进行试探}
先记住当前点的位置，已走过的情况和走过的路；
如果第i个点(xl，y1)可以走，则走过去；
如果已达终点，则输出所走的路径并置有路可走的信息，
否则继续从新的点往下查找search(xl，y1，b1，p1)；
end；
【思考与提高】
该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想――换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。
有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”――明显无用的节点可以先行“剪掉”，从而提高搜索速度。
1.6 单向双轨道
track.???（pas, c, cpp）
可执行文件名
track.exe
输入文件名
track.in
输出文件名
track.out
【问题描述】
如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。
从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新位置。或者输出‘NO’表示不能完成这样的调度。
【输入】
一个数n(1&n&27)及由n个小写字母组成的字符串。
【输出】
可以调度则输出最短的调度序列，不可以调度时则输出‘NO’。
【样例】
c B D
【算法分析】
这是一道类似于栈的操作题目，只不过是有两个栈B和C可以操作，而对于A序列里的元素，既可以进入B，也可以进入C，或直接到D。解决问题可以从D序列出发反过来看，当前要到D的字符在哪里，如果在A，再看它前面有没有字符，如果有，先让它们进栈(B或C)，否则直接到D；如果在B，看是否是栈顶元素，如果是，直接到D，否则将上面的字符进C；如果在C，看是否是栈顶元素，如果是，直接到D，否则无法进行操作，因为只能向右不能向左，这时要回溯。如果所有的情况都检测过，某个字符不能进行到D的操作，则输出无解信息。
由于A里的非直接进入D的字符可以进入B或C，可以跟二进制建立起对应关系，将所有情况列举一遍，再找出其中步骤最少的输出。
1.7 组合的输出
track.???（pas, c, cpp）
可执行文件名
track.exe
输入文件名
track.in
输出文件名
track.out
【问题描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r&＝n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n＝5，r＝3，所有组合为：
3 4 5
【输入】
一行两个自然数n、r(1&n&21，1&＝r&＝n)。
【输出】
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
【样例】
compages.in
compages.out
3 4 5
【算法分析】
如果通过循环加递归来实现回溯比较简单，相应程序为：
const max=20;
var a:array[0..max]
n,r:1..
procedure compages(k:integer);{选取第k个元素}
begin
{当前所选元素最小为前一个元素加1，最大为n-(r-k)，因为后面还有(r-k)个元素要选取，至少为每次选取留一个}
for i:=a[k-1]+1 to n-(r-k) do begin
{选取一个元素}
if k=r then begin
for j:=1 to r do write(a[j]:3);
else compages(k+1);
readln(n,r);
compages(1);
{从第一个元素开始选取给合数}
end.
本题要求不用递归来实现回溯，关键要定好回溯的条件。如果选取第i个元素时选择了a[i]，根据输出条件应有a[i]-i&＝n-r，如果不满足这个条件说明当前第i个元素已再无数可取，要进行回溯，将其值减1，退到上一步将上一步原来的值再增加1，重复上述过程。当全部选取完时，i回到了0，a[0]的值增加1后变为1，这是整个选取过程结束的条件。
1.8 售货员的难题
salesman.???（pas, c, cpp）
可执行文件名
salesman.exe
输入文件名
salesman.in
输出文件名
salesman.out
【问题描述】
某乡有n个村庄(1&n&40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0&s&1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
【输入】
村庄数n和各村之间的路程(均是整数)。
【输出】
最短的路程。
【样例】
salesman.in
salesman.out
{村庄1到各村的路程}
{村庄2到各村的路程}
{村庄3到各村的路程}
【算法分析】
题目给定的村庄数不多(≤40)，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。
用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果step＝n，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的村庄号)。
1.9 驾车旅游
tour.???（pas, c, cpp）
可执行文件名
tour.exe
输入文件名
tour.in
输出文件名
tour.out
【问题描述】
如今许多普通百姓家有了私家车，一些人喜爱自己驾车从一个城市到另一个城市旅游。自己驾车旅游时总会碰到加油和吃饭的问题，在出发之前，驾车人总要想方设法得到从一个城市到另一个城市路线上的加油站的列表，列表中包括了所有加油站的位置及其每升的油价(如3.25元/L)。驾车者一般都有以下的习惯：
（1）除非汽车无法用油箱里的汽油达到下一个加油站或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来；
（2）在第一个停下的加油站总是将油箱加满；
（3）在加油站加油的同时，买快餐等吃的东西花去20元。
（4）从起始城市出发时油箱总是满的。
（5）加油站付钱总是精确到0.1元(四舍五入)。
（6）驾车者都知道自己的汽车每升汽油能够行驶的里程数。
现在要你帮忙做的就是编写一个程序，计算出驾车从一个城市到另一个城市的旅游在加油和吃饭方面最少的费用。
【输入】
第一行是一个实数，是从出发地到目的地的距离(单位：km)。
第二行是三个实数和一个整数，其中第一个实数是汽车油箱的最大容量(单位：I。)；第二个实数是汽车每升油能行驶的公里数；第三个实数是汽车在出发地加满油箱时的费用(单位元)；一个整数是1到50间的数，表示从出发地到目的地线路上加油站的数目。
接下来n行都是两个实数，第一个数表示从出发地到某一个加油站的距离(单位：km)；第二个实数表示该加油站汽油的价格(单位：元)。
数据项中的每个数据都是正确的，不需判错。一条线路上的加油站根据其到出发地的距离递增排列并且都不会大于从出发地到目的地的距离。
【输出】
就一个数据，是精确到0.1元的最小的加油和吃饭费用
【样例】
365
【算法分析】
驾车者从出发地出发后对于每个加油站都可能有两种操作，一是进去加油买食品，二是不进去继续前行(如果当前汽车的余油可以的话)，这样有n个加油站最多可能有2n种选择。由于加油站数目不太多，可以采用回溯的算法来解决问题。从第一个加油站开始，依次选择所要停下的下一个加油站，从而找出总费用最少的方案，加油站数目最多为50，这样回溯不会进行得很深。在选择下一个要停下的加油站时比较麻烦，不能完全一个一个地试过去，这样时间太长。可以用这样的方法：先找出第一个要停下的加油站，判断其后面的加油站是否可以到达，如果不可到达就必须在这里停下来加油；否则就找出可以到达但如果只用一半汽油则无法到达的所有加油站，依次进行停靠。
1.10关路灯
power.???（pas, c, cpp）
可执行文件名
power.exe
输入文件名
power.in
输出文件名
power.out
【问题描述】
某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。
【输入】
文件第一行是两个数字n(0&n&50，表示路灯的总数)和c(1&＝c&=n老张所处位置的路灯号)；
接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。
【输出】
一个数据，即最少的功耗(单位：J，1J＝1W?s)。
【样例】
{此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序}
8 10
【算法分析】
设老张开始所在位置为c，以起始点c为分界点，算出左右两部分总的功率p_left和p_right，再来分别看向左与向右的情况。
向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_left+w[i])*t，增加的功为p_right*2t。
向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_righ+w[i])*t，增加的功为p_left*2t。
比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，但不能求出所有情况下最佳的解。
对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变化都跟上面所述一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左与向右的情况，在所有可能的情况中找出最优解。
【思考与提高】
上面的程序运算的范围很有限，当n比较大时就会栈溢出，如n&30时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：
最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种；
最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。
如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。
第二章 递规与递推
2.1 遍历问题
travel.???（pas, c, cpp）
可执行文件名
travel.exe
输入文件名
travel.in
输出文件名
travel.out
【问题描述】
我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
【输入】
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，第二行表示该二叉树的后序遍历结果s2。
【输出】
输出可能的中序遍历序列的总数，结果不超过长整型数。
【样例】
trave1.out
bca
【算法分析】
根据二叉树先序遍历和后序遍历的特点，可以知道，先序遍历的第一个结点是后序遍历的最后一个结点，对于中序遍历来说却是中间的一个结点，这里所说的中间也只是相对而言的中间。如果一棵二叉树的根结点没有左子树，那么先序遍历的第一个结点也是中序遍历的第一个结点，如果一棵二叉树的根结点没有右子树，那么先序遍历的第一个结点是中序遍历的最后一个结点。我们这里还认为就是中序遍历的中间结点，上面两种情况只是特殊的情况。
设二叉树的结点总数为n(对于输入的字符串来说是它的长度)，对于先序遍历的结果，第一个结点为根结点，从第二个结点到最后一个结点分为n种情况：
根结点的左子树结点个数为n-1，右子树结点的个数为0；
根结点的左子树结点个数为n-2，右子树结点的个数为1；
……
根结点的左子树结点个数为n-i，右子树结点的个数为i-1；{0&＝i&=n-1)；
……
根结点的左子树结点个数为0，右子树结点的个数为n-1。
根据这n种情况，分别将二叉树拆分为左子树和右子树，左子树结点个数为n-i，右子树结点的个数为i-l(0&＝i&＝n-1)，先序遍历的结果是从第二个结点(字符)开始取，而后序遍历的结果里是从第1个结点字符开始取。也就是说对于每一种情况，分两步处理：第一步在先序遍历和后序遍历的结果里取左子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目；第二步在先序遍历和后序遍历的结果里取右子树，看是否符合规则，统计这部分可能有的中序遍历的结果数目。这两步都递归调用了统计过程，不再递归调用的条件就是当统计的是空树或只有一个结点的树，这时返回的值是可能有的中序遍历结果数目。
结合“分类相加原理”和“分步相乘原理”，可以得到下面的递归函数：
Function count (先序结果first，后序结果last : string) :
Len:=遍历结果的长度；
如果len为0或1，则返回结果即count:=l
t为当前统计后符合条件的数目，初值为0；
分类统计for i:=len-1 downto 0 do
在first中取出长度为i的左子树结果LF；
在last中取出长度为i的左子树结果LL；
在first中取出长度为len-1-i的左子树结果RF；
在last中取出长度为len-1-i的右子树结果RL；
如果LF、LL符合基本规则(LF的首字符跟LL的尾字符相同、LF中，所有的
字符在LL中也都有)
并且RF、RL也符合基本规则，那么
t:=t+count(LF，LL)*count(RF，RL);
{分步相乘、分步相加}
{这里count函数中递归调用了count}
返回值为t即count:=t;
其中，检查先序结果和后序结果两个字符串是否符合基本规则，可以再通过一个函数来实现：
function check(先序字符串F，后序字符串L)：boolean；
如果F的首字符不等于L的尾字符则check:=
从F的第二个字符取到最后一个字符，如果该字符不在L中，则check:=
【思考与提高】
上面的算法通过递归，结合统计的基本原理“分步相乘，分类相加”，从而统计出所有可能解的个数，如果输入的两个字符串没有解，上述算法同样能得到结果。
在肯定有解的情况下，上述算法最终可以递归调用到0、1个结点，如果有多组解，那么调用到两个结点时，如先序为ab、后序为ba，此时有可能有如下两种结构：
a
这两种结构的中序遍历结果分别为：ba、ab，有两种。
根据分步相乘的原理，对比两个字符串，每出现一次如上的情况，可能有的结构数目(结构不同，中序遍历结果也不同，因此可能有的二叉树结构的数目就是可能有的中序遍历结果数目)就乘以2一次，最终得到总的数目。这也可以理解为一种递推的方法。
从这里可以看到，在肯定有解的情况下，给定先序遍历的结果和后序遍历的结果，可能有2n种可能的结构，也就是中序遍历可能得到2n种不同的结果，其中n&＝0。那么这里的n最大可能是多少呢？可以证明n的最大值为字符串的长度加1整除2。
递推的程序如下：
Program travel(intput,output);
Var
Total,I,m:
S1,s2:
Assign(input,’travel.in’);
Assign(output,’travel.out’);
Reset(input);
rewrite(output);
Readln(s1);
readln(s2);
For i:=1 to length(s1)-1 do
M:=pos(s1[i],s2);
If m&1 then if s[i+1]=s[m-1] then total:=total*2;
Writeln(total);
close(iinput);
close(output);
2.2 产生数
build.???（pas, c, cpp）
可执行文件名
build.exe
输入文件名
build.in
输出文件名
build.out
【问题描述】
给出一个整数n(n&1030)和m个变换规则(m≤20)。
约定：一个数字可以变换成另一个数字，规则的右部不能为零，即零不能由另一个数字变换而成。而这里所说的一个数字就是指一个一位数。
现在给出一个整数n和m个规则，要你求出对n的每一位数字经过任意次的变换(0次或多次)，能产生出多少个不同的整数。
【输入】
共m+2行，第一行是一个不超过30位的整数n，第2行是一个正整数m，接下来的m行是m个变换规则，每一规则是两个数字x、y，中间用一个空格间隔，表示x可以变换成y。
【输出】
仅一行，表示可以产生的不同整数的个数。
【样例】
2 3
【算法分析】
如果本题用搜索，搜索的范围会很大(因为n可能有30位!)，显然无法在规定的时间内出解。而我们注意到本题只需计数而不需要求出具体方案，所以我们稍加分析就会发现，可以用乘法原理直接进行计数。
设F[i]表示从数字i出发可以变换成的数字个数(这里的变换可以是直接变换，也可以是间接变换，比如样例中的1可以变换成2，而2又可以变换成3，所以1也可以变换成3；另外自己本身不变换也是一种情况)。那么对于一个长度为m位的整数a，根据乘法原理，能产生的不同的整数的个数为：F[a[1]]*F[a[2]]*F[a[3]]*…*F[a[m]]。
下面的问题是如何求F[i]呢？由于这些变换规则都是反映的数字与数字之间的关系，所以定义一个布尔型的二维数组g[0..9，0..9]来表示每对数字之间是否可以变换，初始时都为False；根据输入的数据，如果数字i能直接变换成数字j，那么g[i，j]置为True，这是通过一次变换就能得到的；接下来考虑那些间接变换可得到的数字对，很明显：如果i可以变为k，k又可以变为j，那么i就可以变为j，即：
for k:=0 to 9 do
for i:=0 to 9 do
for j:=0 to 9 do
g[i,j]＝g[i,j]or(g[i,k] and g[k,j])；
最后还要注意，当n很大时，解的个数很大，所以要用高精度运算。
2.3 出栈序列统计
源程序名
stack.???（pas, c, cpp）
可执行文件名
stack.exe
输入文件名
stack.in
输出文件名
stack.out
【问题描述】
栈是常用的一种数据结构，有n个元素在栈顶端一侧等待进栈，栈顶端另一侧是出栈序列。你已经知道栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。现在要使用这两种操作，由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n，计算并输出由操作数序列1，2，…，n，经过一系列操作可能得到的输出序列总数。
【输入】
就一个数n(1≤n≤1000)。
一个数，即可能输出序列的总数目。
【样例】
5
【算法分析】
在第一章练习里，我们通过回溯的方法计算并输出不同的出栈序列，这里只要求输出不同的出栈序列总数目，所以我们希望能找出相应的递推公式进行处理。
从排列组合的数学知识可以对此类问题加以解决。
我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。
出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：
C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*…*(n+2)/n!。
考虑到这个数据可能比较大，所以用高精度运算来计算这个结果。
本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考《组合数学》等书。
【思考与提高】
我们知道，在某个状态下，所能做的操作(移动方法)无非有两种：
（1）将右方的等待进栈的第一个元素进栈；
（2）将栈顶的元素出栈，进入左边的出栈序列。
设此时右方、栈、左方的元素个数分别为a，b，c。我们就能用(a,b,c)表示出当前的状态。显然n=a+b+c，则c=n-a-b。即已知a和b，c就被确定，所以我们可以用(a,b)来作为状态的表示方法。则起始状态为(n,0)，目标状态为(0,0)。
又由上面的两种移动方法，我们可类似的得到两种状态转移方式：
再设f(a,b)为从状态(a,b)通过移动火车变为状态(0,0)的所有移动方法。类似于动态规划的状态转移方程，我们可写出以下递归式：
边界值：f(0,0)=1。
有了这个递归公式后，再写程序就比较简单了，请读者自己写出递归程序。
2.4 计数器
count.???（pas, c, cpp）
可执行文件名
count.exe
输入文件名
count.in
输出文件名
count.out
【问题描述】
一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0，1，2，…，9。其中―个页码不含多余的0，如N＝1234时第5页不是0005，只是5。
【输入】
一个正整数N(N≤109)，表示总的页码。
【输出】
共十行：第k行为数字k-1的个数。
【样例】
1
【算法分析】
本题可以用一个循环从1到n，将其拆为一位一位的数字，并加到相应的变量里，如拆下来是1，则count[1]增加1。这种方法最简单，但当n比较大时，程序运行的时间比较长。这种方法的基本程序段如下：
for i:=1 to n do begin
while j&0 do begin
count[j mod 10]:=count[j mod 10]+1;
j:=j div 10;
当n是整型数据时，程序执行的时间不会太长。而n是长整型范围，就以n是一个9位数为例，当i执行到8位数时，每拆分一次内循环要执行8次，执行完8位数累计内循环执行的次数为：
9*1+90*2+900*3+00*5+++
时间上让人不能忍受。
可以从连续数字本身的规律出发来进行统计，这样速度比较快，先不考虑多余的0的情况，假设从，这一万个连续的数，0到9用到的次数都是相同的，一万个四位数，0到9这十个数字共用了40000次，每个数字使用了4000次。
进一步推广，考虑所有的n位数情况，从n个0到n个9，共10n个n位数，0到9十个数字平均使用，每个数字共用了n*10n-1次。
有了这样的规律后，可以从高位向低位进行统计，最后再减去多余的0的个数。
以n=3657为例：(用count数组来存放0到9各个数字的使用次数)
最高位(千位)为3，从0千、1千到2千，000~999重复了3次，每一次从000到999，每个基本数字都使用了3*102＝300次，重复3次，所以count[0]～count[9]各增加3*300；
另外最高位的0到2作为千位又重复了1000次，count[0]～count[2]各增加1000，3作为千位用了657次(＝n mod 100)，因此count[3]增加657；
接下来对百位6再进行类似的处理，0到9在个位和十位平均重复使用6*20次，所以count[0]～count[9]先各增加6*20，0到5作为百位重复使用了100次，所以count[0]～count[5]再各增加100，6作为百位在这里重复用了57次(＝n mod 100)；因此count[6]增加57；
对十位和个位也进行相同的处理，得出count[0]~count[9]的值；
最后再减去多算的0的个数。
那么0到底多算了多少次呢?
当没有十位及以更高位时，个位的0，只多算了1次；
当没有百位及以更高位时，十位的0，多算了10次；
当没有千位及以更高位时，百位的0，多算了100次；
因此在统计m位数时，0多算了(11……1)这样一个全是1的m位数。
基本算法描述如下：
计算n的位数Len；
将n每一位上的数字存放到数组c里；
计算10的0次方到len-1次方并存放到数组b里；
i控制位数，for i:=len downto 1 do
0到9的使用次数增加平均使用的次数b[i-1]*(i-1)*c[i]；
0到c[i-1]的使用次数增加作为当前位使用的次数b[i-1]；
c[i]的使用次数增加n mod b[i-1]
最后减去多计算的0的个数；
输出结果。
2.5 诸侯安置
empire.???（pas, c, cpp）
可执行文件名
empire.exe
输入文件名
empire.in
输出文件名
empire.out
【问题描述】
很久以前，有一个强大的帝国，它的国土成正方形状，如图2―2所示。
这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地(正方形中的一格)。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图2―3为n＝3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。
国王自然不愿意看到他的诸侯们互相开战，致使国家动荡不安。
因此，他希望通过合理的安排诸侯所处的位置，使他们两两之间都不能攻击。
现在，给出正方形的边长n，以及需要封地的诸侯数量k，要求你求出所有可能的安置方案数。(n≤l00，k≤2n2-2n+1)
由于方案数可能很多，你只需要输出方案数除以504的余数即可。
【输入】
仅一行，两个整数n和k，中间用一空格隔开。
【输出】
一个整数，表示方案数除以504的余数。
【样例】
empire.out
4
【样例说明】
四种安置方案如图2-4所示。注意：镜面和旋转的情况属于不同的方案。
【算法分析】
重新描述一下问题，其实就是在一个边长为2n-1的正菱形(如上图2-2为n＝3的情形)上摆放k个棋子，使得任意两个棋子都不在同一行、同一列。试问：这样的摆法共有多少种?
看到这道题目，我们就会立即想起一道经典的老题目：n皇后问题。这道题目与n皇后问题非常相似。但有两个不同点：一是n皇后问题可以斜着攻击对方棋子，而本题不能；二是n皇后问题是在n，n的正方形棋盘上面放置k个皇后，而本题却是在一个正菱形上摆放。我们试着先将n皇后变为不可斜攻的，再作思考，如果不能够斜着攻击，n皇后的公式是：(C(k,n))2*k!。但是本题不是一个正方形，所以这个公式对本题好像没有任何帮助。看来只能够从另外一个角度思考问题了。
首先想到在2n-1列中任意取出k列进行具体分析，这样一来问题就转化成：有一个长为k的数列(无重复元素)，每一个数在一个不定的区间[a,b]当中，第i个数一定在区间[ai,bi]之间，求这样的数列有多少种?如果就是这个问题，那么比较难解决，但若把这个数列放在本题中，就比较简单。
因为题目中任意两个区间都是一种包含关系。可以先把区间按照长度排一下序，就可以看出来，再用乘法原理进行求解即可。但是，n最多可到100，k最多可到50，穷举要进行C(50,100)种方案!
显然无法在规定的时间内出解!那么怎么办呢?再继续分析一下问题发现，里面有重叠子问题。如果一个列作为最后一列，且这一列以及前面所有列共放置p个诸侯，设有q种情况，那么这一列后面的所有列共放置p+1个棋子的方案数都要用到q，从而引用乘法原理。而且在穷举过程中，这一个工作做了许多遍，所以干脆用递推。递推前，先把图形转化为类似图2-5的形式(即列排序)。
设f[i,j]表示以第i列为最后一列，放置j个棋子的总方案数，得出公式：
不过还要注意，当k≥2n-1时，问题无解。
2.6 括号序列
bracket.???（pas, c, cpp）
可执行文件名
bracket.exe
输入文件名
bracket.in
输出文件名
bracket.out
【问题描述】
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…， 和序列bl，b2，…， ，如果存在一组下标1≤i1&i2&…& ≤m，使得aj＝ 对一切1≤j≤n成立，那么a1，a2…， 就叫做b1，b2，…， 的子列。
【输入】
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
【输出】
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
【样例】
bracket.in
bracket.out
{最多的嵌套层数为1，如层数为2时的一种为()[()]}
【算法分析】
对于输入的括号序列字符串，从左向右进行查找，用一个数组来记录查找配对的情况，如果一个括号有相应的括号跟它对应，则将它标记为0，如果没有相应的括号跟它对应，则保存原子始代码的编号，“[]”分别为-1和1，“()”分别为-2和2。
因此对于读入的字符串，首先将其转换为相应的代码存放到数组里，为后面查找匹配做准备。
查找匹配时，可用这样的方法：
如果当前的字符是右括号，则跟前面的一个没有匹配的左括号对照，看是否匹配，如果匹配，则将两个字符标记为0，查找并定位到左边的第一个没有匹配的左括号(如果有的话)。如果当前的字符是左括号，则记住这个不匹配的左括号的位置，为后面找到右括号时匹配做准备。
从第一个字符开始到最后一个字符重复上面的过程，检查处理完毕。
输出时考虑到不增加嵌套的层数，以就近的原则，将出现不匹配的一个括号时，输出两个匹配的括号。
2.7 新汉诺塔
hanoi.???（pas, c, cpp）
可执行文件名
hanoi.exe
输入文件名
hanoi.in
输出文件名
hanoi.out
【问题描述】
设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。
现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。
移动时有如下要求：
?一次只能移一个盘；
?不允许把大盘移到小盘上面。
【输入】
文件第一行是状态中圆盘总数；
第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号；
第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。
【输出】
每行一步移动方案，格式为：move I from P to Q
最后一行输出最少的步数。
【样例】
move 1 from A to B
move 2 from A to C
move 1 from B to C
move 3 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to C
7
【算法分析】
要从初始状态到目标状态．就是要把每个圆盘分别移到自己的目标状态。
怎样才能保证总的移动步数最少呢?关键是首先考虑把编号最大的圆盘移到它的目标状态，因为编号最大的圆盘移到目标位置后就不再移动了，而在编号最大的圆盘没有移到目标之前，编号小的圆盘可能还要移动，即使它已在目标状态。所以编号最大的圆盘一旦固定，对以后的移动不会造成影响。最大的移动好后，再考虑剩余的没有到达目标状态的最大号圆盘……直到最小的编号为1的圆盘到目标状态为止。
设计一个移动过程：move(k,w)，表示把编号k的圆盘移到w柱。
2.8 排序集合
sort.???（pas, c, cpp）
可执行文件名
sort.exe
输入文件名
sort.in
输出文件名
sort.out
【问题描述】
对于集合N={1,2,…,n}的子集，定义一个称之为“小于”的关系：
设S1={X1,X2,…,Xi}，（X1&X2&…&Xi），S2={Y1, Y2, …,Yj}，（Y1&Y2&…&Yj），如果存在一个k，（0≤k≤min(i,j)），使得X1=Y1，…，Xk=Yk，且k=i或X(k+1)&Y(k+1)，则称S1“小于”S2。
你的任务是，对于任意的n(n≤31)及k(k&2n)，求出第k小的子集。
【输入】
输入文件仅一行，包含两个用空格隔开的自然数，n和k。
【输出】
输出文件仅一行，使该子集的元素，由小到大排列。空集输出0。
【样例】
1 2 3
【算法分析】
我们知道，n个元素构成的集合有2n种情况。本题的意思是：把这些集合按照某种规则排序，然后输入k，输出第k个集合。所以排序的规则是本题的关键，其实很简单，当n＝3时，8个集合排序如下：{}&{1}&{l,2}&{l,2,3}&{1,3}&{2}&{2,3}&{3}，你发现规律了吗?具体算法为：先推出第k小的一个子集的第一个数宇是多少，第一个数字确定了之后，再推出第二个数字，从第一个数字加1一直计算累加集合个数，直到得到不超过k的最大的那个数字，就是第二位数字，这样一直递推，推到最后一个。要注意：终止条件是有了n个数字或者第i个数字为空，这时递推终止，输出最后的结果。
2.9 青蛙过河
源程序名
frog.???（pas, c, cpp）
可执行文件名
frog.exe
输入文件名
frog.in
输出文件名
frog.out
【问题描述】
有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图2―5所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：
(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；
(2)青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D；
(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。
你的任务是对于给出的h，k，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
【样例】
{河中间有2个石礅，3个荷叶}
16 {最多有16只青蛙可以按照规则过河}
【算法分析】
结论为：f(h,k)=2h(k+1)
从具体到一般，推导过程如下：
f(0,k)=k+1;
（如k=3时，有4只青蛙可以过河）
f(1,k)=2(k+1);
（递推思想）
依此类推：f(2,k)=(2*(k+1))*2=22(k+1);
2.10电话号码
源程序名
phone.???（pas, c, cpp）
可执行文件名
phone.exe
输入文件名
phone.in
输出文件名
phone.out
【问题描述】
电话机上每一个数字下面都写了若干个英文字母。分布如下：
现在给定一个单词表和一串数字密码，请你用单词表中的单词翻译这个密码。
【输入】
第一行为一个正整数N表示单词表中单词的个数(N≤100)；
第二行为一个长度不超过100的数字串，表示密码；
接下来的N行，每行一个长度不超过20的单词，表示单词表。
【输出】
仅一行，表示翻译后的原文，如果密码无法翻译，则输出“No Solutions!”，如果密码有多种翻译方式，则输出任意一种即可。
【样例】
thi shs b boo k
k
【算法分析】
本题可以用递归搜索求解。首先，我们注意到一个数字串对应的单词是不惟一的，而反之，一个单词所对应的数字串却是惟一的!所以，我们一开始就读入一大串的数字密码和一些可以出现的单词，我们把每一个单词所表示的密码(是惟一的)存在数组中。然后从密码的开头开始扫描，得出密码的第一个单词有可能的情况，选择其中一种，得出第一个单词，得到除第一个单词以外的后面的子密码。然后用递归实现子密码的破译。若子密码无解，就可以换一种第一个单词的取法，再次试验。如果全是无解，那整个密码也是无解的。另外，首先要判断整个密码串是否是一个单词，避免无限递归。
encode.???（pas, c, cpp）
可执行文件名
encode.exe
输入文件名
encode.in
输出文件名
encode.out
【问题描述】
编码工作常被运用于密文或压缩传输。这里我们用一种最简单的编码方式进行编码：把一些有规律的单词编成数宇。
字母表中共有26个字母{a，b，…，z}，这些特殊的单词长度不超过6且字母按升序排列。把所有这样的单词放在一起，按字典顺序排列，一个单词的编码就对应着它在字典中的位置。
你的任务就是对于所给的单词，求出它的编码。
【输入】
仅一行，被编码的单词。
【输出】
仅一行，对应的编码。如果单词不在字母表中，输出0。
【样例】
encode.out
27
【算法分析】
对于输入的字符串，首先检查是否符合编码的条件：全是由小写字母组成并且前面的字母不会比后面的字母大。如果符合条件则进行编码，否则输出0。
编码时如果不找规律，可以根据顺序，从第一个符合条件的单词a开始往后构造，每构造一个，相应的编码增加1，直到构造到输入的字符串。
一个单词的后序单词类似于数字的进位，如十进制中8后面是9，9后面是10――进位的情况，再如99后面是100，199后面是200。而这里单词的规则是一串中后面的字符不比前面的大，所以z后是ab，az后是bc，……两个字符的单词最大的为yz，三个字符最小的为abc，最大的为xyz，……六个字符的单词最小的为abcdef，最大的为uvwxyz。
根据上面的进位规则进行构造，构造到输入的字符串时则输出相应的序号。
由此可以写出程序。
另外可以从数学上寻找递推的规则：
一个字符的单词有26个；
两个字符的单词有：25+24+23+…+1个；
{其中ab~az共25个，bc~bz共24个，cd~cz共23个…，yz共1个}
三个字符的单词有：
(24+23+22+…+1)+(23+22+21+…+1)+…+(2+1)+(1)个
xyz
四个字符的单词有：
((23+22+21+…+1)+(22+21+20+…+1)+…+(2+1)+(1))+
abcd~axyz
((22+21+20+…+1)+(21+20+…+1)+…+(2+1)+(1))+…+…+((1))个
wxyz
以此类推，得到相应的数学公式。
第三章 贪心法
3.1 排队接水
源程序名
water.???（pas, c, cpp）
可执行文件名
water.exe
输入文件名
water.in
输出文件名
water.out
【问题描述】
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
【输入】
输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
【输出】
输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
【样例】
3 2 7 8 1 4 9 6 10 5
56 12 1 99
291.90
【算法分析】
平均等待时间是每个人的等待时间之和再除以n，因为n是一个常数，所以等待时间之和最小，也就是平均等待时间最小。假设是按照1~n的自然顺序排列的，则这个问题就是求以下公式的最小值：
如果用穷举的方法求解，就需要我们产生n个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！
其实，我们认真研究一下上面的公式，发现可以改写成如下形式：
这个公式何时取最小值呢？对于任意一种排列k1, k2, k3, …, kn，当 ≤ ≤ ≤…≤ 时，total取到最小值。如何证明呢？方法如下：
假设i&j，而 & ，这是的和为total1，而把ki和kj互换位置，设新的和为total2，则：
我们发现上述△total恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。从而证明了我们的设想。
既然如此，我们就得到了一种最有贪心策略：把接水时间少的人尽可能排在前面。这样一样，问题的本质就变成：把n个等待时间按非递减顺序排列，输出这种排列，并求出这种排列下的平均等待时间。
3.2 智力大冲浪
源程序名
riddle.???（pas, c, cpp）
可执行文件名
riddle.exe
输入文件名
riddle.in
输出文件名
riddle.out
【问题描述】
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：
首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!
【输入】
输入文件riddle.in，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
【输出】
输出文件riddle.out，仅1行。表示小伟能赢取最多的钱。
【样例】
riddle.out
4 2 4 3 1 4 6
70 60 50 40 30 20 10
【算法分析】
因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢?应该放在第k个时段，因为放在1～k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请看下面的参考程序1。
本题也可以有另外一种贪心算法，即先把所有的数据按照结束时间的先后排序，然后从前向后扫描。
当扫描到第n个时段，发现里面所分配的任务的结束时间等于n-1，那么就说明在前面这些任务中必须舍弃一个，于是再扫描第1～n这n个时段，挑出一个最小的去掉并累加扣款值，然后再去调整排列顺序，让后面的元素填补前面的空缺，具体实现请看下面的参考程序2。
3.3 取火柴游戏
源程序名
match.???（pas, c, cpp）
可执行文件名
match.exe
输入文件名
match.in
输出文件名
match.out
【问题描述】
输入k及k个整数n1，n2，…，nk，表示有k堆火柴棒，第i堆火柴棒的根数为ni；接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：k＝2，n1＝n2＝2，A代表你，P代表计算机，若决定A先取：
A：(2,2)→(1,2)
{从一堆中取一根}
P：(1,2)→(1,1)
{从另一堆中取一根}
A：(1,1)→(1,0)
P：(1,0)→ (0,0)
如果决定A后取：
P：(2,2)→(2,0)
A：(2,0)→ 0,0)
又如k＝3，n1=1，n2＝2，n3＝3，A决定后取：
P：(1,2,3)→(0,2,3)
A：(0,2,3)→(0,2,2)
A已将游戏归结为(2,2)的情况，不管P如何取A都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输
出第一次该如何取。如果是先取必败，则输出“lose”。
【样例1】
{表示第一次从第3堆取4个出来，必胜}
3 6 5 {第一次取后的状态}
【样例2】
{先取必败}
15 22 19 10
【算法分析】
从问题的描述分析，可以将问题中的k堆火柴棒抽象为k个非负整数，而每取一次火柴棒可抽象为使其中的一个自然数变小，当所有的数都变为0时，游戏结束，最后―次取火柴棒的人为胜方。
当k较小，且k堆火柴棒也都较小时，可使用递推的方法来处理这个问题，具体做法是从终了状态(全零)反推出初始状态的值是先取必胜还是先取必败，因为某一状态的值可以从它的所有的取一次后的下一状态得到，如果某状态的所有的下一状态都为先取必败，则这一状态为先取必胜，否则为先取必败。
但当k和ni都很大时，上述方法很难行得通，为了解决这个问题，首先引进关于n个非负整数的奇偶状态的定义：如果把n个非负整数都化成二进制数，然后对n个二进制数按位相加(不进行进位)，若每一位相加的结果都为偶数，则称这n个非负整数的状态为偶状态，否则称之为奇状态。可以证明：任何一个偶状态在某一个数变小后一定成为奇状态，而对任何一个奇状态，必定可以通过将某一个数的值变小，使得改变后的状态成为偶状态。前一种情况是显然的，因为一个数变小以后其对应的二进制数至少有一位发生改变。这一位的改变就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状态，从高位向低位寻找到第一位按位加之和为奇数的二进制位，设这一位为第k位，则n个数的对应的二进制数中至少存在一个数，其第k位为1，将这个二进制数的第k位变成0，则所有二进制数的第k位上的数字之和就变成了偶数。然后再对这个数的比k位低的所有位作如下调整：如果所有二进制数在该位按位加之和为偶数，则不改变该位的值，否则改变该数在该位的值，若原来的值为0，则改为1，若原来的值为1，则改为0，这样就构造出了一个偶状态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从1变成了0。
如n＝3时，三堆火柴棒的数量分别为3，6，9，则3＝(＝(＝(1001)2，最高位之和为1，其中9对应的二进制数的最高位为1，将其变为0，次高位之和也是1，9对应的二进制数的次高位为0，根据证明过程将其变为1，最后二位数字之和均为偶数，无需作任何改变，这样9＝(1001)2被变成了(，显然，3=(=(=(0101)2是一个偶状态。
有了前面的分析，一种贪心算法就出来了。程序中用n个包含16个元素的数组（线性表）来存放对每个非负整数对应的二进制数，如b[i, 0]存放第i个数的最低位，n个数的状态取决于它们对应的二进制数的各位数字之和的奇偶性，而各位数字之和的奇偶性只需用0和1来表示，0表示偶，1表示奇。最后的状态(全0)为偶状态，所以开始状态为偶状态时，先取必败，因为先取后局面变成了奇状态，后取方一定可将字取成偶状态，直至取光为止。反之则先取必胜。
【后记】
大家都知道国际象棋特级大师卡斯帕罗夫与IBM公司研制的“深蓝”超级计算机进行国际象棋人机大战的事吧!
有了以上算法后，我们也可以编写出这样一个游戏程序。让程序代表计算机与人做取火柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜。
3.4 加工生产调度
源程序名
prod.???（pas, c, cpp）
可执行文件名
prod.exe
输入文件名
prod.in
输出文件名
prod.out
【问题描述】
某工厂收到了n个产品的订单，这n个产品分别在A、B两个车间加工，并且必须先在A车间加工后才可以到B车间加工。
某个产品i在A、B两车间加工的时间分别为Ai、Bi。怎样安排这n个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【输入】
第一行仅―个数据n(0&n&1000)，表示产品的数量。
接下来n个数据是表示这n个产品在A车间加工各自所要的时间(都是整数)。
最后的n个数据是表示这n个产品在B车间加工各自所要的时间(都是整数)。
【输出】
第一行一个数据，表示最少的加工时间；
第二行是一种最小加工时间的加工顺序。
【样例】
3 5 8 7 10
1 5 4 2 3
【算法分析】
本题是要求一个加工顺序使得总的加工时间最少，而要使加工时间最少，就是让各车间的空闲时间最少。一旦A车间开始加工，便会不停地进行加工(我们不要去管车间是否能够一直生产，因为他们有三班，可以24时间不停地运转)。关键是B车间在生产的过程中，有可能要等待A车间的初加工产品。很显然所安排的第一个产品在A车间加工时，B车间是要等待的，最后一个产品在B车间加工时，A车间已经完成了任务。
要使总的空闲时间最少，就要把在A车间加工时间最短的部件优先加工，这样使得B车间能以最快的速度开始加工；把放在B车间加工时间最短的产品放在最后加工，这样使得最后A车间的空闲时间最少。
设计出这样的贪心法：
设Mi＝min{Ai，Bi}
将M按照由小到大的顺序排序，然后从第一个开始处理，如果Mi=Ai，则将它安排在从头开始的已经安排的生产顺序后面，如果Mi＝Bi，则将它安排在从尾开始的已安排的生产顺序前面。
这种安排是否是最少的加工时间，还要通过数学证明。证明如下：
设S＝&J1，J2，…，Jn)，是等待加工的作业序列，如果A车间开始加工S中的产品时，B车间还在加工其他产品，t时刻后B车间就可利用A车间加工过的产品。在这样的条件下，加工S中任务所要的最短时间T(S, t)=min{Ai+T(s-{Ji}，Bi+max{t-Ai, 0})}，其中，Ji∈S。
图3-1是加工作业i时A车间等待B车间的情况：
A等B的情况
图3-2是加工作业i时B车间等待A车间的情形：
B等A的情况
假设最佳的方案中，先加工作业Ji，然后再加工作业Jj，则有：
如果将作业Ji和作业Jj的加工顺序调整，则有：
按照上面的假设，有T&=T’，所以有：
这说是所谓的Johnson公式，也就是说在此公式成立的条件下，优先安排任务Ji在Jj之前可以得到最优解。也就是在A车间加工时间短的安排在前面，在B车间加工时间短的任务安排在后面。
以样例数据为例：
（A1, A2, A3, A4, A5）=（3, 5, 8, 7, 10）
（B1, B2, B3, B4, B5）=（6, 2, 1, 4, 9）
则（m1, m2, m3, m4, m5）=（3, 2, 1, 4, 9）
排序之后为：（m3, m2, m1, m4, m5）
处理m3，因为m3=B3，所以m3安排在后面（，，，，3）；
处理m2，因为m2=B2，所以m2安排在后面（，，，2，3）；
处理m1，因为m1=A1，所以m1安排在前面（1，，，2，3）；
处理m4，因为m4=B4，所以m4安排在后面（1，，4，2，3）；
处理m5，因为m5=B5，所以m5安排在后面（1，5，4，2，3）。
从而得到加工的顺序1，5，4，2，3。计算出最短的加工时间34。
【补充说明】
由于本题的原始数据并没有保证数据间没有重复，所以在数据有重复的情况下生产调度安排并不是惟一的。但是最少的加工时间是惟一的。
3.5 最大乘积
源程序名
maxmul.???（pas, c, cpp）
可执行文件名
maxmul.exe
输入文件名
maxmul.in
输出文件名
maxmul.out
【问题描述】
一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。
现在你的任务是将指定的正整数n分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
【输入】
只一个正整数n，(3≤n≤10000)。
【输出】
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
【样例】
maxmul.out
30
【算法分析】
初看此题，很容易想到用回溯法进行搜索，但是这里的n范围比较大，最多到10000，如果盲目搜索，运行时间比较长，效率很低，对于部分数据可能得到结果，对于大部分数据会超时或栈溢出。
先来看看几个n比较小的例子，看能否从中找出规律：
n 分解方案 最大的乘积
5 2 3 6
6 2 4 8
7 3 4 12
8 3 5 15
9 2 3 4 24
10 2 3 5 30
可以发现，将n分解成a1, a2, a3, a4,…, am这m个自然数，该序列为从2开始的一串由小到大的自然数，如果a1为1，则对乘积没有影响，而且使n减少，没有实际意义，只有特殊情况如n为3、4时才可能用上。
设h&＝5，可以证明当将h拆分为两个不相同的部分并且两部分都大于1时两部分的乘积大于h。证明如下：
将h分为两部分：a，h-a其中2&＝a&h/2，两部分的乘积为a*(h-a)。
a*(h-a)-h＝h*a-a*a-h＝h*(a-1)-a*a
因为h&2*a，所以a*(h-a)-h&2*a*(a-1)-a*a=a*a-2*a=a*(a-2)
又因为a&＝2，所以a*(a-2)&=0，所以a*(h-a)-h&O即a*(h-a)&h。
从上面的证明可以看出，对于指定的正整数，如果其大于等于5，将它拆分为不同的部分后乘积变大，对于中间结果也是如此。因此可以将指定的n，依次拆成a1+a2+a3+a4+…+am，乘积最大。
现在的问题是如何拆分才能保证n＝a1+a2+a3+a4+…+am呢?
可以先这样取：当和不足n时，a1取2，a2取3，…，am-1取m，即从2开始按照自然数的顺序取数，最后剩余的数给am，如果am&=am-1，此时am跟前面的数字出现了重复，则把am从后面开始平均分布给前面的m-1个数。为什么要从后面开始往前呢?同样是考虑数据不出现重复的问题，如果是从前面往后面来平均分配，如2加上1以后变成3，就跟后面的已有的3出现了重复。这样操作到底是否正确、是否能保证乘积最大呢?还要加以证明。证明过程如下：
设两个整数a，b的和为2s，且a&&b，设a＝s-1，则b＝s+1，a*b=(s-1)*(s+1)=s2-1，如果a=s-2，则b＝s+2，a*b＝(s-2)*(s+2)＝s2-4。
a-b的绝对值越小，乘积的常数项越大，即乘积越大，上面的序列a1, a2, a3, a4, …, am正好满足了a-b的绝对值最小。但是还要注意两个特例就是n=3和n=4的情况，它们的分解方案分别为1，2和1，3，乘积分别为2和3。
以n=10为例，先拆分为：10=2+3+4+1，最后一项为1，比4小，将其分配给前面的一项，得到10=2+3+5，所以最大的乘积为2*3*5＝30。
以n=20为例，拆分为：20=2+3+4+5+6，正好是连续自然数的和，所以最大乘积为2*3*4*5*6=720。
再以n=26为例，先拆分为：26=2+3+4+5+6+6，因为最后一项为6，不比最后第二项大，所以将其平均分给前面的项，优先考虑后面的项，即前面的4项各分到1，笫5项6分到2，最后是26＝3+4+5+6+8，所以最大的乘积为3*4*5*6*8＝2880。
由于n可能大到10000，分解之后的各项乘积位数比较多，超过普通的数据类型的位数，所以要用到高精度运算来进行整数的乘法运算，将结果保存在数组里。
本题的贪心策略就是：
要使乘积最大，尽可能地将指定的n(n&4)拆分成从2开始的连续的自然数的和，如果最后有剩余的数，将这个剩余的数在优先考虑后面项的情况下平均分给前面的各项。
基本算法描述如下：
（1）拆分过程
拆分的数a先取2；
选择a作为一项；
如果n&0，那么将n从最后一项开始平均分给各项；
如果n还大于0，再从最后一项开始分一次；
（2）求乘积
设置一个数组来存放乘积，初始状态位数为1，结果为1；
将上面拆分的各项依次跟数组各项相乘并考虑进位；
3.6 种树
源程序名
trees.???（pas, c, cpp）
可执行文件名
trees.exe
输入文件名
trees.in
输出文件名
trees.out
【问题描述】
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
* 从trees.in读入数据
* 计算最少要种树的数量和位置
* 把结果写到trees.out
【输入】
第一行包含数据N，区域的个数(0&N≤30000)；
第二行包含H，房子的数目(0&H≤5000)；
下面的H行描述居民们的需要：B E T，0&B≤E≤30000，T≤E-B+1。
【输出】
输出文件第一行写有树的数目，下面的行包括所有树的位置，相邻两数之间用一个空格隔开。
【样例】
3 5 2
【算法分析】
不难想到下面的贪心算法：按照每个区间的右端点排序，从左向右扫描，把每个区间内的树都尽量种在该区间的右端，由于后一个区间的右端不在这个区间的右端的左边(排序)，可以保证这些树尽可能多地被下面的区间利用到。
扫描需要的时间为O(h)，更新需要的时间为O(n)，所以总的时间复杂度为O(n*h)。
3.7 餐巾
源程序名
napkin.???（pas, c, cpp）
可执行文件名
napkin.exe
输入文件名
napkin.in
输出文件名
napkin.out
【问题描述】
一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。
(1)购买新的餐巾，每块需p分；
(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f&p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。
(3)把餐巾送到慢洗部，洗一块需n天(n&m)，费用需s分(s&f)。
在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。
【输入】
输入文件共3行，第1行为总天数；第2行为每天所需的餐巾块数；第3行为每块餐巾的新购费用p，快洗所需天数m，快洗所需费用f，慢洗所需天数n，慢洗所需费用s。
【输出】
输出文件共n+1行。第1行为最小的费用。下面的n行为从第1天开始每天需要的总餐巾数、需购买的新餐巾数、结束时往快、慢洗部送洗的餐巾数以及用到的来自快洗的餐巾数和来自慢洗的餐巾数。
【样例】
napkin.out
3 3 1 2 0 0
10 1 6 2 3
2 1 2 0 1 0
4 0 0 0 2 2
【算法分析】
在思考这个问题时，一般容易想到从洗的角度去思考，这就必然要对每天的餐巾来源进行分类穷举，当天数较长，每天需求量较大时，穷举的数量级至少为每天的餐巾数之积，程序很难在规定时间内运行出最优解。如果从买的角度去思考这个问题，则该问题就变得十分简单。在确定要买的餐巾数之后，显然这些餐巾购买得越早，被反复利用的可能就越大。也就是说，这些餐巾必须在最早的几天中购买，余下的缺口用洗出来的餐巾来填补，对每天用下来的餐巾，假设全部都送洗，但送洗时不确定其状态，即它们有可能被快洗，有可能被慢洗，也可能不用洗，其状态在今后被选用时再确定。在确定每天的需求时，除去买的，剩下的首先要选用慢洗为好。这种餐巾有多少应用多少，不够再选用快洗出来的餐巾。选用快洗出来的餐巾时，应选用最近的若干天中才快洗出来的餐巾，这样可以保证有更多的餐巾被慢洗出来。这就是我
们的贪心思想。
对所要购买的餐巾数进行穷举，开始时其值为所需用餐巾数之和，当购买量太少而周转不过来时，程序结束。在确定了购买的餐巾总数后，按上述算法构造出最小费用方案，所有的最小费用方案中的最优解即为问题的解。程序(见本书光盘)中数组need存放每天需用的餐巾数，数组fromslow记录每天来自慢洗的餐巾数。数组fromfast记录每天来自快洗的餐巾数，数组buy记录每天购买的餐巾数。变量restslow存储当天可供选用的已经慢洗好的餐巾数。这个算法的数量级为O(n)，其中n为所有天中需用的餐巾数之总和。
3.8 马拉松接力赛
源程序名
marathon.???（pas, c, cpp）
可执行文件名
marathon.exe
输入文件名
marath.in
输出文件名
marath.out
【问题描述】
某城市冬季举办环城25km马拉松接力赛，每个代表队有5人参加比赛，比赛要求每个的每名参赛选手只能跑一次，一次至少跑1km、最多只能跑10km，而且每个选手所跑的公里数必须为整数，即接力的地方在整公里处。
刘老师作为学校代表队的教练，精心选择了5名长跑能手，进行了训练和测试，得到了这5名选手尽力连续跑1km、2km、…、10km的所用时间。现在他要进行一个合理的安排，让每个选手跑合适的公里数，使学校代表队跑完25km所用的时间最短。根据队员的情况，这个最短的时间是惟一的，但安排方案可能并不惟一。
根据测试情况及一般运动员的情况得知，连续跑1km要比连续跑2km速度快，连续跑2km又要比连续跑3km速度快……也就是说连续跑的路程越长，速度越慢，当然也有特殊的，就是速度不会变慢，但是绝不可能变快。
【输入】
5行数据，分别是1到5号队员的测试数据，每行的10个整数，表示某一个运动员尽力连续跑1km、2km、…、10km所用的时间。
【输出】
两行，第一行是最短的时间，第二行是五个数据，分别是1到5号队员各自连续跑的公里数。
【样例】
marath.out
333 700 40 56
300 610 960 12 98 7682
298 612 990 96 96 7654
289 577 890 34 90 9876
312 633 995 34 99 8123
【算法分析】
初看此题，好象是一个排列问题，选取5个10之间的数，共有10*10*10*10*10＝100000种情况，对每一种情况，再看其和是否为25，在和为25的情况下再计算所用的总时间，找出其中最少的。
这种枚举的方法，肯定能找到最优解，但是这样做的效率不高，执行时间长，这里是5个选手还行，如果更多，如15个选手，就要对l015种可能情况进行判定，再快的计算机也要较长的时间来执行。
因为运动员连续跑一公里要比连续跑两公里速度快、连续跑两公里又要比连续跑三公里速度快……也就是说连续跑的路程越长，速度越慢，所以我们可以将每个选手的所跑时间进行分段处理，计算出各自所跑每一公里所用的时间。又因为要求每个选手至少跑一公里，先给每一个人分配一公里。剩下的里程由哪个选手来跑呢?这时检查各自所跑第二公里所用的时间，哪个用的时间最短就选这个选手继续跑一公里，因为这样做可以保证当前所用的时间最少，这个所手所跑的公里数增加1。下一公里继续用这种方法选，看当前要跑一公里哪个用的时间最短就选谁，选了谁，谁所跑的公里数增加l，下面要检查的时间段就是他的下一段……如此反复直到25公里分配完为止。
对于每个运动员跑各公里所用的时间不一定要单独计算出来，如它跑第5公里所用的时间等于他连续跑完5公里所用的时间减去他连续跑4公里所用的时间。
本题所用的贪心策略就是：
先分配每个运动员跑一公里；剩下的20公里始终选择所有运动员当中下一公里跑的时间最短的，直到分配完。
这样局部的最优保证整体的最优。
3.9 线性存储问题
源程序名
storage.???（pas, c, cpp）
可执行文件名
storage.exe
输入文件名
storage.in
输出文件名
storage.out
【问题描述】
磁带等存储介质存储信息时基本上都是一种线性存储的方式，线性存储方式虽然简单，但查询检索时往往要经过一些其它信息，不象磁盘等存储介质在目录区找到后可直接定位到某一区城，因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点，现在仍然在使用。
如果有n段信息资料要线性存储在某种存储介质上，它们的长度分别是L1，L2，…，Ln，存储介质能够保存下所有这些信息，假设它们的使用(查询检索)的频率分别是F1，F2，…，Fn，要如何存储这些信息资料才能使平均检索时间最短。
你的任务就是编程安排一种平均检索时间最短的方案。
【输入】
第一行是一个正整数n(n&10000)，接下来是n行数据，每行两个整数分别是第1段信息的长度(1到10000之间)和使用的频率(万分比，在0到9000之间)，总的频率之和为10000。
所输入数据均不要判错。
【输出】
依次存储信息段的编号。每个数据之间用一个空格隔开。
【样例】
storage.in
storage.out
12 2500
【算法分析】
根据统计的基本原理，n段信息资料的使用（查询检索）的频率之和应为1，即F1+F2+…+Fn=1，如果总的检索次数为m，第I段信息资料使用的次数为m*Fi，设平均检索速度为v单位长度/单位时间，而它的长度为Li，每次所用的时间为Ti-1+Li/V，其中Ti-1为通过安排在第I个信息段前面的所有信息所要的时间，访问信息段I所有次数总的时间时：
m*Fi*(Ti-1+Li/v)。
因为上表达式中m、v可看作是常数，所以单一访问时间Fi与Li及前面的安排有关，每段信息均是这样，由此我们可采用如下的贪心方法：
根据(频率*长度)进行由大到小的排序，然后根据这个排序安排某一信息段在相应位置，从而得到的总的检索时间最短，也就是平均检索时间最短。
3.10扇区填数
源程序名
fan.???（pas, c, cpp）
可执行文件名
fan.exe
输入文件名
fan.in
输出文件名
fan.out
【问题描述】
有一个圆，当输入一个整数n(1≤n≤6)后，它被分成n个扇区，请你为每一扇区选择一个自然数(大于0的整数)。
向各个扇区放入数之后，你可以从单个扇区中选出―个数，也可以从相邻的两个或多个扇区中各选一个数，相加后形成一个新的数，请使用这些整数形成一个连续的整数序列，：1，2，3，…，i，你的任务是使i尽可能地大。
【输入】
只一个整数n(1&＝n&＝6)。
【输出】
第一行是最大的i，接下来的几行是所有能达到最大i的填法。
由于圆里不分顺序，所以同一种填法可以有多种输出。为了减少这种情况，这里规定从1，开始输出(因为连续数里要有1，所以所填的数中肯定有1)。
【样例】
1
【算法分析】
假设圆已经被分成了n个扇区，并且已经在这n个扇区中填好了数字，先来看看填好数字后最多有多少种选择连续的数字并求和的方法，以N＝4为例：
单独选一个，有n种即1、2、3、4；
选择相邻两个也有n种即12、23、34、41
选择相邻三个也有n种即123、234、341、412；
选择相邻四个只有一种即1234。
总共有n*(n-1)+1种，当n=4时有13种。
如果每一种选择所求的和都不同，那么能够构成的最多有n*(n-1)+1个不同的数。我们当然希望能够达到的最大的连续数就是从1到n*(n-1)+1了，如N=4时就是1到13。
现在的问题是如何保证这n*(n-1)+1个数就是从1到n*(n-1)+1。在填数时首先填1，接下来的n-1个数都保证不同且最小为2，再看其他的取相邻的多个数的情况了。在n&＝6的情况下都能满足这个要求，对于n&6时就不一定了。
从这种最优策略出发，再结合回溯法找出所有可能的情况。
分治
4.1 取余运算
源程序名
mod.???（pas, c, cpp）
可执行文件名
mod.exe
输入文件名
mod.in
输出文件名
mod.out
【问题描述】
输入b，p，k的值，求b p mod k的值。其中b，p，k*k为长整型数。
【样例】
2^10 mod 9=7
【知识准备】
进制转换的思想、二分法。
【算法分析】}
我要回帖
更多推荐
- ·关汉中平原和关中平原又称什么？
- ·到新加坡居士林注意什么问题佛教居士林新篇章
- ·谁用过的比较好用滋润的口碑最好的十大身体乳乳推荐下呗？
- ·阳江市高三模拟考试比高考难吗防真考试难度高吗？
- ·教师资格证什么时候拿证忘记领取了怎么办 教师资格证什么时候拿证书忘记领取了怎么办
- ·宋一国经济状况况，民主思想有什么影响
- ·如何自制自制12v电鱼机线路图产品图片，价格，如何自制自制12v电鱼机线路图企业
- ·提高如何投诉天猫卖家逼格，小卖家该怎么办
- ·如果是个人注册公司名称注册查询网都需要什么。手续和步骤呢！
- ·你好请问美中国联航有飞机餐吗现在上飞机能带100ml的液体吗？自己带的不是免税店买的可以吗？ 粉状的化妆品呢？
- ·DNF凭什么dnf狂战双刀怎么开开双刀不算用了无色技能
- ·我脑子反应慢是智商低吗比较慢，玩什么游戏能锻炼我
- ·泰拉瑞亚瓶中暴雪暴雪气球好么
- ·地下城堡2 万年幽魂狩猎任务愤怒幽魂要怎么才能完成
- ·世界上有没有圣诞老人真的有圣诞
- ·捕扑鱼游戏网有哪些实用的技巧
- ·来个超帅的德莱文超清壁纸好不好
- ·天天炫斗秘境69机械戒指开藏宝秘境章鱼怎么打
- ·魔兽世界 德鲁伊的剧情里德鲁伊处于什么状况
- ·求24点游戏的编程，python计算机视觉编程给你4个任意数，你自己通过输进去运算，如果可以则算正确否则算失败
- ·手机战略游戏单机战争策略游戏
- ·淘宝买棋牌50两银子宋朝能买什么能退吗
- ·魔域幻兽属性龙魂属性介绍 幻兽龙魂怎么样
- ·魔灵召唤符文属性术士吴奇怎么样 属性符文搭配分析
- ·有一款日本动漫改编游戏的游戏，是主角带着2个人有一艘宇宙战舰，宇宙中有4个国家，有个国家研究出帝虎战舰
- ·《王者荣耀上单铭文》里上单这么难守，哪些英雄最抗压
- ·烈火封神召唤师阵法搭配阵法怎么用好 烈火封神召唤师阵法搭配阵法使用技巧
- ·生死狙击霸气名字大全一霸，聚灵力解三个数字几
- ·神无月公测时间ios什么时候公测
- ·究极日月对战树奖励奖励什么时候发放
- ·ps4港版 注册了国服坏了怎么维修
- ·巫师3 爱丽丝钢剑这把剑怎么获得，刚刚做完第三个
- ·QQ空间红包没领完退不双11退款红包怎么办
- ·魂斗罗白熊有必要买吗归来白熊怎么获得
- ·和硕美科游戏耳机推荐哪个好
