ပြFriendsနာတွဲနေသောသူငယ်ချင်းများ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Expedia GE Healthcare Google Honeywell JP Morgan
Dynamic Programming modular ဂဏန်းသင်္ချာ

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

“ မိတ်ဖွဲ့ခြင်းပြFriendsနာများရှိသည့်သူငယ်ချင်းများ” ကသူငယ်ချင်း N များရှိသည်ဟုဖော်ပြသည်။ ထိုအသီးအသီးတစ်ခုတည်းရှိနေဆဲသို့မဟုတ်တစ် ဦး ချင်းစီကတခြားနှင့်အတူတွဲဖက်နိုင်ပါတယ်။ တစ်စုံတစ်တွဲကိုပြုလုပ်သည်နှင့်တစ်ပြိုင်နက်ထိုသူငယ်ချင်းနှစ် ဦး သည်တွဲဖက်မှုတွင်မပါ ၀ င်နိုင်တော့ပေ။ ထို့ကြောင့်သူငယ်ချင်းများနှင့်တွဲဖက်နိုင်သည့်သို့မဟုတ်တစ်ခုတည်းသောနည်းလမ်းများစုစုပေါင်းအရေအတွက်ကိုသင်ရှာဖွေရန်လိုအပ်သည်

နမူနာ

3
4

ပြFriendsနာတွဲနေသောသူငယ်ချင်းများ
သူငယ်ချင်းများအတွက်ချဉ်းကပ်မှုပြairနာတွဲဖက်မှု

အဲဒါကိုကြီးမားတဲ့ပြasနာတစ်ခုအဖြစ်စဉ်းစားမည့်အစား။ ပထမ ဦး ဆုံး N ကို ပို၍ သေးငယ်သောဖြေရှင်းရန်ကြိုးစားကြပါစို့။ N = 1 အတွက်အဖြေမှာ ၁ ဖြစ်သည်။ N = 1 အတွက်အဖြေမှာ ၂ ဖြစ်သည်။ N = 2 အတွက်တတိယသူငယ်ချင်းတစ်ယောက်တည်းနေနိုင်၏။ ဒီတော့ဒီအဖြေအတွက် N = 2. ပြproblemနာကိုအဖြေရှာသင့်သည်။ ဒီကိစ္စတွေအားလုံးမှာငါတို့တတိယသူငယ်ချင်းကတစ်ယောက်တည်းနေလို့ရတယ်။ ထို့အပြင်တွဲဖက်မှုအတွက်သူငယ်ချင်းများကိုရွေးချယ်နိုင်သည်။ ထို့ကြောင့် N-3 သူငယ်ချင်းများမှမိတ်ဆွေတစ် ဦး ကိုရွေးချယ်ပြီးအခြားသူများအနေဖြင့်တွဲဖက် / တည်းခိုနိုင်သည့်နည်းလမ်းများစွာရှိသည်။ (N-2) * F (N-1) ။ ယခုကျွန်ုပ်တို့သည်ပြforနာအတွက်ပြန်လည်ထူထောင်ရေးဖော်မြူလာကိုစဉ်းစားနိုင်သည်။

F(N)     =     F(N-1)   +   (N-1)*F(N-2)
                  ^              ^
                  |              |
Nth friend (stays single) (pairs with N-1 friends)

မှ recursive ပုံသေနည်းF ကို (N) တွက်ချက်ရာတွင် F (N-2) ကိုတွက်ချက်သည်။ ပြီးတော့ F (N-1) အတွက်လည်း F (N-2) ကိုတွက်ချက်ပါတယ်။ ဒီတော့ recomputing values ​​အစားကျနော်တို့သုံးသင့်ပါတယ် dynamic programming ကို။ ဤနေရာတွင်ကျွန်ုပ်တို့သည် F (N) တန်ဖိုးများကို 0 မှ N. အထိသိမ်းနိုင်သည်။ သို့သော်၎င်းသည်မလိုအပ်ပါ။ F (N) ၏တန်ဖိုးသည်နောက်ဆုံးတန်ဖိုး ၂ ခုဖြစ်သော F (N-1) နှင့် F (N-2) အပေါ်တွင်သာမှီတည်သည်။ ဒီတော့နောက်ဆုံးတန်ဖိုး ၂ ခုကိုသာဆက်ထိန်းထားမည်။ ကျွန်တော်တို့ကိုအာကာသကယ်တင်မည်အကြောင်း။

ကုဒ်

သူငယ်ချင်းများပြingနာအတွက် C ++ code

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

int main()
{
  // number of friends
  int n;cin>>n;

  int last = 2, lastTolast = 1;
  // here last denotes F(N-1) and lastTolast denotes F(N-2)
  // we can also use a dp array but that will only increase space complexity
  // and from the recursive formula we can see that
  // F(N) is dependent only on F(N-1) and F(N-2)
  int current;
  for(int i=3;i<=n;i++){
    current = last + (i-1)*lastTolast;
    lastTolast = last;
    last = current;
  }
  cout<<current<<endl;
}E
4
10

သူငယ်ချင်းများအတွက်ပြPနာအတွက် Java ကုဒ်

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// number of friends

    int last = 2, lastTolast = 1;
    // here last denotes F(N-1) and lastTolast denotes F(N-2)
    // we can also use a dp array but that will only increase space complexity
    // and from the recursive formula we can see that
    // F(N) is dependent only on F(N-1) and F(N-2)
    int current;
    for(int i=3;i<=n;i++){
      current = last + (i-1)*lastTolast;
      lastTolast = last;
      last = current;
    }
    System.out.println(current);
  }
}
4
10

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

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

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ငါတို့ရှာရန် N ကိုမှီသည့်တိုင်အောင်ကွင်းဆက်ကို run ရမယ်။ F (N) သည် F (N-1) နှင့် F (N-2) ပေါ်တွင်မူတည်သည်။

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

အို (၁)၊ ကျနော်တို့တွက်ချက်မှုများအတွက်သာသုံး variable တွေကိုသုံးထို့ကြောင့်လိုအပ်သောအကွာအဝေးစဉ်ဆက်မပြတ်ဖြစ်ခဲ့သည်။