格雷码问题递归算法设计和实验

一. 实验目的和要求 

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 00 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平台上提交程序,要求输出的编码序列与给出的范例具有相同的规律。

本站大部分下载资源收集于网络,不保证其完整性以及安全性,请下载后自行测试。 本站资源仅供学习和交流使用,版权归资源原作者所有,请在下载后24小时之内自觉删除。 若作商业用途,请购买正版,由于未及时购买和付费发生的侵权行为,与本站无关。
写毕设-专注毕业设计源码程序定制下载 » 格雷码问题递归算法设计和实验

提供最优质的论文资源集合

立即查看 了解详情