Pascal جو ٽڪنڊي II جو ليٽ ڪوڊ حل


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon Microsoft جي
ڪيريو متحرڪ پروگرامنگ Math

مسئلي جو بيان

هن مسئلي ۾ اسان کي پاسسل ٽريگولي جو آر انڊيڪس (آءِ) ڏنو ويو آهي. اسان کي قطار واري قدرن تي مشتمل لينر اسٽري ٺاهيو ۽ ان کي واپس ڪرڻو پوندو. قطار انڊيڪس 0 کان شروع ٿئي ٿي.
اسان thatاڻون ٿا ته پاسلل ٽڪنڊي هڪ ٽڪنڊي آهي جتي هر نمبر سڌو سنئون ٻن نمبرن جو مجموعو آهي.

Pascal جو ٽڪنڊي II جو ليٽ ڪوڊ حل

مثال

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

جئين اسان thatاڻون ٿا ته پاسلل جي ٽڪنڊي ۾ هر ويليو هڪ بائنومل ڪوسٽر آهي (اين سي آر) جتي اين قطار آهي ۽ ر هن قيمت جو ڪالم انڊيڪس آهي.

اسان ساڳئي مسئلي تي بحث ڪيو آهي ، جتي اسان کي پاسڪيز جي ٽڪنڊي جي قطار انڊيڪس 0 کان قطار تائين سڀني قطار کي واپس موٽڻو آهي. Pascal ٽڪنڊي ليٽ ڪوڊ

پر ان مسئلي ۾ اسان کي رڳو هڪڙي ئي قطار موٽڻي آهي جنهن جي انڊيڪس ڏني وئي آهي.
هتي اسين هن مسئلي جي حل لاءِ ٽن طريقن تي بحث ڪنداسين:

رستو 1 (بروٽ فورس جو تسلسل)

اسان thatاڻون ٿا ته هن مثلث ۾ هر نمبر سڌو سنئون ٻن نمبرن جو مجموعو آهي. يعني
نمبر (قطار ، ڪال) = نمبر (قطار -1 ، ڪال) + نمبر (قطار -1 ، ڪال -1).
تنهن ڪري اسان انهي قطار جي هر ڪالم انڊيڪس لاءِ فنڪشن نمبر (قطار انڊيڪس ، ج) کي بار بار سڏي سگهون ٿا ۽ ٺاهيل فهرست واپس ڪري سگهون ٿا.

جئين اسان ڏسي سگهون ٿا اسان نمبر تلاش ڪرڻ جي لاءِ recursive نقطو جوڙي ڇڏيو آهي (i، j). ھاڻي ڪجھ بنيادي ڪيس آھن جن لاءِ:

  • پهرين قطار تي قدر 1 ٿي ويندي. تنهن ڪري قطار = 0 ، نمبر (قطار ،…) = 0.
  • پهرين ڪالم ۾ قدر هوندي 1. تنهن ڪري کول = 0 ، نوم (… ، col) = 0 لاءِ.
  • هر قطار جي آخري قيمت برابر ٿي ويندي 1. تنهن ڪري col = قطار = ڪ ، نون (ڪ ، k) = 0.

Pascal جي مثلث II ليٽڪوڊ حل لاءِ عمل درآمد

سي ++ پروگرام

#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

Pascal جي مثلث II ليٽڪوڊ حل لاءِ پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (2 ^ k): جي ڪٿي ڏني وئي رو انڊيڪس.
اسان نوم (i ، j) کي نمبر (I-1 ، j) + نمبر (i-1 ، j-1) جي لاءِ سڏيندا آهيون. ان ڪري نمبر تلاش ڪرڻ وقت (n، r) nCr ٿي وينديون.
اسان سڏايل قطار کي (آر) جي ڪالم واري انڊيڪس لاءِ اهو تعميري فنڪشن چئي رهيا آهيون
kC0 + kC1 + kC2 +…. + ڪييڪ = 2 ^ ڪ.
ان ڪري ڪل وقت جي پيچيدگي O (2 ^ k) هوندي.

خلائي پيچيدگي 

اي (ڪ): اسان کي قطار ۾ ڏنل سڀني قدرن کي ذخيرو ڪرڻ جي لاءِ O (k) جاءِ جي ضرورت آهي. بدترين صورت ۾ اسان جي ٻيهر ترغيب لاءِ ڪال (O) اسٽيڪ جي جڳهه جي ضرورت پوندي. ان ڪري O (k) + O (k) = ~ O (k).

پهچ 2متحرڪ پروگرامنگ)

مٿين بيانن ۾ اسين ڏسي سگھون ٿا ته اسان نمبر (i ، j) کي ساڳي (I ، j) فعل لاءِ بار بار سڏيون ٿا.

تنهن ڪري اسان ڇا ڪري سگهون ٿا اهو هر ڪنهن لاءِ اسان کي ياد ڪنداسين (i ، j) ته جيئن جڏهن ٻيهر انهي فنڪشن کي سڏڻ جي ضرورت هجي ته اسان ٻيهر ڳڻپيوڪر کان سواءِ يادداشت کان سڌو محفوظ ڪيل جواب موٽايو. اھڙي طرح گھڻو وقت بچائيندي.
متحرڪ طور انهن جوابن کي محفوظ ڪرڻ لاءِ جيڪي اسين استعمال ڪري سگھون ٿا هش نقشو جتي صف بندي انڊيڪس ۽ ڪالم انڊيڪس جي ميلاپ هوندي.

هڪ وڌيڪ شي جيڪا اسان هتي ڏسي سگهون ٿا اهو هي آهي ته اسان کي صرف موجوده قطار جي قدر ڳولڻ جي لاءِ اڳئين قطار واري قدر جي ضرورت آهي. ان ڪري اسان ھڪ وقت ۾ صرف ھڪڙي قطار جي قدرن کي ذخيرو ڪري سگھون ٿا ۽ ان کي استعمال ڪندي ايندڙ قطار جي قدر کي ڳولي سگھون ٿا. ان ڪري اسان هتي جي (ڪلو) تائين خلائي پيچيدگي گهٽائي سگھون ٿا.

خلائي بهتر ڪيل الگوريتم:
1. ترتيب ڏيو پوئين قطار ۽ موجوده قطار لاءِ.
2. شروعات غالب قطار وانگر {1}.
3. Iith کان I = 1 تائين =قطار انڊيڪس. ۽ پوئين قطار کان نئين صف جا قدر پيدا ڪريو ۽ ان کي اسٽور ڪريو ڪرنسي صف.
4. هاڻي اپڊيٽ ڪريو غالب ترتيب ڏيڻ سان قطار cur ڏانهن قطار غالب قطار ۽ ساڳي عمل کي ھن لوپ ۾ ورجائي.
5. محفوظ ڪيو ويو آخري قطار کي محفوظ ڪريو غالب صف.

Pascal جي مثلث II ليٽڪوڊ حل لاءِ عمل درآمد

ياداشت کي استعمال ڪندي سي ++ پروگرام

#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; 
}

سي ++ پروگرام (خلائي بهتر ٿيل ڊي پي)

#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

Pascal جي مثلث II ليٽڪوڊ حل لاءِ پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ڪي ^ 2):  ياداشت اهو يقيني بڻائي سگهندي ته هڪ خاص عنصر صرف هڪ ڀيرو حساب ٿيل آهي. ۽ اهو فرض ڪرڻ ته هش نقشي مان اين ايس آڻڻ ۾ لڳاتار وقت لڳندو آهي پاسسل جي مثلث جي هر قيمت کي حساب ڏيڻ لاءِ مسلسل وقت لڳندو آهي.
هاڻي اسان حساب ڪرڻ ختم ڪيو 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 قيمتون = = O (k ^ 2).

خلائي پيچيدگي 

1. سادي يادداشت سڀني 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 عنصرن بدترين حالتن ۾ وهائي ڇڏيندي. انهي جي ضرورت پوندي اي (ڪ ^ 2) خلا.
2. خلا ۾ آپگهاتي ڪيل ڊي پي جي ضرورت آهي اي (ڪ) جديد پيدا ٿيل قطار کي محفوظ ڪرڻ لاءِ جڳهه صرف.

پهچ 3 (رياضي)

جئين اسان thatاڻون ٿا ته پاسلل جي ٽڪنڊي ۾ هر ويليووينو ڪمينشل (NCr) آهي. ۽ اسان NCr لکي سگھوٿا:
Pascal جو ٽڪنڊي II جو ليٽ ڪوڊ حل

ھاڻي جيڪڏهن اسان ڏسون ٿا ، لڳاتار بينوميشنل گنجائش (N-R) ۽ NCr فڪر جي لحاظ کان مختلف آھن:
Pascal جو ٽڪنڊي II جو ليٽ ڪوڊ حل

اهڙيءَ طرح ، پوسل واري قريب ۾ اسان ايندڙ اصطلاح کي پوئين اصطلاح مان حاصل ڪري سگهون ٿا.

الگهان:

  1. 1 جي قطار جي پهرين اصطلاح جي شروعات ڪريو.
  2. ith indexed ڪالمن لاءِ لوپ هليو ۽ ايندڙ اصطلاح جي حساب ڪريو (اصطلاح (i)) ، اصطلاح (i) = term (i-1) * (n-i + 1) / i.
  3. ڳڻپيو ويل قدر ھڪڙي فهرست طور واپس ڪريو.

Pascal جي مثلث II ليٽڪوڊ حل لاءِ عمل درآمد

سي ++ پروگرام

#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

Pascal جي مثلث II ليٽڪوڊ حل لاءِ پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ڪ): قطار جي هر قيمت حساب سان مسلسل وقت ۾.

خلائي پيچيدگي 

اي (ڪ): ٻاھر ڪ holdingڻ کان سواءِ وڌيڪ ڪا جڳھ گهربل ناھي.