พิมพ์หมายเลขฟีโบนักชีตามลำดับย้อนกลับ  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน แอคเซนเจอร์ MAQ โซลูชัน o9 UHG Optum
การเขียนโปรแกรมแบบไดนามิก ลำดับ

คำชี้แจงปัญหา  

ระบุหมายเลข n ให้พิมพ์หมายเลข fibonacci ตามลำดับย้อนกลับ

ตัวอย่าง  

n = 5
3 2 1 1 0

คำอธิบาย: หมายเลข Fibonacci คือ 0, 1, 1, 2, 3 ตามลำดับ แต่เนื่องจากเราจำเป็นต้องพิมพ์ในลำดับย้อนกลับ

n = 7
8 5 3 2 1 1 0

พิมพ์หมายเลขฟีโบนักชีตามลำดับย้อนกลับหมุด  

ตัวเลขแสดงให้เห็นว่าตัวเลข Fibonacci ขึ้นอยู่กับผลลัพธ์ของตัวเลข Fibonacci 2 ตัวสุดท้ายอย่างไร

ขั้นตอนวิธี  

  1. ป้อนข้อมูลจำนวนองค์ประกอบที่จะพิมพ์
  2. ประกาศอาร์เรย์ที่มีขนาดเท่ากับอินพุตที่กำหนด
  3. เริ่มต้นดัชนีอาร์เรย์ที่ 0 และ 1 ด้วย 0 และ 1
  4. เราเริ่มรันลูปจาก i = 2 จนกระทั่งค่าของ i น้อยกว่า n ในขณะที่เพิ่มค่าของ i ทีละหนึ่ง
    1. เก็บส่วนที่เพิ่มขององค์ประกอบดัชนีสุดท้ายและองค์ประกอบดัชนีสุดท้ายถึงสุดท้าย
  5. ตอนนี้พิมพ์อาร์เรย์นี้ในลำดับย้อนกลับ

เข้าใกล้  

วิธีการที่ไร้เดียงสาในการพิมพ์ตัวเลข Fibonacci นั้นมีมาโดยตลอด การเรียกซ้ำ. และเมื่อใดก็ตามที่เราได้รับแจ้งเกี่ยวกับการเรียกซ้ำสิ่งแรกที่เรามักจะได้รับแจ้งคือตัวเลข Fibonacci ดังนั้นการใช้การเรียกซ้ำเราสามารถค้นหาหมายเลขฟีโบนักชี จากนั้นก็พิมพ์ตามลำดับย้อนกลับ แต่การทำเช่นนี้ต้องใช้การคำนวณอย่างหนักดังนั้นแทนที่จะทำเช่นนั้นเราต้องคิดหาแนวทางอื่น

แนวทางอื่นคือ การเขียนโปรแกรมแบบไดนามิกซึ่งเราจัดเก็บข้อมูลซึ่งจำเป็นต้องใช้บ่อยกว่าในการแก้ปัญหา นอกจากนี้เรายังได้หารือเกี่ยวกับการค้นหาหมายเลข fibonacci โดยใช้ การเขียนโปรแกรมแบบไดนามิก ในก่อนหน้า เสา.

ดูสิ่งนี้ด้วย
ขนาดของ Subarray ที่มีผลรวมสูงสุด

รหัส  

รหัส C ++ เพื่อพิมพ์หมายเลข fibonacci ในลำดับย้อนกลับ

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;cin>>n;
    int fib[n];
    if(n>=1)
    fib[0] = 0;
    if(n>=2)
    fib[1] = 1;
    for(int i=2;i<n;i++)
        fib[i] = fib[i-1] + fib[i-2];
    for(int i=n-1;i>=0;i--)
        cout<<fib[i]<<" ";
}
4
2 1 1 0

รหัส Java เพื่อพิมพ์หมายเลข fibonacci ในลำดับย้อนกลับ

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int fib[] = new int[n];
    	if(n>=0)
    		fib[0] = 0;
    	if(n>=1)
    		fib[1] = 1;
    	for(int i=2;i<n;i++)
    		fib[i] = fib[i-1] + fib[i-2];
    	for(int i=n-1;i>=0;i--)
    		System.out.print(fib[i]+" ");
  	}
}
4
2 1 1 0

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

O (N) เวลานี้จำเป็นต้องใช้ในการคำนวณตัวเลข fibonacci เพราะเราเรียกใช้ลูปเดียวเพื่อค้นหาลำดับฟีโบนักชี ความซับซ้อนของเวลาเป็นเส้นตรง

ความซับซ้อนของอวกาศ

O (N) เนื่องจากเราใช้อาร์เรย์เพื่อเก็บค่าของตัวเลข fibonacci ความซับซ้อนของปริภูมิจึงเป็นเส้นตรง