版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、/算法實驗1.11.5;任選一道實驗、寫實驗報告,當堂 1分;實驗報告4分算法實現(xiàn)題1-1統(tǒng)計數(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); /從高位到低位取各個位數(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);/去掉已計算的高位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;算法實現(xiàn)題1-2字典序問題#include <stdio.h>#include <string.h>unsigned long dp2711, sum17, ans;本代碼實現(xiàn),字符串長度不超過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個字母開頭的長度為j的單詞個數(shù)dpij += dpi+1j;dpij += dpi+1j-1;for(i = 1; i <= 10; i+)/長度為i是的總個數(shù)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的單詞總數(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 長度為 j 的字符串個數(shù)ans+=dpij;start=strlen-j-'a'+2;打頭字符在字典序中下一個字符位置for (i = 0; i < len - 1; i+)if (stri >= stri + 1) ans = -1;printf("%un", ans + 1);算法實現(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ù)個數(shù),
8、numb存放約數(shù)個數(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為當前約數(shù)最多個數(shù),num為約數(shù)個數(shù)最多的數(shù),/from表示現(xiàn)在是第幾個質(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;/算法實現(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;目標狀態(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;/算法實現(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ù)字才進行檢查,無數(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è)計)報告參考格式設(shè)計多段圖問題的動態(tài)規(guī)劃算法與實現(xiàn)班級 學(xué)號 姓名 成績分一、 設(shè)計目的1 .掌握有向網(wǎng)的成本鄰接矩陣表示法;2 .掌握多段圖問題的動態(tài)規(guī)劃遞推算法;3 .進一步掌握動態(tài)規(guī)劃法的基本思想和算法設(shè)計方法;二、設(shè)計內(nèi)容1. .任務(wù)描述1)多段圖問題簡介2)設(shè)計任務(wù)簡介設(shè)計求解多段圖問題的動態(tài)規(guī)劃算法,即設(shè)計和實現(xiàn)多段圖問題的表示方案、動態(tài) 規(guī)劃遞推算法,設(shè)計對算法或程序的測試方案并完成測試。2. 多段圖問題的表示方案本設(shè)計采用成本鄰接矩陣表示多段圖,針對多段圖(可插入圖例)描述成本鄰接矩陣的規(guī)模與元素意義3. 遞推過程的抽象描述本設(shè)計采用前向或后向遞推公式。用自然語言、偽程序設(shè)計語言或流程圖等形式針對多段圖問題的求解(抽象地)描述遞推過程4. 主要數(shù)據(jù)類型與變量typedef NodeNumbe門nt; /*
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 電子商務(wù)服務(wù)外包合同
- 的三方入股合作協(xié)議書
- 2025年云南貨運從業(yè)資格考試題目
- 2025年泰安道路貨物運輸從業(yè)資格證考試
- 電子產(chǎn)品點膠代加工協(xié)議書(2篇)
- 2024年高考歷史藝體生文化課第八單元工業(yè)文明沖擊下的中國近代經(jīng)濟和近現(xiàn)代社會生活的變遷8.20近代中國經(jīng)濟結(jié)構(gòu)的變動和資本主義的曲折發(fā)展練習(xí)
- 2024-2025學(xué)年高中數(shù)學(xué)課時分層作業(yè)13結(jié)構(gòu)圖含解析新人教B版選修1-2
- 2024-2025學(xué)年三年級語文下冊第三單元11趙州橋教案新人教版
- 2024-2025學(xué)年高中歷史第1單元中國古代的思想與科技第6課中國古代的科學(xué)技術(shù)教案含解析岳麓版必修3
- 員工物品交接單
- QC成果地下室基礎(chǔ)抗浮錨桿節(jié)點處防水施工方法的創(chuàng)新
- 第一章:公共政策理論模型
- 中藥審核處方的內(nèi)容(二)
- (完整)金正昆商務(wù)禮儀答案
- RB/T 101-2013能源管理體系電子信息企業(yè)認證要求
- GB/T 10205-2009磷酸一銨、磷酸二銨
- 公司財務(wù)制度及流程
- 高支模專項施工方案(專家論證)
- 《物流與供應(yīng)鏈管理-新商業(yè)、新鏈接、新物流》配套教學(xué)課件
- 物聯(lián)網(wǎng)項目實施進度計劃表
- MDD指令附錄一 基本要求檢查表2013版
評論
0/150
提交評論