第1关：双关系递推数列

题目

任务描述

本关任务：运用枚举和递推的基本思想，通过编程计算出双关系递推数列。设集合 M 定义如下：

1.初始 \(1\in M\)；

2.若\(x\in M\)，则有\(2x+1\in M\),\(5x-1\in M\)；

3.再无其它的数属于\(M\)。

试求集合\(M\)中的元素从小到大排列后所得序列的第\(n\)项，其中\(n<10001\)。

相关知识

为了完成本关任务，你需要掌握：1.枚举算法的两种框架，2.递推算法的实施步骤，3.问题求解思路。

枚举算法的两种框架
枚举的本质就是从所有的备选答案中去查询正确的解。一般的，使用枚举算法需要满足两个基本条件：

• 备选答案的数量是确定的或是有限个数的；
• 备选答案的范围在求解之前也应该是确定的。
  枚举算法有两种常见的框架：区间枚举和递增枚举。它们在不同的任务中都有着各自的优势。

区间枚举的主要思想是对于一个给定的闭区间，从该区间的下限一直逐个枚举到该区间的上限，其伪代码如下所示：

n=0;
for(k=<区间下限>;k<=<区间上限>;k++)
{
    <运算操作序列>;
    if(<约束条件>)
    {
        printf(<满足要求的解>);
        n++;
    }
}
printf(<解的个数>);

递增枚举的主要思想是从给定的枚举起点开始，一直逐个枚举，直到找到满足条件的解，程序结束，其伪代码如下所示：

k=<枚举起点>
while(1)
{
    k++;
    <运算操作序列>;
    if(<约束条件>)
    {
        printf(<满足要求的解>);
        return;
    }
}

递推算法的实施步骤
递推的定义：给定一个数的序列\(H_{0}\), \(H_{1}\),… , \(H_{n}\) ,… 若存在整数\(n_{0}\)，使当\(n > n_{0}\)时，可以用等号（或大于号、或小于号）将\(H_{n}\)与其前面的某些项\(H_{i}, i \in [0,n_{0}]\)联系起来，这样的式子就叫做\(H_{n}\)的递推式。递推算法的具体实施步骤如下：

1. 确定递推变量：递推变量可以是简单变量，也可以是一维或多维数组；
2. 建立递推关系：递推关系是递推的依据，是解决递推问题的关键；
3. 确定初始值和边界条件：根据问题最简单情形的数据，确定递推变量的初始值和边界条件，这是递推的基础；
4. 对递推过程进行控制：和枚举算法互相配合，完成递推问题的求解。

问题求解思路
该问题已经给出了递推变量\(x\)和递推关系\(2x+1,5x−1\)，以及初始值为\(x=1\)，但是不知道边界条件，也就是说要递推出足够多的项，然后才能找到排序后的第n项。

借助从小到大排序这一限制条件，我们可以设置两个变量，分别控制递推关系\(2x+1\)和\(5x−1\)的递推进程，使得依次递推出的序列是有序的，那么边界条件即为第n项递推的结束。

例如\(n=10\)时，通过递推可以得到第10项为31，具体步骤如下：

1. 第1步：给定数组m，从下标1开始存储有序递推数列，初始值\(m[1]=1\)，设定\(p_{2}=p_{5}=1\)，分别表示递推关系\(F_{2}(x)=2x+1\)和\(F _{5}(x)=5x−1\)的上一项递推变量x在数组m中的索引。

2. 第2步：分别计算两个递推式的值，若\(F_{2}(m[p_{2}])<F_{5}(m[p_{5}])\)，则数组m的第\(i=2\)项为\(m[2]=F_{2}(m[p_{2}])\)，并更新\(p _{2}=p+1\)；若\(F2(m[p_{2}])>F_{5}(m[p_{5}])\)，则数组m的第\(i=2\)项为\(m[2]=F_{5}(m[p_{5}])\)，并更新\(p_{5}=p_{5}+1\)；若\(F_{2}(m[p_{2}])=F_{5}(m[p_{5}])\)，则数组m的第\(i=2\)项为\(m[2]=F_{2}(m[p_{2}])\)，并更新\(p_{2}=p_{2}+1,p_{5} =p_{5}+1\)。

3. 第3步至第n步：按照第2中的递推过程，依次递推出第3项，第4项，直到第n项的值。

编程要求

本关的编程任务是补全右侧代码片段main中Begin至End中间的代码，具体要求如下：

• 在main中，根据枚举和递推的基本思想，计算出双关系递推数列的前n项，并从小到大存储到数组m中，下标从1开始，即第一项为m[1]=1。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：10
预期输出：31

开始你的任务吧，祝你成功！

参考答案

main.cpp

//
//  main.cpp
//  step2
//
//  Created by ljpc on 2018/12/8.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include <iostream>
#include <cstdio>

int main(int argc, const char * argv[]) {
 
    long long m[10001];     // 数组：从小到大保存的集合M的元素
    int n;                  // 查询第n项
    int p2;                 // F2(x)=2x+1的索引指针
    int p5;                  // F5(x)=5x-1的索引指针
    
    scanf("%d",&n);
    
    m[1]=1;
    p2=1;
    p5=1;
    
    // 请在这里补充代码，完成本关任务
    /********* Begin *********/
    int k = 2;
    int sum = m[1];
    while(k <= n) {
        int f2 = 2 * m[p2] + 1;
        int f5 = 5 * m[p5] - 1;
        if(f2 < f5) {
            m[k] = f2;
            p2++;
        } else if(f2 > f5) {
            m[k] = f5;
            p5++;
        } else {
            m[k] = f2;
            p2++;
            p5++;
        }
        k++;
    }
    /********* End *********/

    
    printf("%lld\n",m[n]);
 
    return 0;
}