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

Daraxt ko‘rinishida:

• Daraxt ko‘rinishida:
• 0 bo’lsa chapga, 1 bo’lsa ongga tamon davom etadi.

0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
a0
a1
a2
a3

Endi rekursiyasiz yechilgan ikkilik perebor masalasini rekursiv yechamiz. Bizda ikkita parametr kerak bo’ladi: birinchisi joriy pozitsiya, ikkinchisi hozirgi yig’indi. Joriy pozitisyaga 0 qo’yib keyingi holatga o’tishda hozirgi yig’indi o’zgarmaydi, 1 bo’lsa shu pozitsiyadagi songa ortadi.

Endi rekursiyasiz yechilgan ikkilik perebor masalasini rekursiv yechamiz. Bizda ikkita parametr kerak bo’ladi: birinchisi joriy pozitsiya, ikkinchisi hozirgi yig’indi. Joriy pozitisyaga 0 qo’yib keyingi holatga o’tishda hozirgi yig’indi o’zgarmaydi, 1 bo’lsa shu pozitsiyadagi songa ortadi.

• int ans = 0, n, X;
• int a[1000];
• void go(int pos, long long s) {
• if (pos==n) {
• if (s==X)
• ans++;
• return;
• }

go(pos+1, s);

• go(pos+1, s);
• go(pos+1, s+a[pos]);
• }
• int main() {
• cin>>n>>X;
• for (int i = 0; i < n; i++) {
• cin>>a[i];
• }
• go(0, 0);
• cout<
• }

E’tiboringiz uchun raxmat.

Savollar?