Olimpiada masalalari

Dasturni tuzishga oid mulohazalar

n ta elementdan birinchi elementni tanlab olamiz va olinayotgan joylashtirishlarda uni qat’iy birinchi o‘rinda joylashtirib qo‘yamiz.
U holda joriy to‘plamda n-1 ta element qoladi, ulardan esa yana m - 1 tadan element tanlab, mavjud va birinchi o‘rinda turgan birinchi elementga qo‘shib boramiz.
Endi n-1 tadan nechta usul orqali m-1 tadan tanlash mumkinligini aniqlash qoldi xolos. Buni usullar orqali amalga oshirish mumkin.
Birinchi element olinayotgan joylashtirishlarda qat’iy birinchi o‘ringa o‘rnatilganligi uchun, barcha mavjud usullar soni ga teng bo‘ladi.
#include
#include
using namespace std;
int Almashtirishlar(int n, int k)
{
int S=1;
for (int i = 1; i <= k; i++)
S *= (n - k + i);
return S;
}
int main()
{

int S, n, m;
cout << "n="; cin >> n;
cout << "m="; cin >> m;

S = Almashtirishlar(n - 1, m - 1);

cout << S << endl;

return 0;
}


153-misol. 10 ta elementdan 7 tadan elementlar joylashuvi tuzilgan. Bu joylashishlardan nglechtasi: а) birinchi elementni, b) ikkinchi va to‘rtinchi elementni o‘z ichiga oladi?
Yechish


Birinchidan, bu masala oldingisidan nimasi bilan farq qiladi?
Oldingi masalada birinchi elementga qat’iy talab bor edi - u hosil bo‘layotgan joylashtirishlarda albatta birinchi o‘rinda turishi kerak edi.
Bu masalada esa, birinchi element faqatgina olinayotgan joylashtirishlarda ishtirok etishi kerak, uning birinchi o‘rinda turishi shart emas, demak u olinayotgan joylashtirishlardagi 7 ta o‘rinning ixtiyoriysida joylashishi mumkin.
To‘plam elementlarini 1 dan 7 gacha bo‘lgan raqamlar orqali belgilaymiz, u holda berilgan elementlar to‘plami quyidagi ko‘rinishda yozilishi mumkin: {1, 2, 3, 4, 5, 6, 7}. Birinchi elementni berilgan to‘plamdan tanlab olamiz, “bandmas” o‘rinlarni esa “x” deb belgilaymiz. Ko‘rinib turibdiki, 7 ta qism to‘plam hosil bo‘ladi.

Bu yerdan uning to‘plamini olinayotgan joylashtirishlarda ta usul bilan qo‘yish mumkinligi kelib chiqadi.
Ikkinchidan, 10 ta elementdan bittasini “chiqarib olgandan” so‘ng unda 9 ta element qoldi. Ushbu 9 tasidan yana 6 tasini tanlab birinchisiga yana 6 ni qo‘shib, jami 7 ta element hosil qilish kerak. Bu amalni usul bilan qilish mumkin:

Hammasi bo‘lib, bizda joylashtirishlar ko‘paytmasiga teng bo‘lgan usullar miqdori mavjud. Bu masaladagi b) punktning yechimi ham yuqoridagi g’oya kabi amalaga oshiriladi, ya’ni 2 va 4- elementlarni ta usul bilan qo’yish mumkinligini topamiz. 10 ta elementdan ikkitasini “chiqarib olgandan” so‘ng unda 8 ta element qoldi. Ushbu 8 tasidan yana 5 tasini tanlab birinchisiga yana 5 ni qo‘shib, jami 7 ta element hosil qilish kerak. Bu amalni usul bilan qilish mumkin: