头歌实验：

第一关：双关系递推数列

任务描述

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

1.初始 1∈M；

2.若x∈M，则有2x+1∈M，5x−1∈M；

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

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

枚举算法的两种框架

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

• 备选答案的数量是确定的或是有限个数的；
• 备选答案的范围在求解之前也应该是确定的。

枚举算法有两种常见的框架：区间枚举和递增枚举。

区间枚举的主要思想是对于一个给定的闭区间，从该区间的下限一直逐个枚举到该区间的上限；

递增枚举的主要思想是从给定的枚举起点开始，一直逐个枚举，直到找到满足条件的解，程序结束。

递推算法的实施步骤

递推的定义：给定一个数的序列H0​，H1​，...，Hn​，...，若存在整数n0​，使当n>n0​时，可以用等号（或大于号、或小于号）将Hn​与其前面的某些项Hi​,i∈[0,n0​]联系起来，这样的式子就叫做Hn​的递推式。递推算法的具体实施步骤如下：

    确定递推变量：递推变量可以是简单变量，也可以是一维或多维数组；

   建立递推关系：递推关系是递推的依据，是解决递推问题的关键；

   确定初始值和边界条件：根据问题最简单情形的数据，确定递推变量的初始值和边界条件，这是递推的基础；

   对递推过程进行控制：和枚举算法互相配合，完成递推问题的求解。

问题求解思路

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

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

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

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

2.第2步：分别计算两个递推式的值，若F2​(m[p2​])<F5​(m[p5​])，则数组m的第i=2项为m[2]=F2​(m[p2​])，并更新p2​=p2​+1；若F2​(m[p2​])>F5​(m[p5​])，则数组m的第i=2项为m[2]=F5​(m[p5​])，并更新p5​=p5​+1；若F2​(m[p2​])=F5​(m[p5​])，则数组m的第i=2项为m[2]=F2​(m[p2​])，并更新p2​=p2​+1,p5​=p5​+1。

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

 

编程要求

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

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

 实验代码段：

#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 sum = m[1];
	for(int i=2;i<=n;i++){
		int tmp2 = 2*m[p2]+1;	
		int tmp5 = 5*m[p5]-1;
		if(tmp2>tmp5){
			m[i] = tmp5;
			p5++;
		}
		else if(tmp2<tmp5){
			m[i] = tmp2;
			p2++;
		}
		else{
			m[i] = tmp2;
			p2++;
			p5++;
		}
		sum+=m[i];
	} 

    /********* End *********/

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

 实验结果：