当前位置:首页 >> 英语 >>

试题库


题目
题目 (1) 母牛生小牛 (2) 数列极差问题 (3) 穿越沙漠 (4) 四塔问题 (5) 食物链 (6) 取石子游戏 (7) 幻方矩阵 (8) 猫捉老鼠 (9) 残缺棋盘 (10)字符串的距离 (11) 采药 (12) 炮兵阵地 (13) 整数划分问题 (14) 行编辑器 (15) Tom 的烦恼 (16) 陶陶摘苹果 (17) 百度语言翻译机 (18) 猪的安

家 (19) 勇气的挑战 (20) 青蛙的约会 (21) 八枚银币 (22) 超长整数运算 (大 数运算) (23) 完美数 (24) 中序式转后序式 (前序式) (25) 后序式的运算 (26) 4N 魔方阵 (27) 统计数字问题 (28) 最大间隙问题 (29) 编辑距离问题 (30) 吝啬的国度 组员 分数

(1) 母牛生小牛
Problem 设有一头小母牛,从出生第四年起每年生一头小母牛,按此规律,第 N 年时有几头母牛?

Input 本题有多组数据。每组数据只有一个整数 N,独占一行。(1≤N≤50)

Output 对每组数据,输出一个整数(独占一行)表示第 N 年时母牛的数量

Sample Input 1 4 5 20

Sample Output 1 2 3 872

(2) 数列极差问题 在黑板上写了 N 个正整数组成的一个数列,进行如下操作: 每次擦去其中的两个数 a 和 b,然后在数列中 加入一个数 a×b+1,如此下去直至黑板上 剩下一个数,在所有按这种操作方式最后得到的数中,最大的 为 max,最小的为 min, 则该数列的极差定义为 M=max-min。 请你编程,对于给定的数列,计算极差。 输入 输入包含多个测试集。每个测试集的第一个数 N 表示 正整数序列长度(0<=N<=50000),随后是 N 个正整数。N 为 0 表示输入结束。 输出 每个结果一行 输入样例 3 1 2 3

0 输出样例 2

( 3 ) 穿越沙漠
一辆吉普车来到 x 公里宽的沙漠边沿 A 点,吉普车的耗油量为 1 升/公里,总装油量为 500 升。通常,吉 普车必须用自身油箱中的油在沙漠中设置若干个临时储油点,才能穿越沙漠的。假设在沙漠边沿 A 点有充 足的汽油可供使用,那么吉普车从 A 点穿过这片沙漠到达终点 B,至少要耗多少升油。请编写一个程序, 计算最少的耗油量(精确到小数点后 3 位)。 (1)假设吉普车在沙漠中行进时不发生故障; (2)吉普车在沙漠边沿 A 点到终点 B 的直线距离为 x≧500 公里(即沙漠宽度);

输入 输入的第一行含一个正整数 k (1<=k<=6),表示测试例的个数。后面紧接着 k 行,每行对应一个测试例,包 含一个正整数 x,表示从 A 点到 B 点的距离(1<=x<=2000)。 输出 每个测试例对应一行输出,包含一个数,表示最少的油耗量。 输入样例 2 500 1000 输出样例 500.000 3836.497

(4) 四塔问题
“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有 4 根柱子,而不是 3 根,那么至少需要移动盘子多少次,才能把所有的盘子从第 1 根柱子移动到第 4 根柱子上呢? 为了编程方便,您只需要输出这个结果 mod 10000 的值。

Input 该题含有多组测试数据,每组一个正整数 n。(0<n<=50000)

Output 一个正整数,表示把 n 个盘子从第 1 根柱子移动到第 4 根柱子需要的最少移动次数 mod 10000 的值。

Sample Input 15

Sample Output 129

(5) 食物链
Description 动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B, B 吃 C,C 吃 A。 现有 N 个动物,以 1-N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这 N 个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示 X 和 Y 是同类。 第二种说法是"2 X Y",表示 X 吃 Y。 此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一 句话满足下列三条之一时,这句话就是假话,否则就是真话。 1) 当前的话与前面的某些真的话冲突,就是假话; 2) 当前的话中 X 或 Y 比 N 大,就是假话; 3) 当前的话表示 X 吃 X,就是假话。 你的任务是根据给定的 N(1 <= N <= 50,000)和 K 句话(0 <= K <= 100,000),输出假话的总数。

Input 第一行是两个整数 N 和 K,以一个空格分隔。 以下 K 行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中 D 表示说法的种类。 若 D=1,则表示 X 和 Y 是同类。 若 D=2,则表示 X 吃 Y。

Output 只有一个整数,表示假话的数目。

Sample Input 100 7 1 101 1 212 223 233 113 231

155

Sample Output 3

Source

(6) 取石子游戏
Description 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全 部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最 后你是胜者还是败者。

Input 输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数 a 和 b,表示两堆石子的数 目,a 和 b 都不大于 1,000,000,000。

Output 输出对应也有若干行,每行包含一个数字 1 或 0,如果最后你是胜者,则为 1,反之,则为 0。

Sample Input 21 84 47

Sample Output 0 1 0

(7)幻方矩阵
Problem description 幻方是一种很有意思的数字矩阵,在很早著名的九宫八卦阵就与幻方有关。 幻方的定义为: 1 到 N*N 的整数填入 N*N 的方格中,每行和每列以及对角线的数字之和必须是相等的。 你作为八卦公司的顶级程序员,现在需要你解决一个问题,将任意奇数阶的幻方找出来。

Input 输入包括多个测试集,每行为一个正奇数 N(1 <= N < 1000),0 作为输入的结束且不需要处理。

Output 对于输入的每一个 N, 输出一个它所对应的 N 阶幻方,如果存在多个,任意一个即可。 每个幻方为 N*N 的矩阵, 对于每个幻方,每行输出幻方的一行,每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个 空行分开。

Sample Input 1 3 0

Sample Output 1

492 357 816

(8) 猫捉老鼠
一只猫和一只老鼠在 10*10 的迷宫中。迷宫中的每个方格可以是空的,或者含有障碍。猫和老鼠可以进入 任意一个空的方格中。当他们相遇时,猫和老鼠在同一个方格中。但是,无论猫或老鼠都不能进入有障碍 的方格。我们可以用字符组成的二维数组表示迷宫,如下图所示。

老鼠在迷宫中按照一种固定的方式行走:每个时刻,老鼠都向它所面对的方向前进一格,这需要花费1秒 时间。如果前方是一个障碍或者是迷宫的边界,它将花1秒的时间按顺时针方向转 90 度。 为了抓到老鼠,这只猫决定也按照与老鼠相同的行走方式行进。 猫和老鼠在每个单位时间内是同时行动的。因此,如果猫和老鼠在行进过程中“擦肩而过”,猫是无法捉到 老鼠的。只有当猫和老鼠同时到达一个相同的格子时,猫才能捉住老鼠。 初始时,猫和老鼠不会在同一个方格中。并且它们都面向北方。 你的任务是编一个程序,求出猫捉到老鼠的所花时间。

输入输出格式

输入数据的第一行 n,表示输入数据的组数。 每组数据由 10 行组成,每行 10 个字符,表示迷宫的地图以及猫和老鼠的初始位置。输入数据保证只有一 只猫和一只老鼠。 每组输入数据之后均有一个空行作为间隔。 对于每组给定的输入,输出一行仅含一个数,即猫捉到老鼠所花的时间。如果猫永远都无法抓到老鼠,则 输出 0。 样例输入

1 *...*..... ......*... ...*...*.. .......... ...*.c.... *.....*... ...*...... ..m......* ...*.*.... .*.*...... 样例输出

49

(9)残缺棋盘问题
问题描述: 残缺棋盘是一个有 2k×2k(k≥1)个方格的棋盘,其中恰有一个方格残缺。如图给 出 k=1 时各种可能的残缺棋盘,其中残缺的方格用阴影表示。

? 残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆盖中要求: 1)两个三格板不能重叠 2)三格板不能覆盖残缺方格,但必须覆盖其他所有的方格。 小格子数 (2k×2k -1) 三格板中小格子数 3。 所以所需要的三格板总数为(2k×2k -1 )/3。 ? 例如,一个 4*4 的残缺棋盘 2k*2k

以 k=2 时的问题为例,用二分法进行分解,得到的四个 k=1 的棋盘。但要注意 这四个棋盘,并不都是与原问题相似且独立的子问题。 因为当如图中的残缺方格在左上部时, 第 1 个子问题与原问题相似, 而右上角、 左下角和右下角三个子棋盘(也就是图中标识为 2、3、4 号子棋盘),并不是原问 题的相似子问题,自然也就不能独立求解了。当使用一个①号三格板覆盖 2、3、4 号三个子棋盘的各一个方格后,我们把覆盖后的方格,也看作是残缺方格(称为“伪” 残缺方格),这时的 2、3、4 号子问题就是独立且与原问题相似的子问题了。 ? 问题分析 从以上例子还可以发现 当残缺方格在第 1 个子棋盘, 用①号三格板覆盖其余三个子棋盘的交界方 格,可以使另外三个子棋盘转化为独立子问题; 当残缺方格在第 2 个子棋盘时,则首先用②号三格板进行棋盘覆盖 当残缺方格在第 3 个子棋盘时,则首先用③号三格板进行棋盘覆盖 当残缺方格在第 4 个子棋盘时,则首先用④号三格板进行棋盘覆盖,这样 就使另外三个子棋盘转化为独立子问题。
(10)字符串的距离
Problem 设有字符串 X,我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串,如字符串 X 为“abcbcd”, 则字符串“abcb□cd”, “□a□bcbcd□”和“abcb□cd□”都是 X 的扩展串, 这里“□”代表空格字符。 如 果 A1 是字符串 A 的扩展串,B1 是字符串 B 的扩展串,A1 与 B1 具有相同的长度,那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义为它们的 ASCII 码的差的 绝对值,而空格字符与其它任意字符之间的距离为已知的定值 K,空格字符与空格字符的距离为 O。在字 符串 A、B 的所有扩展串中,必定存在两个等长的扩展串 A1、B1,使得 A1 与 B1 之间的距离达到最小, 我们将这一距离定义为字符串 A、B 的距离。 请你写一个程序,求出字符串 A、B 的距离。

Input 有多组数据,每一组数据第一行为字符串 A,第二行为字符串 B,A、B 均由小写字母组成且长度均不超过 2000,第三行为一个整数 K,1≤K≤100,表示空格与其它字符的距离。

Output 每组数据一行包含一个整数,表示要求的字符串 A、B 的距离。

Sample Input cmc snmn 2

Sample Output 10

(11) 采药
【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。 医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这 个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间, 在这段时间里, 你可以采到一些草药。 如果你是一个聪明的孩子, 你应该可以让采到的草药的总价值最大。 ” 如果你是辰辰,你能完成这个任务吗?

【输入文件】 输入文件 medic.in 的第一行有两个整数 T(1 <= T <= 1000)和 M(1 <= M <= 100),用一个空格隔开, T 代表总共能够用来采药的时间,M 代表山洞里的草药的数目。接下来的 M 行每行包括两个在 1 到 100 之 间(包括 1 和 100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

【输出文件】 输出文件 medic.out 包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总 价值。

【样例输入】 70 3 71 100 69 1 12

【样例输出】 3

【数据规模】 对于 30%的数据,M <= 10; 对于全部的数据,M <= 100。

(12) 炮兵阵地
Description 司令部的将军们打算在 N*M 的网格地图上部署他们的炮兵部队。一个 N*M 的地图由 N 行 M 列组成,地图 的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可 以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域 所示:

如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域: 沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受 地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击, 即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的 炮兵部队。

Input 第一行包含两个由空格分割开的正整数,分别表示 N 和 M; 接下来的 N 行, 每一行含有连续的 M 个字符('P'或者'H'), 中间没有空格。 按顺序表示地图中每一行的数据。 N <= 100;M <= 10。

Output 仅一行,包含一个整数 K,表示最多能摆放的炮兵部队的数量。

Sample Input 54 PHPP PPHH PPPP PHPP PHHP

Sample Output 6

(13)整数划分问题
整数划分是一个经典的问题。希望这道题会对你的组合数学的解题能力有所帮助。

Input 每组输入是两个整数 n 和 k。(1 <= n <= 50, 1 <= k <= n)

Output 对于每组输入,请输出六行。 第一行: 将 n 划分成若干正整数之和的划分数。 第二行: 将 n 划分成 k 个正整数之和的划分数。 第三行: 将 n 划分成最大数不超过 k 的划分数。 第四行: 将 n 划分成若干奇正整数之和的划分数。 第五行: 将 n 划分成若干不同整数之和的划分数。 第六行: 打印一个空行。

Sample Input 52

Sample Output 7 2 3 3 3

Hint: 1、将 5 划分成若干正整数之和的划分为: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 2、将 5 划分成 2 个正整数之和的划分为: 3+2, 4+1 3、将 5 划分成最大数不超过 2 的划分为: 1+1+1+1+1, 1+1+1+2, 1+2+2 4、将 5 划分成若干奇正整数之和的划分为: 5, 1+1+3, 1+1+1+1+1 5、将 5 划分成若干不同整数之和的划分为: 5, 1+4, 2+3

(14)行编辑器
Problem 一个简单的行编辑程序的功能是:接受用户从终端输入的程序或数据,并存入用户的数据区。

由于用户在终端上进行输入时,不能保证不出差错,因此,若在编辑程序中,“每接受一个字符即存入用户 数据区”的做法显然不是最恰当的。较好的做法是,设立一个输入缓冲区,用以接受用户输入的一行字符, 然后逐行存入用户数据区。允许用户输入出差错,并在发现有误时可以及时更正。例如,当用户发现刚刚 键入的一个字符是错的时,可补进一个退格符"#",以表示前一个字符无效; 如果发现当前键入的行内差错较多或难以补救,则可以键入一个退行符"@",以表示当前行中的字符均无 效。 如果已经在行首继续输入'#'符号无效。

Input 输入一个多行的字符序列。但行字符总数(包含退格符和退行符)不大于 250。

Output 按照上述说明得到的输出。

Sample Input whli##ilr#e(s#*s) outcha@putchar(*s=#++);

Sample Output while(*s) putchar(*s++);

(15)Tom 的烦恼
Problem Tom 是一个非常有创业精神的人,由于大学学的是汽车制造专业,所以毕业后他用有限的资金开了一 家汽车零件加工厂,专门为汽车制造商制造零件。由于资金有限,他只能先购买一台加工机器。现在他却 遇到了麻烦,多家汽车制造商需要他加工一些不同零件(由于厂家和零件不同,所以给的加工费也不同), 而且不同厂家对于不同零件的加工时间要求不同(有些加工时间要求甚至是冲突的,但开始和结束时间相 同不算冲突)。 Tom 当然希望能把所有的零件都加工完,以得到更多的加工费,但当一些零件的加工时间要求有冲突 时,在某个时间内他只能选择某种零件加工(因为他只有一台机器),为了赚得尽量多的加工费,Tom 不 知如何进行取舍。 现在请你帮 Tom 设计一个程序,合理选择部分(或全部)零件进行加工,使得得到最大的加工费。

Input 第一行是一个整数 m,表示测试数据的个数。 每组测试数据的第一行是一个整数 n(n<=30000),表示共有 n 个零件须加工。 接下来的 n 行中,每行有 3 个整数,分别表示每个零件加工的时间要求。 第一个表示开始时间,第二个表示该零件加工的结束时间,第三个表示加工该零件可以得到的加工费。 注:数据中的每个数值不会超过 100000.

Output 对每组测试数据,输出一个整数,表示 Tom 可以得到的最大加工费。

Sample Input 1 3 1 3 10 4 6 20 2 5 25

Sample Output 30

(16) 陶陶摘苹果
【问题描述】 陶陶家的院子里有一棵苹果树, 每到秋天树上就会结出 10 个苹果。 苹果成熟的时候, 陶陶就会跑去摘苹果。 陶陶有个 30 厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。 现在已知 10 个苹果到地面的高度, 以及陶陶把手伸直的时候能够达到的最大高度, 请帮陶陶算一下她能够 摘到的苹果的数目。假设她碰到苹果,苹果就会掉下来。

【输入文件】 输入文件 apple.in 包括两行数据。第一行包含 10 个 100 到 200 之间(包括 100 和 200)的整数(以厘米 为单位)分别表示 10 个苹果到地面的高度,两个相邻的整数之间用一个空格隔开。第二行只包括一个 100 到 120 之间(包含 100 和 120)的整数(以厘米为单位),表示陶陶把手伸直的时候能够达到的最大高度。

【输出文件】 输出文件 apple.out 包括一行,这一行只包含一个整数,表示陶陶能够摘到的苹果的数目。

【样例输入】 100 200 150 140 129 134 167 198 200 111

110

【样例输出】 5

(17) 百度语言翻译机

2006 年百度之星程序设计大赛初赛题目 6 百度语言翻译机 时限 1s 百度的工程师们是非常注重效率的,在长期的开发与测试过程中,他们逐渐创造了一套他们独特的缩率语。 他们在平时的交谈,会议,甚至在各中技术文档中都会大量运用。 为了让新员工可以更快地适应百度的文化,更好地阅读公司的技术文档,人力资源部决定开发一套专用的 翻译系统,把相关文档中的缩率语和专有名词翻译成日常语言。 输入数据: 输入数据包含三部分 1. 第一行包含一个整数 N ( N<=10000 ),表示总共有多少个缩率语的词条。 2. 紧接着有 N 行的输入,每行包含两个字符串,以空格隔开。第一个字符串为缩率语(仅包含大写英文 字符,长度不超过 10 ),第二个字符串为日常语言(不包含空格,长度不超过 255 ) . 3. 从第 N+2 开始到输入结束为包含缩略语的相关文档。(总长度不超过 1000000 个字符) 输出数据: 输出将缩率语转换成日常语言的文档。(将缩率语转换成日常语言,其他字符保留原样) 输入样例

6 PS 门户搜索部 NLP 自然语言处理 PM 产品市场部 HR 人力资源部 PMD 产品推广部 MD 市场发展部

百度的部门包括 PS , PM , HR , PMD , MD 等等,其中 PS 还包括 NLP 小组。

输出样例

百度的部门包括门户搜索部,产品市场部,人力资源部,产品推广部,市场发展部等等,其中门户 搜索部还包括自然语言处理小组。

注意: 1 . 输入数据中是中英文混合的,中文采用 GBK 编码。 2 . 为保证答案的唯一性,缩率语的转换采用正向最大匹配(从左到右为正方向)的原则。请注意输入例 子中 PMD 的翻译。

(18) 猪的安家
Andy 和 Mary 养了很多猪。他们想要给猪安家。但是 Andy 没有足够的猪圈,很多猪只能够在一个猪圈安 家。 举个例子, 假如有 16 头猪, Andy 建了 3 个猪圈, 为了保证公平, 剩下 1 头猪就没有地方安家了。 Mary 生气了,骂 Andy 没有脑子,并让他重新建立猪圈。这回 Andy 建造了 5 个猪圈,但是仍然有 1 头猪没有 地方去,然后 Andy 又建造了 7 个猪圈,但是还有 2 头没有地方去。Andy 都快疯了。你对这个事情感兴趣 起来,你想通过 Andy 建造猪圈的过程,知道 Andy 家至少养了多少头猪。 输入 输入包含多组测试数据。每组数据第一行包含一个整数 n (n <= 10) – Andy 建立猪圈的次数,解下来 n 行, 每行两个整数 ai, bi( bi <= ai <= 1000), 表示 Andy 建立了 ai 个猪圈, 有 bi 头猪没有去处。 你可以假定(ai, aj) = 1. 输出 输出包含一个正整数,即为 Andy 家至少养猪的数目。 样例输入

3 31 51

72 样例输出

16

(19) 勇气的挑战
Problem 给定 n 个点的坐标(x,y,z),且 n<=50,从点 1 出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的 距离和最小?

Input 多组数据. 第 1 行 n,然后 n 行 3 个整数坐标

Output 每组一行,代表最小权和

Sample Input 3 000 110 1 -1 0

Sample Output 3.4

(20) 青蛙的约会
Description 两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条 纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没 有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某 个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰 面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候 碰面。 我们把这两只青蛙分别叫做青蛙 A 和青蛙 B,并且规定纬度线上东经 0 度处为原点,由东往西为正方向, 单位长度 1 米,这样我们就得到了一条首尾相接的数轴。设青蛙 A 的出发点坐标是 x,青蛙 B 的出发点坐 标是 y。青蛙 A 一次能跳 m 米,青蛙 B 一次能跳 n 米,两只青蛙跳一次所花费的时间相同。纬度线总长 L 米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行 5 个整数 x,y,m,n,L,其中 x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。

Output 输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"

Sample Input 12345

Sample Output 4

(21)Algorithm Gossip: 八枚银币 说明现有八枚银币a b c d e f g h,已知其中一枚是假币,其重量不同于真币,但不知是较轻 或较重,如何使用天平以最少的比较次数,决定出哪枚是假币,并得知假币比真币较轻或较 重。 解法单就求假币的问题是不难, 但问题限制使用最少的比较次数, 所以我们不能以单纯的回 圈比较来求解,我们可以使用决策树(decision tree) ,使用分析与树状图来协助求解。一个 简单的状况是这样的,我们比较a+b+c与d+e+f ,如果相等,则假币必是g或h,我们先比较g 或h哪个较重,如果g较重,再与a比较(a是真币) ,如果g等于a,则g为真币,则h为假币, 由于h比g轻而 g是真币,则h假币的重量比真币轻。

(22) Algorithm Gossip: 超长整数运算(大数运算) 说明基于记忆体的有效运用, 程式语言中规定了各种不同的资料型态, 也因此变数所可以表 达的最大整数受到限制,例如123456789123456789这样的 整数就不可能储存在long变数中 (例如C/C++等) ,我们称这为long数,这边翻为超长整数(避免与资料型态的长整数翻译混 淆) ,或俗称大数运算。 解法一个变数无法表示超长整数,则就使用多个变数,当然这使用阵列最为方便,假设程式 语言的最大资料型态可以储存至65535的数好了, 为了计算方便及符合使用十进位制的习惯, 让每一个阵列元素可以储存四个位数,也就是0到9999的数,例如:

很多人问到如何计算像50!这样的问题,解法就是使用程式中的乘法函式,至于要算到多大, 就看需求了。 由于使用阵列来储存数值, 关于数值在运算时的加减乘除等各种运算、 位数的进位或借位就 必须自行定义,加、减、乘都是由低位数开始运算,而除法则是由高位数开始运算,这边直 接提供加减乘除运算的函式供作参考,以下的N为阵列长度。

(23)Algorithm Gossip: 完美数 说明如果有一数n, 其真因数 (Proper factor) 的总和等于n, 则称之为完美数 (Perfect Number) , 例如以下几个数都是完美数: 6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 程式基本上不难,第一眼看到时会想到使用回圈求出所有真因数,再进一步求因数和,不过 若n值很大,则此法会花费许多时间在回圈测试上,十分没有效率,例如求小于10000的所有 完美数。 解法如何求小于10000的所有完美数?并将程式写的有效率?基本上有三个步骤: 求出一定数目的质数表 利用质数表求指定数的因式分解 利用因式分解求所有真因数和,并检查是否为完美数 步骤一 与 步骤二 在之前讨论过了,问题在步骤三,如何求真因数和?方法很简单,要先 知道将所有真因数和加上该数本身,会等于该数的两倍,例如: 2 * 28 = 1 + 2 + 4 + 7 + 14 + 28 等式后面可以化为: 0 1 2 0 1 2 * 28 = (2 + 2 + 2 ) * (7 + 7 ) 所以只要求出因式分解, 就可以利用回圈求得等式后面的值, 将该值除以2就是真因数和了; 等式后面第一眼看时可能想到使用等比级数公式来解, 不过会使用到次方运算, 可以在回圈 走访因式分解阵列时,同时计算出等式后面的值,这在下面的实作中可以看到。

(24)Algorithm Gossip: 中序式转后序式(前序式) 说明平常所使用的运算式,主要是将运算元放在运算子的两旁,例如a+b/d这样的式子,这 称之为中序(Infix)表示式,对于人类来说,这样的式子很容易理 解,但由于电脑执行指 令时是有顺序的,遇到中序表示式时,无法直接进行运算,而必须进一步判断运算的先后顺 序,所以必须将中序表示式转换为另一种表示方 法。 可以将中序表示式转换为后序( Postfix )表示式,后序表示式又称之为逆向波兰表示式 (Reverse polish notation) , 它是由波兰的数学家卢卡谢维奇提出, 例如(a+b)*(c+d)这个式子, 表示为后序表示式时是ab+cd+*。 解法用手算的方式来计算后序式相当的简单,将运算子两旁的运算元依先后顺序全括号起 来,然后将所有的右括号取代为左边最接近的运算子(从最内层括号开始) ,最后去掉所有 的左括号就可以完成后序表示式,例如: a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+ 如果要用程式来进行中序转后序,则必须使用堆叠,演算法很简单,直接叙述的话就是使用 回圈,取出中序式的字元,遇运算元直接输出,堆叠运算子与左括号, ISP>ICP的话直接 输出堆叠中的运算子,遇右括号输出堆叠中的运算子至左括号。 OUTPUT 例 如 (a+b)*(c+d) STACK 这个式子, 依演算 法的输出过程如 下: OP ( ( a ( a + (+ a b (+ ab ) ab+ * * ab+ ( *( ab+ c *( ab+c + *(+ ab+c

d *(+ ab+cd ) * ab+cd+ ab+cd+* 如果要将中序式转为前序式, 则在读取中序式时是由后往前读取, 而左右括号的处理方式相 反,其余不变,但输出之前必须先置入堆叠,待转换完成后再将堆叠中的 值由上往下读出, 如此就是前序表示式。

(25)Algorithm Gossip: 后序式的运算 说明 将中序式转换为后序式的好处是, 不用处理运算子先后顺序问题, 只要依序由运算式 由前往后读取即可。 解法 运算时由后序式的前方开 堆叠 始读取,遇到运算元先存入 堆叠,如果遇到运算子,则 由堆叠中取出两个运算元进 行对应的运算,然后将结果 存回堆叠,如果运算式读取 完 毕, 那么堆叠顶的值就是 答案了,例如我们计算 12+34+*这个运算式 (也就是 (1+2)*(3+4)) : 读取 1 1 2 12 + 3 // 1+2 后存回 3 33 4 334 + 3 7 // 3+4 后存回 * 21 // 3 * 7 后存回

.

(26)Algorithm Gossip: 4N 魔方阵

说明 与 奇数魔术方阵 相同,在于求各行、各列与各对角线的和相等,而这次方阵的维度是 4 的倍数。 解法 先来看看4X4方阵的解法:

简单的说,就是一个从左上由1依序开始填,但遇对角线不填,另一个由左上由16开始填, 但只填在对角线,再将两个合起来就是解答了;如果N大于2,则以 4X4为单位画对角线:

至于对角线的位置该如何判断,有两个公式,有兴趣的可以画图印证看看,如下所示: 左上至右下:j % 4 == i % 4 右上至左下:(j % 4 + i % 4) == 1

(27) 统计数字问题 1、问题描述: 一本书的页码从自然数 1 开始顺序编码直到自然数 n。 书的页码按照通常的习惯编排, 每个 页码都不含多余的前导数字 0。例如,第 6 页用数字 6 表示,而不是 06 或 006 等。数字 计数问题要求对给定书的总页码 n, 计算出书的全部页码中分别用到多少次数字 0, 1,2, …, 9。 2、题目分析: 考虑由 0,1,2,…,9 组成的所有 n 位数。从 n 个 0 到 n 个 9 共有个 n 位数,在这些 n 位数中, 0,1,2,…,9 每个数字使用次数相同,设为。满足如下递归式:由此可知, 。 据此,可从低位向高位进行统计,再减去多余的 0 的个数即可。 3、算法设计: 定义数组 a[10]存放 0 到 9 这 10 个数出现的次数,个位为第 0 位,第 j 位的数字为 r。采用 while 循环从低位向高位统计: a. 统计从个位算起前 j 位 0~9 个数; b. 如果 j+1 位为 0,去掉第 j+1 位补 0 个数; c. 统计第 j+1 位出现 1~(r-1)个数; d. 统计第 j+1 位出现 r 个数。

(28)最大间隙问题 1、问题描述: 最大间隙问题: 给定 n 个实数 x1 , x2 ,... , xn,求这 n 个数在实轴上相邻 2 个数之间的最 大差值。 假设对任何实数的下取整函数耗时 O(1), 设计解最大间隙问题的线性时间算法。 对 于给定的 n 个实数 x1 , x2 ,... , xn,编程计算它们的最大间隙。 2、题目分析: 考虑到实数在实轴上按大小顺序排列, 先对这 n 个数排序, 再用后面的数减去前面的数,

即可求出相邻两数的差值,找出差值中最大的即为最大差值。 3、算法设计: a. 用快速排序算法对这 n 个数排序,快速排序算法是基于分治策略的一个排序算 法。其基本思想是,对于输入的子数组 a[p:r],按以下三个步骤进行排序: ①分解:以 a[p]为基准元素将 a[p:r]划分为 3 段 a[p:q-1],a[q]和 a[q+1:r],使 a[p:q-1]中 任何一个元素小于等于 a[p],而 a[q+1:r]中任何一个元素大于等于 a[q]。下标 q 在划分过程 中确定。 ②递归求解:通过递归调用快速排序算法分别对 a[p:q-1]和 a[q+1:r]进行排序。 ③合并:由于对 a[p:q-1]和 a[q+1:r]的排序是就地进行的,所以在 a[p:q-1]和 a[q+1:r]都已排好的序后,不需要执行任何计算,a[p:r]就已排好序。 b. 用函数 maxtap()求出最大差值。

(29)编辑距离问题 1、问题描述: 设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 A 转换为字符串 B。这里所说的 字符操作包括 (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符。将字 符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离,记为 d(A,B)。试设计一个有效算法,对任给的 2 个字符串 A 和 B,计算出它 们的编辑距离 d(A,B)。 2、题目分析: 题目要求计算两字符串的编辑距离, 可以采用动态规划算法求解, 由最优子结构性质可 建立递归关系如下: 其中数组 d[i][j] 存储长度分别为 i、j 的两字符串的编辑距离;用 edit 标记所比较 的字符是否相同,相同为 0,不同为 1;用 m、n 存储字符串 a、b 的长度。 3、算法设计: a. 函数 min()找出三个数中的最小值; b. 函数 d()计算两字符串的编辑距离: ①用 edit 标记所比较的字符是否相同,相同为 0,不同为 1; ②分别用 m、n 存储字符串 a、b 的长度,用数组 d[i][j] 存储长度分别为 i、j 的两字符 串的编辑距离,问题的最优值记录于 d[n][m]中; ③利用递归式写出计算 d[i][j]的递归算法。 (30) 吝啬的国度
描述
在一个吝啬的国度里有 N 个城市,这 N 个城市间只有 N-1 条路把这个 N 个城市连接起来。现在, Tom 在第 S 号城市,他有张该国地图,他想知道如果自己要去参观第 T 号城市,必须经过的前一 个城市是几号城市(假设你不走重复的路)。

输入

第一行输入一个整数 M 表示测试数据共有 M(1<=M<=5)组 每组测试数据的第一行输入一个正整数 N(1<=N<=100000)和一个正整数 S(1<=S<=100000),N 表示 城市的总个数,S 表示参观者所在城市的编号 随后的 N-1 行,每行有两个正整数 a,b(1<=a,b<=N),表示第 a 号城市和第 b 号城市之间有一条路 连通。

输出
每组测试数据输 N 个正整数,其中,第 i 个数表示从 S 走到 i 号城市,必须要经过的上一个城市 的编号。(其中 i=S 时,请输出-1)

样例输入

1 10 1 1 9 1 8 8 10 10 3 8 6 1 2 10 4 9 5 3 7
样例输出

-1 1 10 10 9 8 3 1 1 8


相关文章:
试题库
试题库[1]挖掘机 6页 免费 挖掘机常见液压故障诊断排... 2页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
机械制图试题库及答案
机械制图试题库一、填空题: 1、工程常用的投影法分为两类 中正投影法属于平行投影法 中心投影法 投影法。 和 平行投影法 ,其 2、 在工程技术中为了准确地...
移动通信试题库及答案全完整
移动通信试题库 2012.10 一、填空题 1. ___个人通信___是人类通信的最高目标,它是用各种可能的网络技术实现任何人在任何时间、任 何地点与任何人进行任何种类...
操作系统试题库(经典版)
操作系统试题库(经典版)_工学_高等教育_教育专区。操作系统试题库 一, 选择题 第一部分:操作系统概述 1. 在计算机系统中,操作系统是(B). A. 一般应用软件 ...
妇产科试题库
妇产科试题库 第一部分 绪言、女性生殖系统解剖 一.是非题: 1 子宫下段由非孕时长约 1cm 的子宫颈管形成。 (-) 2.宫颈内口柱状上皮与鳞状上皮交界处是...
理论考试题库
理论考试题库_其它考试_资格考试/认证_教育专区。体育考试试题库一、单项选择题(每题 2 分,共 30 分) 1. 对老年人心血管机能有益的练习是( A 太极拳 B ...
试题库管理系统
试题库管理系统_电脑基础知识_IT/计算机_专业资料。试题库管理系统 试题库管理系统 摘要随着当今计算机技术的飞速发展, 利用计算机进行试题库的管理和考试分析已成为...
对试题库建设的认识和做法
试题库建设的认识和做法_从业资格考试_资格考试/认证_教育专区。对试题库建设的认识和做法 《山东省师专试题库建设》教学改革课题经过数年不懈努力已基本完成,通过...
《水电站》试题库完整版
5 《水电站》课程考试试题库 第二部分 填空题 录入:张超、鲁桂勇、王昊、周子杰、杨启龙 校核:李凯 1.水电站产生电能的过程是有能水流通过水轮机,将 又带动水轮...
涉密人员考试试题库及答案(整理)
涉密人员考试试题库及答案(整理)_从业资格考试_资格考试/认证_教育专区。涉密人员考试试题库及答案 保密人员考试试题 一、单项选择题(下列各题中只有一个正确答案。...
更多相关标签:
猿题库 | 360题库 | 试题库管理系统 | 题库 | 合肥工业大学试题库 | 高考试题库 | 试题库系统 | 试题 |