සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන වන දී දී ඇති දිගෙහි අනුක්‍රමය  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇමේසන් කෝඩ්නේෂන් ෆේස්බුක් ගූගල් පේපෑල් Qualcomm
බෙදන්න සහ ජය ගන්න ගතික වැඩසටහන්කරණය

“සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන වන දී දී ඇති දිගෙහි අනුක්‍රමය” යන ගැටළුව අපට m සහ n යන පූර්ණ සංඛ්‍යා දෙකක් සපයයි. මෙතන m යනු අනුක්‍රමය තුළ පැවතිය හැකි විශාලතම සංඛ්‍යාව සහ යනු අවශ්‍ය අනුක්‍රමය තුළ තිබිය යුතු මූලද්‍රව්‍ය ගණන වේ. අනුක්‍රමය මත තවත් එක් කොන්දේසියක් පනවා ඇත, එනම් සෑම මූලද්‍රව්‍යයක්ම පෙර මූලද්‍රව්‍යයට වඩා දෙගුණයකට වඩා හෝ සමාන විය යුතුය. සියලුම කොන්දේසි සපුරා ඇති අනුපිළිවෙල ගණන සොයා ගන්න.

උදාහරණයක්  

n = 3, m = 6
4

පැහැදිලි කිරීම

ලබා දී ඇති කොන්දේසි යටතේ කළ හැකි අනුපිළිවෙල 4 ක් ඇත: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

ප්රවේශය  

සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන වූ දී දී ඇති දිගක අනුක්‍රම ගණන සොයා ගැනීමට ගැටළුව අපෙන් ඉල්ලා සිටී. ඉහළ කාල සංකීර්ණත්වයක් ඇති බොළඳ විසඳුමක් වන්නේ දිගෙහි සියලු අනුක්‍රමයන් උත්පාදනය කිරීමයි n. මූලද්‍රව්‍යයන් නැගී එන අනුපිළිවෙල අනුගමනය කළ යුතු අතර උපරිම සංඛ්‍යාව නොඉක්මවිය යුතුය m. නමුත් සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන විය යුතුය යන කාරණය අප ඇතුළත් කළහොත් වඩාත් කාර්යක්ෂම විසඳුමක් විය හැකිය. මේ අනුව අපට පුනරාවර්තන සූත්‍රයක් ලිවිය හැකිය. අපි තෝරා ගත්තොත් එවිට අපට දිග සමඟ අනුක්‍රමය සොයාගත යුතුය n-1 සහ උපරිම මූලද්‍රව්‍යය m / 2. නැතිනම් අපට දිග සමඟ අනුක්‍රමය සොයාගත යුතුය සහ උපරිම මූලද්‍රව්‍යය m-1. මෙම ප්‍රවේශය කලින් සාකච්ඡා කළ ක්‍රමයට වඩා ටිකක් කාර්යක්ෂම වුවද. මෙයද කාලය ගත වේ.

මෙයද බලන්න
උපසිරැසිය කන්දක ස්වරූපයෙන් තිබේද නැද්ද යන්න සොයා බලන්න

සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන වන දී දී ඇති දිගෙහි අනුක්‍රමයපින්

අපට පුනරාවර්තන සූත්‍රයක් ඇති අවස්ථාවන්හිදී, අපි භාවිතා කරමු ගතික වැඩසටහන්කරණය. අපි ඉහත සඳහන් දෑ සරලව මතක තබා ගනිමු පුනරාවර්තන අපි සාකච්ඡා කළ විසඳුම. මෙම අවස්ථාවේ දී, අපට ප්රාන්ත 2 ක් ඇත. පළමුවැන්න උපරිම සංඛ්‍යාව වන අතර අනෙක අනුක්‍රමයේ දිග වේ.

කේතය  

සෑම මූලද්‍රව්‍යයක්ම පෙර දෙගුණයකට වඩා වැඩි හෝ සමාන වූ දී දී ඇති දිගෙහි අනුක්‍රම සොයා ගැනීමට සී ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

ඕ (එන් * එම්), මන්ද ගැටළුව සඳහා වන රාජ්‍යයන් අනුක්‍රමයේ දිග සහ සලකා බැලිය හැකි උපරිම සංඛ්‍යාවයි. මේ අනුව කාල සංකීර්ණතාව බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් * එම්), අපි අතරමැදි ප්‍රති .ල ගබඩා කිරීම සඳහා 2D DP වගුවක් නිර්මාණය කර ඇති නිසා. අවකාශයේ සංකීර්ණතාව ද බහුපද වේ.