經(jīng)典ACM算法合集經(jīng)典ACM算法合集

經(jīng)典ACM算法合集經(jīng)典ACM算法合集

ID:42406664

大?。?9.00 KB

頁數(shù):28頁

時間:2019-09-14

經(jīng)典ACM算法合集經(jīng)典ACM算法合集_第1頁
經(jīng)典ACM算法合集經(jīng)典ACM算法合集_第2頁
經(jīng)典ACM算法合集經(jīng)典ACM算法合集_第3頁
經(jīng)典ACM算法合集經(jīng)典ACM算法合集_第4頁
經(jīng)典ACM算法合集經(jīng)典ACM算法合集_第5頁
資源描述:

《經(jīng)典ACM算法合集經(jīng)典ACM算法合集》由會員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫

1、實(shí)驗(yàn)一統(tǒng)計數(shù)字問題實(shí)驗(yàn)二最大間隙問題實(shí)驗(yàn)三眾數(shù)問題實(shí)驗(yàn)四半數(shù)集問題實(shí)驗(yàn)五集合劃分問題實(shí)驗(yàn)六最少硬幣問題實(shí)驗(yàn)七編輯距離問題實(shí)驗(yàn)八程序存儲問題實(shí)驗(yàn)九最優(yōu)服務(wù)次序問題實(shí)驗(yàn)十汽車加油問題實(shí)驗(yàn)十一工作分配問題實(shí)驗(yàn)十二0-1背包問題實(shí)驗(yàn)十三最小重量機(jī)器設(shè)計問題實(shí)驗(yàn)十四最小權(quán)頂點(diǎn)覆蓋問題實(shí)驗(yàn)十五集合相等問題實(shí)驗(yàn)十六戰(zhàn)車問題實(shí)驗(yàn)一統(tǒng)計數(shù)字問題1、問題描述:一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排,每個頁碼都不含多余的前導(dǎo)數(shù)字0。例如,第6頁用數(shù)字6表示,而不是06或006等。數(shù)字計數(shù)問題要求對給定書的總頁碼n,計算出書的全部頁碼中分別用到多少次數(shù)字0,1,

2、2,…,9。2、題目分析:考慮由0,1,2,…,9組成的所有n位數(shù)。從n個0到n個9共有個n位數(shù),在這些n位數(shù)中,0,1,2,…,9每個數(shù)字使用次數(shù)相同,設(shè)為。滿足如下遞歸式:由此可知,。據(jù)此,可從低位向高位進(jìn)行統(tǒng)計,再減去多余的0的個數(shù)即可。3、算法設(shè)計:定義數(shù)組a[10]存放0到9這10個數(shù)出現(xiàn)的次數(shù),個位為第0位,第j位的數(shù)字為r。采用while循環(huán)從低位向高位統(tǒng)計:a.統(tǒng)計從個位算起前j位0~9個數(shù);b.如果j+1位為0,去掉第j+1位補(bǔ)0個數(shù);c.統(tǒng)計第j+1位出現(xiàn)1~(r-1)個數(shù);d.統(tǒng)計第j+1位出現(xiàn)r個數(shù)。4、源程序:#include

3、>intmain(){longintsn[10];inti,n,c,k,s,pown;for(i=0;i<10;i++)sn[i]=0;cin>>n;for(k=s=0,pown=1;n>0;k++,n/=10,pown*=10){c=n%10;for(i=0;i<10;i++)sn[i]+=c*k*(pown/10);for(i=0;i

4、count(),故該算法的時間復(fù)雜度為O(1)。實(shí)驗(yàn)二最大間隙問題1、問題描述:最大間隙問題:給定n個實(shí)數(shù)x1,x2,...,xn,求這n個數(shù)在實(shí)軸上相鄰2個數(shù)之間的最大差值。假設(shè)對任何實(shí)數(shù)的下取整函數(shù)耗時O(1),設(shè)計解最大間隙問題的線性時間算法。對于給定的n個實(shí)數(shù)x1,x2,...,xn,編程計算它們的最大間隙。2、題目分析:考慮到實(shí)數(shù)在實(shí)軸上按大小順序排列,先對這n個數(shù)排序,再用后面的數(shù)減去前面的數(shù),即可求出相鄰兩數(shù)的差值,找出差值中最大的即為最大差值。3、算法設(shè)計:a.用快速排序算法對這n個數(shù)排序,快速排序算法是基于分治策略的一個排序算法。其基本思想是,對于輸入的子

5、數(shù)組a[p:r],按以下三個步驟進(jìn)行排序:①分解:以a[p]為基準(zhǔn)元素將a[p:r]劃分為3段a[p:q-1],a[q]和a[q+1:r],使a[p:q-1]中任何一個元素小于等于a[p],而a[q+1:r]中任何一個元素大于等于a[q]。下標(biāo)q在劃分過程中確定。②遞歸求解:通過遞歸調(diào)用快速排序算法分別對a[p:q-1]和a[q+1:r]進(jìn)行排序。③合并:由于對a[p:q-1]和a[q+1:r]的排序是就地進(jìn)行的,所以在a[p:q-1]和a[q+1:r]都已排好的序后,不需要執(zhí)行任何計算,a[p:r]就已排好序。b.用函數(shù)maxtap()求出最大差值。4、源程序:#incl

6、ude#includedoublea[1000000];templatevoidswap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateintPartition(Type*a,intlow,inthigh){Typepivotkey;intmid=(low+high)/2;if((a[low]

7、

8、(a[low]>a[mid]&&a[mid]>a[high]))swap(a[low],a[mid])

9、;if((a[low]a[high])

10、

11、(a[low]>a[high]&&a[mid]pivotkey);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=pivotkey;returnj;}templat

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動畫的文件,查看預(yù)覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對本文檔版權(quán)有爭議請及時聯(lián)系客服。
3. 下載前請仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時可能由于網(wǎng)絡(luò)波動等原因無法下載或下載錯誤,付費(fèi)完成后未能成功下載的用戶請聯(lián)系客服處理。