2013《计算机算法设计与分析》习题及答案

}

5.统计数字问题：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是

9

06或006等。数字计数问题要求对给定书的总页码n(1≤n≤10)，计算出书的全部页码中分别用到多少次数字0，1，2，?，9。

输入数据、输出结果示例 输入数据：11

输出结果：数 字: 0 1 2 3 4 5 6 7 8 9

用到次数: 1 4 1 1 1 1 1 1 1 1

void count(int n,int a[10]) {int i,x,y;

for (i=0;i<=9;i++) a[i]=0; for (i=1;i<=n;i++) {x=i;

while (x)

{y=x; a[y]++; x/=10; } } }

6. 顺序表存储表示如下： typedef struct

{RedType r[MAXSIZE+1]; //顺序表

int length; //顺序表长度 }SqList;

编写对顺序表L进行快速排序的算法。

int Partition(SqList &L,int low,int high) //算法10.6(b)

{//交换顺序表L中子表L.r[low..high]的记录,枢轴记录到位,并返回其所在位置, //此时在它之前(后)的记录均不大(小)于它. int pivotkey;

L.r[0]=L.r[low]; //用子表的第一个记录作枢轴记录 pivotkey=L.r[low].key; //枢轴记录关键字

while (low=pivotkey) --high;

L.r[low]=L.r[high]; //将比枢轴记录小的记录移到低端 while (low

L.r[high]=L.r[low]; //将比枢轴记录大的记录移到高端 }

L.r[low]=L.r[0]; //枢轴记录到位 return low; //返回枢轴位置 }

void QSort(SqList &L,int low,int high)

{//对顺序表L中的子序列L.r[low..high]作快速排序 int pivotloc;

if (low1

{pivotloc=Partition(L,low,high); //将L.r[low..high]一分为二

13

QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置 QSort(L,pivotloc+1,high); //对高子表递归排序 } }

void QuickSort(SqList &L) {//对顺序表L作快速排序 QSort(L,1,L.length); }

7. 顺序表存储表示如下： typedef struct

{RedType r[MAXSIZE+1]; //顺序表

int length; //顺序表长度 }SqList;

编写对顺序表L进行2_路归并排序的算法。 void Merge(RedType SR[],RedType TR[],int i,int m,int n) {//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] int l,j,k;

for (j=m+1,k=i; i<=m&&j<=n; ++k) //将SR中记录由小到大地并入TR if (LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++]; else TR[k]=SR[j++];

if (i<=m) for (l=i; l<=m; l++,k++) TR[k]=SR[l]; //将剩余的SR[i..m]复制到TR if (j<=n) for (l=j; l<=n; l++,k++) TR[k]=SR[l]; //将剩余的SR[j..n]复制到TR }

void MSort(RedType SR[],RedType TR1[],int s,int t) {//将SR[s..t]归并排序为TR1[s..t]. int m; RedType TR2[MAXSIZE+1]; if (s==t) TR1[s]=SR[s];

else {m=(s+t)/2; //将SR[s..t]平分为SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m); //递归地将SR[s..m]归并为有序的TR2[s..m] MSort(SR,TR2,m+1,t); //递归地将SR[m+1..t]归并为有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t); //将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] } }

void MergeSort(SqList &L) {//对顺序表L作归并排序 MSort(L.r, L.r, 1, L.length); }

数据结构中算法的时间复杂度的计算方法

一个算法的时间复杂度(Time Complexity)是指该算法的运行时间与问题规模的对应关系。一个算法是由控制结构和原操作构成的，其执行的时间取决于二者的综合效果。为了便于比较同一问题的不同算法，通常把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句，因此，算法中基本操作语句的频度是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))。其中“O”表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，或者说，用“O”符号表示数量级的概念。例如，如)1n(n21)n(T?=，则 )1n(n21?的数量

14

级与n2相同，所以T(n)=O（n2）。

如果一个算法没有循环语句，则算法中基本操作的执行频度与问题规模n无关，记作O(1)，也称为常数阶。如果算法只有一个一重循环，则算法的基本操作的执行频度与问题规模n呈线性增大关系，记作O（n），也叫线性阶。常用的还有平方阶O（n2）、立方阶O（n3）、对数阶O(log2n)等。 下面举例来说明计算算法时间复杂度的方法。 【例1-4】 分析以下程序的时间复杂度。 x=n; /*n>1*/ y=0; while(y < x) { y=y+1; ① }

解：这是一重循环的程序，while循环的循环次数为n，所以，该程序段中语句①的频度是n，则程序段的时间复杂度是T(n)=O（n）。

【例1-5】 分析以下程序的时间复杂度。 for(i=1；i1*/ y=0; while(x >= (y+1)*(y+1)) { y=y+1; ① }

解：这是一重循环的程序，while循环的循环次数为n，所以，该程序段中语句①的频度是n，则程序段的时间复杂度是T(n)=O（n）。

【例1-7】 分析以下程序的时间复杂度。 for(i=0;i

2.1. 交换i和j的内容

sum=0； （一次） for(i=1;i<=n;i++) （n次 ） for(j=1;j<=n;j++) （n^2次 ） sum++； （n^2次 ）

解：T(n)=2n^2+n+1 =O(n^2) 2.2. for (i=1;i

wk_ad_begin({pid : 21});wk_ad_after(21, function(){$('.ad-hidden').hide();}, function(){$('.ad-hidden').show();}); {

y=y+1; ①

for (j=0;j<=(2*n);j++) x++; ② } 解： 语句1的频度是n-1

语句2的频度是(n-1)*(2n+1)=2n^2-n-1 f(n)=2n^2-n-1+(n-1)=2n^2-2 该程序的时间复杂度T(n)=O(n^2). O(n)

15

2.3. a=0;

b=1; ① for (i=1;i<=n;i++) ② { s=a+b; ③ b=a; ④ a=s; ⑤ }

解： 语句1的频度：2, 语句2的频度： n, 语句3的频度： n-1, 语句4的频度：n-1,

语句5的频度：n-1, T(n)=2+n+3(n-1)=4n-1=O(n). O(log2n ) 2.4.

i=1; ①

while (i<=n) i=i*2; ② 解： 语句1的频度是1,

设语句2的频度是f(n), 则：2^f(n)<=n; f(n)<=log2n 取最大值f(n)= log2n, T(n)=O(log2n ) O(n^3) 2.5.

for(i=0;i

for(j=0;j

for(k=0;k

解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).

16