Bajaruvchi: Bekmatov e tekshiruvchi: Axmedov f samarqand-2022 5-mavzu. P, Np, np-to’liq masalalar

Mavzu: To’plam ostilari yig’indisini hisoblash
Ishning maqsadi: Yig’indilarni hisoblash algoritmlarini tahlil qilish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
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

}