ნიუმენ – შენქსი – უილიამსი პრემიერ


Რთული ტური Easy
ხშირად ეკითხებიან HackerRank
დინამიური პროგრამირება მათემატიკის Მარტივი რიცხვი თანმიმდევრობა

პრობლემის განცხადება

Newman – Shanks – Williams (NSW Prime) სხვა არაფერია, თუ არა უბრალო რიცხვი, რომელიც შეიძლება წარმოდგენილი იყოს კონკრეტული ფორმით შემდეგი ფორმულის გათვალისწინებით:

ასე რომ, ჩვენ უნდა ვიპოვოთ NSW პირველი.

მაგალითი

n = 3
7

განმარტება

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

მიდგომა

NSW პირველი აღწერეს მორის ნიუმენმა, დენიელ შენკსმა და ჰიუ უილიამსმა 1981 წელს, კვადრატული რიგის მქონე სასრული მარტივი ჯგუფების შესწავლის დროს.

NSW პირველი პირველი რიცხვებია 7, 41, 239, 9369319, 63018038201,… (თანმიმდევრობა A088165 OEIS– ში), რომელიც შეესაბამება 3, 5, 7, 19, 29, ind ინდექსებს (A005850 თანმიმდევრობა OEIS– ში). {აღებულია ვიკიპედიიდან}

ამ პრობლემის დროს, ჩვენ გვეძლევა მხოლოდ n ნომერი, რომელიც ნიშნავს, რომ უნდა ვიპოვოთ NSW პირველყოფილი. ჩვენ შეგვიძლია ვიპოვოთ NSW პრემიერ განმეორებითი მიმართების გამოყენებით.

რეციდივის მიმართება

ნიუმენ – შენქსი – უილიამსი პრემიერ

ასე რომ, შეიძლება გამოყენებულ იქნას გულუბრყვილო მიდგომა NSW პრემიერის მოსაძებნად. გულუბრყვილო მიდგომისთვის, როგორც ვხედავთ, NSW თითოეული პრემიერი დამოკიდებულია NSW- ის ბოლო პრემიერზე და ბოლოს, NSW- ის პრემიერზე. ასე რომ, ჩვენ შეგვიძლია გამოვიყენოთ დინამიური პროგრამირება, სადაც შეგვიძლია შევინახოთ NSW ბოლო ორი ძირითადი. მიზეზი, თუ არ დაზოგავთ NSW ბოლო ორი პირველ რიგში. ჩვენ პრობლემას გადავჭრით რეკურსიული გზით, რაც გამოიწვევს ექსპონენციალური დროის სირთულეს. ამრიგად, ამჟამინდელი ექსპონენციალური დროის სირთულე ხაზოვან სირთულემდე შემცირდება. ჩვენ გავიხსენებთ ამ ღირებულებებს.

კოდი

C ++ კოდი Newman – Shanks – Williams– ის პრემიერ-მინისტრის მოსაძებნად

#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

ჯავის კოდი Newman – Shanks – Williams– ის პირველი რიცხვის მოსაძებნად

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

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

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

O (N), ვინაიდან ჩვენ უნდა განვსაზღვროთ მანამ, სანამ NSW- ის მე -XNUMX პრემიერს არ მივაგნებთ. დროის სირთულე წრფივია.

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

O (1), რადგან რომელი ცვლადებიც გამოვიყენეთ შედეგის გამოსათვლელად, ეს არ არის დამოკიდებული შეყვანაზე. ამრიგად, სივრცის სირთულე მუდმივია.