የአጥር አልጎሪዝም ሥዕል


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ የኮድ ቁጥር ፌስቡክ google ኢላማዊ ጂፒ ሞርጋን ሞርጋን ስታንሊ
ሰልፍ ተለዋዋጭ ፕሮግራም ሊት ኮድ

የችግሩ መግለጫ

“የስዕል አጥር አልጎሪዝም” አንዳንድ ልጥፎችን (አንዳንድ የእንጨት ቁርጥራጮችን ወይም ሌሎች ቁርጥራጮችን) እና አንዳንድ ቀለሞችን የያዘ አጥር ይሰጥዎታል ይላል። አጥሩን ለመሳል የሚረዱባቸውን መንገዶች ብዛት ይፈልጉ ፣ ቢበዛ በአጠገብ ያሉ አጥር ሁለት ብቻ ተመሳሳይ ቀለም ይኖረዋል ፡፡ ይህ ቁጥር ትልቅ ሊሆን ስለሚችል መልሱን ሞዱሎ 2 ይመልሱ ፡፡

ለምሳሌ

የአጥር አልጎሪዝም ሥዕል

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) ቢበዛ በአጠገብ ያሉ 2 ልጥፎች ብቻ ተመሳሳይ ቀለም ሊኖራቸው የሚችል እና ለ F (n-2) ተመሳሳይ የሆነባቸውን መንገዶች እንደሚወክል እናውቃለን ፡፡ አሁን (n-1) ኛ እና nth አቋም ላይ አንድ አይነት ቀለም ያላቸውን ልጥፎችን ከቀለም ፣ የ (n-1) ኛ ልጥፍ ልክ እንደ (n-2) nd ልጥፍ ተመሳሳይ ቀለም ሊኖረው እንደማይገባ እንመለከታለን ፡፡ ይህ እሴት F (n-2) ን ተጠቅሷል ፡፡ ስለዚህ የኛ ልጥፍ ካለፈው ልጥፍ ጋር አንድ አይነት ቀለም ያለውበትን ጉዳይ ተመልክተናል ፡፡ እንዲሁም የአሁኑ ልጥፍ እና የመጨረሻው ልኡክ ጽሁፍ አንድ አይነት ቀለም ሊኖራቸው የማይገባባቸውን መንገዶች ማገናዘብ አለብን ፡፡ ይህ እሴት F (n-1) ን ተጠቅሷል ፡፡ አሁን የ nth ልጥፍን ለመቀባት (k-1) መንገዶች አሉን ፡፡ ስለሆነም አጠቃላይ የመንገዶቹ ብዛት ከ (F (n-1) + F (n-2)) * (k-1) ጋር እኩል ነው።

ኮድ

የ 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

የጃቫ ኮድ ለሥዕል አጥር አልጎሪዝም

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ከአልጎሪዝም እንደምናየው ከ n ጋር እኩል እስከሆንኩ ድረስ የሚሠራውን አንድ ነጠላ ዑደት ተጠቅመናል ፡፡ ስለዚህ n ድግግሞሾችን ማድረግ ፣ ይህ ማለት የመስመር ጊዜ ውስብስብነት አለብን ማለት ነው።

የቦታ ውስብስብነት

ኦ (1) ፣  የዲ ፒ ድርድር ከማድረግ ይልቅ የማይለዋወጥ ቁጥሮችን እንደተጠቀምን ፡፡ ይህ አካሄድ የበለጠ አዋጪ ነው ለችግሩ መፍትሄው በመጨረሻዎቹ ሁለት ትናንሽ ችግሮች ላይ ብቻ ጥገኛ ነው ፡፡