在 C++ 中查找给定递推关系的第 n 项

概念

假设 b_n 是一个数字序列，由递推关系 b₁=1 和 b_n+1/b_n=2ⁿ 表示。我们的任务是确定给定 n 时 log₂(b_n) 的值。

输入

6

输出

15

解释

log₂(b_n) = (n * (n - 1)) / 2 = (6*(6-1))/2 = 15

输入

200

输出

19900

方法

b_n+1/b_n = 2ⁿ

b_n/b_n-1 = 2^n-1

.

.

.

b₂/b₁ = 2¹，我们将以上所有式子相乘以得到

(b_n+1/b_n).(b_n/_n-1)……(b₂/b₁) = 2^{n + (n-1)+……….+1}

所以，b_n+1/b₁ = 2^n(n+1)/2

因为我们知道，1 + 2 + 3 + ………. + (n-1) + n = n(n+1)/2

所以，b_n+1 = 2^n(n+1)/2 . b₁；假设初始值 b₁ = 1

所以，b_n+1 = 2^n(n+1)/2

现在用 (n+1) 代替 n，我们得到，

b_n = 2^n(n-1)/2

两边取对数，我们得到，

log₂(b_n) = n(n-1)/2

示例

 在线演示

// C++ program to find nth term of
// a given recurrence relation
#include <bits/stdc++.h>
using namespace std;
// Shows function to return required value
int sum(int n1){
   // Now get the answer
   int ans1 = (n1 * (n1 - 1)) / 2;
   //Now return the answer
   return ans1;
}
// Driver program
int main(){
   // Get the value of n
   // int n = 6;
   int n = 200;
   // Uses function call to print result
   cout << sum(n);
   return 0;
}

输出

19900

Arnab Chakraborty

更新于: 2020-07-25

196 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习