Презентация Четвертухина Александра


Masalan n=6, buyumlar og’irliklari 4, 7, 2, 5, 3, 2 bo’lsa, va S=7 o’g’rilikni quyidagicha usullarda olishimiz mumkin



Yüklə 18,53 Kb.
səhifə4/7
tarix25.12.2023
ölçüsü18,53 Kb.
#194874
1   2   3   4   5   6   7
11701521 (1)

Masalan n=6, buyumlar og’irliklari 4, 7, 2, 5, 3, 2 bo’lsa, va S=7 o’g’rilikni quyidagicha usullarda olishimiz mumkin;

7, 4+3, 2+5, 5+2, 2+3+2 jami 5 ta usul.

Bizda n ta buyum bor. Biz ulardan tanlash amalga oshirganimzida har bir buyum uchun ikkita variant bor, tanlangan to’plamga tegishliligi yoki tegishli emasligi. n ta razriyadli ikkilik sanoq sistemasida 0 dan 2n-1 gacha bo’lgan sonlarni ikkilikdagi kodida mumkin bo’lgan barcha kombinatsiyalar ko’riladi.

Bizda n ta buyum bor. Biz ulardan tanlash amalga oshirganimzida har bir buyum uchun ikkita variant bor, tanlangan to’plamga tegishliligi yoki tegishli emasligi. n ta razriyadli ikkilik sanoq sistemasida 0 dan 2n-1 gacha bo’lgan sonlarni ikkilikdagi kodida mumkin bo’lgan barcha kombinatsiyalar ko’riladi.

Masalan n=3 bo’lsa 0 dan 23-1 gacha sonlarning ikkilik kodlari:

000 100

001 101

010 110

011 111

Har bir kombinatsiyada sonning ikkilik kodidagi mos belgisi 1 ga teng bo’lsa uni tegishli, 0 ga teng bo’lsa tegishli emas deb olamiz.

Har bir kombinatsiyada sonning ikkilik kodidagi mos belgisi 1 ga teng bo’lsa uni tegishli, 0 ga teng bo’lsa tegishli emas deb olamiz.

  • int main() {
  • int n;
  • long long X;
  • cin>>n>>X;
  • int a[n];
  • for (int i = 0; i < n; i++) {
  • cin>>a[i];
  • }
  • int ans = 0;
  • for (int mask = 0; mask < (1 << n); mask++) {
  • long long sum = 0;
  • for (int i = 0; i < n; i++) {
  • if ((mask & (1 << i)) != 0)
  • sum += a[i];
  • }
  • if (sum==X)
  • ans++;
  • }
  • cout<
  • }

Bu usulning ishlash vaqti O(2n n). Demak n≤20 uchun qo’llash mumkin.

Bu usulning ishlash vaqti O(2n n). Demak n≤20 uchun qo’llash mumkin.

Ikkilik pereborni qilishning boshqacha usuli bitli amallar ishlatmasdan, har bir sonni ikkilik sanoq tizimiga o’tkazamiz va har bir belgisini tekshirib chiqamiz:


Yüklə 18,53 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin