游戏开发论坛

 找回密码
 立即注册
搜索
查看: 19597|回复: 58

算法帖-大家都来试试

[复制链接]

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2005-11-27 12:32:00 | 显示全部楼层 |阅读模式
不时有人提议研究研究算法吗,我发了几道题却没有几个人做。 [em10]
这里发十道题,从最简单到较难,一定有你会做的,试试吧。 [em3]
看看你能做几道题,当然,如果你是高手,你可以鄙视这里发的全部题,因为这些题考的都是基础算法。

[em13]

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

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

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

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

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:33:00 | 显示全部楼层

Re:算法帖-大家都来试试

1、级数求和
难度:*

[问题描述]:
  已知:Sn= 1+1/2+1/3+…+1/n。显然对于任意一个整数K,当n足够大的时候,Sn大于K。
  现给出一个整数K(1<=k<=15),要求计算出一个最小的n;使得Sn>K。
[输入]
键盘输入 k
[输出]
屏幕输出 n
[输入输出样例]
输人:1
输出:2

测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:34:00 | 显示全部楼层

Re:算法帖-大家都来试试

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

测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:34:00 | 显示全部楼层

Re:算法帖-大家都来试试

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


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


测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:34:00 | 显示全部楼层

Re:算法帖-大家都来试试

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

测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:35:00 | 显示全部楼层

Re:算法帖-大家都来试试

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

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

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

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

样例输入:8

样例输出:92


测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:35:00 | 显示全部楼层

Re:算法帖-大家都来试试

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

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:35:00 | 显示全部楼层

Re:算法帖-大家都来试试

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



测试数据下载

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:35:00 | 显示全部楼层

Re:算法帖-大家都来试试

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


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

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

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

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

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
 楼主| 发表于 2005-11-27 12:35:00 | 显示全部楼层

Re:算法帖-大家都来试试

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)
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2026-1-23 10:43

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表