พิมพ์ลำดับฟีโบนักชีโดยใช้ 2 ตัวแปร


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน เดลี ข้อเท็จจริง โฟร์ไคต์ ธุดงค์ MAQ โซลูชัน o9 payu
การเขียนโปรแกรมแบบไดนามิก ฟีโบนักชี ลำดับ

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

ปัญหา“ พิมพ์ลำดับฟีโบนักชีโดยใช้ 2 ตัวแปร” ระบุว่าคุณต้องพิมพ์ลำดับฟีโบนักชี แต่มีข้อ จำกัด ในการใช้เพียง 2 ตัวแปร

ตัวอย่าง

พิมพ์ลำดับฟีโบนักชีโดยใช้ 2 ตัวแปร

n = 5
0 1 1 2 3 5

คำอธิบาย

ลำดับเอาต์พุตมีห้าองค์ประกอบแรกของอนุกรมฟีโบนักชี

เข้าใกล้

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

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

ถ้าเราเห็นสูตรวนซ้ำ F (n) = F (n-1) + F (n-2) เราขึ้นอยู่กับตัวเลข Fibonacci สองตัวสุดท้ายเท่านั้น ดังนั้นเราจึงสามารถจัดเก็บตัวเลข Fibonacci สองตัวสุดท้ายเพื่อค้นหาจำนวนปัจจุบันและทำให้อัลกอริทึมทำงานในความซับซ้อนของพื้นที่ O (1)

รหัส

รหัส C ++ เพื่อพิมพ์ลำดับฟีโบนักชีโดยใช้ 2 ตัวแปร

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

รหัส Java เพื่อพิมพ์ลำดับฟีโบนักชีโดยใช้ 2 ตัวแปร

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

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

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

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

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

O (1),  เราได้แก้ปัญหาด้วยความซับซ้อนของพื้นที่คงที่เพราะเราใช้ตัวแปรเพียงสองตัว