የጉልበት ችግር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ 24 * 7 የፈጠራ ላብራቶሪዎች አማዞን ዴ ሻው አቅርቦት የ PayPal
ተለዋዋጭ ፕሮግራም Fibonacci ሒሳብ

የችግሩ መግለጫ

“የድካም ችግር” የመጠን ፍርግርግ እንዳለዎት ይገልጻል 2 x ኤን እና የመጠን ሰድር 2 x 1 እ.ኤ.አ. ስለዚህ ፣ የተሰጠውን ፍርግርግ ለማሸብለል የሚያስችሏቸውን መንገዶች ብዛት ያግኙ።

ለምሳሌ

3
2

ማብራሪያ: የጉልበት ችግር

ለችግር ችግር አቀራረብ

እኛ እንደገና በመጠቀም በመጠቀም ይህንን ችግር መፍታት እንችላለን ፡፡ በችግሩ ውስጥ የ 2xN ፍርግርግ ንጣፍ ማድረግ ያስፈልገናል ፡፡ ስለዚህ የመጠን 2x (N-1) እና 2x (N-2) ን ፍርግርግ ለማጣራት መንገዶች ብዛት ላይ የተመሠረተ ይሆናል። እንዴት ማለት እንችላለን?

የመጀመሪያውን አምድ በፍርግርግ ከዚያም በሁለተኛ እና ወዘተ ላይ ከማሰላሰል ይልቅ ምክንያቱ ቀላል ነው። መጀመሪያ የኒን አምዱን ፣ ከዚያም N-1 እና የመሳሰሉትን ለመለጠፍ እየሞከርን ነው ፡፡ በ N th አምድ ላይ 2 × 1 ንጣፍ ብናስቀምጥ በዚህ መንገድ ያውቃሉ። ችግሩ አሁን ወደ መጠኑ 2x (N-1) የማጣሪያ ፍርግርግ ንዑስ ችግር ተለውጧል ፡፡ በተመሳሳይ ሁኔታ ሁለት 1 × 2 ንጣፎችን በ 2xN ፍርግርግ ውስጥ ካስቀመጥን ችግሩ ወደ 2x (N-2) መጠን ይቀየራል ፡፡ አሁን እነዚህን ችግሮች እንደምንም መፍታት ከቻልን መልሱን ማግኘት እንችላለን ፡፡

ሰድር እንበል [N] የ 2XN መጠንን ፍርግርግ ለመለጠፍ የሚያስችሉ መንገዶችን ብዛት ያሳያል። ከዚያ ሰድር [N] = ሰድር [N-1] + ሰድር [N-2]. በተመሳሳይ ሰድር [N-1] = ሰድር [N-2] + ሰድር [N-3]። ስለሆነም ችግሩ የተመቻቸ ንዑስ መዋቅር ያሳያል ፡፡ ውጤቱን ለጤል [N-2] ማከማቸት የተሻለ ነው ምክንያቱም ሁለት ጊዜ ጥቅም ላይ እየዋለ ነው ፡፡ ውጤቱን ካከማቸን ሁለት ጊዜ አናሰላለትም እና የጊዜ ውስብስብነቱን በከፍተኛ ሁኔታ ይቀንሰዋል ፡፡ እኛ እንጠቀማለን ተለዋዋጭ ፕሮግራም ችግሩን ለመፍታት።

የጉልበት ችግር

ኮድ

ለችግር ችግር ሲ + ኮድ

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

int main(){
  int n;cin>>n;
  // create an array to store number of ways to tile a grid of size 2xi
  int tile[n+1];
  // base case
  tile[0] = 0; tile[1] = 1;
  for(int i=2;i<=n;i++)
    tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
  cout<<tile[n];
}
3
2

የጃቫ ኮድ ለቲሊንግ ችግር

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // create an array to store number of ways to tile a grid of size 2xi
    int tile[] = new int[n+1];
    // base case
    tile[0] = 0; tile[1] = 1;
    for(int i=2;i<=n;i++)
      tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
    System.out.println(tile[n]);
  }
}
3
2

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም የማጣሪያ ፍርግርግ 2xN ችግርን ለመፍታት ፡፡ ከኤን ያነሰ መጠን ያለው የፍርግርግ ፍርግርግ መልሱን ማስላት ያስፈልግዎታል።

የቦታ ውስብስብነት

ኦ (ኤን)፣ ውጤቱን ለሁሉም ንዑስ ፕሮጄክቶች እያከማቸነው ስለሆነ ስለሆነም የሚፈለገው ቦታ መስመራዊ ነው ፡፡

ማስታወሻ በመጨረሻው እና በሁለተኛ የመጨረሻ ሁለት ተለዋዋጮችን በመጠቀም የ O (1) ቦታ እና ኦ (ኤን) ጊዜ ውስጥ ችግሩን መፍታት እንችላለን ይህም የ Tile [N-1] እና Tile [N-2] እሴቶችን በቅደም ተከተል ያከማቻል ፡፡ አሁን የአሁኑ = የመጨረሻ + ሰከንድ በኋላ እና በመቀጠልም የአለዋዋጮቹን እሴቶች ያዘምኑ። ተደጋጋሚ ቀመር ከ ‹Nth ፊቦናቺ ›ቁጥር ጋር ተመሳሳይ ነው ፡፡ ስለዚህ የፊቦናቺ ቁጥሮችን ለማግኘት ቀመርን በመጠቀም ይህንን ችግር ኦ (ሎግ ኤን) ጊዜ መፍታት ይችላሉ ፡፡