算法设计：第八讲

《算法设计：第八讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【例题7】游戏问题：12个小朋友手拉手站成一个圆圈，从某一个小朋友开始报数，报到7的那个小朋友退到圈外，然后他的下一位重新报“1”。这样继续下去，直到最后只剩下一个小朋友，求解这个小朋友原来站在什么位置上呢？3.2.3数组记录状态信息在个人计算机中，对超过长整型的多位数操作时，只能借助于数组才能精确存储及计算。（1）使用字符数组存储输入的高精度数，每个数组元素对应一个数字。【例题8】高精度数据*长整数3.2.4大整数存储及运算（2）使用数组存储输出的高精度数，每个数组元素存储多位数字。【例题9】编程求N！的准确值。N<=100

2、（每个数组元素存储6位数字）（1）存储结果需要的数组长度事先估计（长度=log(n)*n/6+2)边计算边统计（2）结果的输出3.2.4大整数存储及运算矩阵：用二维数组存储问题：趣味矩阵中字符或数据的规律很容易发现，但是按规律直接输出却不容易。解决方法：设计算法将数据先存储到二维数组中，最后输出二维数组的内容。3.2.5构造趣味矩阵3.2.5构造趣味矩阵3）用i代表行下标，以j代表列下标，则对n*n矩阵有以下常识：主对角线元素i==j；副对角线元素:下标下界为1时i+j==n+1，下标下界为0时i+j==n-1；主上三角◥元素

3、:i<=j；主下三角◣元素:i>=j；次上三角◤元素：下标下界为1时i+j<=n+1，下标下界为0时i+j<=n-1；次下三角◢元素：下标下界为1时i+j>=n+1，下标下界为0时i+j>=n-1；【例题10】编程打印有如下规律的n*n方阵3.2.4大整数存储及运算【例题11】螺旋阵：任意给定的n值，按如下螺旋的方式输出方阵3.2.4大整数存储及运算3.2.5构造趣味矩阵【算法设计1】：四角元素分别归四个边（1）此例可以按照“摆放”数据的过程，逐圈分别处理每圈的左侧、下方、右侧、上方的数据。圈数：(n+1)/2第i圈的处理过程

4、：for(j=i;j<=n-i;j=j+1){a[j][i]=k；k=k+1;}/左侧/for(j=i;j<=n-i;j=j+1){a[n+1-i][j]=k;k=k+1;}/下方/for(j=n-i+1;j>=i+1;j=j-1){a[j][n+1-i]=k;k=k+1;}/右侧/for(j=n-i+1;j>=i+1;j=j-1){a[i][j]=k;k=k+1;}/上方/3.2.5构造趣味矩阵【算法设计2】：通过算术运算将4个方位的处理归结为一个循环完成，约定四角数据分别属于先处理的行或列。一圈的情况为：3.2.5构造趣味

5、矩阵//n代表矩阵的规模，x代表填入的数据inta[100][100];k=n;t=1;while(x<=n*n){for(y=1;y<=2*k-1;y++)//半圈{if(y<=k)i+=t;elsej+=t;a[i][j]=x;x++;}t=-t;k--;}intb[2];//b[0]代表i，b[1]代表jb[y/(k+1)]+=t;a[b[0]][b[1]]=x;【例题12】打印魔方阵（奇数魔方阵）3.2.4大整数存储及运算3.2.5构造趣味矩阵【算法设计】规则描述如下：（1）首先将1填在方阵第一行的中间。（2）下一个数

6、填在上一个数的主对角线的上方，即若上一个数的位置是（i,j），下一个数应填在（i-1,j-1）。（3）若应填写的位置下标出界，则出界的值用n来替代；（4）若应填的位置虽然没有出界，但是已经填有数据的话，则应填在上一个数的下面（行加1，列不变），即取i1=i+1，j1=j。直到把n*n个数全部填入方阵中。3.2.5构造趣味矩阵Input(n);while(n%2==0){printf(“error!”,input(n);}i=1;j=(n+1)/2;x=1;While(x<=n*n){a[i][j]=x;m=i;n=j;i--;

7、j--;if(i==0)i=n;if(j==0)j=n;if(a[i][j]!=0){i=m+1;j=n;}}3.2.6一维与二维的选择在有些应用中，原始数据表面上看是一维信息，但使用二维数组存储有关信息后，更容易设计算法。【例题13】统计问题：找出链环数字对的出现的次数输入n（2≤n≤100）个数字（即0—9之间的数据），然后统计出这组数中相邻两数字组成的链环数字对出现的次数。例如：输入：n=2001598722232787879659输出：（7,8)=2(8,7)=3(7,2)=1(2,7)=1(2,2）=2(2,3)=1

8、(3,2)=13.2.6一维与二维的选择[实现]（1）使用一维数组存储计数：将相邻的两个数转换成一维数组的下标：x=m*10+j;a[x]++将一维数组下标转换成对应的数对：m=i/10n=i%10if(m*10+n)!=0&&(n*10+m)!=0（2）使用二维数组存储计数