Ҳалли санҷиши ҳамаи вариантҳо ҳамаи имкониятҳоро месанҷад ва беҳтаринро нигоҳ медорад ё хубҳоро мешуморад. Ин соддатарин барномаи дурустест, ки навиштан мумкин аст. Вақте ки маҳдудиятҳо хурданд, ин худи тамоми ҳал аст. Маҳорат дар он аст, ки аввал вариантҳоро ҳисоб кунед.
Пеш аз сикл ҳисоб кунед
Барои n ашё шумораи вариантҳо чунин аст:
- ҳар ҷуфт: тақрибан n² / 2 (n = 1 000: 5 · 10⁵);
- ҳар сегона: тақрибан n³ / 6 (n = 300: 4,5 · 10⁶);
- ҳар тартиби ашё: n! (n = 8: 40 320; n = 10: 3,6 · 10⁶; n = 12: 4,8 · 10⁸, хеле зиёд);
- ҳар зермаҷмуъ: 2ⁿ (n = 20: тақрибан 10⁶; n = 30: 10⁹, хеле зиёд).
Агар шумораи вариантҳо ба кори як вариант зарбшуда аз тақрибан 10⁸ камтар бошад, пеш равед. Маҳдудиятҳои хурд нишондоди муаллиф аст: n ≤ 8 тартибҳоро, n ≤ 20 зермаҷмуъҳоро, n ≤ 300 сегонаҳоро мефаҳмонад.
Ҳар сегона
Чанд секунҷаи росткунҷа бо тарафҳои бутун ҳаст, ки ҳамаи тарафҳо аз
nзиёд нестанд? Тарафҳоиa ≤ b ≤ cшарти a² + b² = c²-ро қаноат мекунанд. Маҳдудият: 1 ≤ n ≤ 200.
Ҳамаи a ≤ b ≤ c-ро санҷед: тақрибан n³ / 6 ≈ 1,3 миллион санҷиш, дар як лаҳза анҷом мешавад. Агар b-ро аз a ва c-ро аз b оғоз кунед, ҳар секунҷа як бор ҳисоб мешавад.
Вуруд
Баромад
Шаш секунҷа: (3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17) ва (12, 16, 20).
Ҳамаи тартибҳо
next_permutation векторро ба тартиби навбатӣ иваз мекунад ва баъд аз охирин false-ро медиҳад. Аз вектори танзимшуда оғоз кунед, вагарна тартибҳои пеш аз онро гум мекунед.
nдӯст ҳар кадом як кулоҳ меорад (n ≤ 8). Кулоҳҳо аз нав тақсим мешаванд, ба ҳар дӯст яктоӣ. Бо чанд роҳ ҳеҷ кас кулоҳи худашро намегирад?
Тартиби ададҳои аз 1 то n роҳи тақсим кардани кулоҳҳост: дӯсти i + 1 кулоҳи p[i]-ро мегирад.
Вуруд
Баромад
Барои n = 4 24 тартиб ҳаст ва 9-тои он хуб аст. Барои n = 8 40 320 тартиб ҳаст: дар як лаҳза.
Ҳар зермаҷмуъ
Барои санҷидани ҳар зермаҷмуъ дар бораи ададҳо як-як ҳал кунед: бе a[i] ё бо он. Ин функсияи рекурсивӣ бо ду даъват ва 2ⁿ роҳи анҷом аст.
nадад (n ≤ 20) ва ададиkдода шудааст. Чанд зермаҷмуъ ҷамъиkдоранд?
Вуруд
Баромад