資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定遞推關係的第 N 項，其中每一項都等於前 K 項的乘積
遞推關係 - 在數學中，遞推關係是指一個方程，其中序列的第 n 項等於前幾項的某種組合。
對於一個遞推關係，其中每一項都等於前 K 項的乘積，讓我們定義 N 和 K，以及一個包含關係前 K 項的陣列 arr[]。
因此，第 n 項由下式給出：
$$\mathrm{F_N= F_{N−1} ∗ F_{N−2} ∗ F_{N−3} ∗ . . .∗ F_{N−K}}$$
問題陳述
給定兩個正整數 N 和 K，以及一個包含 K 個正整數的整數陣列。求遞推關係的第 N 項。
示例 1
Input: N = 5, K = 3, arr[] = {2,1,4}
Output: 1024
解釋
F0 = 2, F1 = 1, F2 = 4 F3 = 2*1*4 = 8 F4 = 1*4*8 = 32 F5 = 4*8*32 = 1024
示例 2
Input: N = 10, K = 4, arr[] = {0, 1, 3, 2}
Output: 0
解釋
F0 = 0, F1 = 0, F2 = 0 F3 = 0, F4 = 0, F5 = 0, F6 = 0, F7 = 0, F8 = 0, F9 = 0, F10 = 0
方法 1：暴力求解
該問題的暴力求解方法是計算遞推關係中的所有項，並列印所需的第 n 項。
虛擬碼
function NthTerm(arr[], K, N)
Create an array ans of size N + 1 and initialize all elements to 0.
// Initialize first K terms
for i from 0 to K - 1
ans[i] = F[i]
// Find all terms from Kth term to the Nth term
for i from K to N
ans[i] = 1
for j from i - K to i - 1
// Current term is the product of previous K terms
ans[i] = (ans[i] * ans[j]) % MOD // If MOD is needed
// Print the Nth term
print ans[N]
end function
示例：C++ 實現
在下面的程式碼中，我們正在查詢遞推關係中的所有項。
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007; // The modulus value if needed.
// Function to find the Nth term
void NthTerm(int arr[], int K, int N){
// Stores the terms of recurrence relation
vector<int> ans(N + 1, 0);
// Initialize first K terms
for (int i = 0; i < K; i++)
ans[i] = arr[i];
// Find all terms from Kth term to the Nth term
for (int i = K; i <= N; i++) {
ans[i] = 1;
for (int j = i - K; j < i; j++) {
// Current term is the product of previous K terms
ans[i] = (1LL * ans[i] * ans[j]) % MOD;
}
}
// Print the Nth term
cout << ans[N] << endl;
}
int main(){
// Given N, K, and F[]
int arr[] = { 1, 2 };
int K = 2;
int N = 5;
// Function Call
NthTerm(arr, K, N);
return 0;
}
輸出
32
方法 2：最佳化方案
最佳化的解決方案將使用快速冪技術進行高效的模冪運算。可以使用雙端佇列資料結構來儲存序列的項。
虛擬碼：
// Function to calculate (x ^ y) % p using fast exponentiation
function power(x, y, p):
res = 1
x = x % p
while y > 0:
if y is odd:
res = (res * x) % p
y = y >> 1
x = (x * x) % p
return res
// Function to calculate modular inverse using Fermat's Little Theorem
function modInverse(n, p):
return power(n, p - 2, p)
// Function to find Nth term of the given recurrence relation
function NthTerm(arr[], K, N):
Create an empty deque named q
product = 1
// Initialize the product of the first K terms and the deque
for i from 0 to K - 1:
product = (product * arr[i]) % MOD
q.push_back(arr[i])
// Push (K + 1)th term to the deque
q.push_back(product)
for i from K + 1 to N:
f = q.front()
e = q.back()
// Calculate the (i + 1)th term
next_term = ((e % MOD * e % MOD) % MOD * modInverse(f, MOD)) % MOD
// Add the current term to the end of the deque
q.push_back(next_term)
// Remove the first number from the deque
q.pop_front()
// Print the Nth term
print q.back()
end function
示例：C++ 實現
上述方法可以實現為。
#include <iostream>
#include <deque>
using namespace std;
const int MOD = 1000000007; // The modulus value if needed.
// Function to calculate (x ^ y) % p using fast exponentiation ( O(log y) )
int power(int x, int y, int p){
int res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
// Function to find mod inverse using Fermat Little Theorem
int modInverse(int n, int p){
return power(n, p - 2, p);
}
// Function to find the Nth term of the given recurrence relation
void NthTerm(int arr[], int K, int N){
deque<int> q;
int product = 1;
// Initialize the product of the first K terms and the deque
for (int i = 0; i < K; i++) {
product = (product * arr[i]) % MOD;
q.push_back(arr[i]);
}
// Push (K + 1)th term to the deque
q.push_back(product);
for (int i = K + 1; i <= N; i++) {
int f = *q.begin();
int e = *q.rbegin();
// Calculate the ith term
int next_term = ((e % MOD * e % MOD) % MOD * (modInverse(f, MOD))) % MOD;
// Add the current term to the end of the deque
q.push_back(next_term);
// Remove the first number from the deque
q.pop_front();
}
// Print the Nth term
cout << *q.rbegin() << endl;
}
int main(){
// Given N, K, and arr[]
int arr[] = { 1, 2 };
int K = 2;
int N = 5;
// Function Call
NthTerm(arr, K, N);
return 0;
}
輸出
0
結論
總而言之，可以使用上述兩種方法找到給定遞推關係的第 N 項，其中每一項都等於前 K 項的乘積，第一種方法是暴力求解方法，然後是更最佳化的方案。
更新於：2023年10月25日
61 次瀏覽
廣告