برايم نيومان - شانكس - ويليامز


مستوى الصعوبة سهل
كثيرا ما يطلب في HackerRank
البرمجة الديناميكية الرياضيات رقم اولي تسلسل

المشكلة بيان

رئيس نيومان - شانكس - ويليامز (NSW prime) ليس سوى عدد أولي يمكن تمثيله في شكل محدد وفقًا للصيغة التالية:

لذا علينا إيجاد عدد شرطة نيو ساوث ويلز رقم n.

مثال

n = 3
7

تفسير

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

الرسالة

تم وصف الأعداد الأولية لولاية نيو ساوث ويلز لأول مرة من قبل موريس نيومان ودانييل شانكس وهيو سي ويليامز في عام 1981 أثناء دراسة المجموعات البسيطة المحدودة ذات الترتيب المربع.

أول عدد قليل من الأعداد الأولية لولاية نيو ساوث ويلز هي 7 ، 41 ، 239 ، 9369319 ، 63018038201 ، ... (تسلسل A088165 في OEIS) ، المقابلة للمؤشرات 3 ، 5 ، 7 ، 19 ، 29 ، ... (تسلسل A005850 في OEIS). {مأخوذ من Wikipedia}

في المسألة ، لدينا رقم n فقط مما يدل على أننا بحاجة إلى إيجاد العدد n من NSW. يمكننا إيجاد رئيس NSW باستخدام علاقة التكرار.

علاقة تكرارية

برايم نيومان - شانكس - ويليامز

لذلك يمكن للمرء أن يستخدم نهجًا ساذجًا للعثور على العدد الأولي لولاية نيو ساوث ويلز. بالنسبة للنهج الساذج كما يمكننا أن نرى أن كل رئيس من ولاية نيو ساوث ويلز يعتمد على آخر رئيس لولاية نيو ساوث ويلز ويستمر حتى آخر رئيس لولاية نيو ساوث ويلز. حتى نتمكن من الاستفادة من البرمجة الديناميكية، حيث يمكننا تخزين آخر اثنين من الأعداد الأولية في نيو ساوث ويلز. لأننا إذا لم نحفظ آخر اثنين من الأعداد الأولية لولاية نيو ساوث ويلز. سنحل المشكلة بطريقة تكرارية والتي ستؤدي إلى تعقيد زمني أسي. وبالتالي لتقليل التعقيد الزمني الأسي الحالي إلى تعقيد الوقت الخطي. سنحافظ على هذه القيم في الذاكرة.

رمز

كود C ++ لإيجاد برايم نيومان - شانكس - ويليامز

#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 من شرطة نيو ساوث ويلز. التعقيد الزمني خطي.

تعقيد الفضاء

يا (1)، لأنه مهما كانت المتغيرات التي استخدمناها لحساب النتيجة لا تعتمد على المدخلات. وبالتالي فإن تعقيد الفضاء ثابت.