算法设计与分析习题答案1-6章

factor = r;

r = factor1% factor; }

cout<<\输出该真分数的最简分数: \return 0; }

3. 设计算法，判断一个大整数能否被11整除。可以通过以下方法:将该数的十进制表示

从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其和能否被11整除。

例如，将562843748分割成5,62,84,37,48，然后判断(5+62+84+37+48)能否被11整除 //将一个大整数看成一个数组

//数组的奇数位对应数的10倍加上数组偶数对应数的本身 //验证结果能否被11整除 #include using namespace std; int main() {

int a[9]={5,6,2,8,4,3,7,4,8};

int result=0; //result为题目要求的各位之和 for(int i=0;i!=9;++i) {

if(i%2==0)

result+=a[i]; //i 为偶数位时，结果加上其对应数组数的本身 else

result+=a[i]*10; //i 为奇数位时，结果加上对应数组数的10倍 }

if(result==0)

cout<<\该整数能被11整除\else

cout<<\该整数不能被11整除\return 0; }

4. 数字游戏。把数字 1,2,?,9这9个数字填入以下含有加、减、乘、除的四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘和除的一位数中(即排除运算式中一位数为1的平凡情形)。

,,×,，,,,?,,,, = 0

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

超出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

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

if(b[i]!=0) {

if(b[i]==2) { k++; } a[j]=i; j++; } }

for(i=0;i

int main() {

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