நியூமன்-கான்வே வரிசையின் n விதிமுறைகளை அச்சிடுக


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் சிட்டாடல் உண்மை வெறியர்கள் ஜேபி மோர்கன்
டைனமிக் புரோகிராமிங் கணித தொடர்

சிக்கல் அறிக்கை

“நியூமன்-கான்வே வரிசையின் அச்சு n விதிமுறைகள்” என்ற சிக்கல் உங்களுக்கு ஒரு முழு எண் “n” வழங்கப்பட்டதாகக் கூறுகிறது. நியூமன்-கான்வே வரிசையின் முதல் n சொற்களைக் கண்டுபிடித்து அவற்றை அச்சிடுங்கள்.

உதாரணமாக

n = 6
1 1 2 2 3 4

விளக்கம்
அச்சிடப்பட்ட அனைத்து சொற்களும் நியூமன்-கான்வே வரிசையைப் பின்பற்றுகின்றன, எனவே நாம் அதையே செய்ய வேண்டும். முதல் n சொற்களைக் கண்டுபிடிக்க முயற்சிப்போம்.

நியூமன்-கான்வே வரிசையின் n விதிமுறைகளை அச்சிடுவதற்கான அணுகுமுறை

நியூமன்-கான்வே வரிசைமுறை என்பது ஒவ்வொரு காலமும் பின்வரும் மறுநிகழ்வு உறவை திருப்திப்படுத்துகிறது:

பி (1) = பி (2) = 1

நியூமன்-கான்வே வரிசையின் n விதிமுறைகளை அச்சிடுக

இப்போது நாம் செய்ய வேண்டியது வரிசையின் முதல் n சொற்களைக் கண்டுபிடிப்பதாகும். இதேபோன்ற சிக்கலை நாங்கள் ஏற்கனவே தீர்த்துள்ளோம், அங்கு நாம் n வது உறுப்பைக் கண்டுபிடிக்க வேண்டியிருந்தது நியூமன்-கான்வே சீக்வெங்க்e. அந்த நேரத்தில், எங்களுக்கு இரண்டு விருப்பங்கள் இருந்தன. ஒன்று மறுநிகழ்வைப் பயன்படுத்தி சிக்கலைத் தீர்க்கலாம் அல்லது நாம் பயன்படுத்தியிருக்கலாம் டைனமிக் புரோகிராமிங். மறுநிகழ்வைப் பயன்படுத்துவது நேர வரம்பை மீறும் என்பதை நாங்கள் அறிந்தோம். மறுநிகழ்வின் நேர சிக்கலானது அதிவேகமானது என்பதால். மறுநிகழ்வு தீர்வுக்காக, நாங்கள் மீண்டும் நிகழும் சூத்திரத்தைப் பயன்படுத்துவோம், மேலும் வெவ்வேறு கூறுகளுக்கான மதிப்புகளைக் கணக்கிடுவோம். நீங்கள் பி (3) ஐக் கண்டுபிடிக்க வேண்டும் என்பதைக் கவனியுங்கள், எனவே நீங்கள் பி (பி (2)) மற்றும் பி (3-பி (2)) ஆகியவற்றைக் காண்பீர்கள். எனவே பி (3) ஐக் கண்டுபிடிக்க, முதலில், நீங்கள் பி (2) ஐக் கணக்கிட வேண்டும், பின்னர் மீண்டும் அதே கணக்கீடுகளைச் செய்யுங்கள். இந்த பணி மிகவும் நேரம் எடுக்கும்.

டைனமிக் புரோகிராமிங் அணுகுமுறை

எனவே நேர சிக்கலைக் குறைக்க, நாங்கள் பயன்படுத்தினோம் டைனமிக் நிரலாக்க. ஏனென்றால் நாங்கள் சில கூறுகளை பல முறை கணக்கிட்டு வந்தோம். உறுப்புகளை பல முறை கணக்கிடுவதற்கு பதிலாக, இடைநிலை உறுப்புகளுக்கான பதிலை சேமித்து வைத்தோம். நுட்பம் மறுநிகழ்வுக்கு மிகவும் ஒத்திருக்கிறது. ஆனால் ஒரு பகுதியின் சேர்த்தல் உள்ளது, இது ஒரு நினைவூட்டல் அட்டவணையைப் பயன்படுத்துகிறது. கணக்கிடப்பட்ட ஒவ்வொரு காலத்திற்கும் மதிப்புகளை நினைவூட்டல் சேமிக்கிறது.

ஆகவே, நமக்கு ஏதேனும் ஒரு சொல் தேவைப்படும்போதெல்லாம், அது ஏற்கனவே கணக்கிடப்பட்டதா என்பதைச் சரிபார்க்கிறோம். நாம் அதை கணக்கிடவில்லை என்றால், வேறு அதைப் பயன்படுத்துங்கள். இடைநிலை சொற்களை சேமிக்கும் இந்த நுட்பம் பொதுவாக அறியப்படுகிறது டைனமிக் புரோகிராமிங். இவ்வாறு நாம் மதிப்புகளைத் தேக்கி வைப்போம், கடைசியில், இந்த மதிப்புகளை அச்சிடுவோம்.

குறியீடு

நியூமன்-கான்வே வரிசையின் n விதிமுறைகளை அச்சிட சி ++ குறியீடு

#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

நியூமன்-கான்வே வரிசையின் n விதிமுறைகளை அச்சிட ஜாவா குறியீடு

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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), ஏனெனில் நாங்கள் ஒரு டைனமிக் நிரலாக்க அணுகுமுறையில் ஒரு சுழற்சியை இயக்கினோம். தற்போதைய உறுப்பு கணக்கிடுவதற்குத் தேவையான அனைத்து கூறுகளையும் மீண்டும் கணக்கிட்டுள்ளோம்.

விண்வெளி சிக்கலானது

ஓ (என்), அனைத்து n உறுப்புகளையும் சேமிக்க நேரியல் இடம் தேவைப்படுகிறது, இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.