Tatu samarqand filiali

15.2 Laboratoriya mashg’uloti

Mavzu: To’plam ostilari yig’indisini hisoblash

Ishning maqsadi: Yig’indilarni hisoblash algoritmlarini tahlil qilish

Kerakli jihozlar: Kompyuter, C++ dasturlash muhiti

To’plam ostilari yig’indisi masalasi algoritm murakkabligi nazariyasi va kriptografiyaning muhim masalasidir. Masala shundaki, ba'zi raqamlar to'plamining bo'sh bo'lmagan kichik to'plamini (kamida bitta) topish kerak, shunda bu kichik to'plamdagi raqamlar yig'indisi nolga teng bo'ladi. Masalan, {−7, −3, −2, 5, 8} to‘plam berilsin, keyin {−3, −2, 5} kichik to‘plam nolga teng bo‘lsin. Bu NP-to'liq masala.

Ekvivalent masala - elementlarning yig'indisi qandaydir berilgan s soniga teng bo'lgan kichik to'plamni topishdir. To’plam ostilari yig’indisi masalasi xalta masalasining alohida holati sifatida ham ko'rish mumkin. Kichik to'plamlarni yig'ish masalasining qiziqarli holati bo'lish masalasi bo'lib, unda s to'plamning barcha elementlari yig'indisining yarmiga teng.

Kichik to'plamlar yig'indisi masalasini hisoblash murakkabligi ikkita parametrga bog'liq - to'plam elementlarining N soni va aniqligi P (to'plamni tashkil etuvchi raqamlarning ikkilik raqamlari soni sifatida aniqlanadi). Eslatma: bu erda N va P harflarining NP masalalar sinfiga hech qanday aloqasi yo'q.

Eng yaxshi ma'lum bo'lgan algoritmning murakkabligi N va P ikkita parametrning eng kichigida eksponensialdir. Shunday qilib, N va P bir xil tartibda bo'lganda masala eng qiyin bo'ladi. Vazifa faqat N yoki P juda kichik bo'lganda oson bo'ladi.

Agar N (o'zgaruvchilar soni) kichik bo'lsa, to'liq qidiruv juda maqbuldir. Agar P (o'rnatilgan raqamlardagi raqamlar soni) kichik bo'lsa, dinamik dasturlashdan foydalanish mumkin.

Masala. Berilgan sonlar to‘plamining elementlari yig‘indisi ostto’plamga teng bo‘ladigan kichik to‘plamni toping.

#include

using namespace std;
int main()

{

double* a, s, p;

int n, k, ires;

bool flag;

do

{

cout << "to’plam elemntlar sonini kiriting: ";

cin >> n;

} while (n < 1); // n ning haqiqiy qiymatini tekshirish

a = new double[n]; // xotirani ajratish
for (int i = 0; i < n; i++)

{

cout << "Введите " << (i + 1) << " элемент : ";

cin >> a[i];

flag = false;

for (int j = 0; j < i; j++)

{

if (a[i] == a[j])

{

flag = true;

break;

}

}

if (flag)

{

cout << " Bu element to'plamda mavjud. " << endl;

i--;

}

}

cout << "Sonlar yig’indisini kiriting: ";

cin >> s;

cout << "To’plam: " << endl;

for (int i = 0; i < n; i++)

cout << a[i] << " ";

cout << endl;

ires = -1;

k = powf(2, n); // to’plamostilar soni

for (int i = 0; i < k; i++)

{

p = 0;

flag = false;

for (int j = 0; j < n; j++)

if (i & (1 << j))

{

p += a[j];

flag = true;

}

if (p == s && flag)

{

ires = i;

break;

}

}

if (ires == -1)

{

cout << " Berilgan yig‘indili kichik to‘plam mavjud emas " << endl;

}

else

{

cout << " Berilgan yig'indili kichik to'plam:" << endl;

for (int j = 0; j < n; j++)

if (ires & (1 << j))

{

cout << a[j] << " ";

}

cout << endl;

}
delete[] a; // xotiradan o’chirish

}

To'plam elementlari sonini kiriting: 10

1 ta elementni kiriting: 3

2 ta elementni kiriting: 5

3 ta elementni kiriting: 1

4 ta elementni kiriting: 7

5 ta elementni kiriting: 2

6 ta elementni kiriting: 8

7 ta elementni kiriting: 9

8 ta elementni kiriting: 6

9: 11 elementni kiriting

10 elementni kiriting: 13

Raqamlar yig'indisini kiriting: 22

Bir guruh:

3 5 1 7 2 8 9 6 11 13

Berilgan yig'indili kichik to'plam:

5 7 2 8

Masala. Berilgan manfiy va musbat sonlar to‘plamining shunday kichik to‘plamini topingki, uning elementlari yig‘indisi berilgan songa teng bo‘lsin.