Алгебра

Изчисляване на биномен коефициент чрез триъгълник на Паскал

Нека имаме двучлен, бином повдигнат на степен цяло число. Получават се определени зависмости на коефициентите - биномни коефициенти, които са в пряка зависимост от предходната, по-ниска степен на същия бином. Блез Паскал описва в съчинението си "Трактат за аритметичния триъгълник" триъгълна таблица за коефициентите на бинома (x+1) повдигнат на степен естествено число. Тази таблица получава впоследствие названието триъгълник на Паскал. Тя дава стойностите на всички биномни коефициенти до определен степенен показател. В разглежданата задача трябва да се пресметне брой комбинации без повторения от общо n-елемента съдържащи k броя от тях. Ще използваме числа от триъгълник на Паскал за извеждане на биномни коефициенти на двучлен от вида x+1.

Ще използваме означение за биномен коефициент чрез C(n, k) имащ значението "n над k" брой комбинации без повторения от n елемента k-ти клас.
Може да се използва общата формула: C(n, k) = n!/((n - k)! k!).
Подобни зависимости ни дава триъгълник на Паскал. При него първият и последният елемент от всеки ред имат стойност 1.
Ползва се рекурентна формула от вида:
C(n, k) = 1, за k = 0 или k = n; - има само 1 комбинация n елемента клас n.
C(n, k) = C(n - 1, k - 1) + C(n - 1, k), за 0 < k < n; - сума от 2 елемента от предходен ред, предходна и текуща позция
C(n, k) = 0, за k > n - този случай не се разглежда в програмата.
С изключение на първия и последния елемент от текущия ред всеки друг елемент се получава като сума от съответните 2 елемента от предходния ред.
Така, за достигане на крайния резултат не е необходимо да се съхранява цялата таблица - всеки отделен елемент, а само съдържанието на предходен ред от таблицата.

Следващата примерна програма дава решена задача за биномен коефициент чрез триъгълник на Паскал - използва се динамично програмиране за решаване на задача за :

#include <iostream>  
using namespace std;  
  
 long mas[32];  //koeficientite narastwat mnogo byrzo
  
 long niut_bin(int n, int k)  
  { int i, j;  
    for (i=0;i<=n;i++)  
     { mas[i]=1;     
       if (i>1)   
        {if (k<i-1) j=k; else j=i-1;  
         for (; j>=1; j--) mas[j]+=mas[j-1];   
     }//if  
    }//for i  
 return mas[k];  
}//  binom
  
int main ()  
{ int i,n,k;  
  char ose;  
//dinamichno optimirane broj kombinacii - triygylnik na Paskal  
  cout<<"Da se systawi programa, chrez koqto se wywevdat n i k - estestweni\n";  
  cout<<"chisla ot interwala [2..22]. n e broj elementi, k - klas na kombinaciq.\n";  
  cout<<"Programata da izwede broqt kombinacii bez powtoreniq ot n elementa klas k.\n";  
  cout<<"Primer: 12 5 Izhod 792\n";   
  do {  
   cout<<"Wywedete broj elementi: "; cin>>n;  
   cout<<"Wywedete klas: ";cin>>k;  
   cout<<"Kombinaciq n elementa; klas k: "<<niut_bin(n, k)<<endl;  
   cout<<"Posledniq red ot triygylnika na Paskal sydyrva slednite elementi: \n";  
   for (i=0;i<=k;i++) cout<<mas[i]<<"; ";  
   cout<<endl;  
   cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;  
  }  
 while (ose=='y');  
 system ("pause");  
return 0;  
}//kraj na programa triygylnik na Paskal

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Размер на шрифта

Търсене в сайта:

Полезни връзки

Изпълними приложения за

Изчисляване на биномен коефициент чрез триъгълник на Паскал