2 variable တွေကိုသုံးပြီး Fibonacci sequence ကိုပုံနှိပ်ပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ ဒေလီ အချက်အလက် လေးကစ် ခရီးသွား MAQ o9 ဖြေရှင်းနည်းများ PayU
Dynamic Programming Fibonacci အစဉ်အတိုင်းလိုက်ခြင်း

ပြProbleနာဖော်ပြချက်

“ Fibonacci sequence ကို 2 variable ကို သုံး၍ ပုံနှိပ်ခြင်း” ပြproblemနာကသင်ဟာ Fibonacci sequence ကိုပုံနှိပ်ဖို့လိုပေမယ့် variable ၂ ခုသာအသုံးပြုရန်ကန့်သတ်ထားသည်။

နမူနာ

2 variable တွေကိုသုံးပြီး Fibonacci sequence ကိုပုံနှိပ်ပါ

n = 5
0 1 1 2 3 5

ရှင်းလင်းချက်

output sequence တွင် Fibonacci series ၏ပထမအပိုင်းငါးခုရှိသည်။

ချဉ်းကပ်နည်း

ကျွန်ုပ်တို့သည် input တစ်ခုအနေဖြင့် element တစ်ခုတည်းနှင့်ကျွန်ုပ်တို့အားထောက်ပံ့ပေးထားသည်။ ၎င်းသည်နိဂုံးစဉ်ဆက်၏ထုတ်လုပ်ရန်လိုအပ်သည့်ဒြပ်စင်အရေအတွက်ကိုဖော်ပြသည်။ ဒီတော့ Fibonacci sequence ကိုပုံနှိပ်ဖို့နုံနည်းလမ်းက ပြန်လည်။ ထို့နောက်ကျွန်တော်တို့၏နံပါတ်တွက်ချက်မှုကိုတွက်ချက်ရန်ကျွန်ုပ်တို့၏ recursive function ကိုခေါ်သော loop ကိုသုံးနိုင်သည်။ ဒါပေမယ့်ဒီချဉ်းကပ်မှုကအဆအဆလိုအပ်တယ်၊ ဒါကြောင့်ကျွန်တော်တို့ဟာပိုပြီးထိရောက်တဲ့အရာတစ်ခုခုလိုအပ်တယ်။

ကျနော်တို့စဉ်းစားနိုင်ပါတယ် dynamic programming ကို/ ပြproblemနာများအတွက်မှတ်စုတို။ အဆိုပါချဉ်းကပ်surelyကန်အမှန်အချိန်ရှုပ်ထွေးလျှော့ချပါလိမ့်မယ်။ အဆိုပါအဆအချိန်ရှုပ်ထွေး linear အချိန်ရှုပ်ထွေးလျှော့ချလိမ့်မည်။ ဒါပေမယ့်ဒီချဉ်းကပ်နည်းကကျွန်တော်တို့ကို linear space ရှုပ်ထွေးမှုလိုအပ်နေတယ်။ ဒီအာကာသရှုပ်ထွေးမှုကိုထပ်မံလျှော့ချရန်လိုအပ်သည်။ ကျွန်တော်တို့လုပ်နိုင်တာကအကောင်းဆုံးဖြစ်အောင်ကြိုးစားပါ dynamic programming ကို ချဉ်းကပ်နည်း။

အကယ်၍ ကျွန်ုပ်တို့သည် Recursive formula ကိုတွေ့ရပါက F (n) = F (n-1) + F (n-2) ။ ကျွန်ုပ်တို့သည်နောက်ဆုံးဖီဘိုနာချီဂဏန်းနှစ်ခုအပေါ်တွင်သာမှီခိုနေရသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်လက်ရှိနံပါတ်ကိုရှာရန်နောက်ဆုံးဖီဘိုနာချီဂဏန်းနှစ်ခုကိုသာသိမ်းဆည်းထားနိုင်ပြီး၎င်းသည်အို (၁) အာကာသကိုရှုပ်ထွေးစေသည်။

ကုဒ်

Fibonacci sequence ကို variable 2 ခု သုံး၍ ပုံနှိပ်ရန် C ++ code

#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

Fibonacci sequence ကိုပုံ ၂ ပုံ သုံး၍ ပုံနှိပ်ရန် Java code

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ print ထုတ်ဖို့လိုအပ်တဲ့ element အရေအတွက်မများမချင်းပဲဖြတ်သွားခဲ့လို့ပဲ။ ပထမ ဦး စွာကျွန်ုပ်တို့သည်ပြproblemနာကိုပြန်လည်အသုံးချခြင်းဖြင့်ဖြေရှင်းရန်စဉ်းစားခဲ့သည်၊ သို့သော်၎င်းသည်အချိန်အတိုင်းအတာတစ်ခုဖြစ်သည်။ အဲဒီနောက်မှာငါတို့အချိန်ရှုပ်ထွေးမှုကိုလျှော့ချခဲ့သည် dynamic programming ကို။ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာပြtimeနာကို linear အချိန်မှာဖြေရှင်းနိုင်ခဲ့တယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊  ကျနော်တို့ကသာနှစ်ခု variable တွေကိုအသုံးပြုသောကြောင့်, စဉ်ဆက်မပြတ်အာကာသရှုပ်ထွေးအတွက်ပြproblemနာကိုဖြေရှင်းကြပါပြီ။