递归算法设计与应用

1、实验二 递归算法设计与应用一. 实验目的和要求1. 加深对递归算法的理解，并针对具体问题设计算法； 2. 分析算法的复杂性，寻找比较高效的算法，并实现。3. 分析格雷码问题，并设计递归算法求解之。二. 基本原理递归是一种重要的程序设计方法。使用递归方法有时可使算法简洁明了，易于设计。递归指算法自己调用自己, 有直接递归与间接递归两种。递归方法用于解决一类满足递归关系的问题。即：对原问题的求解可转化为对其性质相同的子问题的求解。三. 该类算法设计与实现的要点1. 递归关系（特性）：产生递归的基础。当算法中某步骤要通过解性质相同的子问题实现时，该步骤用递归调用实现。2. 递归出口（结束条件）：确定

2、递归的层数。 当子问题的规模充分小时可直接求解时，递归结束。3. 参数设置：参数表示了原问题及其不同的子问题。参数表示了子问题的大小和状态，以区别原问题以及不同层次的子问题。4. 算法功能的设定：严格规定递归算法要解决什么样的问题。算法功能的正确设定是保证递归过程正确进行的前提。四. 实验内容格雷码问题1.问题描述对于给定的正整数n，格雷码为满足如下条件的一个编码序列：(1) 序列由2n个编码组成，每个编码都是长度为n的二进制位串。(2) 序列中无相同的编码。(3) 序列中位置相邻的两个编码恰有一位不同。例如：n=2时的格雷码为：00, 01, 11, 10。设计求格雷码的递归算法并实现。 2

3、. 具体要求（若在ACM平台上提交程序，必须按此要求）平台上1769题输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由一个正整数n组成。输出：对于每个测试例n，输出2n个长度为n的格雷码。（为方便查看，在每个格雷码内，两个位之间用一个空格隔开，如，00输出为：0 0）。两个测试例的输出数据之间用一个空行隔开，最后一个测试例后无空行。3. 测试数据输入：2 45输出：0 0 0 00 0 0 10 0 1 1 0 0 1 0 0 1 1 0 0 1 1 10 1 0 10 1 0 01 1 0 01 1 0 11 1 1 11 1 1 01 0

4、1 01 0 1 11 0 0 11 0 0 0 0 0 0 0 00 0 0 0 10 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 10 0 1 0 10 0 1 0 00 1 1 0 00 1 1 0 10 1 1 1 10 1 1 1 00 1 0 1 00 1 0 1 10 1 0 0 10 1 0 0 01 1 0 0 01 1 0 0 11 1 0 1 11 1 0 1 01 1 1 1 01 1 1 1 11 1 1 0 11 1 1 0 01 0 1 0 01 0 1 0 11 0 1 1 11 0 1 1 01 0 0 1 01 0 0 1 11

5、0 0 0 11 0 0 0 04. 设计与实现的提示长度为n的格雷码是由长度为n-1的格雷码变换而成的。可以用数组或字符串来存储格雷码。注意：对于较大的正整数n，用数组存储容易引起死机。按照定义2n个长度为n的格雷码序列是不唯一的，若在ACM平台上提交程序，要求输出的编码序列与给出的范例具有相同的规律。五、实验的运行程序方法一：#include<stdio.h>#include<sstream>#include <map>#include <iostream>#include <math.h>using namespace std;

6、char * P ;void GetNearest(int N) P=new charN+1;for(int i=0;i<N;i+)Pi='0'PN=0;cout<<P<<endl;for( i=0;i<N;i+)PN-i-1='1'cout<<P<<endl;for(int j=0;j<(int)pow(2.0,i)-1;j+) PN-j%i-1=PN-j%i-1='0'?'1':'0'cout<<P<<endl; void

7、 main() GetNearest(4);方法二：#include <iostream>#include <string>#include <cstdio>#include <string>#include <stack>#include <conio.h>using namespace std;/定义结点数据结构typedef struct CodeNode char *code; /格雷码串 struct CodeNode *next; /指向上一个码段的指针CodeNode, *CodeList;/函数声明void

8、 GenerateGrayCode( int n );CodeList CreateCodeList();void IncreaseCode( CodeList L );void PrintGrayCode( CodeList L );void ReleaseGrayCode( CodeList L );char *CodeCat( char *des, char *src );/定义全局变量CodeList L;void main() int nbits, array10; / char c;cin>>nbits;for(int i=0;i<nbits;+i)cin>

9、>arrayi;for(int k=0;k<nbits;+k)GenerateGrayCode( arrayk); /产生编码printf("n");PrintGrayCode( L ); /打印编码printf("n"); ReleaseGrayCode( L ); /释放内存void GenerateGrayCode( int n ) /算法主体 if(n = 1) L = CreateCodeList(); else GenerateGrayCode( n-1 ); IncreaseCode( L ); CodeList CreateC

10、odeList() /建立链表 CodeList Head = (CodeList)malloc(sizeof(CodeNode); CodeList p = (CodeList)malloc(sizeof(CodeNode); CodeList q = (CodeList)malloc(sizeof(CodeNode); p->code = "0" q->code = "1" p->next = q; q->next = NULL; Head->next = p; return Head;void ReleaseGrayC

11、ode( CodeList L ) /释放内存空间 CodeList q; while( L ) q = L; L = L->next; free(q); void IncreaseCode( CodeList L) /做编码的一位扩展 CodeList p; p = L; int count = 0; stack <char*> CodeStack; /定义栈 while( p->next ) CodeStack.push( p->next->code ); p->next->code = CodeCat("0",p->

12、;next->code ); p = p->next; count+; while( count > 0 ) CodeList q = (CodeList)malloc(sizeof(CodeNode); q->code = CodeCat( "1",CodeStack.top() ); CodeStack.pop(); q->next = NULL; p->next = q; p = p->next; count-; void PrintGrayCode( CodeList L ) /打印编码 CodeList p; p = L->next; while(p) cout<<p->code<