算法设计与分析练习题（c++版）（持续更新ing)

1.给定能随机生成整数1~5的函数rand5()，写出能随机生成整数1~7的函数rand7()

解：通过rand5()*5+rand5()产生6、7、8、9、…、26、27、28、29、30这25个整数，每个整数x出现的概率相等，取前面3*7=21个整数，舍弃后面的4个整数，将{6，7，8}转化成1，将{9,10,11}转化成2，依此类推，即有

为最终结果。以下为c++代码：

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

int rand5()
{
int a=1,b=5;
return rand()%(b-a+1)+a;
}

int rand7()
{
int x;
do
{
x=rand5()*5 + rand5();

}
while(x>26);
int y = (x - 3) / 3;
return y;
}

int main()
{
srand((unsigned)time(NULL));
for(int i=1;i<20;i++)
cout<<rand7()<<" ?";
cout<<"\n";
}

2.给定一个含n个整数的a，编写一个实验程序随机打乱数组a的程序。

解：首先从所有元素中选取一个元素与a[0]交换，然后在a[1……n-1]中选择一个元素与a[1]交换，依此类推，对应程序如下:

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

void swap(int &x,int &y) ? ?//交换
{
int tmp;
tmp=x;x=y;y=tmp;
}

void random(int a[],int n)
{
for(int i=0;i<n;i++)
{
int j=rand()%(n-i)+i;
if(j!=i)swap( a[i],a[j]);
}
}

int main()
{
int n=5;
int a[n]={1,2,3,4,5};
srand((unsigned)time(NULL)); ? ? //随机种子
for(int num=1;num<=10;num++) ? ? ? ? //产生10个随机序列
{
random(a,5);
cout<<"随机序列"<<num<<":";
for(int i=0;i<n;i++)
? ? cout<<a[i]<<" ?";
? ? cout<<"\n";

}

}

3.用分治法设计的合并排序算法描述，其中A[low:high]存放的待排序序列，部分代码如下:

void MergeSort (int A[],int low,int high)

{ ? ?int middle;

? ? ? ? if (low<high)

? ? ? ? ? ?{
? ? ? ? ? ??? ?middle=(low+high)/2;

? ? ? ? ? ? ? MergeSort(A,low,middle);

? ? ? ? ? ? ? MergeSort(A,middle+1,high);

? ? ? ? ? ? ? Merge(A,low,middle,high);

? ? ? ? ? ?}

}

4.有一个三位数，个位数字比百位数字大，百位数字又比十位数字大，并且各位数字之和等于各位数字相乘之积，设计一个算法用蛮力法求此三位数。

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

void ?solve()
{
?? ?int a,b,c;
?? ?for(a=1;a<=9;a++)
?? ?for(b=0;b<=9;b++)
?? ?for(c=0;c<=9;c++)
?? ?{
?? ??? ?if(c>a&&a>b&&a+b+c==a*b*c)
?? ??? ?cout<<a<<b<<c<<endl;
?? ?}
}

int main()
{
?? ?cout<<"求解结果是:"<<solve()<<endl;
?? ?solve();
}

5.埃拉托色尼筛法简称埃氏筛法，基本思想是，假定区间[1, n]内的所有数都是素数，再去掉所有合数，剩下的就是所有素数。判断合数的方法是从 2 开始依次过筛，如果是 2 的倍数则该数不是素数，进行标记处理，直至将 n/2 过筛，将所有合数打上标记。

解：设函数EratoSieve实现埃拉托色尼筛法，程序如下：

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

void EratoSieve(int A[ ], int n)
{
? ? int i, j;
? ? for (i = 2; i <= n/2; i++)
? ? {
? ? ? ? if (A[i] != 0) continue;
? ? ? ? else
? ? ? ? {
?? ??? ?for (j = 2; i * j <= n; j++)
? ? ? ? ? ? ?A[i*j] = 1;
? ? ? ? }

? ? }

}