මිතුරන් යුගල කිරීමේ ගැටළුව


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් Expedia GE සෞඛ්යාරක්ෂණය ගූගල් හනිවෙල් ජේපී මෝගන්
ගතික වැඩසටහන්කරණය මොඩියුලර් අංක ගණිතය

ගැටළු ප්රකාශය

“මිතුරන් යුගල කිරීමේ ගැටලුව” පවසන්නේ මිතුරන් N සිටින බවයි. ඒ සෑම කෙනෙකුම තනිකඩව සිටීමට හෝ එකිනෙකා සමඟ යුගලනය වීමට හැකිය. නමුත් යුගලයක් සෑදූ පසු, එම මිතුරන් දෙදෙනා යුගලනය සඳහා සහභාගී විය නොහැක. එබැවින්, මිතුරන් යුගලනය කළ හැකි හෝ ඔවුන්ට තනිකඩව සිටිය හැකි මුළු ක්‍රම ගණන ඔබ සොයා ගත යුතුය

උදාහරණයක්

3
4

මිතුරන් යුගල කිරීමේ ගැටළුව
මිතුරන් යුගල කිරීමේ ගැටළුව සඳහා ප්‍රවේශය

එය විශාල ගැටලුවක් ලෙස සිතීම වෙනුවට. අපි මුලින්ම කුඩා N සඳහා විසඳීමට උත්සාහ කරමු. N = 1 සඳහා, පිළිතුර 1. N = 2 සඳහා, පිළිතුර 2. එක්කෝ මිතුරන් දෙදෙනාම තනිකඩව සිටිති, නැතහොත් ඔවුන් යුගලනය වේ. N = 3 සඳහා, තුන්වන මිතුරාට තනිකඩව සිටිය හැකිය. එබැවින් එම පිළිතුර N = 2 සමඟ ඇති ගැටලුවට පිළිතුර විය යුතුය. මේ සෑම අවස්ථාවකම අපගේ තෙවන මිතුරාට තනිකඩව සිටිය හැකිය. යුගල කිරීම සඳහා, එයට ඕනෑම මිතුරෙකු තෝරා ගත හැකිය. එබැවින් N-1 මිතුරන්ගෙන් 1 මිතුරෙකු තෝරා ගැනීම සහ අනෙක් අයට යුගලනය / රැඳී සිටීමට හැකි ක්‍රම ගණන = (N-1) * F (N-2). දැන්, ගැටළුව සඳහා පුනරාවර්තන සූත්රය ගැන අපට සිතිය හැකිය.

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

සිට පුනරාවර්තන සූත්‍රය, F (N) ගණනය කිරීමේදී අපි F (N-2) ගණනය කරන බව අපට පෙනේ. ඉන්පසු F (N-1) සඳහාද අපි F (N-2) ගණනය කරමු. එබැවින් අගයන් නැවත ගණනය කිරීම වෙනුවට අප භාවිතා කළ යුතුය ගතික වැඩසටහන්කරණය. මෙන්න, අපට සම්පූර්ණ F (N) අගයන් 0 සිට N දක්වා ගබඩා කළ හැකිය. නමුත් එය අවශ්‍ය නොවේ. F (N) හි අගය රඳා පවතින්නේ F (N-1) සහ F (N-2) මත පමණක් වන අතර එය අවසාන අගයන් 2 වේ. එබැවින් අපි අවසාන අගයන් 2 දිගටම ගබඩා කරමු. එය අපට ඉඩ ඉතිරි කරයි.

කේතය

මිතුරන් යුගල කිරීමේ ගැටළුව සඳහා C ++ කේතය

#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

මිතුරන් යුගල කිරීමේ ගැටළුව සඳහා ජාවා කේතය

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 වන තෙක් ලූපයක් ධාවනය කළ යුතුයි. F (N) F (N-1) සහ F (N-2) මත රඳා පවතින බැවින්.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි ගණනය කිරීම සඳහා විචල්යයන් තුනක් පමණක් භාවිතා කළ අතර එබැවින් අවශ්ය පරතරය නියත විය.