Ακολουθίες δεδομένου μήκους όπου κάθε στοιχείο είναι μεγαλύτερο ή ίσο με το διπλάσιο του προηγούμενου  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Accenture αμαζόνα 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 και μέγιστο στοιχείο m / 2. Αλλιώς πρέπει να βρούμε την ακολουθία με μήκος και μέγιστο στοιχείο m-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

Κωδικός Java για να βρείτε Ακολουθίες δεδομένου μήκους όπου κάθε στοιχείο είναι μεγαλύτερο ή ίσο με το διπλάσιο του προηγούμενου

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 για την αποθήκευση των ενδιάμεσων αποτελεσμάτων. Η πολυπλοκότητα του διαστήματος είναι επίσης πολυώνυμη.