“藍橋杯”遞推和遞歸(二)——數列求值、快速排序
點擊領取>>>藍橋杯算法講解視頻(適合Java,C語言選手)/ 藍橋杯歷年真題
1. 數列求值(2019 年試題 C)
【問題描述】
給定數列 1,1,1,3,5,9,17,……,從第 4 項開始,每項都是前 3 項的和。求第 20190324 項的最后 4 位數字。[答案提交]
這是一道結果填空題,考生只需要計算出結果并提交即可。本題的結果為一個 4 位整 數(提示:答案的千位不為 0),在提交答案時只填寫這個整數,填寫多余內容將無法得分。
[提示]
該數列很容易讓人想起斐波那契數列,可以采用計算斐波那契數列的遞推法進行計算,遞推公式為:
a[i]=a[i-3]+a[i-2]+a[i-1]
但要注意一個問題,那就是由于數列中的數據到后面會變得過大,從而超過 long long 所表示的范圍,所以數組中只保留計算結果的后 4 位,這就需要在每次存放數據之前就對數據進行取余運算,只保留數據的后 4 位。
2.快速排序 (2018 年試題 E)
[問題描述]
以下代碼可以從數組 a[]中找出第 k 小的元素,它使用了類似快速排序中的分治算法。
請仔細閱讀分析源碼,填寫下劃線部分缺失的內容。
#include <iostream>
#include <stdlib.h>
using namespace std;
int quick_select(int a[], int left, int right, int k)
{
//p是一個速記值取值為[left,right]
int p=rand()%(right- left+1) + left;
//將 a[p] 和a[right]進行交換
int x= a[p]; //把數軸的內容保存在變量x中
int t = a[p];
a[p] = a[right];
a[right] = t;
int i= left, j=right;
while(i < j)
{
while((i<j)&&a[i]<x) i++;
if(i < j)
{
a[j]=a[i];
j--;
}
while((i<j)&&a[j]>x) j--;
if(i < j)
{
a[i]=a[j];
i++;
}
}
a[i]=x; //a[i]左邊的數據都小于x,右邊的數據都大于x
p=i;
if(i-left+1==k) return a[i];
else if (i-left+1<k)
//填寫下面畫線里的內容
else quick_select(a, left, i-1, k);
}
int main()
{
int a[15]={1,4,2,8,5,7,23,58,16,27,55,13,26,24,12};
cout<<quick_select(a,0,14,7)<<endl;
}
[提示]
找第 K 小的元素利用的是快速排序的基本思想。首先隨機選中一個中心軸數據 ,然后將比中心軸大的數據都放在其右邊,比中心軸小的數據都放在其左邊,如下圖 1 所示。

從圖中可以看到,中心軸左邊一共有 4 個數據,右邊有 3 個數據。如果要找的數據剛好是第 5 小(4+1)的,則找到;如果要找的數據是第 3 小(3<4+1)的,則在左邊序列中尋找;如果要找的數據是第 7 小(7>4+ 1)的,則在右邊序列中尋找。
這里以本題的數據案例為例模擬程序的執行過程。
① 隨機生成一個中心軸,假設 p=9。
x=a[9]; //將中心軸數據存入變量 x
② 將中心軸 27 和右指針交換位置。此步的意義在于給下面的每次交換騰出一個空間,不用擔心中心軸沒了,其值被保存于 x 中。

③ 從左往右移動指針 i,找到一個比中心軸數據 27 大的數,即 58,將 58 放到 j 指針指向的位置上,指針 j 前移。

④ 從右往左移動;指針,找到一個比中心軸 27 小的數,即 24,將其移動到 i 指針指向的位置上,指針 i 后移。

⑤ 重復第 ③ 步,從左向右移動指針 i,找到一個比中心軸 27 大的數,即 55,將 55 放到 j 指針指向的位置上。

⑥ 重復第 ④ 步,從右往左移動 j 指針,找到一個比中心軸 27 小的數,即 26,將其移動到 i 指針指向的位置上。

⑦ 重復第 ③ 步,從左往右我當發現 i= 12 時,已經 i=j,所以跳出循環。將中心軸 x=27, 插入 i=12 的位置。此時 i 的位置即是中心軸的位置,在左邊的數都比中心軸數據小,右邊的數都比中心軸數據大。
此時一趟快速排序已經結束,接下來要考慮如何尋找第 k 小的數.i-left 是 i 在區間[eft,right]區間中的第幾個數。因為 k 的取值是從 1 開始的,而 i 是從 0 開始的,所以判斷的是 i-left 和 k-1 之間的關系,或者說是 i-left+1 和 k 之間的關系。如果正好相等,則說明中心軸就是 a[i],直接返回即可。如果 i-left+1 大于 k,則說明 k 在中心軸的左邊,下一次就只在中心軸左邊去找,將(a,left,i-1,k)遞歸。反之,如果 i-left+1 小于 k,則說明 k 在中心軸的右邊,下一次就只在中心軸右邊去找,執行(a,i+ l,right,k-(i- left+1))。
注意:在中心軸右邊尋找時,第 k 小的數是[i+1,right]這個區間中第 k-(i- -left+1)個數。
#include <iostream>
#include <stdlib.h>
using namespace std;
int quick_select(int a[], int left, int right, int k)
{
//p 是一個速記值取值為[left,right]
int p=rand()%(right- left+1) + left;
//將 a[p] 和 a[right]進行交換
int x= a[p]; //把數軸的內容保存在變量 x 中
int t = a[p];
a[p] = a[right];
a[right] = t;
int i= left, j=right;
while(i < j)
{
while((i<j)&&a[i]<x) i++;
if(i < j)
{
a[j]=a[i];
j--;
}
while((i<j)&&a[j]>x) j--;
if(i < j)
{
a[i]=a[j];
i++;
}
}
a[i]=x; //a[i]左邊的數據都小于 x,右邊的數據都大于 x
p=i;
if(i-left+1==k) return a[i];
else if (i-left+1<k) quick_select(a, i+1, right, k-i+left-1);
else quick_select(a, left, i-1, k);
}
int main()
{
int a[15]={1,4,2,8,5,7,23,58,16,27,55,13,26,24,12};
cout<<quick_select(a,0,14,7)<<endl;
}
3. 上期答案——取數位(2017 年試題 E)
//求 x 用十進制表示時的數位長度
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
//取 x 的第 k 位數字
int f(int x, int k) {
if(len(x)-k==0) return x%10;
return f(x/10,k) ;//填空
}
int main()
int x= 23574;
printf("&d\n", f(x,3));
return 0;
}
微信公眾號搜索: 北京小學學習資料 家長升學指南 家長升學訓練營 關注公眾號,獲取最新資訊!
掃碼添加“家長論壇”微信好友(微信號 16619908263)
獲取藍橋杯算法講解視頻(適合Java,C語言選手)/ 藍橋杯歷年真題
咨詢信息學奧賽政策請撥打電話 16619908263 (同微信號)
-END-

八少八素 早培:
①《人大附中早培海選必刷》《八中海選訓練與解析》電子版教材
http://www.syzly.net/question/110094
② 八少八素、人大附早培神測千題(上 下冊)
http://www.syzly.net/question/110096
③ 人大附、八中海選神測萬題練習冊及答案解析.pdf
http://www.syzly.net/question/110097
④ 八少八素試題分享&人大附早培班試題分享+神測復習資料
http://www.syzly.net/question/110099
北京幼升小、人大附早早培資料:
① 北京各學校幼升小面試真題、小學入學白皮書、學區房詳解
http://www.syzly.net/question/6232
② 知名機構人大附早早培(zzp)學前集訓隊-數學/神測和動手
http://www.syzly.net/question/110082
3)知名機構人大附早早培(zzp)學前集訓隊-數學/神測和動手
http://www.syzly.net/question/110082
4)知名機構人大附早早培(zzp)沖刺班講義(可自學)-春(下)數學
http://www.syzly.net/question/109824
5)知名機構人大附早早培(zzp)集訓隊- 春(下)- 神測和動手
http://www.syzly.net/question/109823
6)知名機構人大附早早培(zzp)集訓隊- 春(中)- 神測和動手
http://www.syzly.net/question/109820
杯賽-解析版 附詳細解題過程:
① 華杯賽/華數之星真題試卷-解析版 附詳細解題過程
http://www.syzly.net/question/110072
② 迎春杯/青少年創新能力測試-解析版 附詳細解題過程
http://www.syzly.net/question/110073
③ 希望杯/希望數學-解析版 附詳細解題過程
http://www.syzly.net/question/110074
④ YMO世界青少年奧林匹克數學競賽-解析版 附詳細解題過程
http://www.syzly.net/question/110075
⑤ 美國數學思維活動AMC8/10/12真題及答案解析
http://www.syzly.net/question/30256
⑥ 歷年全國小數測初評、終評真題及答案解析
http://www.syzly.net/question/109378
⑦ 美國數學大聯盟杯-解析版 附詳細解題過程
http://www.syzly.net/question/110076
⑧ 鵬程杯-解析版 附詳細解題過程
http://www.syzly.net/question/110077
9)IMAS小學中年/高年級第一/二輪檢測試題競賽數學試卷幾答案解析匯總
http://www.syzly.net/question/118541
10)2012-2021年Math Kangaroo袋鼠數學1-6年級競賽中英+全英歷年真題電子版(帶答案)
http://www.syzly.net/question/118507
11)2012-2021年Math Kangaroo袋鼠數學7-10年級競賽中英+全英歷年真題電子版(帶答案)
http://www.syzly.net/question/118508
12)32套香港亞太杯/亞太杯4-6年級競賽初賽、決賽數學試卷-解析版 附詳細解題過程
http://www.syzly.net/question/118509
13)114套香港亞洲國際數學奧林匹克公開賽(AIMO)1-6年級競賽初賽、復賽數學試卷-解析版 附詳細解題過程
http://www.syzly.net/question/118510
14)語文素養大賽 第七-第十屆真題(含答案)
http://www.syzly.net/question/118511
15)IMC國際數學競賽歷年真題合集
http://www.syzly.net/question/118739
16)[可打印]中環杯-解析版 附詳細解題過程
http://www.syzly.net/question/118514
17)[可打印]走美杯-解析版 附詳細解題過程
http://www.syzly.net/question/118515
18)[可打印]全國小學生數學能力測評真題試卷-解析版 附詳細解題過程
http://www.syzly.net/question/118516
19)美國數學思維活動AMC8/10/12真題
http://www.syzly.net/question/118517
20)數學花園探秘總決賽暨迎春杯大師賽試題合集
http://www.syzly.net/question/118543
北京小升初:
① 北京小升初各區真題、模擬題答案和詳細過程解析[可打印]
http://www.syzly.net/question/110105
2)北京小升初語數英筆試面試真題、點招、分班考真題、簡歷模板
http://www.syzly.net/question/118506
人大附練習冊含答案「有答案」 —— 初一到高三
http://www.syzly.net/question/118494
信息學奧賽
1)NOIP 1995年-2021年CSP提高組提高組復賽試題
http://www.syzly.net/question/118495
2)中小學生編程信息學奧賽NOIP中級班課程
http://www.syzly.net/question/118496
3)編程L1-L2系統班
http://www.syzly.net/question/118497
原版英文教材
1)最新English in mind最全資源,含學生書、教師書、練習冊
http://www.syzly.net/question/118518
2)劍橋頂級英文原版教材Unlock!聽說讀寫齊全 0-5級 電子課本、教師用書、視頻、音頻
http://www.syzly.net/question/118519
3)TOEFL Junior小托福語言形式與含義、聽力、閱讀真題模擬題試卷及電子版教材
http://www.syzly.net/question/118520
4)全球頂級閱讀教材 Reading Explorer 視頻、音頻、學生用書、老師用書
http://www.syzly.net/question/118521
西安交通大學少年班:
1)西安交通大學“少年班” 全科備考資料+模擬題+歷年真題+ 面試/復試資料
http://www.syzly.net/question/11809
2)西安交通大學“少年班” 考前突擊班 數學英語文綜理綜(TK)【數學+理綜+文綜+英語(85節)】
http://www.syzly.net/question/118475
3)西安交通大學少年班 數理化集訓營【數學12講+化學4講+物理8講+其他5講】
http://www.syzly.net/question/118474
4)西安交通大學少年班數理化集訓【數學15講+物理12講+化學4講+文綜知識點模擬3講】http://www.syzly.net/question/118473
IESOL朗思真題
1)IESOL朗思A2考試6套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1184982)IESOL朗思B1考試6套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1184993)IESOL朗思B2考試12套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1185004)IESOL朗思C1考試6套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1185015)LRN—朗思A2考試5套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1185026)LRN—朗思B1考試6套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/1187367)LRN—朗思B2考試10套真題--帶聽力、答案、聽力文本、答題卡
http://www.syzly.net/question/118503
KET/PET/FCE/IESOL:
1) KET/PET官方真題、官網樣卷、聽力閱讀答題卡、高頻單詞表
http://www.syzly.net/question/1101032)KET聽說讀寫逐項突破
http://www.syzly.net/question/1185223)38講KET劍橋語法初級
http://www.syzly.net/question/1185234)【完結】66天KET單詞訓練營
http://www.syzly.net/question/1185245)Nancy KET考前沖刺真題課(真題講解)
http://www.syzly.net/question/1185256)170講 PET劍橋語法 百日營
http://www.syzly.net/question/1185267)劍橋PET英語精講75節
http://www.syzly.net/question/1185278)20講Nancy2020新版PET沖刺訓練營
http://www.syzly.net/question/1185289)60講北外青少FCE口語/寫作/聽力/閱讀考官通關班【完結】
http://www.syzly.net/question/118529
北京小學期中期末試卷:
① 北京小學1-6年級上學期期中試卷+單元測試試卷及答案+單元知識點匯總
http://www.syzly.net/question/24908
② 北京各小學1-6年級期末真題試卷及解析 復習資料匯總
http://www.syzly.net/question/2952
③ 北京小學1-6年級下學期期中試卷+單元測試試卷及答案+單元知識點匯總
http://www.syzly.net/question/24914
④ 北京各小學1-6年級下學期期末真題試卷及解析 復習資料匯總
http://www.syzly.net/question/24915
5)157套-北京各小學1-6年級下學期語文/數學/英語期末試卷及答案
http://www.syzly.net/question/118491
6)北京各區小學1-6年級語數英各科期中真題及答案解析
http://www.syzly.net/question/118492
7)百套北京各區小學1-6年級語數英各科真題及答案解析
http://www.syzly.net/question/118493
高思學校競賽數學導引
高思學校競賽數學導引三年級詳解升級版教材和配套課程(69講錄播課)
http://www.syzly.net/question/118534高思學校競賽數學導引四年級詳解升級版教材和配套課程(72講錄播課)
http://www.syzly.net/question/118535高思學校競賽數學導引五年級詳解升級版教材和配套課程(72講錄播課)
http://www.syzly.net/question/118536三年級高思學校競賽數學課本&競賽數學同步課程
http://www.syzly.net/question/118530四年級高思學校競賽數學課本&競賽數學同步課程
http://www.syzly.net/question/118531五年級高思學校競賽數學課本&競賽數學同步課程
http://www.syzly.net/question/118532六年級高思學校競賽數學課本&競賽數學同步課程
http://www.syzly.net/question/118533
北京初中:
① 北京中考真題、北京各區初三一模、二模試卷及答案解析匯總
http://www.syzly.net/question/2815
② 中考英語聽說考試試卷及答案、口語和聽力訓練題及備考視頻
http://www.syzly.net/question/24732
北京高中:
① 北京高考英語聽力機考模擬試卷及答案、聽力原文、音頻
http://www.syzly.net/question/24738
② 北京高考一模、二模、高考試卷真題答案及解析、視頻解析
http://www.syzly.net/question/5684
添加 家長論壇微信
獲取 以上資料
沒有找到相關結果
0 個回復