算法设计与分析(第2版) 王红梅 胡明 习题答案

5. 设计算法求解an mod m，其中a、n和m均为大于1的整数。（提示：为了避免an

超出int型的表示范围，应该每做一次乘法之后对n取模）

#include using namespace std;

int square(int x) {

return x*x; }

//用递归思想

int resultmod(int a, int n) {

if(n== 0) return 1; if(n%2 == 0) return square(resultmod(a, n/2));//n为偶数的时，取n的一半防止溢出 else return a*resultmod(a, n-1);//n为奇数时，取n-1； }

int main() {

int a, n, m;

cout<<\请输入a，n, m: \ cin>>a>>n>>m; cout<

int result = resultmod(a, n);

cout<<\的结果为：\ return 0; }

6. 设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间复杂性为O(1)。

7. 设计算法，在数组r[n]中删除重复的元素，要求移动元素的次数较少并使剩余元素间的相对次序保持不变。 #include using namespace std;

void deletere(int a[],int N) { int b[100]={0}; int i,k; k=0; static int j=0; for(i=0;i

int main() { int a[]={1,2,1,3,2,4}; deletere(a,6); return 0; }

//在数组查找相同的元素

//把其中一个相同的数值的元素位置设成一个“特殊数值” //输出所求函数

#include

using namespace std;

int main() {

int a[]={1,2,1,5,3,2,9,4,5,5,3,5}; int i,j;

for( i=0;i<12;i++) {

for(j=0;j

a[i]=64787250;//设一个数组不存在的数值 } }//for

for(i=0;i<12;i++) { if(a[i]!=64787250) cout<

8. 设表A={a1, a2, ?, an}，将A拆成B和C两个表，使A中值大于等于0的元素存入表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。

//先对A进行快排

//将大于0的元素给B，小于0的元素给C

#include using namespace std;

int partions(int l[],int low,int high) {

int prvotkey=l[low]; l[0]=l[low];

while (low

while (low=prvotkey) --high;

l[low]=l[high];

while (low

l[high]=l[low]; }

l[low]=l[0]; return low; }

void qsort(int l[],int low,int high) {

int prvotloc; if(low

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high } }

void quicksort(int l[],int n) {

qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个 }

int main() { int a[11]={-2,2,32,43,-23,45,36,-57,14,27,-39};

quicksort(a,11);

for(int i=1;i<11;i++) { if(a[i]<0)

cout<<\ else cout<<\ }

cout<

return 0;