K階錦標(biāo)賽算法

一個(gè)賽馬場有100匹馬，5條賽道，至少要比賽多少場才能選出跑得最快的10匹馬?

步驟：

1. 將100匹馬分成20次比賽，每次5匹馬，并保存每次比賽的結(jié)果（即第1名到第5名的順序）

2. 從勝利的20匹馬分成4次比賽，每次5匹馬，并保存每次比賽的結(jié)果（即第1名到第5名的順序）

3. 對最后的4匹馬進(jìn)行比賽，并保存每次比賽的結(jié)果（即第1名到第4名的順序）

即通過以上3個(gè)步驟，其實(shí)已經(jīng)建立一個(gè)4層的樹結(jié)構(gòu)。并且已經(jīng)得到第1名A

4. 在4層樹結(jié)構(gòu)中，挑出與A比過賽的且失敗的，且是第2名的馬（不超過5位），挑選出第2名B

在此過程中，可以想象將A刪除，并在比較過程中恢復(fù)樹結(jié)構(gòu)

依次輪推，直至找出前10名

總的比較次數(shù)為：

選出第一名：20+4+1

選出第二名：1

選出第三名：1

...

選出第十名：1

總次數(shù)：34次

?

問題描述：一個(gè)骰子有6面，概率均勻，我有7件事要隨機(jī)均勻選擇，用最少的扔擲次數(shù)如何仍？

問題擴(kuò)展：如果我有4件事，5件事，8件事，9件事，10件事 …… n件事要選擇，那么我如何用最少的扔擲次數(shù)來做到均勻分布？

思路：

注意問題中的關(guān)鍵字：(1) 最少扔擲的次數(shù) (2) 要求概率均勻分布

用容易理解的方式再將問題描述一遍：我們周末決定去聚餐，此時(shí)有6家備選飯店供我們選擇，為了公平，用骰子扔擲一次即可以隨機(jī)選出一家飯店。

但是，此時(shí)如果有7家備選飯店，同樣要做到公平，我們?nèi)绾斡?個(gè)面的骰子選擇去哪家飯店呢？

方法：

用骰子扔2次，可以得到 [7, 42] 區(qū)間中的一個(gè)數(shù)（視為6進(jìn)制），假設(shè)扔擲的數(shù)表示為m，如果 m=7 則舍棄，否則將 m mod 7 得到的數(shù)即為最終結(jié)果。

PS: m=7 時(shí)，會使得 0 的概率變大，所以要舍棄。

將上述表述再換種方式理解，用骰子扔2次，可以得到 [7, 42] 區(qū)間中的一個(gè)數(shù)，即此時(shí)得到了 36 個(gè)隨機(jī)數(shù)，對應(yīng)區(qū)間 [1, 36]。因此，假設(shè)扔擲的數(shù)表示為m，如果 m=36 則舍棄，否則將 m mod 7 得到的數(shù)即為最終結(jié)果。同理，當(dāng) m=36 時(shí)，會使得 1 的概率變大，所以要舍棄。

結(jié)論：

(1) 靈活使用N進(jìn)制的思想，雖然生活中多用10進(jìn)制。本題使用的是6進(jìn)制的思想，即表示為： result = Y * 6 + X，其中，X 表示第一次扔擲的點(diǎn)數(shù)，Y 表示第二次扔擲的點(diǎn)數(shù)。

(2) 使用求和的方法不滿足概率均勻分布，求和的結(jié)果屬于正態(tài)分布，中間值的概率最大，出現(xiàn)最大值和最小值的概率最小。

?

設(shè)計(jì)一個(gè)算法找到數(shù)組中兩個(gè)元素相加等于指定數(shù)的所有組合

思路：將數(shù)組排序，然后用兩個(gè)指向數(shù)組的指針，一個(gè)從前往后，一個(gè)從后往前，記為first和last，如果 fist + last < sum 則將fist向前移動，如果fist + last > sum，則last向后移動。

#if 1 #include <vector> #include <iostream> #include <algorithm> #include <iterator> #include <cstdlib> using namespace std; int main(){vector<int> iv;int N=20;// srand(time(0));for(int i=0;i<N;i++){int val=rand()%1000;if(val&0x1)val=-val;iv.push_back(val);}int s=109;//rand()%10000;copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));cout<<endl;sort(iv.begin(),iv.end());copy(iv.begin(),iv.end(),ostream_iterator<int>(cout," "));cout<<endl;vector<int>::const_iterator ite1=iv.begin(),ite2=iv.end()-1;while(ite1!=ite2){int sum=*ite1+*ite2;if(sum>s)--ite2;else if(sum<s)++ite1;else {cout<<*ite1<<' '<<*ite2<<endl;++ite1;--ite2;}} } #endif

18. 卡特蘭數(shù)

http://baike.baidu.com/view/2499752.htm

19. LIS最長遞增子序列

請給出一個(gè)O（nlogn)的算法，使之能夠找出一個(gè)n個(gè)數(shù)的序列中最長的單調(diào)遞增子序列。

這是算法導(dǎo)論中的一道課后題。

解法一：利用求最長公共子序列的思想，將n個(gè)數(shù)的序列A先排序形成一個(gè)有序的序列B，然后利用動態(tài)規(guī)劃的思想求A與B的最長公共子序列，得到的最長公共子序列就是所求的解。但是我們知道最長公共子序列的解法是O（n2），所以不滿足題目要求，此法不通。

解法二：對包含n個(gè)數(shù)的序列A，我們使用一個(gè)數(shù)組C，其中C[i]記錄長度為i的所有單調(diào)遞增子序列的最小的元素（可能說的不清楚，舉例說明比如A有3個(gè)長為2的單調(diào)遞增子序列1,2；3,4；5,6；那么C[2]的值就是2，記錄的是最小的那個(gè)子序列的最后一個(gè)元素）。具體的遍歷過程是對于一個(gè)元素A[i]，通過二分查找C（因?yàn)镃是有序數(shù)組），獲取A[i]的位置flag，比較A[i]與C[flag]的大小，如果小于C[falg]用A[i]替換C[flag]，如果大于用A[i]替換C[flag+1]。這樣遍歷一遍就能得到數(shù)組A的最長的公共子序列的長度，但是要獲得最長公共子序列的組成，需要利用第一次遍歷獲得長度，再遍歷一次，在給定的長度時(shí)將C中的元素拷貝出來，防止后邊可能進(jìn)行的破壞。雖然需要遍歷兩邊但是滿足時(shí)間復(fù)雜度的要求，大家有更好的方法歡迎討論。

?

問題描述：兩個(gè)數(shù)組a[N]，b[N]，其中A[N]的各個(gè)元素值已知，現(xiàn)給b[i]賦值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；

要求：

1.不準(zhǔn)用除法運(yùn)算

2.除了循環(huán)計(jì)數(shù)值，a[N],b[N]外，不準(zhǔn)再用其他任何變量（包括局部變量，全局變量等）

3.滿足時(shí)間復(fù)雜度O（n），空間復(fù)雜度O（1）

#include <iostream> #include <cstdlib> using namespace std; const int N=10; int main1(int* a) {int i;int b[N];b[0] = 1;for(i = 1; i < N; i++){b[0] *= a[i - 1];b[i] = b[0];}b[0] = 1;for(i = N-2; i > 0; i--){b[0] *= a[i + 1];b[i] *= b[0];}b[0] *= a[1];for(i = 0; i < N; i++){cout << b[i] << " ";}cout << endl;return 0; } int main2(int *a){int i;int b[N];b[N-1]=1;for(int i=1;i<N-1;i++){b[N-1]*=a[i-1];b[i]=b[N-1];}b[N-1]*=a[N-2];b[0]=1;for(int i=N-2;i>0;i--){b[0]*=a[i+1];b[i]*=b[0];}b[0]*=a[1];for(i = 0; i < N; i++) {cout << b[i] << " ";}cout << endl; } int main(){srand(time(0));int a[N];for(int i=0;i<N;i++) {int val;while((val=rand()%10)==0);a[i]=val;}main1(a);main2(a); } 騰訊筆試題:計(jì)算下面函數(shù)的結(jié)果： static int ack(int m,int n){if(m==0){return n+1;}else if(n==0){return ack(m-1,1);}else{return ack(m-1,ack(m,n-1));} }

?

騰訊面試題:1-20的兩個(gè)數(shù)把和告訴A,積告訴B，A說不知道是多少，B也說不知道，這時(shí)A說我知道了，B接著說我也知道了，問這兩個(gè)數(shù)是多少？

設(shè)和為S，積為M。

首先，A:我不知道。

說明：S可以分解成多個(gè)組合，而2=1+1，3=1+2,40=20+20,39=19+20，只有一種分解方式，因此S應(yīng)屬于[4,38]集合。

其次，B:我也不知道。

說明：M也可以分解成多個(gè)組合，因此M不是質(zhì)數(shù)。

再者，A:我現(xiàn)在知道了。

說明：S分解方式中只有一個(gè)相乘之后是合數(shù)，其他分解方式相乘之后都是質(zhì)數(shù)。這樣，A才能根據(jù)B說不知道，而排出所有相乘是質(zhì)數(shù)（M是質(zhì)數(shù)，分解方式只有一種：1*質(zhì)數(shù)）的可能，剩下的一個(gè)相乘之后是合數(shù)的組合就是A所得到的解。

而相乘之后是質(zhì)數(shù)的：只有1*質(zhì)數(shù) = 質(zhì)數(shù)！

1-20的所有質(zhì)數(shù)：T = {2， 3， 5， 7， 11， 13， 17， 19}。

設(shè)x為T中的任意一個(gè)質(zhì)數(shù)。那么，S的可能取值集合：{2+1, 3+1, 5+1, 7+1, 11+1, 13+1, 17+1, 19+1}，即：SS = {3， 4， 6， 8， 12， 14， 18， 20}

S= 3時(shí)：3不在【4,38】集合，排除；

S= 4時(shí)：4=2+2=1+3，（2,2）相乘為4（非質(zhì)數(shù)，滿足條件），（1，3）相乘為3（質(zhì)數(shù)，排除）；

S= 6時(shí)：6=1+5=2+4=3+3，相乘分別為5,8,9，出現(xiàn)兩個(gè)合數(shù)，排除；

其他值都是存在多個(gè)合數(shù)分解的情況，因此均排除了。

因此，A得到的解是2和2.

最后，B:我也知道了。

說明：B根據(jù)自己已知的M值，站在A的立場思考，能夠獲得M=4的結(jié)果，現(xiàn)在驗(yàn)證如下：

M=4=2*2=1*4，相加結(jié)果為4,5.而5不在SS集合之中，因此結(jié)果為2和2.

因此，最終答案為2和2.

以上給出的分析是假設(shè)這兩個(gè)數(shù)是可以相同的。

如果認(rèn)為這兩個(gè)數(shù)不同，那又應(yīng)該是哪兩個(gè)數(shù)呢？

還是按照上面的步驟來進(jìn)行分析：

首先，A:我不知道。

說明：S有多個(gè)分解方式。S屬于【5,37】.

其次，B:我不知道。

說明：M有多種分解方式。

再者，A:我知道這兩個(gè)數(shù)了。

說明：

S分解方式中只有一個(gè)相乘之后是合數(shù)，其他分解方式相乘之后的積僅有一種分解方式！這樣，A才能根據(jù)B說不知道，而排出所有相乘是質(zhì)數(shù)（M是質(zhì)數(shù)，分解方式只有一種：1*質(zhì)數(shù)）的可能，剩下的一個(gè)相乘之后是合數(shù)的組合就是A所得到的解。

那么，S的可能取值集合：{3,4,5，......，37}

S= 3時(shí)：3不在【5,38】集合，排除；

S= 4時(shí)：4=1+3，只有一種分解方式，排除；

S=5時(shí)：5=1+4=2+3，相乘分別為4,8，4=1*4僅有一種分解方式排除，8=1*8=2*4滿足，得到一個(gè)解。

S= 6時(shí)：6=1+5=2+4，相乘分別為5,8，顯然也滿足。

其他值都是存在多個(gè)合數(shù)分解的情況，因此均排除了。

因此，解為2和3 或 2和4

最后，B：我也知道了。

說明：

B站在A立場得知結(jié)果。驗(yàn)證如下：

如果為2和3，則積為6，和為5。此時(shí)，5=1+4=2+3，4僅有一種分解方式，A能夠確定為2和3；6=1*6=2*3，相加為7,5，此時(shí)7=1+6=2+5=3+4，相乘后為6,10,12，無法確定唯一解，舍掉1,6的解；而5=1+4=2+3，相乘后為4,6，舍掉4，有解2和3.

如果為2和4，則積為8，和為6.此時(shí)，6=1+5=2+4,5僅有一種分解方式，A能夠確定為2和4. 8=1*8=2*4，相加為9,6，此時(shí)9=1+8=2+7=3+6=4+5，無法確定唯一解，舍掉1和8的解；而6=1+5=2+4，相乘后為5,6，舍掉5，有解2和4.

因此，最終解為2和3 或 2和4 。

?

趣題：從1到4000中各位數(shù)字之和能被4整除的有多少個(gè)？

一個(gè)小學(xué)奧數(shù)老師給我講了一道小學(xué)奧數(shù)題，這是他在上課時(shí)遇到的：從 1 到 4000 中，各位數(shù)字之和能被 4 整除的有多少個(gè)？

注意，問題可能沒有你想的那么簡單，滿足要求的數(shù)分布得并沒有那么規(guī)則。 1 、 2 、 3 、 4 里有一個(gè)滿足要求的數(shù)， 5 、 6 、 7 、 8 里也有一個(gè)滿足要求的數(shù)，但是 9 、 10 、 11 、 12 里就沒有了。

盡管如此，這個(gè)問題仍然有一個(gè)秒殺解。你能多快想到？

答案就是 1000 。首先， 0 和 4000 都是滿足要求的數(shù)，因而我們不去看 1 到 4000 中有多少個(gè)滿足要求的數(shù)，轉(zhuǎn)而去看 0 到 3999 中有多少個(gè)滿足要求的數(shù)，這對答案不會有影響。注意到，如果固定了末三位，比如說 618 ，那么在 0618 、 1618 、 2618 、 3618 這四個(gè)數(shù)中，有且僅有一個(gè)數(shù)滿足，其各位數(shù)字之和能被 4 整除。考慮從 000 到 999 這 1000 個(gè)可能的末三位組合，每一個(gè)組合都唯一地對應(yīng)了一個(gè)滿足要求的四位數(shù)，因此問題的答案就是 1000 。

真正有趣的事情在后面呢。一個(gè)小朋友舉手說：“老師，我明白了，按照這個(gè)道理，從 1 到 3000 里各位數(shù)字之和能被 3 整除的數(shù)也是 1000 個(gè)。”另一個(gè)小朋友說：“廢話，各位數(shù)字之和能被 3 整除就表明整個(gè)數(shù)能被 3 整除，在 1 到 3000 里這樣的數(shù)當(dāng)然有 1000 個(gè)嘛！”全班哄堂大笑。

轉(zhuǎn)自：http://www.matrix67.com/blog/archives/4644

題目：10G 個(gè)整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。

解答：

拿到此題目首先考慮的是內(nèi)存的限制，因而無法用快速排序或是部分排序。若是求的是最大值或最小值，或是K小的值（k<2G）則可以采用堆排序O(NlogK)。但現(xiàn)在是求中位數(shù)即排在第5G和5G+1的數(shù)

算法思路分析：假設(shè)是無符號整數(shù)，

第一步： 借鑒桶排序的思路，因?yàn)檎麛?shù)為32位，我們先按高16位2^16=64K進(jìn)行計(jì)數(shù)，即分成64K段，這樣需要的計(jì)數(shù)數(shù)組大小為2^16，若數(shù)組類型為int型，存在缺點(diǎn)，若10G的數(shù)都是相同，這樣數(shù)組存的計(jì)數(shù)最大為2^32=4G，就會出現(xiàn)溢出，所以數(shù)組類型采用long long8字節(jié)型。占用內(nèi)存為2^16*8B=518KB。而內(nèi)存給了2G,可見利用得過少，表明還有很大的改進(jìn)空間。 改進(jìn)：分成2G/8B=2^28=256M段，這樣段越多，第二步掃描分析的數(shù)據(jù)就越少。

long long Counter[1 < <28];//256M桶 unsigned int x; memset(Counter,0,sizeof(Counter)); foreachnumber(x) {Counter[x>>4]++; //高28位 } long long sum=0; for(i=0;i <1 < <28;i++) {sum+=Counter[i];if(sum>=5LL < <30)break;//找到中位數(shù)所在的段 } sum-=5LL < <30; sum=Counter[i]-sum;//為達(dá)到5G,中位數(shù)所在的段需要的個(gè)數(shù)

第二步：前步已把10G數(shù)據(jù)按高28位分到了256M桶中，且已經(jīng)找到中位數(shù)在哪一段，只要把此段按低4位分到16個(gè)段中，即可以找到

int segment=i; memset(Counter,0,sizeof(Counter)); foreachnumber(x) {if((x>>16)==segment){Counter[x&(~((-1) < <16))]++; //低4位。 -1的8位二進(jìn)制表示為11111111 } } long long lsum=0; for(i=0;i <1 < <4;i++) {lsum+=Counter[i];if(lsum>=sum)break; } int keynum = (segment<<4)|(i);

總共只要讀兩遍整數(shù)，對每個(gè)整數(shù)也只是常數(shù)時(shí)間的操作，總體來說是線性時(shí)間

若是有符號的整數(shù)，只需改變映射即可。

參考：http://grachel1986.blog.163.com/blog/static/5660389320108271179910/

轉(zhuǎn)載于:https://www.cnblogs.com/xkfz007/archive/2012/11/20/2779186.html

總結(jié)

以上是生活随笔為你收集整理的算法题集-2的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。