ბეჭდვა Newman-Conway Sequence– ის პირობები


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ციხედ ფაქტები ფანატიკა JP Morgan
დინამიური პროგრამირება მათემატიკის სერია

პრობლემის განცხადება

პრობლემა "Newman-Conway Sequence- ის n დაბეჭდვა" აცხადებს, რომ გეძლევათ მთელი რიცხვი "n". იპოვნეთ Newman-Conway Sequence– ის პირველი n ტერმინები, შემდეგ დაბეჭდეთ ისინი.

მაგალითი

n = 6
1 1 2 2 3 4

განმარტება
ყველა ტერმინი, რომელიც იბეჭდება, მიჰყვება Newman-Conway Sequence- ს და ამიტომ ჩვენც იგივე უნდა გავაკეთოთ. ჩვენ შევეცდებით ვიპოვოთ პირველი n ტერმინები.

Newman-Conway Sequence– ის ვადების დაბეჭდვის მიდგომა

Newman-Conway Sequence არის თანმიმდევრობა, რომლის თითოეული ტერმინი აკმაყოფილებს შემდეგ რეციდივის უკავშირებას:

P (1) = P (2) = 1

ბეჭდვა Newman-Conway Sequence– ის პირობები

ახლა რაც უნდა გავაკეთოთ არის თანმიმდევრობის პირველი n ტერმინების პოვნა. ჩვენ უკვე გადავწყვიტეთ მსგავსი პრობლემა, სადაც უნდა აღმოგვეჩინა ნიუმენი-კონვეი Sequencე იმ დროს ორი გზა გვქონდა. ან პრობლემის გადაჭრა შეგვეძლო რეკურსის გამოყენებით, ან შეგვეძლო გამოგვეყენებინა დინამიური პროგრამირება. გავიგეთ, რომ რეკურსიის გამოყენება გადააჭარბებს ვადას. ვინაიდან რეკურსის დროული სირთულე ექსპონენციალურია. რეკურსიული ამოხსნისთვის გამოვიყენებთ განმეორების ფორმულას და გავაგრძელებთ სხვადასხვა ელემენტის მნიშვნელობების გამოთვლას. გაითვალისწინეთ, რომ თქვენ უნდა იპოვოთ P (3), ასე რომ თქვენ ნახავთ P (P (2)) და P (3-P (2)). ასე რომ, P (3) მოსაძებნად, ჯერ უნდა გამოთვალოთ P (2), შემდეგ კვლავ გააკეთოთ იგივე გამოთვლები. ეს ამოცანა ძალიან შრომატევადია.

დინამიური პროგრამირების მიდგომა

დროის სირთულის შესამცირებლად გამოვიყენეთ დინამიური პროგრამირება. იმიტომ, რომ ზოგიერთ ელემენტს რამდენჯერმე გამოვთვლიდით. ელემენტების მრავალჯერადი გამოთვლის ნაცვლად, ჩვენ შევინახეთ პასუხი შუალედური ელემენტებისათვის. ტექნიკა ძალიან ჰგავს რეკურსიას. მაგრამ აქ არის ერთი ნაწილის დამატება, რომელიც იყენებს სამახსოვრო ცხრილს. მოგონება ინახავს თითოეული გამოთვლილი ტერმინის მნიშვნელობებს.

ყოველთვის, როდესაც რაიმე ტერმინი დაგვჭირდება, უბრალოდ ვამოწმებთ, არის თუ არა იგი გათვლილი. თუ არა, გამოთვალეთ, სხვა შემთხვევაში გამოიყენეთ. შუალედური ტერმინების შენახვის ეს ტექნიკა ზოგადად ცნობილია, როგორც დინამიური პროგრამირება. ამრიგად, ჩვენ გავაგრძელებთ მნიშვნელობების ქეშირებას და ბოლოს, ჩვენ დავბეჭდავთ ამ მნიშვნელობებს.

კოდი

C ++ კოდი Newman-Conway Sequence– ის ვადების დასაბეჭდად

#include <bits/stdc++.h>
using namespace std;
int main(){
  // elements 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]];
  for(int i=1;i<=n;i++)
  	cout<<dp[i]<<" ";
}
6
1 1 2 2 3 4

ჯავის კოდი Newman-Conway Sequence– ის ვადების დასაბეჭდად

import java.util.*;
class Main{
    public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
    // elemnts 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]];
  	for(int i=1;i<=n;i++)
    	System.out.print(dp[i]+" ");
  }
}
6
1 1 2 2 3 4

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან ჩვენ უბრალოდ განვახორციელეთ დინამიური პროგრამირების მიდგომა. როგორც ჩვენ ყოველთვის გვქონდა გადაანგარიშებული ყველა ელემენტი, რომლებიც საჭიროა მიმდინარე ელემენტის გამოსათვლელად.

სივრცის სირთულე

O (N), ყველა n ელემენტის შენახვა მოითხოვს წრფივ სივრცეს და ამრიგად, სივრცის სირთულე ასევე ხაზოვანია.