C程序查找给定递推关系的第n项

假设我们有三个数字a、b、c和一个值n。我们遵循一个递推公式S(n) -

  • S(1) 返回 a
  • S(2) 返回 b
  • S(3) 返回 c
  • S(n) 返回 S(n-1) + S(n-2) + S(n-3)，对于所有 n > 3。

我们将不得不通过遵循此递推关系来查找第n项。

因此，如果输入类似于 a = 5，b = 2，c = 3，n = 6，则输出将为 28，因为 -

  • S(6) = S(5) + S(4) + S(3)
  • S(5) = S(4) + S(3) + S(2)
  • S(4) = S(3) + S(2) + S(1) = 3 + 2 + 5 = 10
  • 所以现在 S(5) = 10 + 3 + 2 = 15
  • 并且 S(6) = 15 + 10 + 3 = 28

为了解决这个问题，我们将遵循以下步骤 -

定义一个函数 solve()，它将接收 a、b、c、n，

  • 如果 n 等于 1，则
    • 返回 a
  • 如果 n 等于 2，则
    • 返回 b
  • 如果 n 等于 3，则
    • 返回 c
  • 返回 solve((a, b, c, n - 1) + solve(a, b, c, n - 2) + solve(a, b, c, n - 3))

示例

让我们看看以下实现以获得更好的理解 -

#include <stdio.h>
int solve(int a, int b, int c, int n){
    if(n == 1)
        return a;
    if(n == 2)
        return b;
    if(n == 3)
        return c;
    return solve(a, b, c, n-1) + solve(a, b, c, n-2) + solve(a, b, c, n-3);
}
int main(){
    int a = 5, b = 2, c = 3, n = 6;
    int res = solve(a, b, c, n);
    printf("%d", res);
}

输入

5, 2, 3, 6

输出

28

更新于: 2021年10月8日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告