ພິມ ຈຳ ນວນ Fibonacci ຕາມ ລຳ ດັບ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Accenture 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 ຕົວເລກ Fibonacci ສຸດທ້າຍ.

ລະບົບວິເຄາະ

  1. ເອົາການປ້ອນຂໍ້ມູນ, ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ຈະຖືກພິມອອກ.
  2. ປະກາດຂອບເຂດຂອງຂະ ໜາດ ເທົ່າກັບຂອງການປ້ອນຂໍ້ມູນໃຫ້.
  3. ເລີ່ມດັດສະນີດັດຊະນີແຖວທີ 0 ແລະທີ 1 ດ້ວຍ 0 ແລະ 1.
  4. ພວກເຮົາເລີ່ມຕົ້ນແລ່ນ loop ຈາກ i = 2, ຈົນກ່ວາມູນຄ່າຂອງ i ແມ່ນຫນ້ອຍກ່ວາ n ໃນຂະນະທີ່ເພີ່ມມູນຄ່າຂອງ i ຕໍ່ ໜຶ່ງ.
    1. ເກັບຮັກສາການເພີ່ມສ່ວນປະກອບດັດສະນີສຸດທ້າຍແລະສຸດທ້າຍໃຫ້ກັບອົງປະກອບດັດສະນີສຸດທ້າຍ.
  5. ດຽວນີ້ພິມແຖວນີ້ຕາມ ລຳ ດັບ.

ວິທີການ

ວິທີການທີ່ໂງ່ຈ້າໃນການພິມຕົວເລກ Fibonacci ແມ່ນເຄີຍມີມາກ່ອນ ການເອີ້ນຄືນ. ແລະທຸກຄັ້ງທີ່ພວກເຮົາຖືກບອກກ່ຽວກັບການເອີ້ນຄືນ, ສິ່ງ ທຳ ອິດທີ່ພວກເຮົາຖືກບອກເລື້ອຍໆແມ່ນຕົວເລກຂອງ Fibonacci. ດັ່ງນັ້ນ, ການ ນຳ ໃຊ້ການເອີ້ນຄືນພວກເຮົາສາມາດຊອກຫາຕົວເລກ Fibonacci. ແລະຫຼັງຈາກນັ້ນພຽງແຕ່ພິມພວກມັນຕາມ ລຳ ດັບ. ແຕ່ການເຮັດສິ່ງນີ້ຮຽກຮ້ອງໃຫ້ມີການ ຄຳ ນວນທີ່ ໜັກ, ສະນັ້ນແທນທີ່ຈະເຮັດສິ່ງນັ້ນພວກເຮົາ ຈຳ ເປັນຕ້ອງຄິດຫາວິທີອື່ນ.

ວິທີການທາງເລືອກແມ່ນ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ, ບ່ອນທີ່ພວກເຮົາເກັບຮັກສາຂໍ້ມູນທີ່ຕ້ອງການເລື້ອຍໆໃນການແກ້ໄຂບັນຫາ. ພວກເຮົາຍັງໄດ້ປຶກສາຫາລືກ່ຽວກັບການຊອກຫາຕົວເລກ fibonacci ໂດຍໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ໃນເມື່ອກ່ອນ ກະທູ້.

ລະຫັດ

ລະຫັດ 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. ເນື່ອງຈາກວ່າພວກເຮົາພຽງແຕ່ດໍາເນີນການ loop ດຽວເພື່ອຊອກຫາລໍາດັບ fibonacci. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (N), ເພາະວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ອາເລເພື່ອເກັບຮັກສາຄຸນຄ່າຂອງ ຈຳ ນວນ fibonacci, ຄວາມສັບສົນໃນອະວະກາດແມ່ນເປັນເສັ້ນ.