数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究雅可比数和雅可比-卢卡斯数
雅可比数
卢卡斯序列 𝑈𝑛(𝑃,𝑄) 其中 P = 1 且 Q = -2 被称为雅可比数。雅可比数的递推关系为：
$$\mathrm{𝐽_𝑛 = 0\: 𝑓𝑜𝑟 \: 𝑛 = 0}$$
$$\mathrm{𝐽_𝑛 = 1\: 𝑓𝑜𝑟 \: 𝑛 = 1}$$
$$\mathrm{𝐽_𝑛 = 𝐽_𝑛−1 + 2𝐽_{𝑛−2}\: 𝑓𝑜𝑟 \: 𝑛 > 1}$$
以下是雅可比数：
0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, ….
雅可比-卢卡斯数
互补卢卡斯序列 $\mathrm{𝑉_𝑛(𝑃,𝑄)}$ 其中 P = 1 且 Q = -2 被称为雅可比-卢卡斯数。雅可比-卢卡斯数的递推关系为：
$\mathrm{𝐽_𝑛}$ = 2 𝑓𝑜𝑟 𝑛 = 0
$\mathrm{𝐽_𝑛}$ = 1 𝑓𝑜𝑟 𝑛 = 1
$\mathrm{𝐽_𝑛 = 𝐽_{𝑛−1} + 2𝐽_{𝑛−2}\: 𝑓𝑜𝑟 \: 𝑛 > 1}$
以下是雅可比-卢卡斯数：
2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097, ….
问题陈述
给定一个整数 N。找到第 N 个雅可比数和雅可比-卢卡斯数。
示例 1
Input: 2
Output: Jacobsthal = 1 Jacobsthal-Lucas = 5
解释
雅可比数 - 0, 1, 1
雅可比-卢卡斯数 - 2, 1, 5
示例 2
Input: 12
Output: Jacobsthal = 1365 Jacobsthal-Lucas = 4097
解释
雅可比数 - 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365
雅可比-卢卡斯数 - 2, 1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097
方法 1：递归方法
使用雅可比数和雅可比-卢卡斯数的递推关系，我们可以形成一个递归关系，如 $\mathrm{𝐽_𝑛 = 𝐽_{𝑛−1} + 2𝐽_{𝑛−2}}$
伪代码
procedure jacobsthalNumber (n)
if n == 0
ans = 0
end if
if n == 1
ans = 1
end if
ans = jacobsthalNumber(n-1) + 2*jacobsthalNumber(n-2)
end procedure
procedure jacobsthalLucasNumber (n)
if n == 0
ans = 2
end if
if n == 1
ans = 1
end if
ans = jacobsthalLucasNumber(n-1) + 2*jacobsthalLucasNumber(n-2)
end procedure
示例
在下面的程序中，我们为雅可比数和雅可比-卢卡斯数创建了单独的函数，并使用它们的递推关系来递归计算第 n 个数。
#include<bits/stdc++.h>
using namespace std;
// Recursive function for finding the nth Jacobsthal Number
int jacobsthalNumber (int n){
// Defining the first case in recurrence relation
if (n == 0) {
return 0;
}
// Defining the second case in recurrence relation
if (n == 1) {
return 1;
}
// Defining the third case in recurrence relation when n>1
return jacobsthalNumber(n-1) + 2*jacobsthalNumber(n-2);
}
// Recursive function for finding the nth Jacobsthal-Lucas Number
int jacobsthalLucasNumber (int n){
// Defining the first case in recurrence relation
if (n == 0) {
return 2;
}
// Defining the second case in recurrence relation
if (n == 1) {
return 1;
}
// Defining the third case in recurrence relation when n>1
return jacobsthalLucasNumber(n-1) + 2*jacobsthalLucasNumber(n-2);
}
int main(){
int N = 7;
cout << N << "th Jacobsthal number = " << jacobsthalNumber(N) << endl;
cout << N << "th Jacobsthal-Lucas number = " << jacobsthalLucasNumber(N) << endl;
}
输出
7th Jacobsthal number = 43 7th Jacobsthal-Lucas number = 127
时间复杂度 - O(2n)，因为形成了递归树。
空间复杂度 - O(1) + 递归栈空间。
方法 2：记忆化
记忆化有助于降低时间复杂度，因为它有助于仅计算一次输入的函数，方法是存储结果。
伪代码 -
Initialize two arrays j[N+1] and jL[N+1] with -1
procedure jacobsthalNumber (n)
if n == 0
ans = 0
end if
if n == 1
ans = 1
end if
if j[n] == -1
j[n] = jacobsthalNumber(n-1) + 2*jacobsthalNumber(n-2)
end if
ans = j[n]
end procedure
procedure jacobsthalLucasNumber (n)
if n == 0
ans = 2
end if
if n == 1
ans = 1
end if
if jL[n] == -1
jL[n] = jacobsthalLucasNumber(n-1) + 2*jacobsthalLucasNumber(n-2)
end if
ans = jL[n]
end procedure
示例
在此程序中，我们使用记忆化来降低先前方法的时间复杂度。
#include<bits/stdc++.h>
using namespace std;
int N = 12;
// initializing memoization table
vector<int> j(N+1, -1), jL(N+1, -1);
// Memoized function for finding the nth Jacobsthal Number
int jacobsthalNumber (int n){
// Defining the first case in recurrence relation
if (n == 0) {
return 0;
}
// Defining the second case in recurrence relation
if (n == 1) {
return 1;
}
// Checking if nth jacobsthal number is already calculated or not
if(j[n] != -1) {
return j[n];
} else {
return j[n] = jacobsthalNumber(n-1) + 2*jacobsthalNumber(n-2);
}
}
// Memoized function for finding the nth Jacobsthal-Lucas Number
int jacobsthalLucasNumber (int n){
// Defining the first case in recurrence relation
if (n == 0) {
return 2;
}
// Defining the second case in recurrence relation
if (n == 1) {
return 1;
}
// Checking if nth jacobsthal-lucas number is already calculated or not
if(jL[n] != -1) {
return jL[n];
} else {
return jL[n] = jacobsthalLucasNumber(n-1) + 2*jacobsthalLucasNumber(n-2);
}
}
// Driver code
int main(){
cout << N << "th Jacobsthal number = " << jacobsthalNumber(N) << endl;
cout << N << "th Jacobsthal-Lucas number = " << jacobsthalLucasNumber(N) << endl;
}
输出
12th Jacobsthal number = 1365 12th Jacobsthal-Lucas number = 4097
时间复杂度 - O(N)，因为不会计算重复的递归调用。
空间复杂度 - O(N)（因为用于记忆化表的空间）+ 递归栈空间。
方法 3：动态规划
伪代码 -
procedure jacobsthal (n)
initialize dp table jacobsthalDP[n+1]
jacobsthalDP[0] = 0
jacobsthalDP[1] = 1
for i = 2 to n
jacobsthalDP[i] = jacobsthalDP[i-1] + 2*jacobsthalDP[i-2]
end for
ans = jacobsthalDP[n]
end procedure
procedure jacobsthalLucas (n)
initialize dp table jacobsthalLucasDP[n+1]
jacobsthalLucasDP[0] = 2
jacobsthalLucasDP[1] = 1
for i = 2 to n
jacobsthalLucasDP[i] = jacobsthalLucasDP[i-1] + 2*jacobsthalLucasDP[i-2]
end for
ans = jacobsthalLucasDP[n]
end procedure
示例
在下面的程序中，使用了动态规划方法。
#include<bits/stdc++.h>
using namespace std;
// Function for finding the nth Jacobsthal Number
int jacobsthalNumber (int n){
int jacobsthalDP[n+1];
// Defining base condition
jacobsthalDP[0] = 0;
jacobsthalDP[1] = 1;
for (int i = 2 ; i <= n ; i++){
jacobsthalDP[i] = jacobsthalDP[i-1] + 2*jacobsthalDP[i-2];
}
return jacobsthalDP[n];
}
// Function for finding the nth Jacobsthal-Lucas Number
int jacobsthalLucasNumber (int n){
int jacobsthalLucasDP[n+1];
// Defining base condition
jacobsthalLucasDP[0] = 2;
jacobsthalLucasDP[1] = 1;
for (int i = 2 ; i <= n ; i++){
jacobsthalLucasDP[i] = jacobsthalLucasDP[i-1] + 2*jacobsthalLucasDP[i-2];
}
return jacobsthalLucasDP[n];
}
int main(){
int N = 5;
cout << N << "th Jacobsthal number = " << jacobsthalNumber(N) << endl;
cout << N << "th Jacobsthal-Lucas number = " << jacobsthalLucasNumber(N) << endl;
}
输出
5th Jacobsthal number = 11 5th Jacobsthal-Lucas number = 31
时间复杂度 - O(n)，因为每个函数中仅执行一次 for 循环
空间复杂度 - dp 表的 O(n)。在此方法中，不使用额外的栈递归空间。
结论
总之，雅可比数是从卢卡斯序列中获得的，而雅可比-卢卡斯数是从互补卢卡斯序列中获得的。为了找到第 n 个雅可比数和雅可比-卢卡斯数，我们可以从递归方法转向具有最小时间和空间复杂度的动态规划方法。
210 次查看
