Паскальдың үшбұрышының II шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Microsoft
Array Динамикалық бағдарламалау математика

Проблемалық мәлімдеме

Бұл есепте бізге Паскаль үшбұрышының (i) қатар индексі берілген. Бізде ith жолының мәндері бар сызықтық жиым құрылып, оны қайтару керек. Жол индексі 0-ден басталады.
Паскаль үшбұрышы үшбұрыш екенін білеміз, мұнда әрбір сан оның үстіндегі екі санның қосындысы болады.

Паскальдың үшбұрышының II шешімі

мысал

rowIndex = 3
[1,3,3,1]
rowIndex = 0
[1]

Паскаль үшбұрышындағы әрбір мән биномдық коэффициент (nCr) болатынын білеміз, мұндағы n - жол, r - осы мәннің баған индексі.

Біз 0 жолының индексінен барлық жолдарды паскаль үшбұрышының берілген жол индексіне қайтару керек болатын ұқсас мәселені талқыладық - Паскаль үшбұрышы

Бірақ бұл мәселеде тек индексі берілген бір жолды қайтару керек.
Мұнда біз осы мәселені шешудің үш тәсілін талқылаймыз:

1 тәсіл (Brute Force Recursion)

Бұл үшбұрыштағы әрбір сан оның үстіндегі екі санның қосындысы екенін білеміз. яғни
Num (қатар, кол) = Num (жол-1, кол) + Num (қатар-1, кол-1).
Сонымен, біз осы қатардың әрбір баған индексі үшін Num (rowIndex, j) функциясын бірнеше рет шақырып, қалыптасқан тізімді қайтара аламыз.

Көріп отырғанымыздай, біз Num (i, j) табудың рекурсивті тәсілін тұжырымдадық. Енді бірнеше негізгі жағдайлар бар, олар:

  • Бірінші жолдағы мән 1 болады. Сонымен = 0 жол үшін, Num (жол,…) = 0 болады.
  • Бірінші бағандағы мән 1 болады. Сонымен, col = 0 үшін, Num (…, col) = 0 болады.
  • Әр жолдың соңғы мәні 1-ге тең болады, сондықтан col = жол = k үшін, Num (k, k) = 0 болады.

Паскальдағы үшбұрыш II шешім кодын енгізу

C ++ бағдарламасы

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

int nCr(int n,int r)
{
    if(n==0 || r==0 || r==n)
        return 1;

    return nCr(n-1,r-1)+ nCr(n-1,r);
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Java бағдарламасы

import java.util.*;

class Rextester{
    
    static int nCr(int n,int r)
    {
        if(n==0 || r==0 || r==n)
            return 1;

        return nCr(n-1,r-1)+ nCr(n-1,r);
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Паскальдың үшбұрышының II шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (2 ^ к): Мұндағы k - берілген Жолдар индексі.
Num (i, j) үшін рекурсияны Num (i-1, j) + Num (i-1, j-1) деп атаймыз. Демек, Num (n, r) табу уақыты nCr болады.
Біз бұл рекурсивті функцияны берілген жолдың (k) барлық баған индексі үшін шақырамыз .ie
kC0 + kC1 + kC2 +…. + kCk = 2 ^ k.
Демек, уақыттың жалпы күрделілігі O (2 ^ k) болады.

Ғарыштың күрделілігі 

Жарайды ма): Берілген жолдың барлық мәндерін тізімде сақтау үшін бізге O (k) кеңістігі қажет. Сондай-ақ, ең нашар жағдайда біздің рекурсияға рекурсивті қоңырау үшін O (k) стек кеңістігі қажет болады. Демек O (k) + O (k) = ~ O (k).

2-тәсіл (Динамикалық бағдарламалау)

Жоғарыдағы рекурсияда біз Num (i, j) функциясын бірдей (i, j) үшін бірнеше рет шақыратынымызды көреміз.

Сонымен, біз әр функцияны (i, j) үшін есте сақтай аламыз, сол кезде бұл функцияны қайта шақыру қажет болған кезде, біз кэштелген жауапты қайта есептемей-ақ жадтан тікелей қайтарамыз. Осылайша көп уақытты үнемдейді.
Жауаптарды динамикалық түрде сақтау үшін біз пайдалана аламыз хэш картасы мұндағы кілт жол индексі мен баған индексінің тіркесімі болады.

Мұнда тағы бір нәрсе көруге болады: ағымдағы жолдың мәндерін табу үшін тек алдыңғы мәндер қажет. Сондықтан біз бір уақытта бір ғана жол мәндерін сақтай аламыз және оны келесі жолдың мәндерін табу үшін қолдана аламыз. Демек, біз бұл жерде ғарыштық қиындықты O (k) дейін төмендете аламыз.

Кеңістіктің оңтайландырылған алгоритмі:
1. Алдыңғы және ағымдағы жолдарға сәйкесінше екі массив жасаңыз.
2. инициализация алдыңғы қатар {1}.
3. i = 1-ден i = -ге дейінгі қатарға арналған циклды іске қосыңызrowIndex. Алдыңғы қатардан жаңа жол мәндерін жасап, оны сақтаңыз ағын массив.
4. Енді жаңартыңыз алдыңғы тағайындау арқылы қатар с қатарға дейін алдыңғы қатарға қойыңыз және осы процесте осы процесті қайталаңыз.
5. сақталған соңғы жолды қайтарыңыз алдыңғы массив.

Паскальдағы үшбұрыш II шешім кодын енгізу

Есте сақтауды қолданатын C ++ бағдарламасы

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

unordered_map<string,int> cache;

int nCr(int n,int r)
{
    string key= to_string(n)+to_string(r);
    if(cache.count(key)) return cache[key]; 

    if(n==0 || r==0 || r==n)
        return 1;

    return ( cache[key]= nCr(n-1,r-1)+ nCr(n-1,r) );
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}

C ++ бағдарламасы (DP кеңістігі оңтайландырылған)

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

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Есте сақтауды қолданатын Java бағдарламасы

import java.util.*;

class Rextester{
    
    static Map<String,Integer> cache=new HashMap<String,Integer>();
    
    static int nCr(int n,int r)
    {
        String key= "" + n + r;
        if(cache.containsKey(key)) return cache.get(key); 
        
        if(n==0 || r==0 || r==n)
            return 1;
        
        int ans= nCr(n-1,r-1)+ nCr(n-1,r);
        cache.put(key,ans);
        return ans;
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}

Java бағдарламасы (DP кеңістігі оңтайландырылған)

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

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Паскальдың үшбұрышының II шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (k ^ 2):  Есте сақтау белгілі бір элементтің тек бір рет есептелуіне көз жеткізеді. Ans картасын хэш-картадан алу үшін тұрақты уақыт қажет деп есептесек, паскаль үшбұрышының әрбір мәнін есептеу үшін тұрақты уақыт қажет.
Енді біз 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 мәндерін есептейміз, = = O (k ^ 2).

Ғарыштың күрделілігі 

1. Қарапайым жадында 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 элементтері нашар жағдайда болады. Бұл қажет болар еді O (k ^ 2) кеңістік.
2. Ғарыш кеңістігінде бізге қажет Жарайды ма) тек соңғы жасалған жолды сақтау үшін орын.

3-тәсіл (математика)

Паскаль үшбұрышындағы әрбір мән биномдық коэффициент (nCr) болатынын білеміз. Біз nCr-ді келесідей жаза аламыз:
Паскальдың үшбұрышының II шешімі

Енді байқасақ, дәйекті биномдық коэффициенттер nC (r-1) және nCr:
Паскальдың үшбұрышының II шешімі

Осылайша, біз келесі мүшені қатардан Паскаль үшбұрышында алдыңғы мүшеден шығара аламыз.

Алгоритм:

  1. Қатардың бірінші мүшесін 1 деп бастаңыз.
  2. Ith индекстелген бағанға арналған циклды іске қосыңыз және келесі мүшені (мүше (i)) былай есептеңіз, термин (i) = термин (i-1) * (n-i + 1) / i.
  3. Есептелген мәндерді тізім ретінде қайтарыңыз.

Паскальдағы үшбұрыш II шешім кодын енгізу

C ++ бағдарламасы

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

vector<int> getRow(int rowIndex) 
{
    int n=rowIndex;
   vector<int> res;
   res.push_back(1);

    for(int i=1;i<=n;i++)
    {
       int x= (int) ( ((long long)res.back()*(n-i+1) ) /i);
       res.push_back(x);
    }

    return res;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Java бағдарламасы

import java.util.*;

class Rextester{

    public static List<Integer> getRow(int rowIndex) 
    {
       int n=rowIndex;
       List<Integer> res=new ArrayList<Integer>();
       res.add(1);
        
        for(int i=1;i<=n;i++)
        {
           int x= (int) ( ((long)res.get(res.size()-1)*(n-i+1) ) /i);
           res.add(x);
        }
        
        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Паскальдың үшбұрышының II шешімінің күрделілігін талдау

Уақыттың күрделілігі

Жарайды ма): Жолдың әрбір мәні тұрақты уақытта есептеледі.

Ғарыштың күрделілігі 

Жарайды ма): Шығарманы ұстап тұрудан басқа артық орын қажет емес.