职场大变样社区

5598

主题

6638

帖子

79

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
79
跳转到指定楼层
楼主
发表于 2017-3-16 10:46:49 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
技术:ASP等
摘要:
一.    实验目的和要求
1. 加深对递归算法的理解,并针对具体问题设计算法;
2. 分析算法的复杂性,寻找比较高效的算法,并实现。
3. 分析格雷码问题,并设计递归算法求解之。

二.    基本原理
递归是一种重要的程序设计方法。使用递归方法有时可使算法简洁明了,易于设计。
递归指算法自己调用自己, 有直接递归与间接递归两种。
递归方法用于解决一类满足递归关系的问题。即:对原问题的求解可转化为对其性质相同的子问题的求解。

三.    该类算法设计与实现的要点
1. 递归关系(特性):产生递归的基础。
当算法中某步骤要通过解性质相同的子问题实现时,该步骤用递归调用实现。
2. 递归出口(结束条件):确定递归的层数。
    当子问题的规模充分小时可直接求解时,递归结束。
3. 参数设置:参数表示了原问题及其不同的子问题。
参数表示了子问题的大小和状态,以区别原问题以及不同层次的子问题。
4. 算法功能的设定:严格规定递归算法要解决什么样的问题。
算法功能的正确设定是保证递归过程正确进行的前提。

四.    实验内容――格雷码问题
1.问题描述
对于给定的正整数n,格雷码为满足如下条件的一个编码序列:
(1) 序列由2n个编码组成,每个编码都是长度为n的二进制位串。
(2) 序列中无相同的编码。
(3) 序列中位置相邻的两个编码恰有一位不同。
例如:n=2时的格雷码为:{00, 01, 11, 10}。
设计求格雷码的递归算法并实现。
  2. 具体要求(若在ACM平台上提交程序,必须按此要求)――平台上1769题
输入:输入的第一行是一个正整数m,表示测试例个数。接下来几行是m个测试例的数据,每个测试例的数据由一个正整数n组成。
输出:对于每个测试例n,输出2n个长度为n的格雷码。(为方便查看,在每个格雷码内,两个位之间用一个空格隔开,如,00输出为:0 0)。两个测试例的输出数据之间用一个空行隔开,最后一个测试例后无空行。
3. 测试数据
输入:2
      4
5
输出:0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 0
1 1 0 1
1 1 1 1
1 1 1 0
1 0 1 0
1 0 1 1
1 0 0 1
1 0 0 0
      
0 0 0 0 0
0 0 0 0 1
0 0 0 1 1
0 0 0 1 0
0 0 1 1 0
0 0 1 1 1
0 0 1 0 1
0 0 1 0 0
0 1 1 0 0
0 1 1 0 1
0 1 1 1 1
0 1 1 1 0
0 1 0 1 0
0 1 0 1 1
0 1 0 0 1
0 1 0 0 0
1 1 0 0 0
1 1 0 0 1
1 1 0 1 1
1 1 0 1 0
1 1 1 1 0
1 1 1 1 1
1 1 1 0 1
1 1 1 0 0
1 0 1 0 0
1 0 1 0 1
1 0 1 1 1
1 0 1 1 0
1 0 0 1 0
1 0 0 1 1
1 0 0 0 1
1 0 0 0 0
4. 设计与实现的提示
长度为n的格雷码是由长度为n-1的格雷码变换而成的。
可以用数组或字符串来存储格雷码。注意:对于较大的正整数n,用数组存储容易引起死机。
按照定义2n个长度为n的格雷码序列是不唯一的,若在ACM平台上提交程序,要求输出的编码序列与给出的范例具有相同的规律。

截图:


百度网盘下载地址(金币充值):
游客,如果您要查看本帖隐藏内容请回复



回复

使用道具 举报

108

主题

935

帖子

0

积分

禁止发言

积分
0
沙发
发表于 2018-10-24 12:38:27 | 只看该作者
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

职场大变样社区 分享高质量学习资料(电子课本、毕业设计、编程视频、项目源码、电子书籍等)

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