ਨਿmanਮੈਨ-ਕੌਨਵੇ ਸੀਕੁਏਂਸ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਹਨੀਵੈੱਲ
ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਗਣਿਤ ਕ੍ਰਮ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ “ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਐਂਸ” ਕਹਿੰਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੰਪੁੱਟ ਪੂਰਨ ਅੰਕ “ਐਨ” ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ। ਫਿਰ ਤੁਹਾਨੂੰ ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਏਂਸ ਦੇ ਪਹਿਲੇ ਨੌਵੇਂ ਤੱਤ ਨੂੰ ਛਾਪਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਉਦਾਹਰਨ

n = 6
4
n = 10
6

ਕਥਾ

ਕਿਉਂਕਿ ਆਉਟਪੁੱਟ ਤੱਤ ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਏਂਸ ਦੇ ਛੇਵੇਂ ਅਤੇ ਦਸਵੇਂ ਤੱਤ ਨੂੰ ਦਰਸਾਉਂਦੇ ਹਨ. ਆਉਟਪੁੱਟ ਬਿਲਕੁਲ ਸਹੀ ਹੈ.

ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਐਂਸ ਨੂੰ ਲੱਭਣ ਲਈ ਪਹੁੰਚ

ਨਿmanਮੈਨ-ਕੌਨਵੇ ਸੀਕੁਏਂਸ ਇਕ ਤਰਤੀਬ ਹੈ ਜਿਸਦਾ ਹਰੇਕ ਸ਼ਬਦ ਹੇਠ ਦਿੱਤੇ ਮੁੜ ਸੰਬੰਧ ਨੂੰ ਸੰਤੁਸ਼ਟ ਕਰਦਾ ਹੈ.
ਪੀ (1) = ਪੀ (2) = 1

ਨਿmanਮੈਨ-ਕੌਨਵੇ ਸੀਕੁਏਂਸ

 

ਹੁਣ ਸਾਨੂੰ ਲੜੀਵਾਰ ਤੋਂ ਨੌਵਾਂ ਨੰਬਰ ਪ੍ਰਿੰਟ ਕਰਨ ਦੀ ਲੋੜ ਹੈ. ਇੱਥੇ ਦੋ beੰਗ ਹੋ ਸਕਦੇ ਹਨ ਕਿਉਂਕਿ ਕ੍ਰਮ ਦਾ ਹਰੇਕ ਤੱਤ ਪਹਿਲਾਂ ਤਿਆਰ ਕੀਤੇ ਤੱਤਾਂ ਉੱਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ. ਇਸ ਲਈ, ਇਸਦਾ ਇਕ useੰਗ ਇਸਤੇਮਾਲ ਕਰਨਾ ਹੈ ਮੁੜ ਪਰ ਇਹ ਤਰੀਕਾ ਅਯੋਗ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਹਰ ਇਕ ਤੱਤ ਲਈ ਕਈ ਵਾਰ ਹੱਲ ਕਰਾਂਗੇ, ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਲੜੀ ਵਿਚ ਉੱਚੀਆਂ ਸ਼ਰਤਾਂ ਲਈ ਹਿਸਾਬ ਲਗਾਉਂਦੇ ਰਹਿੰਦੇ ਹਾਂ. ਇਸ ਲਈ ਸਾਨੂੰ ਬਹੁਤ ਸਾਰੀਆਂ ਗਣਨਾ ਕਰਨ ਦੀ ਲੋੜ ਹੈ. ਇਸ ਲਈ ਦੁਬਾਰਾ ਗਣਨਾ ਦੀ ਇਸ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ. ਅਸੀਂ ਵਰਤ ਸਕਦੇ ਹਾਂ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਜੋ ਕਿ ਐਲਗੋਰਿਦਮ ਦੀ ਕੁਸ਼ਲਤਾ ਵਿੱਚ ਬਹੁਤ ਜ਼ਿਆਦਾ ਸੁਧਾਰ ਕਰ ਸਕਦਾ ਹੈ. ਵਰਤਮਾਨ ਵਿੱਚ, ਆਵਰਤੀ ਐਲਗੋਰਿਦਮ ਨੂੰ ਘਾਤਕ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅਸੀਂ ਇਸਨੂੰ ਇੱਕ ਲੀਨੀਅਰ ਘੋਲ ਵਿੱਚ ਘਟਾ ਸਕਦੇ ਹਾਂ ਕਿਉਂਕਿ ਇੱਥੇ ਸਿਰਫ ਇੱਕ ਰਾਜ ਹੈ.

ਇਸ ਲਈ, ਵਿਚ ਗਤੀਸ਼ੀਲ ਪ੍ਰੋਗਰਾਮਿੰਗ ਦਾ ਹੱਲ. ਅਸੀ ਇੱਕ ਐਰੇ ਬਣਾਵਾਂਗੇ ਜੋ ਐਲੀਮੈਂਟਸ ਨੂੰ ਸਟੋਰ ਕਰੇਗੀ ਜੋ ਨੌਵੇਂ ਐਲੀਮੈਂਟ ਤੋਂ ਪਹਿਲਾਂ ਆਉਂਦੇ ਹਨ. ਇਹ ਪਹਿਲੇ ਤੱਤ ਤੋਂ ਲੈ ਕੇ (ਐਨ -1) ਤੱਤ ਦੇ ਸਾਰੇ ਤੱਤ ਹਨ. ਤਦ ਇਨ੍ਹਾਂ ਪੂਰਵਗਣਿਤ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਅਸੀਂ ਆਪਣਾ ਨੌਵਾਂ ਤੱਤ ਪਾਵਾਂਗੇ. ਕਿਉਂਕਿ ਸਾਡੇ ਕੋਲ ਸਾਰੇ ਨੰਬਰ ਹਨ ਜਿਨ੍ਹਾਂ ਨੂੰ ਨੌਵੀਂ ਸੰਖਿਆ ਤੋਂ ਪਹਿਲਾਂ ਪੂਰਨ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਲੋੜੀਂਦੇ ਤੱਤ ਦੀ ਬਾਰ ਬਾਰ ਗਣਨਾ ਕਰਨ ਦੀ ਬਜਾਏ ਅਸੀਂ ਅਸਾਨੀ ਨਾਲ ਇਹਨਾਂ ਮੁੱਲਾਂ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ. ਇਸ ਤਕਨੀਕ ਦੀ ਵਰਤੋਂ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਘਟਾਉਣ ਲਈ ਕੀਤੀ ਜਾਂਦੀ ਹੈ

ਕੋਡ

ਸੀ ++ ਕੋਡ ਨੂੰ ਨੌਵਾਂ ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਐਂਸ ਐਲੀਮੈਂਟ ਨੂੰ ਲੱਭਣ ਲਈ

#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

ਨੌਵਾਂ ਨਿmanਮਨ-ਕੌਨਵੇ ਸੀਕੁਐਂਸ ਐਲੀਮੈਂਟ ਨੂੰ ਲੱਭਣ ਲਈ ਜਾਵਾ ਕੋਡ

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਕ੍ਰਮ ਦੇ ਨੌਵੇਂ ਤੱਤ ਨੂੰ ਲੱਭਣ ਲਈ ਇਕੋ ਲੂਪ ਭੱਜੇ. ਇਸ ਪ੍ਰਕਾਰ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਰੇਖੀ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਵਿਚਕਾਰਲੇ ਨਤੀਜਿਆਂ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਡੀਪੀ ਐਰੇ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ ਜੋ ਨੌਵੇਂ ਤੱਤ ਦੀ ਗਣਨਾ ਲਈ ਲੋੜੀਂਦੇ ਸਨ. ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਲੀਨੀਅਰ ਹੈ.

ਹਵਾਲੇ