算法分析考试题(3)

int a; int t;//平均服务时间 vectorx; cout<<\输入等待服务的人数:\ cin>>n; cout<<\输入服务站点数:\ cin>>s; cout<<\输入每个顾客需要等待的时间:\ for(i=1;i<=n;i++) { cin>>a; x.push_back(a); } t=greedy(x, s); cout<<\最少平均等待时间是:\ }

运行结果为：

9. 键盘输入一个高精度的正整数N, 去掉其中任意S个数字后剩下的数字按左右次序将组成一个新的正整数.编程对给定的N和S,寻找一种方案使得剩下的数字组成的新数最小. (P133页 贪婪算法)

10. 最佳调度问题。假设有n个任务由k个并行的机器完成。完成任务i个需要的时间为ti。

试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。（回

溯法）

11.用回溯法做第6题 ( 时间复杂度为2,请详细分析时间复杂度)

12.八皇后问题选做

13．最多约数问题 问题描述:

正整数x的约数是能整除x的正整数。正整数x 的约数个数记为div(x)。例如，1，2，5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，a≤b，找出a和b之间约数个数最多的数x。

a、算法思想：数据规模到1000000000，较大，最一般做法会超时。可以利用n的因子数公式，如果n的素因子分解公式为：n = p1^r1 * p2^r2 * p3^r3 * … * pn^rn，那么n的因子数公式即为Div(n) = (r1+1)*(r2+1)*……*(rn+1)。所以，先打印素数表，用公式求即可。 b、时间复杂度分析

筛选法打印素数表的时间复杂度一定小于MAXsqr（MAX),求数m的因子个数的时间复杂度小于sqr（m） c、代码实现

#include #include #include

#define MAX 100000

int prime[MAX]; bool a[MAX]; int cnt;

//筛选法打印素数表

void Initprime(){ int i, j; cnt = 0;

for( i=2; i

prime[cnt++] = i;

for( j=2*i; j

//求数m的因子个数 int Div( int m ){

n int tmp,ret=1;

if( m<100000 && a[m]==0 ) return 2;

for( int i=0; prime[i]*prime[i]<=m && i

while( m % prime[i] == 0 ){ tmp ++;

m /= prime[i]; }

ret = ret * ( tmp+1 ); } }

if( m != 1 )

ret = ret * 2; return ret; }

int main( ){ int m, n; int max, ret; Initprime( );

while( scanf( \ max = 1;

for( int i=m; i<=n; i++ ){ ret = Div( i ); if( ret > max ) max = ret; }

printf( \和b之间约数个数最多的数为：%d\\n\ }

return 0; }

运行结果为