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