Ընկերներ զուգավորման խնդիր  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Expedia GE Healthcare Google HONEYWELL JP Morgan
Դինամիկ ծրագրավորում Մոդուլային թվաբանություն

Խնդիրի հայտարարություն  

«Ընկերների զուգավորման խնդիրը» նշում է, որ կան N ընկերներ: Եվ նրանցից յուրաքանչյուրը կարող է մնալ միայնակ կամ զուգակցվել միմյանց հետ: Բայց երբ զույգը կազմվի, այդ երկու ընկերները չեն կարող մասնակցել զուգակցմանը: Այսպիսով, դուք պետք է գտնեք այն ուղիների ընդհանուր քանակը, որով ընկերները կարող են զուգակցվել կամ նրանք կարող են մնալ միայնակ

Օրինակ  

3
4

Ընկերներ զուգավորման խնդիրPin
Մոտեցում ընկերների զուգավորման խնդրին  

Փոխանակ այդ մասին մտածել որպես մեծ խնդիր: Նախ փորձենք լուծել փոքր 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 արժեքները: Պատճառը, որը կփրկի մեզ տարածություն:

Տես նաեւ,
Moser-de Bruijn հաջորդականությունը

Կոդ  

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

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

Բարդության վերլուծություն  

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պետք է մի օղակ գործարկենք մինչև N- ն այն գտնելու համար: Քանի որ F (N) կախված է F (N-1) և F (N-2) կախվածությունից:

Տիեզերական բարդություն

O (1), մենք հաշվարկի համար օգտագործեցինք ընդամենը երեք փոփոխական, ուստի պահանջվող տարածությունը հաստատուն էր: