“藍橋杯”遞推和遞歸（二）——數列求值、快速排序

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;
    }