እያንዳንዱ ንጥረ ነገር ከቀዳሚው እጥፍ የበለጠ ወይም እኩል የሆነበት የተሰጠው ርዝመት ቅደም ተከተሎች


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Accenture አማዞን የኮድ ቁጥር ፌስቡክ google የ PayPal Qualcomm
አካፍል እና ድል ተለዋዋጭ ፕሮግራም

ችግሩ “እያንዳንዱ ንጥረ ነገር ከቀዳሚው ሁለት እጥፍ የበለጠ ወይም እኩል የሆነበት የተሰጠው ርዝመት ቅደም ተከተሎች” ሁለት ኢንቲጀሮችን ይሰጣል m እና n። እዚህ m በቅደም ተከተል ውስጥ ሊኖር የሚችል ትልቁ ቁጥር እና በሚፈለገው ቅደም ተከተል ውስጥ መገኘት ያለባቸው የንጥሎች ብዛት ነው። በቅደም ተከተል ላይ የተጫነ አንድ ተጨማሪ ሁኔታ አለ ፣ ይኸውም እያንዳንዱ ንጥረ ነገር ከቀዳሚው አካል ጋር ከሁለት እጥፍ የበለጠ ወይም እኩል መሆን አለበት። ሁሉም ሁኔታዎች እንደተሟሉ አጠቃላይ ቅደም ተከተሎችን ይወቁ።

ለምሳሌ

n = 3, m = 6
4

ማስረጃ

በተሰጡ ሁኔታዎች ውስጥ ሊከናወኑ የሚችሉ 4 ቅደም ተከተሎች አሉ-(1 ፣ 2 ፣ 4) ፣ (1 ፣ 2 ፣ 5) ፣ (1 ፣ 2 ፣ 6) ፣ (1 ፣ 3 ፣ 6) ፡፡

ቀረበ

ችግሩ እያንዳንዱ ንጥረ ነገር ከቀዳሚው ሁለት እጥፍ የበለጠ ወይም እኩል የሆነበት የአንድ የተወሰነ ርዝመት ጠቅላላ ቅደም ተከተሎችን እንድናገኝ ይጠይቀናል። ከፍተኛ የጊዜ ውስብስብነት ያለው የማይረባ መፍትሔ ሁሉንም የርዝመት ቅደም ተከተሎችን ማመንጨት ሊሆን ይችላል n. አባላቱ የሚወጣውን ቅደም ተከተል መከተል አለባቸው እና ከፍተኛው ቁጥር መብለጥ የለበትም m. ነገር ግን እያንዳንዱ ንጥረ ነገር ከቀዳሚው እጥፍ የበለጠ ወይም እኩል መሆን አለበት የሚለውን እውነታ ብናካትት የበለጠ ቀልጣፋ መፍትሔ ሊሆን ይችላል ፡፡ ስለዚህ እኛ አንድ recursive ቀመር መጻፍ ይችላሉ. ከመረጥን ከዚያ ቅደም ተከተሉን ከርዝመት ጋር መፈለግ አለብን n-1 እና ከፍተኛው ንጥረ ነገር m / 2. አለበለዚያ ቅደም ተከተሉን ከርዝመት ጋር መፈለግ አለብን እና ከፍተኛው ንጥረ ነገር M-1. ምንም እንኳን ይህ አካሄድ ቀደም ሲል ከተወያየው የበለጠ ውጤታማ ቢሆንም ፡፡ ይህ ደግሞ ጊዜ የሚወስድ ነው ፡፡

እያንዳንዱ ንጥረ ነገር ከቀዳሚው እጥፍ የበለጠ ወይም እኩል የሆነበት የተሰጠው ርዝመት ቅደም ተከተሎች

እኛ አንድ recursive ቀመር አለን የት ጉዳዮች ውስጥ, እኛ እንጠቀማለን ተለዋዋጭ ፕሮግራም. ከላይ ያሉትን በቀላሉ እናስታውሳቸዋለን ተደጋጋሚ የተነጋገርነው መፍትሄ በዚህ ሁኔታ እኛ 2 ግዛቶች አሉን ፡፡ የመጀመሪያው ከፍተኛው ቁጥር ሲሆን ሌላኛው ደግሞ የቅደም ተከተል ርዝመት ነው ፡፡

ኮድ

እያንዳንዱ ንጥረ ነገር ከቀዳሚው ሁለት እጥፍ የበለጠ ወይም እኩል የሆነበት የተሰጠው ርዝመት ቅደም ተከተሎችን ለማግኘት የ C ++ ኮድ

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

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

እያንዳንዱ ንጥረ ነገር ከቀዳሚው ሁለት እጥፍ የበለጠ ወይም እኩል የሆነበት የተሰጠው ርዝመት ቅደም ተከተሎችን ለማግኘት የጃቫ ኮድ

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N * M) ፣ ምክንያቱም ለችግሩ ግዛቶች የቅደም ተከተል ርዝመት እና ሊታሰብ የሚችል ከፍተኛው ቁጥር ናቸው ፡፡ ስለዚህ የጊዜ ውስብስብነት ፖሊኖሚያል ነው።

የቦታ ውስብስብነት

ኦ (N * M) ፣ ምክንያቱም መካከለኛ ውጤቶችን ለማከማቸት የ 2 ዲ ዲፒ ሰንጠረዥን ፈጥረናል ፡፡ የቦታ ውስብስብነትም እንዲሁ ፖሊኖሚያል ነው።