算法帖-大家都来试试

sandy_zc_1

不时有人提议研究研究算法吗，我发了几道题却没有几个人做。 [em10]
这里发十道题，从最简单到较难，一定有你会做的，试试吧。 [em3]
看看你能做几道题，当然，如果你是高手，你可以鄙视这里发的全部题，因为这些题考的都是基础算法。

[em13]

可以使用各种语言来完成这些题，VB、VC、Dephi，DOS上的QB、TP、FP、TC等都可以，不过好像用C的比Basic的稍占便宜……
不过Win界面下的程序注意要在运算结束后自动结束以免超时（屏幕输出的除外），否则就算你运算完成，但只要窗口还挂在那里都会被程序计时的。

每道题都有10个测试数据，每个10分，满分100，看看你能得多少。

关于运算时间：除非题上特殊注明，其它题给定运算时间一律1秒，如果运算超时，即使结果是正确的也不给分。禁止使用任何汇编、寄存器及指令集。

大家都报一报自己的成绩吧。 [em5]

sandy_zc_1

1、级数求和
难度：*

[问题描述]:
　　已知：Sn= 1＋1／2＋1／3＋…＋1／n。显然对于任意一个整数K，当n足够大的时候，Sn大于K。
　　现给出一个整数K（1<=k<=15），要求计算出一个最小的n；使得Sn＞K。
[输入]
键盘输入 k
[输出]
屏幕输出 n
[输入输出样例]
输人：1
输出：2

测试数据下载

sandy_zc_1

2、津津的储蓄计划
难度：**

【问题描述】

    津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

    为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

    例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。

    津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

    现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】

    输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。


【输出文件】

    输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】

290
230
280
200
300
170
340
50
90
80
200
60
【样例输出1】

-7

【样例输入2】

290
230
280
200
300
170
330
50
90
80
200
60

【样例输出2】

1580

测试数据下载

sandy_zc_1

3、数字三角形
难度：**

输入两个数M、N，（0<=M<=20，1<=N<=10），你需要编一个程序将以M起始的整数排成边长为N的三角形，形式如下：

M+3
M+1     M+4
M         M+2     M+5  ……

例：M=10，N=4时

输出：
16
13  17
11  14  18
10  12  15  19


输出要求：输出为文件，每一行每两个数字间用两个空格隔开，每个数字占两个字符的位置，如果字符只有一位，后面用空格补齐。


测试数据下载

sandy_zc_1

4、成绩排序。
难度：***

王校长有一份很长的成绩单，上面有上次期末考试他学校的每个学生的成绩。然而，这个成绩单是乱序的，王校长需要一张按照成绩由高到低排列的成绩单。
另外，王校长需要向教育局提交其中N个学生的成绩，教育局要求这些成绩按照从低到高的顺序排列，而且如果其中有某几个同学的成绩相同，这些学生的排列次序按照其名称英文字母的顺序排列。
请你编一个程序来帮助王校长解决这些问题。

输入文件：
第一行有一个整数M（1<=M<=10000），表示成绩单上共有M个学生。
接下来M行，每一行有三个数据，首先是学生的名字，名字均为英文字母，长度不超过20。接下来是学生的成绩S，0<=S<=100，但S不一定是整数。最后一个数据只有一个英文字母，如果是"T"，说明这个学生在向教育局提供的成绩单中，如果是"F"，则不在。王校长保证向教育局提供的成绩单上的人数N不超过1000人。每一行三个数据间用一个空格隔开。

输出文件：M+N行，前M行为排序后的成绩单，每行先是学生的名字，然后是他的成绩，之间用一个空格隔开。后N行是向教育局提供的成绩单，每行的要求相同。

样例输入：
5
Sam 99.5 T
Fred 83 F
Terry 77.38 T
David 100 T
Lasty 100 T

样例输出：
Lasty 100
David 100
Sam 99.5
Fred 83
Terry 77.38
David 100
Lasty 100
Sam 99.5
Terry 77.38

测试数据下载

sandy_zc_1

5、n皇后布置。
难度：****

在一个n*n的国际象棋棋盘上，要放置n个皇后，而且使她们不互相攻击。
要求输出所有可能的解的数目。

输入文件：只有一个数，是n的值，保证n<=12。

输出文件：如果有解，输出所有可能的解的数目，如果无解，输出：“No Answer”。

样例输入：8

样例输出：92


测试数据下载

sandy_zc_1

6、数塔路径

难度：*****

有一个高度为n的数塔，塔的底层有n个数，上面一层有n-1个数……直到
最顶层有一个数。

要求找到一条从塔顶到塔底的路径，使得路径上各数字和为最大。
路径要求，如果现在在第s层的第k个数，那么下一步必须是第s+1层的第k个数或者是第s+1层的第k+1个数。
也就是说，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。

输入文件：第一行有一个数，为n（2<=n<=100）。
接下来第2行到第n+1行，第m行有m-1个数，表示数塔从上往下数第m-1层的组成，每个数都是-100到100间的整数（包括-100和100）。相邻两个数用一个空格隔开。

输出文件：两行，第一行是路径上各数字的和。
第二行有n个数，第m个数就是路径在数塔从上往下数第m层所经过的数。

样例输入：
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

样例输出：
86
13 8 26 15 24

sandy_zc_1

7、合并果子
难度：*****

【问题描述】

    在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

    每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

    因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

    例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

【输入文件】

    输入文件test.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。

【输出文件】

    输出文件test.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。

【样例输入】

3
1 2 9

【样例输出】

15



测试数据下载

sandy_zc_1

8、石子归并
难度：******


问题描述
在一个圆形操场的四周摆放着n堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分.试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分.

编程任务
对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分.

输入文件：第一行有一个数n（2<=n<=40），是石子堆数。
第二行有n个数，每一个数m表示每一堆石子的数量（1<=m<=100），每两个数用一个空格隔开。

输出文件：第一行有一个数，将n堆石子合并成一堆的最小得分，
第二行有一个数，将n堆石子合并成一堆的最大得分。

sandy_zc_1

9、房间问题
难度：******

下图示意出了一张建筑平面图，编程计算：
1、该建筑中有多少个房间。
2、最大的房间有多大。
3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间，指出该墙。



输入数据：平面图以数字方式存储。
1、文件开头是南北方向的方块数，其次是东西方向的方块数。
2、后面的行中，每个方块中墙的特征用数字p来描述（0<=p<=15），数字p是下面可能取的数字之和：1（西墙West），2（北墙North），4（东墙East），8（南墙South）。
3、建筑中至少有两个房间。
输出数据：
第一行是总共的房间数。
第二行是最大的房间有多大（用占用了几个方块表示）
第三行是该拆除的墙的位置，格式为：(x1,y1)(x2,y2)，表示拆除坐标为(x1,y1)和坐标为(x2,y2)的方块之间的墙。以西北角的方块为(1,1)，向东横坐标递增，向南纵坐标递增。

以上图为例：
输入：
2  3
15  3  14
11  12  15
输出：
3
4
(1,1)(1,2)