Newman-Conway Sequence


Кыйынчылык деңгээли жеңил
Көп суралган Amazon ЭлЭлПи
Динамикалык программалоо Math ирээт

Маселени билдирүү

"Ньюман-Конвейдин ырааттуулугу" көйгөйүндө сизге "n" бүтүн саны берилгендиги айтылат. Андан кийин Ньюман-Конвей тизмегинин биринчи n-элементин басып чыгаруу керек.

мисал

n = 6
4
n = 10
6

түшүндүрүү

Чыгуу элементтери Ньюман-Конвей тизмегинин алтынчы жана онунчу элементин чагылдыргандыктан. Чыгуу таптакыр туура.

Newman-Conway Sequence табуу ыкмасы

Ньюман-Конвей ырааттуулугу - бул ар бир мүчөсү төмөнкүдөй кайталануу мамилесин канааттандырган ырааттуулук.
P (1) = P (2) = 1

Newman-Conway Sequence

 

Эми ырааттуулуктан n-санын басып чыгарышыбыз керек. Эки ыкма болушу мүмкүн, анткени ырааттуулуктун ар бир элементи мурун түзүлгөн элементтерге көз каранды. Ошентип, жолдорунун бири колдонуу болуп саналат рекурсия бирок бул ыкма натыйжасыз. Себеби, биз ар бир элемент боюнча бир нече жолу чечебиз, анткени катардагы чоң терминдерди эсептей беребиз. Ошентип, биз эсептөө бир топ көп жүргүзүшүбүз керек. Ошентип, кайра эсептөө көйгөйүн чечүү үчүн. Биз колдонушубуз мүмкүн Динамикалык программалоо алгоритмдин натыйжалуулугун жогору көтөрүүгө болот. Учурда рекурсивдик алгоритм убакыттын экспоненциалдык татаалдыгына муктаж. Биз аны бир сызыктуу чечимге чейин кыскарта алабыз, анткени бир гана мамлекет бар.

Ошентип, динамикалык программалоо чечим. N элементтен мурун келген элементтерди сактай турган массивди түзөбүз. Бул биринчи элементтен (n-1) үчүнчү элементке чейинки бардык элементтер. Андан кийин ушул алдын ала эсептелгендерди колдонуп, биз үчүнчү элементти табабыз. N сандан мурун алдын-ала эсептелиши керек болгон бардык сандар болгондуктан. Биз керектүү элементтерди кайра-кайра эсептөөнүн ордуна, бул баалуулуктарды оңой эле колдоно алабыз. Бул ыкма убакыттын татаалдыгын азайтуу үчүн колдонулат

коду

Newman-Conway Sequence элементин табуу үчүн C ++ коду

#include <bits/stdc++.h>
using namespace std;

int main(){
  // element to be printed
  int n;cin>>n;
  int dp[n+1];
  dp[0] = 0;
  dp[1] = dp[2] = 1;
  for(int i=3;i<=n;i++)
    dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
  cout<<dp[n];
}
6
4

Nth Newman-Conway Sequence элементин табуу үчүн Java коду

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // eleemnt to be printed
    int n = sc.nextInt();
    int dp[] = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i=3;i<=n;i++)
      dp[i] = dp[dp[i-1]] + dp[i-dp[i-1]];
    System.out.print(dp[n]);
  }
}
6
4

Комплекстик анализ

Убакыт татаалдыгы

O (N), анткени биз жөн гана ырааттуулуктун n-элементин табуу үчүн бир цикл чуркадык. Ошентип, убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (N), n элементин эсептөө үчүн талап кылынган аралык жыйынтыктарды сактоо үчүн DP массивин колдондук. Космостун татаалдыгы дагы сызыктуу.

шилтемелер