நியூமன்-ஷாங்க்ஸ்-வில்லியம்ஸ் பிரதம


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ஹேக்கர் தரவரிசை
டைனமிக் புரோகிராமிங் கணித முதன்மை எண் வரிசை

சிக்கல் அறிக்கை

ஒரு நியூமன்-ஷாங்க்ஸ்-வில்லியம்ஸ் பிரைம் (என்.எஸ்.டபிள்யூ பிரைம்) என்பது ஒரு பிரதான எண்ணைத் தவிர வேறொன்றுமில்லை, இது பின்வரும் சூத்திரத்தின் அடிப்படையில் ஒரு குறிப்பிட்ட வடிவத்தில் குறிப்பிடப்படலாம்:

எனவே நாம் nth NSW prime ஐக் கண்டுபிடிக்க வேண்டும்.

உதாரணமாக

n = 3
7

விளக்கம்

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

அணுகுமுறை

சதுர வரிசையுடன் வரையறுக்கப்பட்ட எளிய குழுக்களின் ஆய்வின் போது 1981 ஆம் ஆண்டில் மோரிஸ் நியூமன், டேனியல் ஷாங்க்ஸ் மற்றும் ஹக் சி. வில்லியம்ஸ் ஆகியோரால் NSW முதன்மையானவை முதலில் விவரிக்கப்பட்டது.

முதல் சில NSW ப்ரீம்கள் 7, 41, 239, 9369319, 63018038201,… (OEIS இல் வரிசை A088165), 3, 5, 7, 19, 29,… (OEIS இல் வரிசை A005850) குறியீடுகளுடன் தொடர்புடையது. Wikipedia விக்கிபீடியாவிலிருந்து எடுக்கப்பட்டது}

சிக்கலில், எங்களுக்கு ஒரு எண் n மட்டுமே வழங்கப்படுகிறது, இது n வது NSW பிரதமத்தைக் கண்டுபிடிக்க வேண்டும் என்பதைக் குறிக்கிறது. தொடர்ச்சியான உறவைப் பயன்படுத்தி NSW பிரதமத்தைக் காணலாம்.

மறுநிகழ்வு உறவு

நியூமன்-ஷாங்க்ஸ்-வில்லியம்ஸ் பிரதம

எனவே n வது NSW பிரதமத்தைக் கண்டுபிடிக்க ஒரு அப்பாவியாக அணுகுமுறையைப் பயன்படுத்தலாம். அப்பாவி அணுகுமுறைக்கு, ஒவ்வொரு என்.எஸ்.டபிள்யூ பிரதமமும் கடைசி என்.எஸ்.டபிள்யூ பிரதமத்தை சார்ந்தது மற்றும் கடைசியாக என்.எஸ்.டபிள்யூ பிரதமத்தை சார்ந்துள்ளது என்பதைக் காணலாம். எனவே நாம் பயன்படுத்திக் கொள்ளலாம் டைனமிக் புரோகிராமிங், கடைசி இரண்டு என்.எஸ்.டபிள்யூ ப்ரீம்களை சேமிக்க முடியும். கடைசி இரண்டு NSW ப்ரைம்களை நாங்கள் சேமிக்கவில்லை என்றால் காரணம். நாங்கள் சிக்கலை ஒரு சுழல்நிலை முறையில் தீர்ப்போம், இதன் விளைவாக அதிவேக நேர சிக்கலானது. இதனால் தற்போதைய அதிவேக நேர சிக்கலை நேரியல் நேர சிக்கலானதாக குறைக்க. இந்த மதிப்புகளை நாங்கள் நினைவில் கொள்வோம்.

குறியீடு

N வது நியூமன்-ஷாங்க்ஸ்-வில்லியம்ஸ் பிரதமத்தைக் கண்டுபிடிப்பதற்கான சி ++ குறியீடு

#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

நியூமன்-ஷாங்க்ஸ்-வில்லியம்ஸ் பிரதமரைக் கண்டுபிடிப்பதற்கான ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), n வது NSW பிரதமத்தைக் கண்டுபிடிக்கும் வரை நாம் வளைய வேண்டும். நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (1), ஏனெனில் முடிவை கணக்கிட நாம் பயன்படுத்திய மாறிகள் எதுவாக இருந்தாலும் உள்ளீட்டைப் பொறுத்தது அல்ல. இதனால் விண்வெளி சிக்கலானது நிலையானது.