Newman-Shanks-Williams baş əyləncə

Çətinlik səviyyəsi Asan
Tez-tez soruşulur HackerRank
Dinamik proqramlaşdırma Riyaziyyat Baş nömrə ArdıcıllıqBaxılıb 21

Problem bəyanat

Newman-Shanks-Williams prime (NSW prime) aşağıdakı düstur verilərək müəyyən bir formada təmsil oluna bilən əsas rəqəmdən başqa bir şey deyil:

Beləliklə, NSW-nin birinci səviyyəsini tapmaq lazımdır.

misal

n = 3
7

Izahat

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

Yanaşma

NSW asaları ilk dəfə 1981-ci ildə kvadrat düzeni olan sonlu sadə qrupların tədqiqatı zamanı Morris Newman, Daniel Shanks və Hugh C. Williams tərəfindən təsvir edilmişdir.

İlk bir neçə NSW asalı 7, 41, 239, 9369319, 63018038201,… (OEIS-də A088165 ardıcıllığı), 3, 5, 7, 19, 29,… (OEIS-də A005850 ardıcıllığı) indekslərinə uyğundur. {Wikipedia-dan götürülmüşdür}

Problemdə bizə n saylı NSW baş təbəqəsini tapmalı olduğumuzu bildirən yalnız bir ədəd verilir. Təkrarlanma əlaqəsindən istifadə edərək NSW başlığını tapa bilərik.

Təkrarlanma əlaqəsi

Newman-Shanks-Williams baş əyləncə

Beləliklə, birinci NSW-nin baş məqamını tapmaq üçün sadəlövh yanaşmadan istifadə etmək olar. Sadəlövh yanaşma üçün görə bilərik ki, hər bir NSW asalı son NSW başdan asılıdır və son NSW baş səviyyəsindən. Beləliklə istifadə edə bilərik Dinamik proqramlaşdırma, son iki NSW əsasını saxlaya biləcəyimiz yer. Səbəbi son iki NSW əsasını saxlamamağımızdır. Problemi rekursiv bir şəkildə həll edəcəyik, bu da eksponent zaman mürəkkəbliyi ilə nəticələnəcəkdir. Beləliklə, cari eksponent zamanın mürəkkəbliyini xətti zaman mürəkkəbliyinə endirmək. Bu dəyərləri xatırlayacağıq.

Kodu

Üçüncü Newman – Shanks – Williams prime tapmaq üçün C ++ kodu

#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

Üçüncü Newman – Shanks – Williams prime tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N)nci NSW başlıcasını tapana qədər döngə aparmaq lazım olduğundan. Zamanın mürəkkəbliyi xətti.

Kosmik Mürəkkəblik

O (1), çünki nəticəni hesablamaq üçün istifadə etdiyimiz dəyişənlər girişdən asılı deyil. Beləliklə kosmik mürəkkəblik sabitdir.

Translate »