მოცემული სიგრძის მიმდევრობა, სადაც ყველა ელემენტი წინაზე ორჯერ მეტია ან ტოლი


Რთული ტური Easy
ხშირად ეკითხებიან Accenture Amazon CodeNation Facebook 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. მაგრამ უფრო ეფექტური გამოსავალი იქნებოდა, თუ ჩავრთეთ ის ფაქტი, რომ თითოეული ელემენტი უნდა ყოფილიყო ორზე მეტი ან ტოლი წინაზე. ამრიგად, შეგვიძლია დავწეროთ რეკურსიული ფორმულა. თუ ავირჩევთ მაშინ უნდა ვიპოვოთ თანმიმდევრობა სიგრძით n-1 და მაქსიმალური ელემენტი მ / 2. სხვაგან უნდა ვიპოვოთ თანმიმდევრობა სიგრძით და მაქსიმალური ელემენტი მე 1. მიუხედავად იმისა, რომ ეს მიდგომა ოდნავ უფრო ეფექტურია, ვიდრე ადრე განხილული. ეს ასევე შრომატევადია.

მოცემული სიგრძის მიმდევრობა, სადაც ყველა ელემენტი წინაზე ორჯერ მეტია ან ტოლი

იმ შემთხვევებში, როდესაც რეკურსიული ფორმულა გვაქვს, ვიყენებთ დინამიური პროგრამირება. ჩვენ უბრალოდ გავიხსენებთ ზემოთქმულს რეკურსიული გამოსავალი, რომელიც ჩვენ განვიხილეთ. ამ შემთხვევაში, ჩვენ გვაქვს 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

სირთულის ანალიზი

დროის სირთულე

O (N * M), რადგან პრობლემის მდგომარეობებია თანმიმდევრობის სიგრძე და მაქსიმალური რიცხვი, რომელიც შეიძლება განვიხილოთ. ამრიგად, დროის სირთულე მრავალწევრია.

სივრცის სირთულე

O (N * M), რადგან ჩვენ შევქმენით 2D DP ცხრილი შუალედური შედეგების შესანახად. სივრცის სირთულე ასევე მრავალწევრია.