Ньюмен – Шенкс – прем’єр Вільямса


Рівень складності Легко
Часто запитують у Хакер Rank
Динамічне програмування Математика Просте число Послідовність

Постановка проблеми

Просте число Ньюмена – Шенкса – Вільямса (просте число Нового Південного Уельсу) - це не що інше, як просте число, яке можна представити у конкретній формі, враховуючи наступну формулу:

Отже, нам потрібно знайти n-ту прем’єру 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,… (послідовність A005850 в OEIS). {взято з Вікіпедії}

У задачі нам дано лише число n, яке означає, що нам потрібно знайти n-й простий штат Південної Південної Америки. Ми можемо знайти простий NSW, використовуючи відношення рецидиву.

Відношення рецидивів

Ньюмен – Шенкс – прем’єр Вільямса

Тож можна використати наївний підхід для пошуку n-го найпростішого штату Південного Південного Уельсу. Для наївного підходу, як ми можемо бачити, кожна прем'єра Нового Південного Уезума залежить від останнього простого штату Нового Південного Університету та від останнього до останнього простого штату Нового Південного Уельсу. Тож ми можемо використати Динамічне програмування, де ми можемо зберігати останні два простих числа NSW. Тому що, якщо ми не збережемо останні два простих числа NSW. Ми будемо вирішувати проблему рекурсивно, що призведе до експоненціальної складності часу. Таким чином, зменшити поточну експоненціальну складність часу до лінійної складності часу. Ми запам’ятаємо ці значення.

код

Код C ++ для пошуку 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

Ява-код для пошуку n-го числа Ньюмена – Шенкса – Вільямса

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), оскільки нам потрібно робити цикл, поки не знайдемо n-й простий штат Південної Америки. Складність часу лінійна.

Складність простору

O (1), оскільки які б змінні ми не використовували для обчислення результату, це не залежить від вхідних даних. Таким чином, космічна складність постійна.