《湖州师范学院100822实验二 递归与分治》由会员分享，可在线阅读，更多相关《湖州师范学院100822实验二 递归与分治（12页珍藏版）》请在金锄头文库上搜索。
1、实验二 递归与分治(二)一、实验目的1、进一步理解递归和分治策略的基本思想。2、进一步掌握递归与分治策略结合使用的算法设计技巧。二、实验要求1、通过试题的设计实验，掌握递归设计以及算法效率分析。2、通过试题的设计实验，掌握递归与分治算法设计以及算法效率分析。三、实验内容和步骤(一)实验11、实验题目2、上机过程 算法设计说明用来说明算法设计的基本思想、算法的复杂性分析。它包括：设计的基本思想、数据的 输入(前提条件)和输出(后置条件)、设计方法、数据结构、数据说明以及算法的复杂性分析 说明等。 程序框图 程序清单 本题小结它包括：上机时遇到的问题及解决方法，观察到的现象及其分析，对算法设计技巧
2、的总 结及分析等；程序的输出结果及对结果的分析；实验的心得体会等。(二)实验2同上实验报告完成 人:年月 日Problem A:再次Hanoi塔问题Time Limit:2000MS Memory Limit:65536KTotal Submit:249 Accepted:164Description古老的汉诺塔问题是：用最少的步数将N个半径互不相等的圆盘从l号柱利用2号柱全部移 动到3 号柱，在移动的过程中小盘要始终在大盘的上面。现在再加上一个条件：不允许直接把盘从l号柱移动到3号柱，也不允许直接把盘从3号柱 移动到 1 号柱。把盘按半径从小到大用1N编号。每种状态用N个整数表示，第i个整数
3、表示i号盘所在 的柱的编号。则N=2时的移动方案为(1,1)三(2,1)三(3,1)三(3,2)三(2,2)三(1,2)三(1,3)三(2,3)三(3,3)初始状态为第O步，编程求在某步数时的状态。Input输入的第1行为整数T (1WTW50000),表示输入数据的组数。接下来的丁行，每行有两个 整数N, M(1WNW19,OWM W移动N个圆盘所需的步数)。Output输出共有 T 行。对于每组输入数据，输出N个整数表示移动N个盘在M步时的状态，每两个数之间用一个 空格隔开，行首和行末不要有多余的空格。Sample Input420253031Sample Output11121112 1
4、 1#include using namespace std;int f20,ans20;void Compute(int n,int m,int s,int anx,int d) if(n=0)return;if(m=fn-1)ansn=s;Compute(n-1,m,s,anx,d); return;if(m=2*fn-1+1)ansn=anx;Compute(n-1,m-(fn-1+1),d,anx,s);return;ansn=d;Compute(n-1,m-(2*fn-1+2),s,anx,d);return;int main()int t,n,m,i;f0=0;for(i=1;i=
5、19;i+)fi=fi-1*3+2;scanf(%d,&t);while(t-)scanf(%d%d,&n,&m);Compute(n,m,1,2,3);for(i=1;i=n;i+)printf(i=1?%d: %d,ansi);printf(n);return 0;Problem B:Gray codeTime Limit:2000MS Memory Limit:65536KTotal Submit:628 Accepted:377DescriptionGray code is an interesting code sequence and has many applications i
6、n computer science.No matter you have known it before or not, here are some introductions about its features:(1) Gray code has 2An unique elements;(2) Each element contains n digits of O or l;(3) Each pair of adjacent elements has exactly one different digit.For example, when n = 2, one of the gray
7、code sequences is: 00,01,11,10.Now, the task is quite simple, given a positive integer n, generate the corresponding Gray code sequence.InputInput may contain multiple test cases. Each test case consists of one positive integer n (n 16), Input is terminated by a case with n = O, which should not be
8、processed.OutputFor eacb test case, output the corresponding Gray code sequence, one element per line.There may be multiple answers, any of them will be accepted. Please output a blank line after each test case.Sample Input12OSample OutputO100011110#include int n,i;char a16;void GrayCode(int k)if(k=
9、n)for(i=0;in;i+)printf(%c,ai);printf(n);return;GrayCode(k+1);ak=0+1-ak;GrayCode(k+1);int main()while(scanf(%d,&n)!=EOF&n)for(i=0;i16;i+)ai=0;GrayCode(0); printf(n);return 0;Problem C:比赛安排设有2An (n=6)个球队进行单循环比赛，计划在2An - 1天内完成，每个队每天进行一 场比赛。设计一个比赛的安排，使在25 - 1天内每个队都与不同的对手比赛。例如 n=2 时的比赛安排：队 1 2 3 4比赛 1=2
10、3=4 一天1=3 2=4 二天1=4 2=3 三天Input输入由多组测试数据组成。 每组测试数据输入一个正整数代表题目中的 n。Output对应每组输入，输出如样例所示。1-2， 3-4 表示第一天1队与2 队， 3队与4队比赛Sample Input2Sample Output1-2， 3-41-3， 2-41-4， 2-3#include#include#define MAX 64void Arrange(int aMAX, int n, int left, int right);int main()int aMAXMAX = 0;int bMAX;int i, j, n ,k,p;w
11、hile(scanf(%d,&n)!=EOF)k=1;for(i=1;i=n;i+) k=k*2;for (i=0; ik; +i) a0i = i + 1;Arrange(a, k, 0, k-1);/* for (i=0; ik; i+) for (j=0; jk; j+)printf(%3d, aij); printf(n);*/ for(j=0;jk-1;j+) memset(b,0,sizeof(b);p=0; printf(,j+1);for(i=0;ik;i+) if(bi+1=0)p+; if(p=k/2) printf(%d-%d,i+1,aij+1);else printf
12、(%d-%d,i+1,aij+1); baij+1=1; printf(n); getchar();return 0;void Arrange(int aMAX, int n, int left, int right) if (n 2) return;int i, j;int mid = (left+right)/2;n /= 2;Arrange(a, n, left, mid); Arrange(a, n, mid+1, right);for (i=0; in; i+)for (j=left; j=mid; j+)ai+nj+n = aij;for (j=mid+1; j=right; j+
13、)ai+nj-n = aij;Problem D:Counting(Extreme)Time Limit:1000MS Memory Limit:65536KTotal Submit:1032 Accepted:501Description问题描述：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个 页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或 006 等。数字 计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0，1,2,， 9。编程任务：给定表示书的总页码的10进制整数n (iWnWlOT)。编程计算书的全部页码中分别用到多 少次数字0, 1, 2,，9。Input输入由多组测试数据组成。每组测试数据输入只有1行，给出表示书的总页码的整数n。Output对应每组输入，输出共有10行，在第k行输出页码中用到数字k-1的次数，k=1, 2,10。Sample Input11Sample Output411111111#include void cx(int sn10, int n)int i,c,k,s,pown;for(i=0;i0;k+,n/=10,pown*=10) c=n%10;for(i=0;i10;i+)sni+=c*k*pown/10; for(i=0;ic;i+)sni +
