计算机编程能力培养课程设计题目_2014.pdf

1 2014 年年通信工程学通信工程学院院计算机能力培养课程设计计算机能力培养课程设计题目题目 题目一题目一 计算圆周率计算圆周率 读懂下面著名的 C 语言 天书 这段代码只用了四行代码 include 预编译命令不算 就计算了 800 位圆周率 其算法自有其高明这处 所以本题更重要的是要论述清楚背后的数 学原理 include long a 10000 b c 2800 d e f 2801 g void main for b c f b a 5 for d 0 g c 2 c 14 printf 4d e d a e d a for b c d f b a f b d g d g b d b scanf s return 题目二题目二 稳定伴侣问题稳定伴侣问题 有 n 个男孩 m1 m2 mn与 n 个女孩 w1 w2 wn 每一个男孩 mi都依照喜爱这 n 个女孩的程度列成一张表 最喜欢的女孩排在第 1 位 最不喜爱的女孩排在第 n 位 同样地 每一个女孩 wi也依照她喜爱 n 个男孩的程度列成一张表 请写一个程序 把每一个男孩与 女孩的喜爱表格读入 并且把男孩与女孩一一配对 使得 如果 mp与 wq是一对的话 那么 第一 对 mp的喜爱表格中排在 wq之前的女孩而言 她的伴侣在她的表格中一定排在 mp之 前 第二 对 wq的喜爱表格中排在 mp之前的男孩而言 他的伴侣在他的表格中一定排在 wq之前 这就是稳定伴侣 Stable Marriage 问题 说明 这个问题恐怕要多说一些才能讲得明白 先讲不稳定 Unstable 的情况 如果 m 的女 伴记成 PM m 而 w 的男伴记成 PW w 如果有一对男孩与女孩 m 与 w 他们不是伴侣 用上面的记号 m 的伴侣是 PM m w 的伴侣是 PW w 但 m 比较中意 w 而不是 PM m 则同时 w 比较中意 m 而不是 PW w 的时候 m 与 w 就一定心不甘情不愿了 例 如 如果 A 与 B 是男孩 X 与 Y 是女孩 A 比较中意 X B 比较中意 Y A 与 Y B 与 X 结伴 那么 A 与 Y 心目中的情人都不是对方 B 与 X 亦然 这就是不稳定的状况 稳定伴 侣的问题 就是要在喜爱的表格中配出最合适 稳定的伴侣 而不是 乔太守乱点鸳鸯谱 制造对对怨偶 看一个完整的例子 假设男孩与女孩都用编号 1 2 3 4 其喜爱表格如表 1 所示 表 1 男 孩 女 孩 1 2 4 1 3 1 2 1 4 3 2 3 1 4 2 2 4 3 1 2 3 2 3 1 4 3 1 4 3 2 4 4 1 3 2 4 2 1 4 3 2 表格中指出 男孩 1 最中意的女孩是 2 其次是 4 与 1 最后是 3 对于女孩 3 而言 她最中意 1 其次是 4 与 3 最后是 2 对于这两份喜欢表格而言 稳定伴侣是如表 2 所示 表 2 男 孩 女 孩 1 4 2 3 3 2 4 1 第 1 号男孩与第 4 号女孩配对 他们是不是怨偶 在第 1 号男孩喜欢表格中 排在第 4 号女孩之前的是第 2 号 再看第 4 号女孩 在她的喜爱表格中排在 1 之前的是第 2 号男孩 于是都符合了稳定条件 用同样的方法可以查证其他的 3 对伴侣 在编写程序时 可以用男孩为主 对女孩求婚 而由女孩由她的喜爱表格来决定接受 还是不接受 如果可以接受 就不妨先接受 等到有更中意的男孩求婚了 就中止上一个约 定 另结新欢 不是现实世界 不必太拘泥 数据证明 一定可以找出稳定伴侣的结果的 在常见的问题中 计算机择友就是一个类似的问题 但要求却比较松些 因为男友双 方不必列出对 所有 对象的喜爱程度 而且也有可能出现喜爱程度相同的情形 当然解题 的方法就复杂了 题目三题目三 生命游戏生命游戏 请写一个模拟生命游戏 Game of Life 的程序 如果不知道所谓生命游戏 请看下面 的说明 说明 生命游戏是一个很简单 但却是很有趣的程序习题 在一个四周都可以延伸到无限的 棋盘上的某个格子中会有一个有机体 每一个有机体在时间 t 时 会依照环绕着它的 8 个邻 居的特性而决定在时间 t 1 时是否能生存下去 如果某一格在时间 t 时 1 有一个有机体 但是它的邻居少于或等于 1 个 或者是大于 3 个 那就会因为不 够稠密或太过稠密 这个有机体在时间 t 1 时就会死亡 换言之 在 t 1 时间 那一格中不 会存在有机体 下面就是几个在时间 t 1 时会死亡的例子 如图 1 所示 图 1 2 有有机体在该处 当只有 2 个或 3 个邻居时 就可以继续生存 下面就是几个可 以生存的例子 如图 2 所示 太 少 太 少 太 多 3 图 2 3 如果没有有机体 而那一格恰好有 3 个邻居时 当时间为 t 1 时 那一格就会生 出一个有机体 下面就是几个可以从 无 到 有 的例子 如图 3 所示 图 3 4 其他情形不会造成新的有机体出生 程序要输入棋盘的大小 毕竟内存有限 不能表示无限的棋盘 不是吗 并且输入 最大的时间值 比如 N 然后输入一个在开始时有机体分布情况 最后显示出时间为 2 3 N 时棋盘上的状态 一般而言 最终的结果不外乎 4 种 第一种是不到时间 N 时 所有有机体全都死光 第二种是到了某个时间 棋盘就不再发生变化 生者生存 这就叫做稳定 Stable 状态 第三种则是到了某个时间之后 棋盘上的分布方式就产生循环 也就是说 棋盘上有某几种 状况周而复始地以周期性方式出现 第四 也就是最后一种 它不是上述三种情况之一 程 序应该可以查出在时间 N 之前棋盘进入稳定状态 或者是有机体全都死 第三种情况是不 容易找出来的 为什么 题目四题目四 完美的代价完美的代价 回文串回文串 是一种特殊的字符串 它从左往右和从右往左读是一样的 有人认为回文串 是一种完美的字符串 现在给你一个字符串 它不一定是回文串 请你计算最少的交换次数 使得该串变成一个回文串 这里的交换指将字符串中两个相邻的字符互换位置 例如所给的 字符串为 mamad 第一次交换 ad 得到 mamda 第二次交换 md 得到 madma 第三次交 换 ma 得到 madam 回文 完美 程序要求从键盘读入数据 第一行是一个整数 N N 8000 表示所给字符串的长度 第二行是所给的字符串 长度为 N 且只包含小写英文字母 如果所给字符串能经过若干次 交换变成回文串 则输出所需的最少交换次数 否则 输出 Impossible 如下面两个例子 例 1 5 mamad 3 4 例 2 6 aabbcd Impossible 题目五题目五 马尔可夫链算法生成随机可读的文本马尔可夫链算法生成随机可读的文本 题目有关马尔可夫链的一个应用 输入一篇文章 其实是单词序列 建立前缀表后缀 表 然后根据前缀随机选择后缀 如此迭代 生成一篇 看起来像文章的随机文本 将输入的文本看作相互重叠的短语序列 每个短语可分为多个词构成的前缀和一个词的 后缀 依据对输入的统计性质 随机地选择前缀后面的特定后缀 生成随机输出 以三个词 的短语 利用连续两个词构成前缀 为例 生成随机文本的过程如下 设置 W1 和 W2 为文本的起始词 输出 W1 和 W2 循环 随机地选出 W1W2 的一个后缀 W3 输出 W3 W1 W2 W2 W3 重复循环 为说明问题 假设采用 人月神话 中的两个句子生成一些随机文本 采用两词前缀 Show your flowchars and conceal your tables and I will be mystified Show your tables and your flowcharts will be obvious end 下面是一些输入的词对和跟随它们之后的词 输入前缀输入前缀 跟随的后缀词跟随的后缀词 Show your flowcharts tables your flowchart and will flowcharts and conceal flowcharts will be your tables and and will be mystified obvious be mystified Show be obvious end 这里注意对 词 的定义 将标点符号也附在词的后面 words 和 words 是不同 的词 词 定义为任何实际位于空格之间的内容 注意上面输入的文本中 Show yourt 和 your flowchart your tables 和 will be 均在文本中 出现了两次 因此他们都有两个后缀 处理上面的文本的马尔可夫算法将首先打印出 show your 然后随机取出 flowcharts 或 table 如果选中了前者 前缀就变成 your flowcharts 而 下一个词应该是 and 或 will 如果它选取 tables 下一个词就应该是 and your tables 的两个 后缀都是 and 这样继续下去 直到产生出足够多的输出 或者在找后缀时遇到了结束标 志 上面文本做为输入后 可能的输出是 Show your tables and I will be obvious 提示 数据结构中应当有一种散列结构 hash table 哈希表 其关键码是前缀 其值是 5 对应于前缀的所有可能后缀的集合 注意注意事项事项 1 任选一题来做 编程语言不做限制 2 请于 2014 8 29 号下午号下午 5 点前点前上交课程设计报告 警告警告 晚于这个时间上交可能将影响成 绩 麻烦各班班长负责收一下报告 交报告地点 逸夫楼一楼大厅 信号处理与检测实验室 注意不要上楼梯 直接从两侧门洞进入 如果温老师不在交给实验室里的研究生即可 3 报告提纲 框架设计 包括算法设计 程序流程图 各模块之间关系等 详细设计 详细 说明关键