algorithm - 将生成所需输出的魔法序列的 C++ 算法代码

Question

神奇的序列

神奇序列的定义如图所示。

Magical[1] = 0
Magical[2] = 1
Magical[n] = Magical[n-1] + 2*Magical[n-2] + 3*Magical[n-3] + ... (n-1)*Magical[1] + n*1., for n > 2

给定n (1 <= n <= 10^9 )，找到Magical[n].

示例 1：输入：3 输出：4

解释：

Magical[n] = 1*Magical[n-1] + 2*Magical[n-2] + 3*1
    Magical[3] = 1*Magical[2] + 2*Magical[1] + 3*1
    Magical[3] = 1*1 + 2*0 + 3*1
    Magical[3] = 4

示例 2：输入：4 输出：10

Magical[4] = 1*Magical[3]+2*Magical[2]+3*Magical[1]+4*1
          = 1*4+2*1+3*0+4 = 10

示例 3：输入：5 输出：26

Magical[5] = 1*Magical[4]+2*Magical[3]+3*Magical[2]+4*Magical[1]+5*1
          = 1*10+2*4+3*1+4*0+5 = 26

我尝试了以下类似的方法：-

int CuckooNum(int n)
{
    if (1 == n)
    {
        return 0;
    }
    else if (2 == n)
    {
        return 1;
    }

    std::vector<int> vec;
    vec.resize(n);
    vec[0] = 4;
    vec[1] = 0;
    vec[2] = 1;

    int multiplyer = n;
    int result = 0;
    for (int index=3; index <= n; index++)
    {
        result += multiplyer * vec[index-1];
        vec[index] = result;
        multiplyer--;
    }
    return result;
}

标签： algorithmc++11

Answer 1

long long func(int n)
{
  if (n==1) return 0;
  else if (n==2) return 1;
  else return 1*func(n-1)+2*func(n-2)+n;
}