Достордун жупташуусу көйгөйү


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Expedia GE Саламаттыкты сактоо Гугл ЭлЭлПи JP Morgan
Динамикалык программалоо Модулдук арифметика

Маселени билдирүү

"Достордун жупташуу көйгөйүндө" 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)

From рекурсивдик формула, 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

Достордун жупташуу көйгөйү үчүн 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), Биз эсептөө үчүн үч гана өзгөрмө колдондук, ошондуктан талап кылынган аралык туруктуу болду.