نیومین - کان وے تسلسل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون ہنیویل
متحرک پروگرامنگ ریاضی تسلسل

مسئلہ یہ بیان

"نیومین۔ کونے تسلسل" مسئلہ یہ بیان کرتا ہے کہ آپ کو ایک ان پٹ انٹراگر دیا جاتا ہے "n"۔ اس کے بعد آپ کو نیومین کان وے سیکوئینس کا پہلاواں عنصر پرنٹ کرنے کی ضرورت ہے۔

مثال کے طور پر

n = 6
4
n = 10
6

وضاحت

چونکہ آؤٹ پٹ عناصر نیومین ۔کونوی تسلسل کے چھٹے اور دسویں عنصر کی نمائندگی کرتے ہیں۔ آؤٹ پٹ بالکل درست ہے۔

نیومین - کون وے تسلسل تلاش کرنے کے ل Appro نقطہ نظر

نیومین ۔کونوی ترتیب ایک ترتیب ہے جس کی ہر اصطلاح مندرجہ ذیل تکرار کے رشتے کو پورا کرتی ہے۔
P (1) = P (2) = 1

نیومین - کان وے تسلسل

 

اب ہمیں ترتیب سے نویں نمبر پرنٹ کرنے کی ضرورت ہے۔ وہاں دو طریقے ہوسکتے ہیں کیونکہ ترتیب کا ہر عنصر پچھلے پیدا شدہ عناصر پر منحصر ہوتا ہے۔ تو ، استعمال کرنے کا ایک طریقہ ہے تکرار لیکن یہ طریقہ کارگر نہیں ہے۔ کیوں کہ ہم ہر عنصر کو کئی بار حل کرتے رہیں گے ، کیوں کہ ہم سلسلہ میں اعلی شرائط کے لئے حساب کتاب کرتے رہتے ہیں۔ اس طرح ہمیں کمپیوٹرز کی بہت زیادہ تعداد انجام دینے کی ضرورت ہے۔ تو دوبارہ گنتی کے اس مسئلے کو حل کرنے کے لئے۔ ہم استعمال کرسکتے ہیں متحرک پروگرامنگ جو الگورتھم کی کارکردگی کو انتہائی بہتر بناسکتی ہے۔ فی الحال ، بار بار چلنے والی الگورتھم کو تیز وقت کی پیچیدگی کی ضرورت ہے۔ ہم اسے خطی حل میں کم کرسکتے ہیں کیونکہ صرف ایک ہی ریاست ہے۔

تو ، میں متحرک پروگرامنگ حل. ہم ایک صف تیار کریں گے جو نویں عنصر سے پہلے آنے والے عناصر کو محفوظ کرے گی۔ وہی عنصر جو پہلے عنصر سے لے کر (n-1) ویں عنصر تک ہے۔ پھر ان مضامین کا استعمال کرتے ہوئے ہمیں اپنا نویں عنصر ملے گا۔ چونکہ ہمارے پاس وہ تمام نمبر ہیں جن کو نویں نمبر سے پہلے ضرب لگانے کی ضرورت ہے۔ ہم ان اقدار کو بار بار مطلوبہ عناصر کا حساب کتاب کرنے کے بجائے آسانی سے استعمال کرسکتے ہیں۔ اس تکنیک کا استعمال وقت کی پیچیدگی کو کم کرنے کے لئے کیا جاتا ہے

ضابطے

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) ، کیونکہ ہم نے ترتیب کے نویں عنصر کو تلاش کرنے کے لئے صرف ایک ہی لوپ چلایا۔ اس طرح وقت کی پیچیدگی لکیری ہے۔

خلائی پیچیدگی

O (N) ، چونکہ ہم نے انٹرمیڈیٹ نتائج کو اسٹور کرنے کے لئے ڈی پی سرنی کا استعمال کیا ہے جو نویں عنصر کی گنتی کے لئے درکار تھا۔ خلائی پیچیدگی بھی لکیری ہے۔

حوالہ جات