神奇的数组和神奇的算法

Question

C++的题目如下：

 

 

然后我看到一个大佬的代码是这样的，很简洁很神奇，但是我看了很久始终没搞懂为什么。

大佬代码如下：

#include <iostream>
using namespace std;
int k,n,i=1,j=1,l=1;

long long q[1001]={0,1};

inline long long min(long long a,long long b){return a<b?a:b;}

int main(){

    cin>>k>>n;
    while(l<n){

        long long a=q[i]*k,b=q[j]*k+1;//1 = 3^0
        q[++l]=min(a,b);

        if(q[l]==a)i++;
        if(q[l]==b)j++;

    }
cout<<q[n]<<endl;

}

有没有老师能解释一下为什么！谢谢啦

Answer 1

其实就是规律吧，你多列几组数据就能明白了，重要的是题目中的那个递增还是很重要的。其实多列几组的话，规律其实更加清楚了。

int res1[1001];
void fun1(int k) {
    res1[1] = 1;
    int a = 1;
    for (int i = 2; i <= 1000;)
    {
        res1[i++] = res1[a] * k;
        if (i <= 1000)
            res1[i++] = res1[a] * k + 1;
        a ++;
    }
}
int main()
{
    fun1(3);
    return 0;
}

代码就像这样了，其实看上去更加清楚了，而不是在哪里猜测下一个数应该是啥。