发布时间 : 星期三 文章算法设计与分析(第2版) 王红梅 胡明 习题答案更新完毕开始阅读
5. 设计算法求解an mod m，其中a、n和m均为大于1的整数。（提示：为了避免an
超出int型的表示范围，应该每做一次乘法之后对n取模）
#include
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 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 int partions(int l[],int low,int high) { int prvotkey=l[low]; l[0]=l[low]; while (low while (low 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<<\ }