نیو مین - کون وے تسلسل کی شرائط پرنٹ کریں


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

مسئلہ یہ بیان

"نیومین۔ کان وے تسلسل کی شرائط" پرنٹ کریں۔ یہ بیان کرتا ہے کہ آپ کو ایک عددی نمبر دیا جاتا ہے۔ نیومین کان وے سیکوئینس کی پہلی ن شرائط ڈھونڈیں پھر انھیں پرنٹ کریں۔

مثال کے طور پر

n = 6
1 1 2 2 3 4

وضاحت
تمام شرائط جو چھپی ہوئی ہیں وہ نیومین۔ کونے تسلسل کی پیروی کرتی ہیں اور اس طرح ہمیں بھی ایسا کرنے کی ضرورت ہے۔ ہم پہلی ن شرائط تلاش کرنے کی کوشش کریں گے۔

نیومین کان وے ترتیب کی شرائط پرنٹ کرنے کے لئے نقطہ نظر

نیومین ۔کونوی ترتیب ایک ترتیب ہے جس کی ہر اصطلاح مندرجہ ذیل تکرار کے رشتے کو پورا کرتی ہے۔

P (1) = P (2) = 1

نیو مین - کون وے تسلسل کی شرائط پرنٹ کریں

اب ہمیں اس سلسلے کی پہلی ن شرائط تلاش کرنے کی ضرورت ہے۔ ہم نے اسی طرح کا مسئلہ پہلے ہی حل کرلیا ہے جہاں ہمیں اس کا نویں عنصر تلاش کرنا تھا نیومین۔ کونے سیوینکای. اس وقت ، ہمارے پاس دو آپشن تھے۔ یا تو ہم تکرار کا استعمال کرتے ہوئے مسئلہ حل کرسکتے ہیں یا ہم استعمال کرسکتے ہیں متحرک پروگرامنگ. ہم نے سیکھا ہے کہ تکرار کا استعمال وقت کی حد سے تجاوز کرجائے گا۔ چونکہ اوقات کی پیچیدگی مبہم ہے۔ تکرار حل کے ل we ، ہم تکرار کے فارمولے کا استعمال کریں گے اور مختلف عناصر کے لئے اقدار کا حساب لگاتے رہیں گے۔ غور کریں کہ آپ کو P (3) تلاش کرنے کی ضرورت ہے ، لہذا آپ کو P (P (2)) اور P (3-P (2)) مل جائے گا۔ تو P (3) تلاش کرنے کے ل first ، پہلے آپ کو P (2) کا حساب لگانا ہوگا ، پھر دوبارہ وہی حساب کتاب کریں۔ یہ کام بہت وقت طلب ہے۔

متحرک پروگرامنگ نقطہ نظر

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

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

ضابطے

نی + مین - کون وے تسلسل کی شرائط پرنٹ کرنے کے لئے C ++ کوڈ

#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

جاوا کوڈ نیومین - کون وے تسلسل کی شرائط پرنٹ کرنے کے لئے

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) ، تمام ن عنصر کو ذخیرہ کرنے کے ل line لکیری جگہ کی ضرورت ہوتی ہے اور اس طرح خلائی پیچیدگی بھی لکیری ہوتی ہے۔