資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢給定遞推關係的第 n 項
概念
假設 bn 是一個數字序列，由遞推關係 b1=1 和 bn+1/bn=2n 表示。我們的任務是確定給定 n 時 log2(bn) 的值。
輸入
6
輸出
15
解釋
log2(bn) = (n * (n - 1)) / 2 = (6*(6-1))/2 = 15
輸入
200
輸出
19900
方法
bn+1/bn = 2n
bn/bn-1 = 2n-1
.
.
.
b2/b1 = 21，我們將以上所有式子相乘以得到
(bn+1/bn).(bn/n-1)……(b2/b1) = 2n + (n-1)+……….+1
所以，bn+1/b1 = 2n(n+1)/2
因為我們知道，1 + 2 + 3 + ………. + (n-1) + n = n(n+1)/2
所以，bn+1 = 2n(n+1)/2 . b1；假設初始值 b1 = 1
所以，bn+1 = 2n(n+1)/2
現在用 (n+1) 代替 n，我們得到，
bn = 2n(n-1)/2
兩邊取對數，我們得到，
log2(bn) = 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
更新於: 2020-07-25
196 次瀏覽
廣告