Mündəricat
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
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.
