binary sequence ကိုပထမနှင့်ဒုတိယတစ်ဝက်၏တူညီသောပမာဏနှင့်အတူပင်ရေတွက်သည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် 24 * 7 တီထွင်မှု Labs အမေဇုံ Dell က GE Healthcare
Dynamic Programming

ပြproblemနာက“ binary sequences တွေကိုတောင်မှပထမနဲ့ဒုတိယတစ်ဝက်တူညီတဲ့ပမာဏအတူတူပါပဲ” ဆိုတာကသင့်ကို integer တစ်ခုပေးတယ်ဆိုတာဖော်ပြတယ်။ အရွယ်အစား 2 * n ၏ binary sequence ကိုတည်ဆောက်ရန်နည်းလမ်းများစွာကိုရှာဖွေပါ။ ပထမတစ်ဝက်နှင့်ဒုတိယတစ်ဝက်တွင် set-bits တူညီသောအရေအတွက်ရှိသည်။

binary sequence ကိုပထမနှင့်ဒုတိယတစ်ဝက်၏တူညီသောပမာဏနှင့်အတူပင်ရေတွက်သည်

မာတိကာ

နမူနာ

2
6

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

အဆိုပါ binary ပာ 0000, 1001, 1010, 0110, 0101, 1111. ထို့ကြောင့်စုစုပေါင်းအရေအတွက်က 1 ဖြစ်ပါတယ်။

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

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

ပြtheနာကိုဖြေရှင်းရန်နည်းတစ်နည်းမှာ recursion ကိုသုံးခြင်းဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်နှစ်ဖက်စလုံးတွင်တပ်ဆင်ရန်လိုအပ်သည့်အရေအတွက်ကိုခြေရာခံသည်။ ထို့ကြောင့်ဖြေရှင်းချက်သည် 3 ပြည်နယ်ဖြေရှင်းချက်ဖြစ်သည်။ ပြည်နယ်များသည်ပထမတစ်ဝက်တွင်ထည့်သွင်းရန်လိုအပ်သည့် bits အရေအတွက်၊ ဒုတိယတစ်ဝက်တွင်ကျန်ရှိနေသေးသော bits အရေအတွက်၊ ဖြတ်သန်းသွားသော bits အရေအတွက်ဖြစ်သည်။ ယေဘူယျအားဖြင့်ပြန်လည်အသုံးပြုခြင်းသည်အောက်ဖော်ပြပါကုဒ်တွင်ပြထားသည့်အတိုင်းဖြစ်သည်။

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

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

ဖြေရှင်းချက်သည်အဆင်ပြေသော်လည်းအလွန်ထိရောက်မှုမရှိပါ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးတိုးတက်စေရန်။ ငါတို့သုံးနိုင်တယ် Dynamic Programming။ သို့သော်နေဆဲအချိန်ရှုပ်ထွေးဘာလို့လဲဆိုတော့သုံးပြည်နယ်များ၏အို (N ^ 3) ဖြစ်လိမ့်မည်။

ပိုမိုကောင်းမွန်သောချဉ်းကပ်မှု

ပိုမိုကောင်းမွန်သောချဉ်းကပ်မှုသည် recursive formula နှင့်အသုံးပြုမှုကိုပြောင်းလဲရန်စဉ်းစားရန်ဖြစ်သည် dynamic programming ကို ပြtheနာကိုဖြေရှင်းဖို့။ ပထမနှင့်ဒုတိယတစ်ဝက်တွင်သတ်မှတ်ထားသော -bits အရေအတွက်ကိုရေတွက်ခြင်းအစား။ ကျနော်တို့ကခြားနားချက်ကိုအသုံးပြု။ နှစ် ဦး စလုံးပြည်နယ်များတစ်ခုတည်းပြည်နယ်မှလျှော့ချနိုင်ပါတယ်။ အခုကျွန်တော်တို့ရဲ့ recursive formula ကိုပြောင်းလဲပြီးကျွန်တော်တို့ရဲ့အချိန်ရှုပ်ထွေးမှုနှင့်နေရာရှုပ်ထွေးမှုတို့သည်ပြောင်းလဲသွားပြီ။ O (N ^ 2) အချိန်တွင် run နိုင်သောဖြေရှင်းချက်တစ်ခုကိုကျွန်ုပ်တို့ရေးနိုင်သည်။

C ++ code သည်ပထမနှင့်ဒုတိယထက်ဝက်တူညီသည့်ပေါင်းလဒ်နှင့်အတူပင် binary sequences များကိုရေတွက်နိုင်သည်

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

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}
6
924

ဂျာဗားကုဒ်သည်ပထမနှင့်ဒုတိယတစ်ဝက်တွင်တူညီသည့်ပေါင်းလဒ်နှင့်အတူပင် binary sequences များကိုပင်ရေတွက်နိုင်သည်

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}
6
924

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

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

အို (N ^ 2) ပြ^နာ၌ N ^ 2 ကွဲပြားခြားနားသောပြည်နယ်များရှိခဲ့လို့ပဲ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေး polynomial ဖြစ်ပါတယ်။

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

အို (N ^ 2) ဘာလို့လဲဆိုတော့ငါတို့က 2D DP ခင်းကျင်းမှုကိုဖန်တီးခဲ့တယ်။ အရှင်အာကာသရှုပ်ထွေးကိုလည်း polynomial ဖြစ်ပါတယ်။

အကောင်းဆုံးချဉ်းကပ်နည်း

အကောင်းဆုံးနည်းလမ်းမှာပြinနာအတွက်အဖြေကိုတွက်ချက်ရန်အတွက် Binomial Coefficients ကိုအသုံးပြုခြင်းဖြစ်သည်။ ကျနော်တို့နှစ်ခုနှစ်ခုလွတ်လပ်သောဖြစ်စဉ်းစားနိုင်ပါတယ်။ ပြီးတော့သူတို့ကအမှီအခိုကင်းတယ်၊ ကျနော်တို့ k bits ကို n bits မှသတ်မှတ်ရန်လိုသည်။ ဒါကြောင့် nCk * nCk နဲ့ညီမျှဖို့လုပ်ဖို့နည်းလမ်းများစွာကိုကျွန်ုပ်တို့ရေးနိုင်ပါတယ်။ ဒီတော့ဒီတန်ဖိုးကို k = 0 ကနေ n နှင့်မြှောက်လျှင်။ ကျနော်တို့အဖြေကိုတွေ့ပြီလိမ့်မယ်။

C ++ code သည်ပထမနှင့်ဒုတိယထက်ဝက်တူညီသည့်ပေါင်းလဒ်နှင့်အတူပင် binary sequences များကိုရေတွက်နိုင်သည်

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

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}
6
924

ဂျာဗားကုဒ်သည်ပထမနှင့်ဒုတိယတစ်ဝက်တွင်တူညီသည့်ပေါင်းလဒ်နှင့်အတူပင် binary sequences များကိုပင်ရေတွက်နိုင်သည်

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}
6
924

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

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

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ N. ထိတိုင်အောင် loop တစ်ခုတည်းကို run ခဲ့လို့ပဲ။

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

အို (၁)အာကာသရှုပ်ထွေးစဉ်ဆက်မပြတ်သောကွောငျ့, ။