Fibonacci là dãy số kinh điển trong toán học được tìm thấy cách đây hơn 800 năm. Đến nay các nhà khoa học phát hiện nhiều trùng hợp thú vị về dãy số này trong tự nhiên. Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 1 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó.

Dã số Fibonacci 1, 1, 2, 3, 5, 8, 13, 21….

Thuật toán về dãy số Fibonacci thường được dùng trong giảng dạy và kiểm tra kỹ năng về thuật toán. Do vậy, nắm rõ về thuật toán này là một lợi thế của bạn.

Yêu cầu

Viết chương trình nhập vào một số n và in ra n số đầu tiên của dãy fibonacci.

Về lý thuyết

  • Dãy fibonacci bắt đầu với hai phần tử f(1)=1, f(2)=1
  • Số tiếp theo sẽ bằng tổng của hai số trước đó f(n) = f(n-1) + f(n-2)

Bài toán này có thể giải bằng phương pháp đệ qui, nhưng ở đây chúng ta sẽ giải bằng vòng lặp.

Phân tích tìm cách giải

  • Đầu vào: cần nhập giá trị cho n, khởi tại biến f1=1, f2=1
  • Đầu ra: In ra dãy số fibonacci với n chữ số đầu tiên

Các bước thực hiện:
Nhập giá trị cho biến n
Kiểm tra n
   Nếu n <=2
      Thông báo nhập lại giá trị lớn hơn 2
   Nếu n >2
      In f1 và f2
      Cho biến i chạy từ 3 đến n
         Tính f=f1+f2
         In f ra
         Gán f1=f2
         Gán f2=f

Cách biểu diễn thuật toán về dãy số Fibonacci

Trong trường hợp này, tôi sử dụng ngôn ngữ giả.

Declare int n, i, f, f1=1,f2=1

Input n

If n<=2 then

   Print ‘Lỗi, n phải lớn hơn 2. Vui lòng nhập lại’

Else

   Print f1,f2

   Loop i=3 to n

      f= f1+f2

      Print f

      f1=f2

      f2=f

Kỹ thuật Dry Run

Kết quả Dry Run khi n=8:

Dry Run-Fibonacci

Bài tiếp: Các thuật toán về vòng lặp lồng nhau

Bài trước: Thuật toán tính tổng một dãy số

Comments



Blog này nhằm mục đích chia sẻ các kiến thức thực tế liên quan đến ngành công nghiệp phần mềm nhằm giúp các bạn trẻ định hướng tốt hơn trong việc chọn lựa nghề nghiệp của mình. Chúng tôi rất mong nhận được sự đóng góp, chia sẽ của các anh chị có kinh nghiệm cũng như các bạn trẻ.

 Học thuật toán

Hướng dẫn học thuật toán

 Thiết kế Cơ sở dữ liệu

Hướng dẫn thiết kế cơ sở dữ liệu.

 Học lập trình

Hướng dẫn dành cho người mới học lập trình.

 Hot or Not

Phân tích xu hướng công nghệ lập trình

 Phân tích thiết kế hệ thống

Phân tích và thiết kế hệ thống phần mềm

 Scrum Methodology

Bàn về mô hình phát triển phần mềm.