計(jì)算機(jī)算法分析與設(shè)計(jì)第四版習(xí)題算法分析部分詳解試驗(yàn)1

1、/算法實(shí)驗(yàn)1.11.5;任選一道實(shí)驗(yàn)、寫實(shí)驗(yàn)報(bào)告，當(dāng)堂 1分；實(shí)驗(yàn)報(bào)告4分算法實(shí)現(xiàn)題1-1統(tǒng)計(jì)數(shù)字問題#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); /從高位到低位取各個(gè)位數(shù)的值for(i=0;i<10;i+) 小K*len的數(shù)數(shù)值0-9出現(xiàn)的次數(shù)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);/在高位小于數(shù)值 K的數(shù)出現(xiàn)的次數(shù) countk+=m-k*pow(10.0,len-1)+1;/ 在高位數(shù)值K的數(shù)出現(xiàn)的次數(shù) m=m-k*pow(10.0,len-1);/去掉已計(jì)算的高位for(i=0;i<L;i+) 去掉前導(dǎo) 0;count0-=pow(10.0,i);分別考慮0在高

3、位的情況有到少種for(i=0;i<10;i+)printf("%dn",counti);return 0;算法實(shí)現(xiàn)題1-2字典序問題#include <stdio.h>#include <string.h>unsigned long dp2711, sum17, ans;本代碼實(shí)現(xiàn)，字符串長(zhǎng)度不超過10,可解char str11;void main()int i, j,k,len,start;memset(dp, 0, sizeof(dp); 為數(shù)組分配空間，并初始化為 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個(gè)字母開頭的長(zhǎng)度為j的單詞個(gè)數(shù)dpij += dpi+1j;dpij += dpi+1j-1;for(i = 1; i <= 10; i+)/長(zhǎng)度為i是的總個(gè)數(shù)for(j = 1; j <= 26; j+)sumi += dp皿i;scanf("%s", str);len=strlen(str);for(i=1;i<len;i+)如果當(dāng)前單詞的長(zhǎng)度為len,計(jì)算長(zhǎng)度為1到le

5、n-1的單詞總數(shù)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 長(zhǎng)度為 j 的字符串個(gè)數(shù)ans+=dpij;start=strlen-j-'a'+2;打頭字符在字典序中下一個(gè)字符位置for (i = 0; i < len - 1; i+)if (stri >= stri + 1) ans = -1;printf("%un", ans + 1);算法實(shí)現(xiàn)題1-3最多約數(shù)問題方法一：

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存放最多約數(shù)個(gè)數(shù)，

8、numb存放約數(shù)個(gè)數(shù)最多的數(shù)void primes。; 用篩選法產(chǎn)生質(zhì)數(shù)存于prim數(shù)組中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;區(qū)間l

10、ow,up上，tot為當(dāng)前約數(shù)最多個(gè)數(shù)，num為約數(shù)個(gè)數(shù)最多的數(shù)，/from表示現(xiàn)在是第幾個(gè)質(zhì)數(shù)。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;/算法實(shí)現(xiàn)題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)行翻轉(zhuǎn)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 列原狀態(tài) b0for( x = 1; x <= n; x+)for( y = 1; y <= m; y+)cin >> b0xy;目標(biāo)狀態(tài)blfor( x = 1; x <= n; x+)for(int y = 1; y <= m; y+)cin >> b1xy;ac

15、py(b,b1);b1 復(fù)制到 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;/算法實(shí)現(xiàn)題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)桶中有數(shù)字才進(jìn)行檢查，無數(shù)字跳過 double tmp=lowi-t; if(tmp>res) res=tmp

19、;t=highi；cout<<res<<endl;return true;int main()while(run();return 0;附：實(shí)驗(yàn)（設(shè)計(jì)）報(bào)告參考格式設(shè)計(jì)多段圖問題的動(dòng)態(tài)規(guī)劃算法與實(shí)現(xiàn)班級(jí) 學(xué)號(hào) 姓名 成績(jī)分一、 設(shè)計(jì)目的1 .掌握有向網(wǎng)的成本鄰接矩陣表示法；2 .掌握多段圖問題的動(dòng)態(tài)規(guī)劃遞推算法；3 .進(jìn)一步掌握動(dòng)態(tài)規(guī)劃法的基本思想和算法設(shè)計(jì)方法;二、設(shè)計(jì)內(nèi)容1. .任務(wù)描述1）多段圖問題簡(jiǎn)介2）設(shè)計(jì)任務(wù)簡(jiǎn)介設(shè)計(jì)求解多段圖問題的動(dòng)態(tài)規(guī)劃算法，即設(shè)計(jì)和實(shí)現(xiàn)多段圖問題的表示方案、動(dòng)態(tài) 規(guī)劃遞推算法，設(shè)計(jì)對(duì)算法或程序的測(cè)試方案并完成測(cè)試。2. 多段圖問題的表示方案本設(shè)計(jì)采用成本鄰接矩陣表示多段圖，針對(duì)多段圖（可插入圖例）描述成本鄰接矩陣的規(guī)模與元素意義3. 遞推過程的抽象描述本設(shè)計(jì)采用前向或后向遞推公式。用自然語(yǔ)言、偽程序設(shè)計(jì)語(yǔ)言或流程圖等形式針對(duì)多段圖問題的求解（抽象地）描述遞推過程4. 主要數(shù)據(jù)類型與變量typedef NodeNumbe門nt; /*