নিউম্যান – শ্যাঙ্কস – উইলিয়ামস প্রাইম


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় HackerRank
ডায়নামিক প্রোগ্রামিং ম্যাথ মৌলিক সংখ্যা ক্রম

সমস্যা বিবৃতি

একজন নিউম্যান – শ্যাঙ্কস – উইলিয়ামস প্রাইম (এনএসডাব্লু প্রাইম) একটি মূল সংখ্যা ছাড়া কিছুই নয় যা নিম্নলিখিত সূত্রের দ্বারা নির্দিষ্ট আকারে উপস্থাপন করা যেতে পারে:

সুতরাং আমাদের নবম এনএসডাব্লু প্রাইম খুঁজে পাওয়া দরকার।

উদাহরণ

n = 3
7

ব্যাখ্যা

এস 0 = 1, এস 1 = 1, এস 2 = 2 * এস 1 + এস 0 = 2 + 1 = 3, এস 3 = 2 * এস 2 + এস 1 = 2 * 3 + 1 = 7

অভিগমন

স্কয়ার অর্ডার সহ সীমাবদ্ধ সরল দলগুলির অধ্যয়নের সময় 1981 সালে মরিস নিউম্যান, ড্যানিয়েল শ্যাঙ্কস এবং হিউ সি উইলিয়ামস দ্বারা এনএসডাব্লিউ প্রাইমগুলি প্রথম বর্ণিত হয়েছিল।

প্রথম কয়েকটি এনএসডব্লিউ প্রাইমগুলি হ'ল 7, 41, 239, 9369319, 63018038201,… (ওইআইএসে ক্রম A088165) 3, 5, 7, 19, 29,… (ওইআইএসে ক্রম A005850)। Wikipedia উইকিপিডিয়া থেকে নেওয়া}

সমস্যাটিতে, আমাদের কেবলমাত্র একটি এন দেওয়া হয়েছে যা বোঝায় যে আমাদের এনথডাব্লিউ প্রাইমটি খুঁজে পাওয়া দরকার। পুনরাবৃত্তি সম্পর্ক ব্যবহার করে আমরা এনএসডাব্লু প্রাইম খুঁজে পেতে পারি।

পুনরাবৃত্তি সম্পর্ক

নিউম্যান – শ্যাঙ্কস – উইলিয়ামস প্রাইম

সুতরাং কেউ নবম এনএসডাব্লু প্রাইম খুঁজে পেতে একটি নির্লজ্জ পদ্ধতির ব্যবহার করতে পারে। নিষ্পাপ পদ্ধতির জন্য আমরা দেখতে পাচ্ছি যে প্রতিটি এনএসডব্লিউ প্রাইম সর্বশেষ এনএসডাব্লিউ প্রাইমের উপর নির্ভরশীল এবং শেষ থেকে শেষ এনএসডাব্লু প্রাইমের উপর নির্ভরশীল। সুতরাং আমরা ব্যবহার করতে পারেন ডায়নামিক প্রোগ্রামিং, যেখানে আমরা শেষ দুটি এনএসডব্লিউ প্রাইম সংরক্ষণ করতে পারি। যদি আমরা শেষের দুটি এনএসডব্লিউ প্রাইম সংরক্ষণ না করি তবে কারণ। আমরা সমস্যাটি একটি পুনরাবৃত্ত ফ্যাশনে সমাধান করব যা ক্ষতিকারক সময় জটিলতার ফলস্বরূপ। সুতরাং বর্তমান তাত্পর্যপূর্ণ সময় জটিলতা রৈখিক সময়ের জটিলতায় হ্রাস করতে। আমরা এই মানগুলি স্মরণ করিয়ে দেব।

কোড

নবম নিউম্যান – শ্যাঙ্কস – উইলিয়ামস প্রাইম সন্ধানের জন্য সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু), যেহেতু আমরা নবম এনএসডাব্লু প্রাইমটি না পাওয়া পর্যন্ত আমাদের লুপ করা দরকার। সময় জটিলতা রৈখিক।

স্পেস জটিলতা ity

ও (1), কারণ ফলাফলটি গণনা করতে আমরা যা কিছু ভেরিয়েবল ব্যবহার করেছি তা ইনপুটের উপর নির্ভর করে না। সুতরাং স্থান জটিলতা ধ্রুবক।