மோசர்-டி ப்ரூய்ன் வரிசை


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது ஃப்ரீசார்ஜ் Snapdeal டைம்ஸ் இணையம்
டைனமிக் புரோகிராமிங் வரிசை

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

உதாரணமாக

7
0, 1, 4, 5, 16, 17, 20

விளக்கம்

வெளியீட்டு வரிசையில் மோசர்-டி ப்ரூய்ன் வரிசையின் முதல் ஏழு கூறுகள் உள்ளன. இதனால் வெளியீடு முற்றிலும் சரியானது.

அணுகுமுறை

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

மோஸர்-டி ப்ரூய்ன் வரிசையை உருவாக்கும் எண்களையும் நாம் கொஞ்சம் வித்தியாசமாக வரையறுக்கலாம். அடிப்படை -4 எண் அமைப்பாக மாற்றப்பட்ட எண் 0 அல்லது 1 ஐ மட்டுமே கொண்டிருந்தால், அந்த எண் மோசர்-டி ப்ரூய்ன் வரிசையில் உள்ளது என்று கூறுகிறோம். அடிப்படை -4 எண் அமைப்பு அதன் இலக்கங்களாக 0 மற்றும் 1 ஐ மட்டுமே கொண்டுள்ளது என்று அர்த்தமல்ல. அடிப்படை -4 பிரதிநிதித்துவம் 0, 1, 2 மற்றும் 3 ஐக் கொண்டுள்ளது. ஆனால் எண் நம் வரிசையில் இருந்தால். அடிப்படை -0 பிரதிநிதித்துவத்தில் 1 அல்லது 4 மட்டுமே இருக்க வேண்டிய சில முன்நிபந்தனைகளை இது பின்பற்ற வேண்டும். எனவே எந்த வகையான எண்கள் வரிசையை உருவாக்குகின்றன என்பதை இப்போது நாம் அறிந்திருக்கிறோம். ஆனால் அத்தகைய எண்களை எவ்வாறு உருவாக்குவது?

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

தொடர்ச்சியான உறவு

மோசர்-டி ப்ரூய்ன் வரிசை

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

குறியீடு

மோஸர்-டி ப்ரூய்ன் வரிசையை உருவாக்க சி ++ குறியீடு

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of elements to be generated
  int n;cin>>n;
  if(n >= 1)cout<<0<<" ";
  if(n >= 2)cout<<1<<" ";
  if(n >= 3) {
    int dp[n];
    dp[0] = 0,dp[1] = 1;
    for(int i=2; i<n;i++){
      if(i%2 == 0)
        dp[i] = 4*dp[i/2];
      else
        dp[i] = 4*dp[i/2] + 1;
      cout<<dp[i]<<" ";
    }
  }
}
6
0 1 4 5 16 17

மோசர்-டி ப்ரூய்ன் வரிசையை உருவாக்க ஜாவா குறியீடு

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements to be generated
    int n = sc.nextInt();
    if(n >= 1)System.out.print("0 ");
    if(n >= 2)System.out.print("1 ");
    if(n >= 3) {
      int dp[] = new int[n];
      dp[0] = 0;dp[1] = 1;
      for(int i=2; i<n;i++){
        if(i%2 == 0)
          dp[i] = 4*dp[i/2];
        else
          dp[i] = 4*dp[i/2] + 1;
        System.out.print(dp[i]+" ");
      }
    }
  }
}
6
0 1 4 5 16 17

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

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

ஓ (என்), ஏனெனில் ஒரு எண்ணைக் கணக்கிட்டதும், பின்னர் கணக்கீட்டில் அதைப் பயன்படுத்த நேரமில்லை. முன் கணக்கீடுக்கு O (N) நேரம் தேவைப்படுவதால். நேரம், சிக்கலானது நேரியல்.

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

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