Newman – Shanks – Williams prime


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

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

Το Newman – Shanks – Williams prime (NSW prime) δεν είναι τίποτα άλλο από έναν πρωταρχικό αριθμό που μπορεί να αναπαρασταθεί σε μια συγκεκριμένη μορφή δεδομένου του ακόλουθου τύπου:

Πρέπει λοιπόν να βρούμε το NTH prime.

Παράδειγμα

n = 3
7

εξήγηση

S0 = 1, S1 = 1, S2 = 2 * S1 + S0 = 2 + 1 = 3, S3 = 2 * S2 + S1 = 2 * 3 + 1 = 7

Προσέγγιση

Τα πρωταρχικά NSW περιγράφηκαν για πρώτη φορά από τους Morris Newman, Daniel Shanks και Hugh C. Williams το 1981 κατά τη διάρκεια μελέτης πεπερασμένων απλών ομάδων με τετραγωνική σειρά.

Οι πρώτοι πρώτοι αριθμοί NSW είναι 7, 41, 239, 9369319, 63018038201,… (ακολουθία A088165 στο OEIS), που αντιστοιχεί στους δείκτες 3, 5, 7, 19, 29,… (ακολουθία A005850 στον OEIS) {λαμβάνονται από τη Wikipedia}

Στο πρόβλημα, μας δίνεται ένας αριθμός n που δηλώνει ότι πρέπει να βρούμε το nth prime NSW. Μπορούμε να βρούμε το NSW prime χρησιμοποιώντας σχέση υποτροπής.

Επαναλαμβανόμενη σχέση

Newman – Shanks – Williams prime

Άρα μπορεί κανείς να χρησιμοποιήσει μια αφελής προσέγγιση για να βρει τον XNUMXο πρωταγωνιστή της ΝΝΟ. Για την αφελής προσέγγιση όπως μπορούμε να δούμε ότι κάθε πρωταρχικός NSW εξαρτάται από τον τελευταίο πρωταγωνιστή NSW και τελευταίος από τον τελευταίο πρωταγωνιστή NSW. Έτσι μπορούμε να χρησιμοποιήσουμε Δυναμικός προγραμματισμός, όπου μπορούμε να αποθηκεύσουμε τα δύο τελευταία prime NSW. Αιτία αν δεν αποθηκεύσουμε τα δύο τελευταία prim NSW. Θα λύσουμε το πρόβλημα με αναδρομικό τρόπο που θα οδηγήσει σε εκθετική πολυπλοκότητα χρόνου. Έτσι, για να μειωθεί η τρέχουσα εκθετική πολυπλοκότητα χρόνου σε γραμμική πολυπλοκότητα χρόνου. Θα απομνημονεύσουμε αυτές τις τιμές.

Κώδικας

Κωδικός C ++ για την εύρεση του nth Newman – Shanks – Williams prime

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

int main(){
  // nth NSW prime which is wanted
  int n;cin>>n;

  if(n == 0 || n == 1)
    cout<<1;
  else{
    int lastToLast = 1, last = 1;
    int cur;
    for(int i=2;i<=n;i++){
      cur = 2*last + lastToLast;
      lastToLast = last;
      last = cur;
    }
    cout<<cur;
  }
}
4
17

Κωδικός Java για την εύρεση του nth Newman – Shanks – Williams prime

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // nth NSW prime which is wanted
    int n = sc.nextInt();

    if(n == 0 || n == 1)
      System.out.print(1);
    else{
      int lastToLast = 1, last = 1;
      int cur = 0;
      for(int i=2;i<=n;i++){
        cur = 2*last + lastToLast;
        lastToLast = last;
        last = cur;
      }
      System.out.print(cur);
    }
    }
}
4
17

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

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

ΕΠΙ), δεδομένου ότι πρέπει να βρούμε μέχρι να βρούμε το πρώτο NSW prime. Η πολυπλοκότητα του χρόνου είναι γραμμική.

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

Ο (1), επειδή όποιες κι αν είναι οι μεταβλητές που χρησιμοποιήσαμε για τον υπολογισμό του αποτελέσματος δεν εξαρτάται από την είσοδο. Έτσι, η διαστημική πολυπλοκότητα είναι σταθερή.