ન્યુમેન – શksક્સ – વિલિયમ્સ પ્રાઈમ  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે હેકરરંક
ડાયનેમિક પ્રોગ્રામિંગ મઠ અવિભાજ્ય સંખ્યા સિક્વન્સ

સમસ્યા નિવેદન  

ન્યુમેન – શksક્સ – વિલિયમ્સ પ્રાઈમ (એનએસડબલ્યુ પ્રાઈમ) એ મુખ્ય સંખ્યા સિવાય બીજું કશું જ નથી જે નીચેના સૂત્રને જોતા વિશિષ્ટ સ્વરૂપમાં રજૂ કરી શકાય:

તેથી આપણે nth NSW પ્રાઇમ શોધવાની જરૂર છે.

ઉદાહરણ

n = 3
7

સમજૂતી

એસ 0 = 1, એસ 1 = 1, એસ 2 = 2 * એસ 1 + એસ 0 = 2 + 1 = 3, એસ 3 = 2 * એસ 2 + એસ 1 = 2 * 3 + 1 = 7

અભિગમ  

ચોરસ ઓર્ડરવાળા મર્યાદિત સરળ જૂથોના અભ્યાસ દરમિયાન 1981 માં મોરિસ ન્યૂમેન, ડેનિયલ શksક્સ અને હ્યુ સી. વિલિયમ્સ દ્વારા એનએસડબ્લ્યુ પ્રાઇમ્સનું પ્રથમ વર્ણન કરવામાં આવ્યું હતું.

પ્રથમ કેટલાક એનએસડબ્લ્યુ પ્રીમમ્સ 7, 41, 239, 9369319, 63018038201,… (OEIS માં ક્રમ A088165) છે, સૂચકાંકોને અનુરૂપ 3, 5, 7, 19, 29,… (OEIS માં ક્રમ A005850). Wikipedia વિકિપીડિયાથી લેવામાં આવ્યું}

સમસ્યામાં, અમને ફક્ત એક નંબર આપવામાં આવે છે જે સૂચવે છે કે આપણે nth NSW પ્રાઇમ શોધવાની જરૂર છે. આપણે પુનરાવર્તન સંબંધનો ઉપયોગ કરીને NSW પ્રાઇમ શોધી શકીએ છીએ.

પુનરાવર્તન સંબંધ

ન્યુમેન – શksક્સ – વિલિયમ્સ પ્રાઈમ

તેથી કોઈ એન.એચ.ડબ્લ્યુ પ્રાઇમ શોધવા માટે નિષ્કપટ અભિગમનો ઉપયોગ કરી શકે છે. નિષ્કપટ અભિગમ માટે આપણે જોઈ શકીએ છીએ કે દરેક એનએસડબલ્યુ પ્રાઈમ છેલ્લા એનએસડબલ્યુ પ્રાઇમ પર આધારિત છે અને છેલ્લાથી છેલ્લા એનએસડબલ્યુ પ્રાઇમ પર આધારિત છે. તેથી આપણે તેનો ઉપયોગ કરી શકીએ ડાયનેમિક પ્રોગ્રામિંગછે, જ્યાં આપણે છેલ્લાં બે એનએસડબલ્યુ પ્રાઇમ્સ સ્ટોર કરી શકીએ છીએ. જો આપણે છેલ્લાં બે એનએસડબ્લ્યુ પ્રાઇમ્સને સાચવી ન રાખીએ તો કારણ. અમે સમસ્યાને રિકર્સિવ ફેશનમાં હલ કરીશું, જેના પરિણામે ઘાતક સમય જટિલતા આવશે. આમ હાલના ઘાતક સમયની જટિલતાને રેખીય સમય જટિલતામાં ઘટાડવા માટે. આપણે આ મૂલ્યોને યાદ કરીશું.

આ પણ જુઓ
સારાંશ શ્રેણીઓ લેટકોડ સોલ્યુશન

કોડ  

નવમી ન્યુમેન – શksક્સ – વિલિયમ્સ પ્રાઈમ શોધવા માટે સી ++ કોડ

#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

નવમા ન્યુમેન – શksક્સ – વિલિયમ્સ પ્રાઈમ શોધવા માટે જાવા કોડ

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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન), જ્યાં સુધી અમને nth NSW પ્રાઇમ ન મળે ત્યાં સુધી લૂપ કરવાની જરૂર છે. સમયની જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે પરિણામની ગણતરી માટે આપણે જે પણ ચલોનો ઉપયોગ કર્યો છે તે ઇનપુટ પર આધારિત નથી. આમ જગ્યા જટિલતા સતત છે.