第三章2 算法与数据结构
算法设计:有趣的是如果我们将1,2,„„n2 按某种规则依次填入 到方阵中,得到的恰好是奇次魔方阵,这个规则可以描述如下: (1)首先将1填在方阵第一行的中间,即(1,(n+1)/2)的位置; (2)若上一个数的位置是(i,j),下一个数应填在(i1,j1),其 中i1=i-1、j1=j-1。 (3)若应填写的位置下标出界,则出界的值用n 来替代;即若i1=0,则取i1=n;若j-1=0,则取j1=n。 (4)若应填的位置虽然没有出界,但是已经填有数据的话,则应填 在上一个数的下面(行加1,列不变),即取i1=i+1,j1=j。 这样循环填数,直到把n*n个数全部填入方阵中,最后得到的是一个 n阶魔方阵。
【例2】统计数字对的出现频率
算法说明: 输入N(2≤N≤100)个数字(在0与9之间),然后统计出这组数中相邻两 数字组成的链环数字对出现的次数。例如: 输入:N=20 {表示要输入数的数目} 0 1 5 9 8 7 2 2 2 3 2 7 8 7 8 7 9 6 5 9 输出:(7,8)=2 (8,7)=3 (7,2)=1 (2,7)=1 (2,2)=2 (2,3)=1 (3,2)=1
算法如下:
while (p<n-1) main( ) {x=0; { int a[100],i,k,p,m; while (x<m) print(“input numbers of game:”); {k=k+1; input(n); if(k>n) k=1; print(“input serial number of game start:”); x=x+a[k];} input(k); print(k); print(“input number of out_ring:”); a[k]=0; input(m); p=p+1; for( i=1;i<=n;i++) } a[i]=1; for( i=1;i<=n;i++) p=0; if ( a[i]=1) k=k-1; print( “i=”,i); }
main( ) for( i=1;i<=n;i=i+1) {int i,j, i1,j1,x,n,t,a[100][100]; print(“input an odd number:”); {print(“换行符”); input(n); for(j=1;j<=n;j=j+1) if (n mod 2=0) {print(“input error!”); return;} print(a[i][j]); for( i=1;i<=n;i=i+1) } for(j=1;j<=n;j=j+1) a[i][j]=0; } i=1; j=int((n+1)/2); x=1; while (x<=n*n) {a[i][j]=x; x=x+1; i1=i; j1=j; i=i-1; j=j-1; if ( i=0) i=n; if (j=0) j=n; if ( a[i][j]<>0 ) { i=i1+1; j=j1;} }
3.2
3.2.1 3.2.2 3.2.3 3.2.4 3.2.5
算法与数据结构
原始信息与处理结果的对应存储 数组使信息有序化 数组记录状态信息 大整数存储及运算 构造趣味矩阵
1、常用的几种数据结构
数据的逻辑结构常分为四大类: (1)集合结构 (2)线性结构 (3)树形结构 (4)图结构(网结构) 存储结构可以分为:连续存储和链式存储
【例1】编程统计身高(单位为厘米)。统计分150——154; 155——159;160——164;165——169;170——174;175— —179及低于150、高于179共八档次进行。
算法如下:
main( ) { int i,sg,a[8]; print(“input height data until input -1”); input(sg); while (sg<>-1) { if (sg>179) a[7]=a[7]+1; else if (sg<150) a[0]=a[0]+1; else a[sg/5-29]=a[sg/5-29]+1; input(sg); } for (i=0;i<=7;i=i+1) print(i+1 ,“field the number of people: ”,a[i]); }
三、数组记录状态信息
【例1】游戏问题:
12个小朋友手拉手站成一个圆圈,从某一个小朋友开始报数, 报到7的那个小朋友退到圈外,然后他的下一位重新报“1”。 这样继续下去,直到最后只剩下一个小朋友,求解这个小朋 友原来站在什么位置上呢?
算法设计:
首先是如何表示状态的问题。开辟12个元素的数组, 记录12个小朋友的状态,开始时将12个元素的数组值均 赋为1,表示大家都在圈内。这样小朋友报数就用累加数 组元素的值来模拟,累加到7时,该元素所代表的小朋友 退到圈外,将相应元素的值改赋为0,这样再累加到该元 素时和不会改变,又模拟了已出圈外的状态。 为了算法的通用性,算法允许对游戏的总人数、报 数的起点、退出圈外的报数点任意输入。其中n表示做游 戏的总人数,k表示开始及状态数组的下标变量,m表示 退出圈外的报数点,即报m的人出队,p表示已退出圈外 的人数。
二、数组使信息有序化
【例1】编程将编号“翻译”成英文。例35706“翻译”成 three-five-seven-zero-six。
பைடு நூலகம்
算法如下:
main( ) {int i,a[10], ind; long num1,num2; char eng[10][6]={“zero”,”one”,”two”,”three ”,” four”, ” five”,”six”,”seven”,“eight”,”nine”}; print(“Input a num”); input(num1); num2=num1; ind=0; while (num2<>0) {a[ind]=num2 mod 10; ind= ind +1; num2=num2/10; } print(num1, “English_exp:”, eng[a[ind-1]]); for( i=ind-2;i>=0;i=i-1) print(“-”,eng[a[i]]); }
算法如下:
main( ) {int a[10][10]={0},m,i,j,k1,k0; print(“How many is numbers?”); input(n); print(“Please input these numbers:”); input(k0); for (i=2;i<=n;i=i+1) {input(k1); a[k0][k1]=a[k0][k1]+1; k0=k1;} for (i=0;i<=9;i=i+1) for (j=0;j<=9;j=j+1) if (a[i][j]<>0 and a[j][i]<>0); print(“(”,i,j,”)=“,a[i][j],”,(”,j,i,”)=”,a[j][i]) }
四、构造趣味矩阵
趣味矩阵 经常用二维数组来解决
【例1】设计算法生成魔方阵 魔方阵是我国古代发明的一种数字游戏:n阶魔方是指 这样一种方阵,它的每一行、每一列以及对角线上的各数 之和为一个常数,这个常数是:1/2*n*(n2+1),此常数被 称为魔方阵常数。由于偶次阶魔方阵(n=偶数)求解起来 比较困难,我们这里只考虑n为奇数的情况。 以下就是一个n=3的魔方阵: 6 1 8 7 5 3 2 9 4 它的各行、各列及对角线上的元素之和为15。
连续存储又可以分为:静态存储和动态存储
2、连续存储和链式存储比较
顺序存储的优点: (1) 方法简单,各种高级语言中都提供数组结构,容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。
顺序存储的缺点:
(1) 在顺序表中做插入删除操作时,平均移动大约表中一 半的元素,因此对n较大的顺序表效率低。
算法设计:
其实并不是只有一维数组这样的数据结构可以在算法设计中有多 彩的应用,根据数据信息的特点,二维数组的使用同样可以使算 法易于实现,此题就正是如此。
用10*10的二维数组(行、列下标均为0-9),存储统计结果,i行 j列存储数字对(i,j)出现的次数,无需存储原始数据,用其做 下标,在数据输入的同时就能统计出问题的结果。
2)基于运算的考虑 在顺序表中按序号访问ai的时间性能时O(1),而链表中 按序号访问的时间性能O(n),所以如果经常做的运算是按序 号访问数据元素,显然顺序表优于链表; 3)基于环境的考虑 顺序表容易实现,任何高级语言中都有数组类型,链表 的操作是基于指针的,操作简单。
一、原始信息与处理结果对应存储
(2) 需要预先分配足够大的存储空间,估计过大,可能会 导致顺序表后部大量闲置;预先分配过小,又会造成溢出。
温馨提示: 链表的优缺点恰好与顺序表相反。
3、在选取存储结构时权衡因素
1)基于存储的考虑 顺序表的存储空间是静态分配的,在程序执行之前必 须明确规定它的存储规模,也就是说事先对“MAXSIZE”要 有合适的设定,过大造成浪费,过小造成溢出。可见对线 性表的长度或存储规模难以估计时,不宜采用顺序表;链 表不用事先估计存储规模,但链表的存储密度较低