প্রদত্ত দৈর্ঘ্যের সিকোয়েন্স যেখানে প্রতিটি উপাদান পূর্বের দ্বিগুণের চেয়ে বেশি বা সমান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় Accenture মর্দানী স্ত্রীলোক কোডনেশন ফেসবুক গুগল পেপ্যাল কোয়ালকম
বিভক্ত এবং বিজয়ী ডায়নামিক প্রোগ্রামিং

সমস্যা "প্রদত্ত দৈর্ঘ্যের সিকোয়েন্স যেখানে প্রতিটি উপাদান পূর্বের দ্বিগুণের চেয়ে বেশি বা সমান" আমাদের দুটি সংখ্যার এম এবং এন সরবরাহ করে। এখানে m ক্রম এবং অস্তিত্ব থাকতে পারে যে বৃহত্তম সংখ্যা প্রয়োজনীয় অনুক্রমের মধ্যে উপস্থিত হওয়া উচিত এমন উপাদানগুলির সংখ্যা। সিকোয়েন্সে আরো একটি শর্ত আরোপ করা হয়েছে, তা হ'ল প্রতিটি উপাদান পূর্ববর্তী উপাদানটির দ্বিগুণের চেয়ে দ্বিগুণ বা তার সমান হওয়া উচিত। সমস্ত শর্ত পূরণ করা হয়েছে এমন ক্রমগুলির মোট সংখ্যা সন্ধান করুন।

উদাহরণ  

n = 3, m = 6
4

ব্যাখ্যা

এখানে 4 টি সিকোয়েন্স রয়েছে যা প্রদত্ত অবস্থার অধীনে তৈরি করা যেতে পারে: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6)

অভিগমন  

সমস্যাটি আমাদের প্রদত্ত দৈর্ঘ্যের ক্রমগুলির মোট সংখ্যা জানতে জিজ্ঞাসা করে যেখানে প্রতিটি উপাদান পূর্বের দ্বিগুণের চেয়ে বেশি বা সমান। একটি নির্লজ্জ সমাধান যা উচ্চ সময়ের জটিলতা সহ দৈর্ঘ্যের সমস্ত ক্রম উত্পন্ন করতে পারে n. উপাদানগুলি আরোহণের ক্রমটি অনুসরণ করবে এবং সর্বাধিক সংখ্যাটি অতিক্রম করবে না m. তবে আরও কার্যকর সমাধান হতে পারে যদি আমরা এই সত্যটি অন্তর্ভুক্ত করি যে প্রতিটি উপাদান আগের চেয়ে দ্বিগুণ বা তার সমান হওয়া উচিত। সুতরাং আমরা একটি পুনরাবৃত্ত সূত্র লিখতে পারেন। যদি আমরা বাছাই তারপরে আমাদের দৈর্ঘ্যের ক্রমটি সন্ধান করতে হবে এন-1 এবং সর্বাধিক উপাদান মিঃ / 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

জটিলতা বিশ্লেষণ  

সময় জটিলতা

ও (এন * এম), কারণ সমস্যার রাজ্যগুলি হল ক্রমের দৈর্ঘ্য এবং সর্বাধিক সংখ্যা যা বিবেচনা করা যেতে পারে। সুতরাং সময় জটিলতা বহুপদী।

স্পেস জটিলতা ity

ও (এন * এম), কারণ আমরা মধ্যবর্তী ফলাফলগুলি সঞ্চয় করতে একটি 2D ডিপি টেবিল তৈরি করেছি। স্থান জটিলতাও বহুপদী।