Ακολουθία Newman-Conway


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

Δήλωση προβλήματος

Το πρόβλημα "Newman-Conway Sequence" δηλώνει ότι σας δίνεται ένας ακέραιος αριθμός εισόδου "n". Στη συνέχεια, πρέπει να εκτυπώσετε το πρώτο ένατο στοιχείο της ακολουθίας Newman-Conway.

Παράδειγμα

n = 6
4
n = 10
6

εξήγηση

Δεδομένου ότι τα στοιχεία εξόδου αντιπροσωπεύουν το έκτο και δέκατο στοιχείο της ακολουθίας Newman-Conway. Η έξοδος είναι απολύτως σωστή.

Προσέγγιση για να βρείτε την ακολουθία Newman-Conway

Η ακολουθία Newman-Conway είναι μια ακολουθία της οποίας κάθε όρος ικανοποιεί την ακόλουθη σχέση υποτροπής.
P (1) = P (2) = 1

Ακολουθία Newman-Conway

 

Τώρα πρέπει να εκτυπώσουμε τον ένατο αριθμό από την ακολουθία. Μπορεί να υπάρχουν δύο μέθοδοι επειδή κάθε στοιχείο της ακολουθίας εξαρτάται από τα στοιχεία που δημιουργήθηκαν προηγουμένως. Έτσι, ένας από τους τρόπους είναι η χρήση αναδρομή αλλά αυτή η μέθοδος είναι αναποτελεσματική. Επειδή θα λύσουμε για κάθε στοιχείο πολλές φορές, καθώς συνεχίζουμε να υπολογίζουμε για υψηλότερους όρους στη σειρά. Επομένως, πρέπει να εκτελέσουμε έναν πολύ μεγαλύτερο αριθμό υπολογισμών. Έτσι, για να επιλύσετε αυτό το πρόβλημα του εκ νέου υπολογισμού. Μπορούμε να χρησιμοποιήσουμε Δυναμικός προγραμματισμός που μπορεί να βελτιώσει σε μεγάλο βαθμό την αποτελεσματικότητα του αλγορίθμου. Επί του παρόντος, ο αναδρομικός αλγόριθμος χρειάζεται εκθετική πολυπλοκότητα χρόνου. Μπορούμε να το μειώσουμε σε μια γραμμική λύση επειδή υπάρχει μόνο μία κατάσταση.

Έτσι, στο δυναμικό προγραμματισμό λύση. Θα δημιουργήσουμε έναν πίνακα που θα αποθηκεύει τα στοιχεία που έρχονται πριν από το ένατο στοιχείο. Αυτό είναι όλα τα στοιχεία από το πρώτο στοιχείο έως (n-1) το στοιχείο. Στη συνέχεια, χρησιμοποιώντας αυτά τα προ-υπολογισμένα θα βρούμε το nth στοιχείο μας. Δεδομένου ότι έχουμε όλους τους αριθμούς που πρέπει να υπολογίζονται πριν από τον ένατο αριθμό. Μπορούμε εύκολα να χρησιμοποιήσουμε αυτές τις τιμές αντί να υπολογίζουμε τα απαιτούμενα στοιχεία ξανά και ξανά. Αυτή η τεχνική χρησιμοποιείται για τη μείωση της πολυπλοκότητας του χρόνου

Κώδικας

Κωδικός C ++ για να βρείτε το nth στοιχείο Newman-Conway Sequence

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

int main(){
  // element to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  cout<<dp[n];
}
6
4

Κωδικός Java για να βρείτε το nth στοιχείο Newman-Conway Sequence

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
    System.out.print(dp[n]);
  }
}
6
4

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

ΕΠΙ), γιατί απλώς τρέξαμε έναν βρόχο για να βρούμε το ένατο στοιχείο της ακολουθίας. Έτσι, η πολυπλοκότητα του χρόνου είναι γραμμική.

Διαστημική πολυπλοκότητα

ΕΠΙ), δεδομένου ότι έχουμε χρησιμοποιήσει έναν πίνακα DP για να αποθηκεύσουμε τα ενδιάμεσα αποτελέσματα που απαιτούνται για τον υπολογισμό του nth στοιχείου. Η πολυπλοκότητα του διαστήματος είναι επίσης γραμμική.

αναφορές