د نیومن - کانوي تسلسل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon Honeywell
متحرک برنامې ریاضی تمرین

ستونزه بیان

د "نیومن - کانویو تسلسل" ستونزه په ګوته کوي چې تاسو ته د ان پټ انټور ورکړل شوی "n". بیا تاسو اړتیا لرئ د نیومن - کانویو تسلسل لومړی nth عنصر چاپ کړئ.

بېلګه

n = 6
4
n = 10
6

تشریح

له دې چې د تولید عناصر د نیومن - کانویو تسلسل شپږم او لسم عنصر استازیتوب کوي. محصول په بشپړ ډول سم دی.

د نیومن - کانوي تسلسل موندلو لپاره لاره

د نیومن - کونیو ترتیب یو ترتیب دی چې هره اصطلاح یې لاندې تکرار اړیکه خوښوي.
P (1) = P (2) = 1

د نیومن - کانوي تسلسل

 

اوس موږ اړتیا لرو د ترتیب څخه نهم نمبر چاپ کړئ. دلته دوه میتودونه شتون لري ځکه چې د ترتیب هر عنصر په تیرو رامینځته شوي عناصرو پورې اړه لري. نو ، یوه لاره یې کارول دي تکرار مګر دا میتود غیر فعال دی. ځکه چې موږ به ډیری وختونه د هر عنصر لپاره حل وکړو ، ځکه چې موږ په لړۍ کې د لوړو شرایطو لپاره محاسبه کوو. پدې توګه موږ اړتیا لرو چې ډیر شمیر کمپیوټري فعالیتونه ترسره کړو. نو د بیا حساب کولو د دې ستونزې حل کولو لپاره. موږ ممکن وکاروو متحرک برنامې کوم چې کولی شي د الګوریتم موثریت خورا لوړ کړي. اوس مهال ، تکرار الګوریتم د وخت وخت پیچلتیا ته اړتیا لري. موږ کولی شو دا یو محلول حل ته راکم کړو ځکه چې دلته یوازې یو دولت شتون لري.

نو ، په متحرک برنامه حل. موږ به یو صف جوړ کړو چې هغه عناصر به زیرمه کړي کوم چې د نهم عنصر دمخه راځي. دا د لومړي عنصر څخه تر (n-1) th عنصر پورې ټول عناصر دي. بیا د دې ناڅرګند کارولو سره موږ به زموږ nth عنصر ومومو. ځکه چې موږ ټول شمیرې لرو چې د نهم نمبر دمخه دمخه احتمال ته اړتیا لرو. موږ کولی شو دا ارزښتونه په اسانۍ سره وکاروو د دې پرځای چې د اړتیا وړ عناصر محاسبه کړو بیا او بیا. دا تخنیک د وخت پیچلتیا کمولو لپاره کارول کیږي

کوډ

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

د جاوا کوډ د نوي نیومین - کونوی تسلسل عنصر موندلو لپاره

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) ، ځکه چې موږ په ساده ډول د ترتیب nth عنصر موندلو لپاره یو واحد لوپ په لاره اچولی. پدې توګه د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

O (N) ، ځکه چې موږ د منځنۍ پایلې ذخیره کولو لپاره د DP سرنی کارولی دی کوم چې د نهم عنصر د حساب کولو لپاره اړین و. د ځای پیچلتیا هم خطي ده.

ماخذونه