Сүрөт тосмо алгоритми


Кыйынчылык деңгээли катуу
Көп суралган CodeNation Facebook Гугл Текшерүү JP Morgan Морган Стэнли
согуштук тизме Динамикалык программалоо LeetCode

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

"Сүрөттүн тосмолорунун алгоритминде" сизге бир нече тирөөч (айрым жыгач же башка бөлүктөр) жана бир нече түстүү тосмо берилгени айтылат. Тосмону сырдоонун бир нече ыкмасын билиңиз, эң көп дегенде жанындагы 2 тосмо бирдей түстө болот. Бул сан чоң болушу мүмкүн болгондуктан, жооп модулуна 1000000007 кайтарыңыз.

мисал

Сүрөт тосмо алгоритми

Number of posts/wooden sticks = 2
Number of colors = 2
4

түшүндүрүү
Эки билдирүүнү тең 2 түстө ар кандай түскө боёсоңуз болот. Ал эми сизде постторду бирдей түскө боёонун 2 жолу бар. Ошентип, сизде 4 жол бар.

Тосмо алгоритмин сүрөт тартуу ыкмасы

Сөздү жөнөкөй эмес мамиледен баштасак. Бизде n билдирүү жана k түстөр бар деп берилет. Эми биз постторду боёонун жолдорунун санын табышыбыз керек, бирдей түстөгү эң көп дегенде 2 жанаша пост бар. Эгерде биз болсо, бир эле ишенчээк мамиле болушу мүмкүн бардык ырааттуулуктарды жаратуу ар бир билдирүү менен алынган түстү белгилөө. Бирок бул ыкма эффективдүү эмес жана убакыттын өтүшүнө алып келет.

Ошентип, мындан мыкты ыкма кандай болушу мүмкүн? Бир жакындоо Эгер биз көйгөйдү кичинекей көйгөйлөргө бөлсөк болот. Билдирүүлөрдүн саны үчүн жоопту билип алалы = n-2 жана n-1. Бул маанилерди тиешелүүлүгүнө жараша F (n-2) жана F (n-1) колдонуп белгилейли. Ошентип, биз F (n-1) эң көп дегенде эки жанаша посттун бирдей түскө ээ болушунун санын жана F (n-2) үчүн бирдей экендигин билдирет. Эми биз (n-2) th жана n позицияларындагы постторду бирдей түс менен боёп алсак, (n-1) th post (n-1) ndpost менен бирдей түстө болбошу керек деп эсептейбиз. Бул маани F (n-2) аркылуу белгиленет. Ошентип, биз nth билдирүүбүз акыркы билдирүү менен бирдей түстө болгон ишти карадык. Ошондой эле, учурдагы билдирүү менен акыркы билдирүү бирдей түстө болбошу керек болгон жолдорду карап чыгышыбыз керек. Бул маани F (n-2) аркылуу белгиленет. Эми n-билдирүүнү боёктун (k-1) жолдору бар. Ошентип жолдордун жалпы саны барабар (F (n-1) + F (n-1)) * (k-2).

коду

Сүрөт тосмо алгоритми үчүн C ++ коду

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

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

Сүрөттөө тосмо алгоритми үчүн Java коду

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

Комплекстик анализ

Убакыттын татаалдыгы

O (N), алгоритмден көрүнүп тургандай. I nге барабар болгончо иштей турган бир циклди колдондук. Ошентип, н кайталоолорду жасоо, бул бизде убакыттын сызыктуу татаалдыгы бар экендигин билдирет.

Космостун татаалдыгы

O (1),  анткени биз DP массивин жасоонун ордуна өзгөрүлмө көлөмдүн туруктуу санын колдондук. Бул ыкма кыйла пайдалуу, себеби көйгөйдү чечүү акыркы эки көйгөйдөн гана көз каранды.