征战蓝桥 —— 2014年第五届 —— C/C++A组第5题——锦标赛
生活随笔
收集整理的這篇文章主要介紹了
征战蓝桥 —— 2014年第五届 —— C/C++A组第5题——锦标赛
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目
如果要在n個數據中挑選出第一大和第二大的數據(要求輸出數據所在位置和值),使用什么方法比較的次數最少?
我們可以從體育錦標賽中受到啟發。
如圖【1.png】所示,8個選手的錦標賽,先兩兩捉對比拼,淘汰一半。優勝者再兩兩比拼…直到決出第一名。
第一名輸出后,只要對黃色標示的位置重新比賽即可。
下面的代碼實現了這個算法(假設數據中沒有相同值)。
代碼中需要用一個數組來表示圖中的樹(注意,這是個滿二叉樹,不足需要補齊)。
它不是存儲數據本身,而是存儲了數據的下標。
第一個數據輸出后,它所在的位置被標識為-1
//重新決出k號位置,v為已輸出值 void pk(int* a, int* b, int n, int k, int v) {int k1 = k*2 + 1;int k2 = k1 + 1;if(k1>=n || k2>=n){b[k] = -1;return;}if(b[k1]==v)pk(a,b,n,k1,v);elsepk(a,b,n,k2,v);//重新比較if(b[k1]<0){if(b[k2]>=0)b[k] = b[k2];elseb[k] = -1;return;}if(b[k2]<0){if(b[k1]>=0)b[k] = b[k1];elseb[k] = -1;return;}if(______________________) //填空b[k] = b[k1];elseb[k] = b[k2]; }//對a中數據,輸出最大,次大元素位置和值 void f(int* a, int len) {int n = 1;while(n<len) n *= 2;int* b = (int*)malloc(sizeof(int*) * (2*n-1));int i;for(i=0; i<n; i++){if(i<len)b[n-1+i] = i;elseb[n-1+i] = -1;}//從最后一個向前處理for(i=2*n-1-1; i>0; i-=2){if(b[i]<0){if(b[i-1]>=0)b[(i-1)/2] = b[i-1];elseb[(i-1)/2] = -1;}else{if(a[b[i]]>a[b[i-1]])b[(i-1)/2] = b[i];elseb[(i-1)/2] = b[i-1];}}//輸出樹根printf("%d : %d\n", b[0], a[b[0]]);//值等于根元素的需要重新pkpk(a,b,2*n-1,0,b[0]);//再次輸出樹根printf("%d : %d\n", b[0], a[b[0]]);free(b); }int main() {int a[] = {54,55,18,16,122,17,30,9,58};dfs(a,9); } 請仔細分析流程,填寫缺失的代碼。通過瀏覽器提交答案,只填寫缺失的代碼,不要填寫已有代碼或其它說明語句等。代碼
#include <iostream> using namespace std;//重新決出k號位置,v為已輸出值 //a原始數據,b是樹,n=31,k=0是下標,v是第一大的值的下標 void pk(int* a, int* b, int n, int k, int v) {int k1 = k*2 + 1;//k的左子下標int k2 = k1 + 1;//右子下標if(k1>=n || k2>=n){//超出樹的邊界,k一定是葉子,b[k]-1b[k] = -1;return;}//沿著冠軍的路,一直追溯到第一次比賽if(b[k1]==v)pk(a,b,n,k1,v);elsepk(a,b,n,k2,v);//到此,k就是冠軍一開始的下標,此時b[k]=-1//重新比較if(b[k1]<0){//if(b[k2]>=0)b[k] = b[k2];//左子<0,右子>0,選右子elseb[k] = -1;//都小于0 標記為-1return;}if(b[k2]<0){if(b[k1]>=0)b[k] = b[k1];elseb[k] = -1;return;}if(a[b[k1]]>a[b[k2]]) //填空b[k] = b[k1];elseb[k] = b[k2]; }//對a中數據,輸出最大,次大元素位置和值 void f(int* a, int len) {int n = 1;while(n<len) n *= 2; // n=16 2n-1=31 //開辟樹的空間 ll=31 樹數組的長度int* b = (int*)malloc(sizeof(int*) * (2*n-1));int i; // 初始化樹的最下層for(i=0; i<n; i++){if(i<len)b[n-1+i] = i;elseb[n-1+i] = -1;}//從最后一個向前處理 2*n-1-1是b數組的最大小標for(i=2*n-1-1; i>0; i-=2){if(b[i]<0){//i一開始一定指向右孩子,每次-2還是右孩子if(b[i-1]>=0)//兄弟大于0,父節點的值就是兄弟節點的值,父節點b[(i-1)/2]b[(i-1)/2] = b[i-1];else //兩個孩子都是-1b[(i-1)/2] = -1;}else{//自身不是-1,左兄弟也一定不是-1if(a[b[i]]>a[b[i-1]])//pk,誰代表的原始數據更大,誰上b[(i-1)/2] = b[i];elseb[(i-1)/2] = b[i-1];}} // 第一輪pk結束//輸出樹根printf("%d : %d\n", b[0], a[b[0]]);//值等于根元素的需要重新pk 2*n-1=31pk(a,b,2*n-1,0,b[0]);//再次輸出樹根printf("%d : %d\n", b[0], a[b[0]]);free(b); }int main() {int a[] = {154,55,18,16,122,17,130,9,58};//原始數據f(a,9); }總結
以上是生活随笔為你收集整理的征战蓝桥 —— 2014年第五届 —— C/C++A组第5题——锦标赛的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 征战蓝桥 —— 2014年第五届 ——
- 下一篇: 征战蓝桥 —— 2014年第五届 ——