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

} }

if (T[j] == '\\0') return (i - strlen(T) +1); //返回本趟匹配的开始位置 else return 0; }

int main() { char s1[]=\ char s2[]=\

cout<

return 0; }

2.分式化简。设计算法，将一个给定的真分数化简为最简分数形式。例如，将6/8化简为3/4。

#include using namespace std;

int main() {

int n;//分子 int m;//分母

int factor;//最大公因子 int factor1;

cout<<\输入一个真分数的分子与分母： \ cin>>n>>m;

int r = m % n;//因为是真分数 所以分母一定大于分子 factor1=m; factor=n; while (r != 0) {

factor1 =factor; 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

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;iint 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