សូលុយស្យុងត្រីកោណ II ឡេឡេកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន Microsoft
អារេ ការសរសេរកម្មវិធីឌីណាមិក គណិតវិទ្យា

តារាង​មាតិកា

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានគេផ្តល់សន្ទស្សន៍ជួរដេក (i) នៃត្រីកោណប៉ាស្កាល់។ យើងត្រូវបង្កើតអារេលីនេអ៊ែរដែលមានតម្លៃនៃជួរអ៊ីតហើយប្រគល់វាមកវិញ។ សន្ទស្សន៍ជួរដេកចាប់ផ្តើមពីលេខ ០ ។
យើងដឹងហើយថាត្រីកោណរបស់ផាស្កាល់គឺជាត្រីកោណមួយដែលលេខនីមួយៗជាផលបូកនៃលេខទាំងពីរដោយផ្ទាល់នៅពីលើវា។

សូលុយស្យុងត្រីកោណ II ឡេឡេកូដ

ឧទាហរណ៍

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

ដូចដែលយើងដឹងហើយថាតំលៃនិមួយៗនៃត្រីកោណរបស់ប៉ាស្កាល់គឺជាមេគុណ binomial (nCr) ដែល n ជាជួរដេកនិង r គឺជាសន្ទស្សន៍ជួរឈរនៃតំលៃនោះ។

យើងបានពិភាក្សាពីបញ្ហាស្រដៀងគ្នានេះដែលយើងត្រូវត្រឡប់ជួរដេកទាំងអស់ពីសន្ទស្សន៍ជួរ ០ ទៅសន្ទស្សន៍ជួរដេកនៃត្រីកោណរបស់ប៉ាស្កាល់នៅទីនេះ - ត្រីកោណប៉ាស្កាល់ឡេឡេកូដ

ប៉ុន្តែនៅក្នុងបញ្ហានេះយើងត្រូវត្រឡប់ជួរដេកតែមួយដែលសន្ទស្សន៍ត្រូវបានផ្តល់។
នៅទីនេះយើងនឹងពិភាក្សាអំពីវិធីសាស្រ្តបីសម្រាប់ដំណោះស្រាយនៃបញ្ហានេះ៖

វិធីសាស្រ្ត ១ (ការសម្លាប់រង្គាលដោយកម្លាំង)

យើងដឹងថាលេខនីមួយៗនៅក្នុងត្រីកោណនេះគឺជាផលបូកនៃលេខទាំងពីរដោយផ្ទាល់ពីលើវា។ ពោលគឺ
Num (ជួរ, កូល) = Num (ជួរ -១, កូ) + Num (ជួរ ១, កូ - ១) ។
ដូច្នេះយើងអាចហៅអនុគមន៍ Num (rowIndex, j) ម្តងហើយម្តងទៀតសម្រាប់សន្ទស្សន៍ជួរឈរនីមួយៗនៃជួរនោះហើយត្រឡប់បញ្ជីដែលបានបង្កើតឡើងវិញ។

ដូចដែលយើងបានឃើញហើយយើងបានបង្កើតវិធីសាស្រ្តហៅខ្លួនឯងដើម្បីរកលេខ (i, ជ) ។ ឥឡូវមានករណីមូលដ្ឋានមួយចំនួនសម្រាប់រឿងដែលមានៈ

  • តម្លៃនៅជួរទីមួយនឹងជាលេខ 1 ។ ដូច្នេះសម្រាប់ជួរ = 0, Num (ជួរដេក, …) = 0 ។
  • តម្លៃនៅជួរឈរដំបូងនឹងមានលេខ 1 ។ ដូច្នេះសម្រាប់ col = 0, Num (…, col) = 0 ។
  • តម្លៃចុងក្រោយនៃជួរនីមួយៗនឹងស្មើ ១ ។ ដូច្នេះសម្រាប់ col = ជួរ = k, Num (k, k) = ០ ។

ការអនុវត្តសម្រាប់ដំណោះស្រាយត្រីកោណ 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

កម្មវិធីចាវ៉ា

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

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយត្រីកោណទី ២ របស់ឡេស្កាល់

ស្មុគស្មាញពេលវេលា

O (២ ^ គ)៖ ដែល k ជាសន្ទស្សន៍ជួរដេកដែលបានផ្តល់។
យើងកំពុងហៅការហៅឡើងវិញសម្រាប់ Num (i, ច) ដូចជា Num (i-1, j) + Num (i-1, j-1) ។ ដូច្នេះពេលវេលាសម្រាប់ការស្វែងរកលេខ (n, r) នឹងជា nCr ។
យើងកំពុងហៅមុខងារហៅនេះសម្រាប់លិបិក្រមជួរឈរទាំងអស់នៃជួរដេកដែលបានផ្តល់ឱ្យ
kC0 + kC1 + kC2 + …។ + kCk = ២ ^ គ។
ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាសរុបគឺ O (2 ^ k) ។

ភាពស្មុគស្មាញនៃលំហ 

យល់ព្រម): យើងត្រូវការកន្លែង O (k) ដើម្បីទុកតម្លៃទាំងអស់នៃជួរដេកដែលបានផ្តល់ឱ្យក្នុងបញ្ជី។ ក្នុងករណីដ៏អាក្រក់បំផុតការស្វែងរករបស់យើងនឹងត្រូវការទំហំជង់ O (K) សម្រាប់ការហៅខ្លួនឯង។ ដូច្នេះ O (k) + O (k) = ~ O (k) ។

វិធីសាស្រ្ត ២ (ការសរសេរកម្មវិធីឌីណាមិក)

នៅក្នុងការដាស់តឿនខាងលើយើងអាចឃើញថាយើងកំពុងហៅមុខងារ Num (i, j) សម្រាប់មុខងារដដែល (i, ច) ម្តងហើយម្តងទៀត។

ដូច្នេះអ្វីដែលយើងអាចធ្វើបានគឺយើងអាចទន្ទេញចាំចម្លើយសម្រាប់ (i, ច) ដូច្នេះរាល់ពេលដែលត្រូវការហៅមុខងារនោះម្តងទៀតយើងត្រឡប់ចម្លើយដែលបានលាក់ទុកដោយផ្ទាល់ពីអង្គចងចាំដោយមិនបានគណនាឡើងវិញ។ ដូច្នេះចំណេញពេលវេលាច្រើន។
ចំពោះការរក្សាទុកចម្លើយប្រកបដោយថាមវន្តយើងអាចប្រើបាន ផែនទីហាស កន្លែងដែលកូនសោនឹងជាបន្សំនៃសន្ទស្សន៍ជួរដេកនិងសន្ទស្សន៍ជួរឈរ។

រឿងមួយទៀតដែលយើងអាចមើលឃើញនៅទីនេះគឺថាយើងត្រូវការតែតម្លៃជួរមុនប៉ុណ្ណោះសម្រាប់ការស្វែងរកតម្លៃនៃជួរដេកបច្ចុប្បន្ន។ ដូច្នេះយើងអាចរក្សាទុកតម្លៃជួរដេកតែមួយក្នុងពេលតែមួយហើយប្រើវាដើម្បីរកតម្លៃនៃជួរដេកបន្ទាប់។ ដូចនេះយើងអាចកាត់បន្ថយភាពស្មុគស្មាញនៃលំហទៅ O (K) នៅទីនេះ។

វិធីដោះស្រាយលំហអាដាប់ធ័រ៖
1. បង្កើតអារេពីរសម្រាប់ជួរមុននិងជួរដេកបច្ចុប្បន្ន។
2. គំនិតផ្តួចផ្តើម prev ជួរដេកជា {1} ។
3. រត់រង្វិលជុំសម្រាប់អ៊ីតជួរពី i = 1 ដល់ i =rowIndex។ ហើយបង្កើតតម្លៃជួរដេកថ្មីពីជួរមុនហើយផ្ទុកវាចូល curr អារេ។
4. ឥឡូវធ្វើបច្ចុប្បន្នភាព prev ជួរដោយកំណត់ cur ជួរទៅ prev ជួរដេកនិងធ្វើឡើងវិញនូវដំណើរការដូចគ្នានៅក្នុងរង្វិលជុំនេះ។
ត្រឡប់ជួរចុងក្រោយដែលបានរក្សាទុក prev អារេ។

ការអនុវត្តសម្រាប់ដំណោះស្រាយត្រីកោណ 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 ++ (ឌីភីភីធ្វើឱ្យប្រសើរកន្លែង)

#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

ចាវ៉ាកម្មវិធីដោយប្រើអនុស្សាវរនីយកម្ម

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+" ");
    }
}

ចាវ៉ាកម្មវិធី (ឌីភីបង្កើនប្រសិទ្ធិភាពចន្លោះ)

#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

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយត្រីកោណទី ២ របស់ឡេស្កាល់

ស្មុគស្មាញពេលវេលា

O (k ^ ២)៖  ការចងចាំនឹងធ្វើឱ្យប្រាកដថាធាតុជាក់លាក់មួយត្រូវបានគណនាតែម្ដងប៉ុណ្ណោះ។ ហើយសន្មតថាវាត្រូវការពេលវេលាថេរដើម្បីប្រមូលចម្លើយពីផែនទីហាំវាត្រូវការពេលវេលាថេរដើម្បីគណនាតម្លៃនីមួយៗនៃត្រីកោណប៉ាស្កាល់។
ឥឡូវយើងបញ្ចប់ការគណនា ១ + ២ + ៣ + … + (k + ១) = (k + ១) (k + ២) / ២ តម្លៃដែល = ~ O (k ^ ២) ។

ភាពស្មុគស្មាញនៃលំហ 

1. អនុស្សាវរីយ៏ងាយៗអាចមានទាំងអស់ ១ + ២ + ៣ + … + (k + ១) = (k + ១) (k + ២) / ២ ធាតុក្នុងករណីអាក្រក់បំផុត។ នោះនឹងតម្រូវឱ្យមាន O (k ^ 2) ចន្លោះ។
នៅក្នុងចន្លោះដែលបានបង្កើនប្រសិទ្ធភាព DP ដែលយើងត្រូវការ យល់ព្រម) កន្លែងសម្រាប់ទុកជួរដេកដែលបានបង្កើតចុងក្រោយបង្អស់។

វិធីសាស្រ្តទី ៣ (គណិតវិទ្យា)

ដូចដែលយើងបានដឹងហើយថាតម្លៃនីមួយៗនៅក្នុងត្រីកោណរបស់ប៉ាស្កាល់គឺជាមេគុណប៊ែលមីណេត (nCr) ។ ហើយយើងអាចសរសេរ nCr ជា៖
សូលុយស្យុងត្រីកោណ II ឡេឡេកូដ

ឥឡូវប្រសិនបើយើងកត់សំគាល់មេគុណកែវពង្រីកបន្តបន្ទាប់ nC (r-1) និង nCr ខុសគ្នាដោយកត្តា៖
សូលុយស្យុងត្រីកោណ II ឡេឡេកូដ

ដូច្នេះយើងអាចទាញយកពាក្យបន្ទាប់នៅក្នុងជួរដេកក្នុងត្រីកោណរបស់ផាស្កាលពីពាក្យមុន។

ក្បួនដោះស្រាយ៖

  1. ចាប់ផ្តើមពាក្យដំបូងនៃជួរដេកជា ១ ។
  2. ដំណើរការរង្វិលជុំសម្រាប់ជួរឈរដែលបានធ្វើលិបិក្រមនិងគណនាពាក្យបន្ទាប់ (រយៈ (i)) ដូចជា, ពាក្យ (i) = ពាក្យ (អាយ -១) * (n-i + ១) / 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

កម្មវិធីចាវ៉ា

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

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយត្រីកោណទី ២ របស់ឡេស្កាល់

ស្មុគស្មាញពេលវេលា

យល់ព្រម): តម្លៃនីមួយៗនៃជួរដេកត្រូវបានគណនាតាមពេលវេលាថេរ។

ភាពស្មុគស្មាញនៃលំហ 

យល់ព្រម): មិនត្រូវការកន្លែងទំនេរបន្ថែមក្រៅពីការកាន់លទ្ធផលទេ។