Рекурсия жана толук издөө
Рекурсия жана толук кыдыруу: подмножестволор, орун алмаштыруулар жана варианттар дарагы.
Рекурсия — өзүн өзү чакырган функция. Туура рекурсияда ар дайым эки элемент бар: база (качан токтош керек) жана кадам (маселени кичинесине кантип алып келүү).
Башкы олимпиадалык колдонулушу — толук кыдыруу: БАРДЫК варианттарды системалуу түрдө басып өтүү. Мисалы, көптүктүн бардык подмножестволору: ар бир элемент үчүн эки тандоо — алуу же албоо. Тереңдиги n, жалбырактары 2ⁿ болгон варианттар дарагы келип чыгат.
Бардык подмножестволор. Киргизиңиз: 3, андан кийин 1 2 3
current.pop_back() сабы — backtracking (артка кайтуу менен кыдыруу) аттуу ыкманын жүрөгү: тандоо жасадык, бутакты изилдедик, тандоону АРТКА АЛДЫК да, кийинкисин сынайбыз. Унутулган артка алуу — кыдырууларда биринчи номердеги ката.
Масштабын баалаңыз: 2ⁿ подмножество — кыдыруу n болжол менен 20-25ке чейин реалдуу. Орун алмаштыруулар андан да көп: n! (n = 10 болгондо эле 3.6 миллион). Орун алмаштыруулар үчүн C++ тилинде даяр next_permutation бар.
Саптын бардык орун алмаштыруулары. Киргизиңиз: abc
Толук кыдыруу өтө чоң болгондо кесип таштоолор (отсечения) куткарат: жооп бербей турганы алдын ала белгилүү бутакка кирбөө. Кесип таштоолору бар акылдуу кыдыруу «түз» жол менен түбөлүк талап кылган маселелерди чечет.
Тапшырма: 1 2 3 4 сандарынын ортосуна + жана - белгилерин жыйынтык нөлгө барабар болгудай коюунун бардык жолдорун чыгарыңыз (белгилердин 2³ вариантын кыдыруу).
Сабакты өттүм деп белгилеп, ач көз алгоритмдерге өтүңүз.