Amaliy matematika va informatika fakulteti axborotlashtirish texnologiyalari kafedrasi mavzu: takror bolmagan kombinatsiyalar

SAMARQAND DAVLAT UNIVERSITETI
AMALIY MATEMATIKA VA INFORMATIKA FAKULTETI
AXBOROTLASHTIRISH TEXNOLOGIYALARI KAFEDRASI

MAVZU:TAKROR BOLMAGAN KOMBINATSIYALAR.
Bajardi: Elamonov Shukurullo
Tekshirdi: Zokirov Muhammad

SAMARQAND 2020
MUSTAQIL ISHI
MAVZU:TAKROR BOLMAGAN KOMBINATSIYALAR.
1-masala.
O’rin almashtirishlar
Elementlari takrorli bo‘lmagan to‘plam elementlarining barcha mumkin bo‘lgan o‘rin almashtirishlar holatlari va ularning sonini aniqlash dasturi tuzilsin.
#include
using namespace std;
void almash(int *a, int i, int j)
{int s = a[i]; a[i] = a[j]; a[j] = s;}
bool holatlar(int *a, int n) {
int j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false;
int k = n - 1;
while (a[j] >= a[k]) k--;
almash(a, j, k);
int l = j + 1, r = n - 1; while (lalmash(a, l++, r--);
return true;}
void Print(int *a, int n) {
static int num = 1;
cout.width(3); cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;}
void Urinalmashtirish(int *a, int n)
{Print(a, n);
while (holatlar(a, n))
Print(a, n);}
int main()
{int n, *a;
cout << "elementlar soni N = ";
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
Urinalmashtirish(a,n);
return 0;}


2-masala.
O’rinlashtirishlar
Turli n (n<150) ta elementli to‘plam elementlaridan m (m<=n<150) tadan mumkin barcha bo‘lgan o‘rinlashtirishlar sonini va holatlari (tuzilmalari)ni hosil qilish dasturi tuzilsin.
#include
using namespace std;
void almash(int *a, int i, int j)
{int s = a[i]; a[i] = a[j]; a[j] = s;}
bool holatlar(int *a, int n, int m) {
int j;
do
{j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false;
int k = n - 1;
while (a[j] >= a[k]) k--;
almash(a, j, k);
int l = j + 1, r = n - 1;
while (l < r)
almash(a, l++, r--);}
while (j > m - 1);
return true;}
void Print(int *a, int n) {
static int num = 1;
cout.width(3);
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;}
void Urinlashtirish(int *a,int n,int m)
{Print(a, m);
while (holatlar(a, n, m))
{Print(a, m);}}
int main() {
int n, m, *a;
cout << "elementlar soni N = ";
cin >> n;
cout << "o'rinlashtirish M = ";
cin >> m;
a = new int[n+m];
for (int i = 0; i < n+m; i++)
a[i] = i + 1;
Urinlashtirish(a,n,m);
return 0;}

3-masala.

Guruppalash
Turli n (n<150) ta elementli to‘plam elementlaridan m (m<=n<150) tadan mumkin barcha bo‘lgan guruhlashlar sonini va holatlari (tuzilmalari)ni hosil qilish dasturi tuzilsin.
#include
using namespace std;
int s[100000];
void chiqarish(int *a, int n)
{static int num = 1;
cout.width(3);
cout << num++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;}
void Guruhlash(int n, int k)
{do
{chiqarish(s,k);
if(++s[k - 1] <= n) continue;
if(k == 1) break;
int ind = -1;
for(int i = k - 2; i >= 0; --i)
if(s[i] <= n - k + i)
{ind = i;
break;}
if(ind == -1) break;
++s[ind];
for(int i = ind + 1; i < k; ++i)
s[i] = s[i - 1] + 1;}
while(1);}
int main()
{int m,n;
cout << "N = ";
cin >> n;
cout << "M = ";
cin >> m;
for(int i = 0; i < m; ++i)
s[i] = i + 1;
Guruhlash(n,m);
return 0;}


4-masala.
Paskal uchburchagi
Elementlari takrorli bo‘lmagan taelementdan tadan guruhlashlar soni formulasi yordamida 1-shakldagi Paskaluch burchagini hosil qilish dasturi tuzilsin.

#include
using namespace std;
int main ()
{long n, i, j;
cin>>n;
long c[(n+1)*(n+2)/2];
for(i = 1; i <= n ; i++) c[i] =0;
c[0] = 1;
for(j = 1 ; j <= n; j++)
{for(i = j; i >= 1 ; i--)
{c[i] = c[i-1] + c[i];
printf ("%ld ", c[i]);}
if(j!=1)cout<<1;
printf ("%\n");}
return 0;}


5-masala.
Ikki had yig‘indisi va ayirmasi darajalari yoyimasi (Nyutonbinomi)ni hosil qilish dasturi tuzisin.
#include
using namespace std;
long fac(int k){
long s=1;
for(int j=1;j<=k;j++)
s=s*j;
return s;}
long binom(int x,int y){
if(y==x||y==0)return 1;
else
return fac(x)/(fac(y)*fac(x-y));}
int main ()
{int n, i, j;
cin>>n;
cout<<"(a+b) ning "<if(i!=n)cout<<"+";}
cout<<"\n"<<"\n";
cout<<"(a-b) ning "<if(i!=n)
if(i%2==0)cout<<"-";
else cout<<"+";}
return 0;}


6-masala.
Nyuton binomini hosil qilish dasturi tuzisin.
#include
using namespace std;
long fac(int k){
long s=1;
for(int j=1;j<=k;j++)
s=s*j;
return s;}
long binom(int x,int y){
if(y==x||y==0)return 1;
else
return fac(x)/(fac(y)*fac(x-y));}
int main ()
{int n, i, j;
cin>>n;
cout<<"(a+b) ning "<if(i!=n)cout<<"+";}
cout<<"\n"<<"\n";
cout<<"(a-b) ning "<if(i!=n)
if(i%2==0)cout<<"-";
else cout<<"+";}
return 0;}


7-masala.
Binom koeffitsiyentlarini hisoblash dasturi tuzisin.
#include
using namespace std;
long fac(int k)
{long s=1;
for(int j=1;j<=k;j++)
s=s*j;
return s;}
long binom(int x,int y){
if(y==x||y==0)return 1;
else
return fac(x)/(fac(y)*fac(x-y));}
int main ()
{int n, i, j;
cin>>n;cout<for(i = 0; i <= n ; i++)
{cout<<" "<cout<<"C ="<cout<<" "<return 0;}


Takrorli kombinatsiyalar. Fibonachi sonlari.
1-masala.
Takrorli o‘rin almashtirishlar
n (n<150) ta elementli (elementlar takrorli bo‘lishi mumkin) to‘plam elementlarini barcha mumkin bo‘lgan o‘rin almashtirishlar sonini va holatlari (tuzilmalari)ni hosil qilish dasturi tuzilsin.
#include
using namespace std;
bool holatlar(int *a, int n)
{int j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false;
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a[j],a[k]);
int l = j + 1, r = n - 1;
while (lswap(a[l++],a[r--]);
return true;}
int main()
{int n, *a;
cout << "N = ";
cin >> n;
a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i + 1;
a[1]=1;
int m = 1;
cout << m++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
while (holatlar(a, n))
{cout << m++ << ": ";
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;}
return 0;}


2-masala.
Takrorli o‘rinlashtirishlar
Berilgan n (n<150) ta elementli to‘plam elementlaridan m (m<150) tadan barcha mumkin bo‘lgan takrorli o‘rinlashtishlar sonini va holatlari (tuzilmalari)ni hosil qilish dasturi tuzilsin.
#include
using namespace std;
bool holatlar(int *a, int n, int m) {
int j = m - 1;
while ( j>=0 && a[j] == n) j--;
if (j < 0) return false;
if (a[j] >= n)
j--;
a[j]++;
if (j == m - 1) return true;
for (int k = j + 1; k < m; k++)
a[k] = 1;
return true;}
int main()
{int n, m, *a;
cout << "N = ";
cin >> n;
cout << "M = ";
cin >> m;
int h = n > m ? n : m;
a = new int[h];
for (int i = 0; i < h; i++)
a[i] = 1;
int num = 1;
cout << num++ << ": ";
for (int i = 0; i < m; i++)
cout << a[i] << " ";
cout << endl;
while (holatlar(a, n, m))
{cout << num++ << ": ";
for (int i = 0; i < m; i++)
cout << a[i] << " ";
cout << endl;}
return 0;}
3-masala.
Takrorli guruhlashlar
Berilgan n (n<150) ta elementli to‘plam elementlaridan m (m<150) tadan barcha mumkin bo‘lgan takrorli guruhlashlar sonini va holatlari (tuzilmalari)ni hosil qilish dasturi tuzilsin.
#include
using namespace std;
bool holatlar(int *a, int n, int m)
{int j = m - 1;
while (a[j] == n && j>=0) j--;
if (j < 0) return false;
if (a[j] >= n)
j--;
a[j]++;
if (j == m - 1) return true;
for (int k = j + 1; k < m; k++)
a[k] = a[j];
return true;}
int main()
{int n, m, *a;
cout << "N = ";
cin >> n;
cout << "M = ";
cin >> m;
int h = n > m ? n : m;
a = new int[h];
for (int i = 0; i < h; i++)
a[i] = 1;
int num = 1;
cout << num++ << ": ";
for (int i = 0; i < m; i++)
cout << a[i] << " ";
cout << endl;
while (holatlar(a, n, m))
{cout << num++ << ": ";
for (int i = 0; i < m; i++)
cout << a[i] << " ";
cout << endl;}
return 0;}


4-masala.
Fibbonachi sonlarini hosil qilish dasturi tuzilsin.
#include
using namespace std;
int main()
{cout<<" Bine formulasi bo'yicha fibbonachi sonlarini topish\n";
long n,p;
cin>>n;
for(long i=1;i<=n;i++)
{p=(pow((1+sqrt(5))/2,i)-pow((1-sqrt(5))/2,i))/sqrt(5);
cout<<"fib-"<return 0;}


5-masala.
Bo‘laklashlarkombinatorikasinihosilqilishdasturituzisin.(Qo‘shiluvchilari tartibi e’tiborga olingan hol uchun)
#include
int a[10000];
int num = 1;
using namespace std;
bool holatlar(int *a, int n)
{int j = n - 2;
while (j != -1 && a[j] >= a[j + 1]) j--;
if (j == -1)
return false;
int k = n - 1;
while (a[j] >= a[k]) k--;
swap(a[j],a[k]);
int l = j + 1, r = n - 1; while (lswap(a[l++], a[r--]);
return true;}
void bolinish(int n, int k, int i)
{if ( n < 0 ) return;
if ( n == 0 )
{int j;
{cout << num++ << ": ";
for (int p = 0; p < i; p++)
cout << a[p] << " ";
cout << endl;
for(int p=0; pswap(a[p],a[i-p-1]);
while (holatlar(a, i))
{cout << num++ << ": ";
for (int p= 0; p < i; p++)
cout << a[p] << " ";
cout << endl;}}}
else
{if ( n - k >= 0)
{a[i] = k;
bolinish(n - k, k, i + 1);}
if ( k - 1 > 0)
{bolinish(n, k - 1, i);}}
return;}
int main()
{int m, i, j;
cin>>m;
for (i = 0; i <= m; i++)
{a[i] = 0;}
bolinish(m, m, 0);
return 0;}
ELAMONOV SHUKURULLO