Để viết thuật toán đệ quy để tính số Fibonacci thứ nn trong C#, chúng ta cần hiểu rằng dãy Fibonacci là một chuỗi số trong đó mỗi số là tổng của hai số trước đó. Công thức toán học của dãy Fibonacci là:
F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)
với điều kiện ban đầu là:
F(0)=0F(0) = 0 F(1)=1F(1) = 1
Dưới đây là mã nguồn C# cho thuật toán đệ quy để tính số Fibonacci thứ nn:
using System;
class FibonacciRecursive
{
// Hàm đệ quy để tính số Fibonacci thứ n
public static int Fibonacci(int n)
{
if (n <= 0)
{
return 0; // Trường hợp cơ bản: F(0) = 0
}
else if (n == 1)
{
return 1; // Trường hợp cơ bản: F(1) = 1
}
else
{
return Fibonacci(n - 1) + Fibonacci(n - 2); // Gọi đệ quy cho F(n-1) và F(n-2)
}
}
static void Main(string[] args)
{
Console.WriteLine("Nhập số n để tính số Fibonacci thứ n:");
int n = int.Parse(Console.ReadLine());
int result = Fibonacci(n);
Console.WriteLine($"Số Fibonacci thứ {n} là: {result}");
}
}
Giải thích chi tiết:
-
Fibonacci Method:
- Đây là hàm đệ quy để tính số Fibonacci thứ nn.
- Tham số:
n: Số thứ tự trong dãy Fibonacci.
- Trường hợp cơ bản:
- Nếu n≤0n \leq 0, trả về 0 (vì F(0)=0F(0) = 0).
- Nếu n=1n = 1, trả về 1 (vì F(1)=1F(1) = 1).
- Trường hợp đệ quy:
- Nếu n>1n > 1, hàm sẽ gọi lại chính nó với các tham số n−1n-1 và n−2n-2, sau đó cộng kết quả lại để tính F(n)F(n).
-
Main Method:
- Đầu vào từ người dùng: Chương trình yêu cầu người dùng nhập giá trị nn.
- Chuyển đổi đầu vào thành số nguyên và gọi hàm
Fibonacciđể tính số Fibonacci thứ nn. - In ra kết quả số Fibonacci thứ nn.
Ưu điểm của Phương pháp Đệ quy:
- Mã nguồn đơn giản, dễ hiểu và dễ viết.
- Phù hợp cho các bài toán nhỏ hoặc khi cần thể hiện nguyên lý đệ quy.
Nhược điểm của Phương pháp Đệ quy:
- Độ phức tạp thời gian là O(2n)O(2^n), rất chậm cho các giá trị lớn của nn do tính toán lặp lại nhiều lần.
- Có thể gây ra tràn ngăn xếp (stack overflow) nếu giá trị nn quá lớn do số lần gọi hàm đệ quy quá nhiều.
Cải tiến:
Để cải thiện hiệu suất, bạn có thể sử dụng phương pháp ghi nhớ (memoization) hoặc phương pháp lặp (iterative) để tính số Fibonacci.
Phương pháp ghi nhớ (memoization):
using System;
using System.Collections.Generic;
class FibonacciMemoization
{
private static Dictionary<int, int> memo = new Dictionary<int, int>();
public static int Fibonacci(int n)
{
if (n <= 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else if (memo.ContainsKey(n))
{
return memo[n];
}
else
{
int result = Fibonacci(n - 1) + Fibonacci(n - 2);
memo[n] = result;
return result;
}
}
static void Main(string[] args)
{
Console.WriteLine("Nhập số n để tính số Fibonacci thứ n:");
int n = int.Parse(Console.ReadLine());
int result = Fibonacci(n);
Console.WriteLine($"Số Fibonacci thứ {n} là: {result}");
}
}
Phương pháp lặp (iterative):
using System;
class FibonacciIterative
{
public static int Fibonacci(int n)
{
if (n <= 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
}
static void Main(string[] args)
{
Console.WriteLine("Nhập số n để tính số Fibonacci thứ n:");
int n = int.Parse(Console.ReadLine());
int result = Fibonacci(n);
Console.WriteLine($"Số Fibonacci thứ {n} là: {result}");
}
}
Giải thích về Phương pháp Ghi nhớ và Lặp:
- Phương pháp ghi nhớ (memoization): Sử dụng một từ điển để lưu trữ kết quả đã tính toán của các giá trị Fibonacci, tránh tính toán lặp lại, giảm độ phức tạp thời gian xuống O(n)O(n).
- Phương pháp lặp (iterative): Sử dụng vòng lặp để tính số Fibonacci, giảm độ phức tạp thời gian xuống O(n)O(n) và sử dụng không gian O(1)O(1).
Bạn có thể sử dụng các phương pháp này tùy thuộc vào yêu cầu và kích thước của đầu vào.
Comments