计算机算法分析与设计第四版习题算法分析部分详解试验1

1、/算法实验1.11.5;任选一道实验、写实验报告，当堂 1分；实验报告4分算法实现题1-1统计数字问题#include<iostream>#include<cmath>using namespace std;int main() int count10;int i,j,k,L;int n,len,m;while(scanf("%d",&n)!=EOF) m=n;L=ceil(log10(n+1);for(i=0;i<10;i+)counti=0;for(j=0;j<L;j+) len=ceil(log10(m+1);k=m/pow

2、(10.0,len-1); /从高位到低位取各个位数的值for(i=0;i<10;i+) 小K*len的数数值0-9出现的次数counti+=k*(len-1)*pow(10.0,len-2);K*n*f(n-1)for(i=0;i<k;i+)counti+=pow(10.0,len-1);/在高位小于数值 K的数出现的次数 countk+=m-k*pow(10.0,len-1)+1;/ 在高位数值K的数出现的次数 m=m-k*pow(10.0,len-1);/去掉已计算的高位for(i=0;i<L;i+) 去掉前导 0;count0-=pow(10.0,i);分别考虑0在高

3、位的情况有到少种for(i=0;i<10;i+)printf("%dn",counti);return 0;算法实现题1-2字典序问题#include <stdio.h>#include <string.h>unsigned long dp2711, sum17, ans;本代码实现，字符串长度不超过10,可解char str11;void main()int i, j,k,len,start;memset(dp, 0, sizeof(dp); 为数组分配空间，并初始化为 0memset(sum, 0, sizeof(sum);for(i =

4、1; i < 27; i+) dpi1 = 1;for(j = 2; j <= 10; j+)for(i = 27 - j; i >= 1; i-)/dpij 以第i个字母开头的长度为j的单词个数dpij += dpi+1j;dpij += dpi+1j-1;for(i = 1; i <= 10; i+)/长度为i是的总个数for(j = 1; j <= 26; j+)sumi += dp皿i;scanf("%s", str);len=strlen(str);for(i=1;i<len;i+)如果当前单词的长度为len,计算长度为1到le

5、n-1的单词总数ans+=sumi;start=1;for(j=len;j>=1;j-)for(i=start,k=1;k<=strlen-j-('a'+start-1);k+,i+)考虑打头为 1i-1 长度为 j 的字符串个数ans+=dpij;start=strlen-j-'a'+2;打头字符在字典序中下一个字符位置for (i = 0; i < len - 1; i+)if (stri >= stri + 1) ans = -1;printf("%un", ans + 1);算法实现题1-3最多约数问题方法一：

6、#include<iostream>using namespace std;bool *back;int a,b;int max=0,maxn;void main()cin>>a>>b;if (a>b) cout<<"a<=b:error"<<endl; return;back =new boolb+1;for(int i=a;i<=b;i+)int count=0;for(int j=0;j<=b;j+) backj=false;for(int k=1;k<=(i/2+1);k+)i

7、f (i%k=0) backk=true; backi/k=true;for(j=0;j<=i;j+) if (backj) count+;if (count>max) max=count; maxn=i;cout<<max<<endl<<maxn<<endl;方法二：#include<iostream>using namespace std;#define max Maxconst long MAXP = 100000;long primMAXP;long max, numb, PCOUNT; /max存放最多约数个数，

8、numb存放约数个数最多的数void primes。; 用筛选法产生质数存于prim数组中void search(long from, long tot, long num, long low, long up);int main()primes();long l, u;cin >> l >> u;if (l = 1) && (u = 1)max = 1;numb = 1;elsemax = 2;numb = l;search。，1, 1, l, u);cout << max << endl << numb <&

9、lt; endl;system("pause");return 0;void primes()bool getMAXP+1;long i;for (i = 2; i <= MAXP; i+)geti = true;for (i = 2; i <= MAXP; i+)if (geti)long j = i + i;while (j <= MAXP)getj = false;j += i;long ii, j;for (ii = 2, j = 0; ii <= MAXP; ii+)if (getii) prim+j = ii;PCOUNT = j;区间l

10、ow,up上，tot为当前约数最多个数，num为约数个数最多的数，/from表示现在是第几个质数。void search(long from, long tot, long num, long low, long up)if (num >= 1)if ( (tot > max) | (tot = max) && (num < numb)max = tot;numb = num;if (low = up) && (low > num) search(from, tot*2, num*low, 1, 1);for (long i = from

11、; i <=PCOUNT; i+)if (primi > up) return;elselong j = primi, x = low - 1, y = up, n = num, t = tot, m = 1; while (true)m+;t += tot;x /= j;y /= j;if (x = y) break;n *= j;search(i+1, t, n, x+1, y);m = 1 << m;if (tot < max / m) return;/算法实现题1-4金币列阵问题#include <fstream>#include <io

12、stream>using namespace std;const int size = 100;int k,n,m,ccount,best;int b0size+1size+1,b1size+1size+1,bsize+1size+1;bool found;void print()for(int i = 1; i <= n; i+)for(int j = 1; j <= m; j+) cout << b1ij << ""cout << endl;void trans1(int x)行翻转for(int i = 1; i

13、<= m; i+)b1xi = b1xiA1;ccount+;void trans2(int x, int y) 列交换for(int i = 1; i <= n; i+)swap(b1ix,b1iy);if (x != y) ccount+;bool same(int x, int y)for(int i = 1; i <= n; i+)if (b0ix != b1皿y) return false;return true;void acpy(int asize+1size+1, int bsize+1size+1)for(int i = 1; i <= n; i+)f

14、or(int j = 1; j <= m; j+) aij = bij;void answer()int x,y,j,p;cin >> k;for(int i = 1; i <= k; i+)(cin >> n >> m;/n 行 m 列原状态 b0for( x = 1; x <= n; x+)for( y = 1; y <= m; y+)cin >> b0xy;目标状态blfor( x = 1; x <= n; x+)for(int y = 1; y <= m; y+)cin >> b1xy;ac

15、py(b,b1);b1 复制到 bbest = m + n + 1;for( j = 1; j <= m; j+)(acpy(b1,b);ccount = 0;trans2(1,j); 列变换int p;for( p = 1; p <= n; p+)if != b1p1)trans1(p); 行变换for(p = 1; p <= m; p+)找列相等的(b1的q歹U和b0的p列相等)(found = false;for(int q = p; q <= m; q+) if (same(p,q) (trans2(p,q);found = true; break;) if (

16、!found) break;)if (found && ccount < best) best = ccount;)if (best < m + n + 1)cout << best << endl;elsecout << -1 << endl;int main()answer。;return 0;/算法实现题1-5最大间隙问题#include<iostream>using namespace std;const int MAX=200001;double numMAX;bool run()int n;if

17、(scanf("%d",&n尸EOF) return false;/ctrl + z 回车退出int i;double max=0.0,min=INT_MAX;/ 大值初始化为最小，小值初始化为最大 for(i=0;i<n;i+)scanf("%lf",&numi);if(numi>max) max=numi;if(numi<min) min=numi;int *cnt=new intn;double *low=new doublen;double *high=new doublen;for(i=0;i<n;i+)

18、 初始化桶cnti=0;lowi=max;highi=min;double ave=(max-min)/(n-1);for(i=0;i<n;i+)int tmp=(int)(numi-min)/ave);cnttmp+;增加桶元素if(numi>hightmp) hightmp=numi;/修改桶边界if(numi<lowtmp) lowtmp=numi;double t=high0,res=0.0;for(i=1;i<n;i+)if(cnti>0)桶中有数字才进行检查，无数字跳过 double tmp=lowi-t; if(tmp>res) res=tmp

19、;t=highi；cout<<res<<endl;return true;int main()while(run();return 0;附：实验（设计）报告参考格式设计多段图问题的动态规划算法与实现班级 学号 姓名 成绩分一、 设计目的1 .掌握有向网的成本邻接矩阵表示法；2 .掌握多段图问题的动态规划递推算法；3 .进一步掌握动态规划法的基本思想和算法设计方法;二、设计内容1. .任务描述1）多段图问题简介2）设计任务简介设计求解多段图问题的动态规划算法，即设计和实现多段图问题的表示方案、动态 规划递推算法，设计对算法或程序的测试方案并完成测试。2. 多段图问题的表示方案本设计采用成本邻接矩阵表示多段图，针对多段图（可插入图例）描述成本邻接矩阵的规模与元素意义3. 递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对多段图问题的求解（抽象地）描述递推过程4. 主要数据类型与变量typedef NodeNumbe门nt; /*