八、候选设计题目
第一类 一维数组的使用 题目1.1 一维数组实现约瑟夫环
问题描述：设有编号为1，2，……，n的n(n>0)个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，求n个人出圈的次序。如果每个人持有的密码不同，如何修改程序完成约瑟夫环。
题目1.2 一维数组实现集合的基本运算
问题描述：用一维数组实现集合的判等、交、并和差等基本运算。集合中的元素具有相同的数据类型，因此，集合可用一维数组进行存储。需要注意集合中元素的唯一性，即在数组中不存在值相同的元素。
题目1.3 大整数的代数运算
问题描述：VC++编程环境中的int类型能表示的整数范围是-231~231-1，不能存储超过10位的整数。有些问题需要处理的整数远远不只10位，这种大整数用C语言的基本数据类型无法直接表示。假设大整数的长度在100位以下，请完成两个大整数的加、减、乘和除等基本的代数运算。
题目1.4 士兵队列训练问题
问题描述：某部队进行新兵队列训练，将新兵从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数。。。，以后从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。给定训练人数，请给出最后剩下三个士兵的编号。
题目1.5 桥本分数
问题描述：把{1, 2, ?,9}这9个数字填入下图所示的9个方格中，使得等式成立（要求不得重复）。请给出所有满足桥本分数的情况。
? ? ? = ＋ ?? ?? ?? 图1 桥本分数 5
题目1.6 荷兰国旗问题
问题描述：要求重新排列一个由Red、White和Blue（这是荷兰国旗的颜色）构成的数组，使得所有的Red都排在最前面，White排在其次，Blue排在最后。
第二类 二维数组的使用
题目2.1 幻方
问题描述：幻方在我国古代称为“纵横图”，是在一个 n×n 的矩阵中填入1到n2的数字，使得每一行、每一列、每条对角线的累加和都相等。例如图2就是一个3阶幻方。请设计二维数组存储幻方，并完成任意n阶幻方的填数过程，注意奇数阶幻方和偶数阶幻方的填数过程不一样。
6 7 2 15 1 5 9 8 3 4 15 15 15 15 15 15 15 图2 3阶幻方示例 题目2.2 数字旋转方阵
问题描述：给定方阵的阶数，输出如图3所示N×N（1≤N≤10）的顺时针旋转和逆时针旋转两种数字旋转方阵。
1 20 19 18 17 16 1 2 3 4 5 6
2 21 32 31 30 15 20 21 22 23 24 7
3 22 33 36 29 14 19 32 33 34 25 8
4 23 34 35 28 13 18 31 36 35 26 9
5 24 25 26 27 12 17 30 29 28 27 10
6 7 8 9 10 11 16 15 14 14 12 11
(a) 逆时针旋转方阵 (b) 顺时针旋转方阵
图3 数字旋转方阵示例
题目2.3 蛇形矩阵
问题描述：蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。例如，图4给出了一个5阶的蛇形矩阵。
1 2 3 4 3 2 1 1 3 6 10 15 2 2 3 4 3 2 2 2 5 9 14 3 3 3 4 3 3 3 4 8 13 4 4 4 4 4 4 4 7 12 3 3 3 4 3 3 3 11 2 2 3 4 3 2 2 6 图4 5阶蛇形矩阵 1 2 3 4 3 2 1 图5 7阶横竖折对称矩阵
题目2.4 横竖折对称方阵
问题描述：在横竖折对称方阵中，横向与纵向正中有一对称轴，两个对称轴将矩阵分为四个区域，每个区域的特征是同数字横竖折递减，至四个顶角元素为1。图5是一个7阶横竖折对称方阵。
题目2.5 湖波问题
问题描述：由于最近下雨频繁，雨水在小明的农场里的不同地域堆积起来，假设小明的农场可以用一个N×M的矩阵表示，则将农场分割成N×M块地。如果某块地盛满雨水则用'W'表示，否则用'L'表示，如果一块地以及周围四块地均有雨水，则形成一个水洼。小明想要知道在他的农场里有多少个水洼。
第三类 指针的使用 题目3.1 链表实现约瑟夫环
问题描述：设有编号为1，2，……，n的n(n>0)个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，求n个人出圈的次序。由于约瑟夫环带有典型的循环特性，考虑用循环单链表存储，请用循环单链表实现约瑟夫环问题。
题目3.2 单词统计
问题描述：从键盘输入n个英语单词，输入格式为n, w1, w2, …,wn，其中n表示随后输入英语单词个数，将输入的单词以单链表形式存储，如果单词重复出现，则在链表上只保留一个，并统计单词重复出现的次数。
题目3.3 输入法词频调整
问题描述：中文输入法对于每个发音相同的汉字都有一个列表，可以根据使用的频率调整出现的顺序。例如，设输入法“de”对应五个字“的”、“得”、“地”、“德”、“低”，按顺序设定其初始频率。每次输入一个字，将这个字的频率加1，再按其频率大小降序输出。
7
题目3.4 发纸牌
问题描述：假设纸牌的花色有梅花、方块、红桃和黑桃，纸牌的点数有2、3、4、5、6、7、8、9、10、J、Q、K、A，请根据用户输入的纸牌张数n，随机发四手纸牌，每手共有n张纸牌。（所谓一手纸牌指的是一个玩家手里的纸牌）
题目3.5 打字游戏
问题描述：在屏幕上随机输出一行英文字符，该行字符逐渐下落，如果游戏者输入这行英文字符中的某个字符，该字符消失，游戏结束后给出用户输入的正确率。注意区分大小写。
第四类 简单的算法设计技术 题目4.1 最近对问题
问题描述：最近对问题要求在一个包含n个点的集合中找出距离最近的两个点。严格地讲，距离最近的点对可能多于一对，简单起见，只考虑二维的情况，只找出其中的一对即可。提示：平面上两个点pi=(xi, yi)和pj=(xj, yj)之间的距离是欧几里德距离（Euclidean distance）：
d?(xi?xj)2?(yi?yj)2
蛮力法求解最近对问题的过程是显而易见的：分别计算每一对点之间的距离，然后找出距离最小的那一对。
题目4.2 两个序列的中位数
问题描述：一个长度为n（n≥1）的升序序列S，处在第n/2个位置的数称为序列S的中位数（median number），例如，序列S1={11, 13, 15, 17, 19}的中位数是15。两个序列的中位数是他们所有元素的升序序列的中位数，例如，S2={2, 4, 6, 8, 20}，则S1和S2的中位数是11。现有两个等长升序序列A和B，请找出两个序列的中位数。
题目4.3 逆序对个数
问题描述：有一个正整数序列{a1, a2, ?, an}，给定序号i和（j1≤i, j≤n），若i
题目4.4 割钢管
问题描述：A公司有一台钢管切割机提供钢管加工业务，钢管切割机每次可以将一根钢
8
管按照要求在指定位置切割为2段。每次切割的费用为钢管的长度。给定一根长度为L的钢管，要求将其在位置l1 题目4.5 埃及分数 问题描述：埃及同中国一样，也是世界文明古国之一。古埃及人只用分子为1的分数，在表示一个真分数时，将其分解为若干个埃及分数之和，例如：7/8表示为1/2 + 1/3 + 1/24。埃及分数问题（Egypt fraction）要求把一个真分数表示为最少的埃及分数之和的形式。 题目4.6 付款问题 问题描述：假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客的现金是m，如何给付才能使付出的货币数量最少？请给出付款方案。 题目4.7 捕鱼知多少 问题描述：A、B、C、D、E五个人合伙夜间捕鱼，上岸时都疲惫不堪，各自在湖边的树丛中找地方睡觉了。清晨，A第一个醒来，将鱼分成5份，把多余的一条扔回湖中，拿自己的一份回家了；B第二个醒来，也将鱼分成5份，扔掉多余的一条鱼，拿自己的一份回家了；接着，C、D、E依次醒来，也都按同样的办法分鱼。问：5个人至少共捕到多少条鱼？每个人醒来后看到多少条鱼？ 题目4.8 假币问题 问题描述：在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，请设计程序找出这枚假币。 第五类 系统设计类 1. 职工信息管理系统设计 职工信息包括职工号、姓名、性别、年龄、学历、工资、住址、电话等（职工号不重复）。试设计一职工信息管理系统，使之能提供以下功能： 1、职工信息录入功能(职工信息用文件保存)－－输入 2、职工信息浏览功能－－输出 3、职工信息查询功能－－算法 9