உருவாக்கப்பட்ட வரிசை லீட்கோட் தீர்வில் அதிகபட்சத்தைப் பெறுங்கள்


சிரமம் நிலை எளிதாக
அணி

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

  1. arr [0] = 0, arr [1] = 1
  2. arr [2 * i] = arr [i] where 2 <= 2 * i <= n
  3. மற்றும் arr [2 * i + 1] = arr [i] + arr [i + 1] அங்கு 2 <= 2 * i + 1 <= n

ஆனால் தீர்வுக்கு மேலும் டைவ் செய்வதற்கு முன். நாம் ஒரு சில எடுத்துக்காட்டுகளைப் பார்க்க வேண்டும்.

உருவாக்கப்பட்ட வரிசை லீட்கோட் தீர்வில் அதிகபட்சத்தைப் பெறுங்கள்

n = 7
3

விளக்கம்: கொடுக்கப்பட்ட விதிகளின்படி:
எண்கள் [0] = 0, எண்கள் [1] = 1
எண்கள் [(1 * 2) = 2] = எண்கள் [1] = 1
எண்கள் [(1 * 2) + 1 = 3] = எண்கள் [1] + எண்கள் [2] = 1 + 1 = 2
எண்கள் [(2 * 2) = 4] = எண்கள் [2] = 1
எண்கள் [(2 * 2) + 1 = 5] = எண்கள் [2] + எண்கள் [3] = 1 + 2 = 3
எண்கள் [(3 * 2) = 6] = எண்கள் [3] = 2
எண்கள் [(3 * 2) + 1 = 7] = எண்கள் [3] + எண்கள் [4] = 2 + 1 = 3

எனவே, நாம் எண்களைக் காணலாம் = [0,1,1,2,1,3,2,3], அவற்றில் அதிகபட்சம் 3 ஆகும். இவ்வாறு பதில் 3.

உருவாக்கப்பட்ட வரிசை லீட்கோட் தீர்வில் அதிகபட்சத்தைப் பெறுவதற்கான அணுகுமுறை

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

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

சிக்கலைத் தீர்க்க, உறுப்பு உருவாக்கத்திற்கான சூத்திரங்களை நாங்கள் கையாள்வோம். 1 வது விதியில், i-3 உடன் மாற்றினால். Ar [2 * i-1] = arr [i] + arr [i-1] என்பதைக் காண்கிறோம். எனவே, இப்போது வரிசை உருவாக்கத்திற்கான விதிகளைப் பயன்படுத்தலாம். ஏனெனில் இந்த விதி ஏற்கனவே உருவாக்கப்பட்ட மதிப்பின் மதிப்பைப் பயன்படுத்துகிறது. எதிர்கால அறியப்படாத மதிப்புகளைப் பயன்படுத்துவதற்குப் பதிலாக இங்கே நாம் முன்பே கணக்கிடப்பட்ட மதிப்புகளைப் பயன்படுத்துகிறோம். எனவே இப்போது முழு செயல்முறையையும் ஒரு ஃபார் லூப்பைப் பயன்படுத்தி உருவகப்படுத்துகிறோம் மற்றும் 2 * i மற்றும் 2 * i-1 ஆகியவை வரிசையின் எல்லையில் இருக்கிறதா என்று சோதிக்கிறோம். இது உறுதிசெய்யப்பட்டதும், வரிசையை நிரப்ப சூத்திரங்களைப் பயன்படுத்துகிறோம்.

குறியீடு

உருவாக்கப்பட்ட வரிசை லீட்கோட் தீர்வில் அதிகபட்சத்தைப் பெறுவதற்கான சி ++ குறியீடு

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

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

உருவாக்கப்பட்ட வரிசை லீட்கோட் தீர்வில் அதிகபட்சத்தைப் பெறுவதற்கான ஜாவா குறியீடு

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

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

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

ஓ (என்), ஏனென்றால் நாம் அனைத்து n உறுப்புகளையும் உருவாக்குகிறோம்.

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

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