Điền số Lucas

Time limit: 1.0s , Memory limit: 256M , Points: 1 (partial)

Trong lý thuyết số có rất nhiều dãy số có quan hệ rất đặc biệt, ví dụ như dãy Fibonacci, dãy số Armstrong. Hôm nay Bi đọc trên internet ở địa chỉ (http://oeis.org/) mới phát hiện ra một dãy số Lucas được định nghĩa như sau:

$\displaystyle \mathrm{L_n} = \begin{cases} 2 & \text{if } n=0 \\ 1 & \text{if } n=1 \\ L_{n-1} + L_{n-2} & \text{if } n \geq 2 \end{cases}$

Bi nhờ Anh chị lập trình bằng cách điền lần lượt các số $L_0, L_1,\ldots, L_n$ ~L_0, L_1,\ldots, L_n~ vào một dãy $L$ ~L~ gồm $n + 1$ ~n + 1~ số Lucas ở trên. Sau đó in dãy ra màn hình.

Input

Dòng duy nhất chứa số nguyên dương $n$ ~n~ thỏa $1 \le n \le 80$ ~1 \le n \le 80~.

Output

In dãy gồm $n + 1$ ~n + 1~ số trên ra màn hình.

Samples

Sample Input 1

Sample Output 1

2 1 3 4 7 11

Comments

0
minhika commented on Feb. 1, 2025, 9:48 a.m.
bài này sử dụng đệ quy có nhớ. code #include <bits/stdc++.h> using namespace std;

define ll long long

include<unordered_map>

unordered_map<ll, ll> dp;

ll lu(ll n) { if (dp.count(n)) return dp[n]; if (n == 1) return 1; if (n == 0) return 2; dp[n]=lu(n - 1) + lu(n - 2); return dp[n]; }

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr);

ll n; cin >> n; for (ll i = 0;i <= n;i++) { cout << lu(i)<<' '; } return 0;

}
Link