kiểm tra số fibonacci c++
Hôm nay, chúng ta sẽ cùng nhau giải một bài tập rất thú vị: viết chương trình C++ để kiểm tra xem một số nguyên n có phải là số Fibonacci hay không. Chúng ta sẽ làm theo từng bước, bám sát kiến thức trong sách giáo khoa để bạn nào cũng có thể hiểu được nhé.
Bước 1: Tìm hiểu về dãy số Fibonacci
Trước khi lập trình, chúng ta cần hiểu rõ “số Fibonacci” là gì.
Dãy số Fibonacci là một dãy số vô hạn, bắt đầu bằng hai số 0 và 1. Các số tiếp theo trong dãy được tạo ra bằng cách cộng hai số ngay trước nó.
Chúng ta có công thức truy hồi như sau:
\( F_0 = 0 \)
\( F_1 = 1 \)
\( F_n = F_{n-1} + F_{n-2} \) với \( n > 1 \)
Vài số đầu tiên trong dãy Fibonacci là: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Bước 2: Xây dựng ý tưởng (Thuật toán)
Làm thế nào để kiểm tra một số n cho trước có nằm trong dãy số trên không?
Ý tưởng đơn giản và phù hợp nhất với kiến thức lớp 8 của chúng ta là:
1. Tạo ra các số trong dãy Fibonacci lần lượt từ đầu (bắt đầu từ 0, 1).
2. Trong khi số Fibonacci chúng ta vừa tạo ra (gọi là fn) còn nhỏ hơn số n cần kiểm tra, chúng ta sẽ tiếp tục tạo ra số Fibonacci tiếp theo.
3. Khi vòng lặp kết thúc, có hai khả năng:
* Số Fibonacci fn vừa tạo ra bằng đúng số n. Điều này có nghĩa là n là một số Fibonacci.
* Số Fibonacci fn vừa tạo ra đã lớn hơn số n. Vì dãy Fibonacci luôn tăng, nên chắc chắn n không thể là số Fibonacci được.
Bước 3: Viết chương trình C++
Bây giờ, chúng ta sẽ chuyển thuật toán trên thành mã lệnh C++ nhé.
1. Khai báo thư viện và không gian tên
Đây là thao tác quen thuộc khi bắt đầu một chương trình C++.
2. Viết hàm main() và khai báo biến
Chúng ta cần một biến n để người dùng nhập vào số cần kiểm tra. Dãy Fibonacci tăng rất nhanh, nên chúng ta nên dùng kiểu dữ liệu long long để có thể kiểm tra được những số lớn.
Chúng ta cũng cần các biến để tạo ra dãy Fibonacci. Cô sẽ dùng 3 biến: f0, f1 để lưu 2 số Fibonacci đứng trước và fn để lưu số Fibonacci tiếp theo.
f0 sẽ khởi tạo là 0.
f1 sẽ khởi tạo là 1.
3. Xử lý các trường hợp đặc biệt
Nếu người dùng nhập n = 0 hoặc n = 1 thì sao? Theo định nghĩa, đây là hai số Fibonacci đầu tiên. Ta có thể kiểm tra và kết luận ngay để chương trình hiệu quả hơn.
4. Dùng vòng lặp để tạo dãy Fibonacci
Chúng ta sẽ dùng vòng lặp while. Vòng lặp sẽ tiếp tục chạy chừng nào số Fibonacci hiện tại (fn) còn nhỏ hơn n.
Bên trong vòng lặp:
– Tính số Fibonacci tiếp theo: \( fn = f0 + f1 \)
– Cập nhật hai số đứng trước cho lần lặp kế tiếp: f0 sẽ bằng f1 cũ, và f1 sẽ bằng fn mới tính được.
5. Kiểm tra kết quả và xuất ra màn hình
Sau khi vòng lặp kết thúc, ta chỉ cần so sánh fn với n.
– Nếu \( fn == n \), ta kết luận n là số Fibonacci.
– Ngược lại, ta kết luận n không phải là số Fibonacci.
Mã nguồn C++ hoàn chỉnh
Dưới đây là chương trình hoàn chỉnh có chú thích rõ ràng từng dòng để các em dễ theo dõi.
cpp
#include
using namespace std;
int main() {
// Bước 1: Khai báo biến
// Dùng long long để chứa được các số Fibonacci lớn
long long n;
// Bước 2: Nhập dữ liệu từ người dùng
cout << "Nhap vao so nguyen n can kiem tra: ";
cin >> n;
// Bước 3: Xử lý các trường hợp đặc biệt (n=0 hoặc n=1)
if (n == 0 || n == 1) {
cout << n << " la so Fibonacci." << endl;
return 0; // Kết thúc chương trình vì đã có kết quả
}
// Bước 4: Tạo dãy Fibonacci để kiểm tra
long long f0 = 0;
long long f1 = 1;
long long fn = 1; // Số Fibonacci hiện tại, bắt đầu bằng 1
// Vòng lặp sẽ tạo ra các số Fibonacci cho đến khi bằng hoặc vượt qua n
while (fn < n) {
// Tính số Fibonacci tiếp theo
fn = f0 + f1;
// Cập nhật 2 số hạng trước đó cho lần lặp tiếp theo
f0 = f1;
f1 = fn;
}
// Bước 5: Kiểm tra kết quả và xuất ra màn hình
if (fn == n) {
// Nếu số Fibonacci cuối cùng tạo ra bằng n
cout << n << " la so Fibonacci." << endl;
} else {
// Nếu số Fibonacci cuối cùng tạo ra lớn hơn n
cout << n << " khong phai la so Fibonacci." << endl;
}
return 0;
}
Ví dụ minh họa
Trường hợp 1: Kiểm tra n = 8
1. Chương trình bắt đầu với \( f0 = 0, f1 = 1, fn = 1 \).
2. Vòng lặp \(while (fn < 8)\):
- Lần 1: \( fn = 0 + 1 = 1 \). \( f0=1, f1=1 \). \(fn\) vẫn nhỏ hơn 8.
- Lần 2: \( fn = 1 + 1 = 2 \). \( f0=1, f1=2 \). \(fn\) vẫn nhỏ hơn 8.
- Lần 3: \( fn = 1 + 2 = 3 \). \( f0=2, f1=3 \). \(fn\) vẫn nhỏ hơn 8.
- Lần 4: \( fn = 2 + 3 = 5 \). \( f0=3, f1=5 \). \(fn\) vẫn nhỏ hơn 8.
- Lần 5: \( fn = 3 + 5 = 8 \). \( f0=5, f1=8 \). Bây giờ \(fn\) không còn nhỏ hơn 8. Vòng lặp dừng lại.
3. Sau vòng lặp, ta kiểm tra \(if (fn == n)\), tức là \(if (8 == 8)\). Điều kiện này đúng.
4. Kết quả: "8 la so Fibonacci."
Trường hợp 2: Kiểm tra n = 10
1. Tương tự như trên, vòng lặp sẽ chạy đến khi \( fn = 8 \).
2. Lần lặp tiếp theo: \( fn = 5 + 8 = 13 \). \( f0=8, f1=13 \). Bây giờ \(fn\) (13) không còn nhỏ hơn \(n\) (10). Vòng lặp dừng lại.
3. Sau vòng lặp, ta kiểm tra \(if (fn == n)\), tức là \(if (13 == 10)\). Điều kiện này sai.
4. Chương trình thực hiện lệnh \(else\).
5. Kết quả: “10 khong phai la so Fibonacci.”
Hy vọng với cách giải thích chi tiết này, các em đã hiểu rõ cách giải bài tập. Đây là một bài toán lập trình cơ bản và rất hay để rèn luyện tư duy logic và kỹ năng sử dụng vòng lặp.
Chúc các em học tốt! Nếu có thắc mắc, đừng ngần ngại hỏi cô nhé
#include <bits/stdc++.h>
using namespace std;
bool check(long long n) {
long long f2 = 1;
long long f1 = 1;
long long fn = 1;
long long i;
if (n == 1|| n == 2) {
return 1;
} else {
for (i = 2; i < n; i++) {
f1= f2;
f2 = fn;
fn = f2 + f1;
if(n==fn){
return 1;
}
}
}
return 0;
}
int main() {
long long n,i;
cin>>n;
if(check(n)==1){
cout<<“YES”;
}
else{
cout<<“NO”;
}
}
\(text{CODE}\)
#include <bits/stdc++.h>
using namespace std;
bool kt(int num) {
int sqrtNum = sqrt(num);
return sqrtNum * sqrtNum == num;
}
bool Fibonacci(int num) {
return kt(5*num*num+4)||kt(5*num*num-4);
}
int main() {
int num;
cin >> num;
if (Fibonacci(num))
cout << num << ” là một số Fibonacci.” << endl;
else
cout << num << ” không phải là một số Fibonacci.” << endl;
return 0;
}