Праблема спалучэння сяброў  


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка Expedia GE Healthcare Google Honeywell JP Morgan
Дынамічнае праграмаванне Модульная арыфметыка

Пастаноўка праблемы  

У "Праблеме спалучэння сяброў" гаворыцца, што ёсць N сяброў. І кожны з іх можа заставацца адзінокім альбо спалучацца паміж сабой. Але як толькі пара створана, гэтыя два сябры не могуць удзельнічаць у спалучэнні. Такім чынам, вам трэба знайсці агульную колькасць спосабаў, якім можна спалучаць сяброў альбо заставацца адзінокімі

Прыклад  

3
4

Праблема спалучэння сяброўPin
Праблема спалучэння сяброў  

Замест таго, каб думаць пра гэта як пра вялікую праблему. Давайце спачатку паспрабуем вырашыць для меншага N. Для N = 1 адказ 1. Для N = 2 адказ 2. Ці альбо сябры застаюцца адзінокімі, альбо яны спарваюцца. Пры N = 3 любы трэці сябар можа застацца адзінокім. Такім чынам, за гэты адказ павінен быць адказ на праблему з N = 2. Таму што ва ўсіх гэтых выпадках наш трэці сябар можа застацца адзінокім. А для спалучэння яго можа выбраць любы з сяброў. Такім чынам, выбіраючы 1 сябра з сяброў N-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

Аналіз складанасці  

Складанасць часу

O (N), таму што мы павінны запусціць цыкл да N, каб знайсці яго. Паколькі F (N) залежыць ад F (N-1) і F (N-2).

Касмічная складанасць

O (1), мы выкарыстоўвалі толькі тры зменныя для вылічэння, і, такім чынам, патрэбны інтэрвал быў пастаянным.