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



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

char w[100];

  • char w[100];
  • string s;
  • for (int mask = 0; mask < (1 << n); mask++) {
  • long long sum = 0;
  • itoa(mask, w, 2);
  • s = string(w);
  • while ((int)s.length() != n)
  • s = "0"+s;
  • for(int i = 0; i < n; i++) {
  • if (s[i]=='1')
  • sum += a[i];
  • }
  • if (sum==X)
  • ans++;
  • }

Yana bitta xosil qilish usuli

Har bir ikkilik ketma-ketlikni ularni leksikografik jihatdan o’sish tartibida ko’rib borish uchun har bir navbatdagi ketma-ketlikdan keyingi ketma-ketlikni topib borish kerak. Buning uchun oshirish mumkin bo’lgan eng kichik bitni topishimiz kerak, bu 0 ga teng bo’lgan eng kichik razryadli bit. Uning qiymatini 1 qilsak avvalgidan kattaroq son ketma-ketlik hosil bo’ladi, lekin eng kichigi bo’lishi uchun undan keyingi barchasini 0 ga aylantiramiz.

Masalan 100101101111 dan keyingisi 100101110000

  • int bit[n];
  • for (int i = 0; i < n; i++) {
  • bit[i] = 0;
  • }

while (1) {

  • while (1) {
  • long long sum = 0;
  • for (int i = 0; i < n; i++) {
  • if (bit[i]==1)
  • sum += a[i];
  • }
  • if (sum==X)
  • ans++;
  • int pos = -1;
  • for (int i = n-1; i >= 0; i--) {
  • if (bit[i]==0) {
  • pos = i;
  • break;
  • }
  • }
  • if (pos==-1)
  • break;
  • bit[pos]++;
  • for (int i = pos+1; i < n; i++) {
  • bit[i] = 0;
  • }
  • }

Uchlik perebor.

Uchlik sanoq sistemasida son 0,1 yoki 2 dan iborat bo’ladi.

Masala: Xaridor X sumlik maxsulot sotib olmoqchi, unda n ta, har biridan ikkitadan bo’lgan qiymati a[1], a[2],…a[n] tangalar bor. U necha xil usulda berilagn X sumni xosil qilishi mumkin?


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