Умовний оператор. Вирішення тематичних завдань

Пропоную читачам "Хабрахабра" переклад публікації "100 Prisoners Escape Puzzle", яку я знайшов на сайті компанії DataGenetics. Усі помилки за цією статтею надсилайте, будь ласка, в особисті повідомлення.

За умовою завдання у в'язниці перебуває 100 ув'язнених, кожен із яких має особистий номер від 1 до 100. Тюремник вирішує дати ув'язненим шанс на звільнення та пропонує пройти вигадане випробування. Якщо всі ув'язнені впораються, то вони вільні, якщо хоча б один провалиться – усі помруть.

Завдання

Змагання починається, тюремник відводить кожного ув'язненого по одному в кімнату з коробками і каже ув'язненим, що вони повинні знайти коробку, в якій буде табличка з номером ув'язненого. Ув'язнені намагаються знайти табличку зі своїм номером, відкриваючи коробки. Кожному дозволяється відкрити до 50 коробок; якщо кожен із ув'язнених знайде свій номер, то ув'язнених відпустять, якщо хоча б один із них не знайде свій номер за 50 спроб, то всі ув'язнені помруть.

Для того, щоб ув'язнених було звільнено, ВСІ ув'язнені мають пройти випробування успішно.

То який же шанс, що в'язнів помилують?

• Після відкриття коробки ув'язненим та перевірки ним таблички вона поміщається назад у коробку і кришка знову закривається;
• Місцями таблички міняти не можна;
• В'язні не можуть залишати один одному підказки або взаємодіяти один з одним після початку випробування;
• Ув'язненим дозволяється обговорити стратегію на початок випробування.

Яка оптимальна стратегія для ув'язнених?

Додаткове питання:

Якщо товариш ув'язнених (не учасник випробування) матиме можливість проникнути в секретну кімнату до початку випробування, вивчити всі таблички у всіх коробках і (за бажанням, але не обов'язково) поміняти місцями дві таблички з двох коробок (при цьому у товариша не буде можливості як повідомити ув'язненим про результат своїх дій), то яку стратегію він має зробити, щоб збільшити шанси ув'язнених на порятунок?

Рішення малоймовірне?

Шанси одного в'язня – 50:50. Всього 100 коробок і він може відкрити до 50 коробок у пошуках своєї таблички. Якщо він відкриватиме коробки навмання і відкриє половину всіх коробок, то знайде свою табличку у відкритій половині коробок, або її табличка залишиться в закритих 50 коробках. Його шанси на успіх – ½.

Візьмемо двох ув'язнених. Якщо обидва вибирають коробки навмання, для кожного шанси будуть ½, а для двох ½x½=¼.
(Для двох ув'язнених успіх буде в одному випадку з чотирьох).

Для трьох ув'язнених шанси будуть ½ × ½ × ½ = ⅛.

Для 100 ув'язнених шанси наступні: ½ × ½ × … ½ × ½ (перемноження 100 разів).

Це дорівнює

Pr ≈ 0.0000000000000000000000000000008

Тобто, це дуже маленький шанс. За такого розкладу, швидше за все, всі ув'язнені будуть мертві.

Неймовірна відповідь

Більше 30% для всіх 100 ув'язнених! Та це навіть більше, ніж шанси для двох ув'язнених, за умови, що ті відкриватимуть ящики навмання. Але як це можливо?

Зрозуміло, що по одному у кожного ув'язненого шанси не можуть бути вищими за 50% (адже немає способу спілкування між ув'язненими). Але не варто забувати, що інформація зберігається в розташуванні табличок усередині коробок. Ніхто не перемішує таблички між відвідуваннями кімнати окремими ув'язненими, тому ми можемо використовувати цю інформацію.

Рішення

Стратегія вкрай легка. Перший із ув'язнених відкриває коробку з номером, який написаний на його одязі. Наприклад, ув'язнений номер 78 відкриває коробку з номером 78. Якщо він знаходить свій номер на табличці всередині коробки, то це чудово! Якщо ні, то він дивиться номер на табличці у своїй коробці і потім відкриває наступну коробку з цим номером. Відкривши другу коробку, він дивиться номер таблички всередині цієї коробки та відкриває третю коробку з цим номером. Далі просто переносимо цю стратегію на ящики, що залишилися. Для наочності дивимося картинку:

Зрештою, ув'язнений або знайде свій номер, або дійде до 50 коробок. На перший погляд, це виглядає безглуздо, в порівнянні з простим вибором коробки навмання (і для одного окремого ув'язненого це так), але так як всі 100 ув'язнених будуть використовувати той же набір коробок, це має сенс.

Краса цього математичного завдання - не тільки знати результат, але й зрозуміти, чомуця стратегія працює.

То чому ж стратегія працює?

Якщо подумати над цим, то коробки утворюють замкнутий круглий ланцюжок. Одна коробка може бути частиною лише одного ланцюжка, тому що всередині коробки лише один покажчик на наступну і, відповідно, у попередній коробці лише один покажчик на дану коробку (програмісти можуть побачити аналогію зі зв'язаними списками).

Якщо коробка не вказує на себе (номер коробки дорівнює номеру таблички в ній), то вона буде в ланцюжку. Деякі ланцюжки можуть складатися з двох коробок, деякі довші.

Оскільки всі ув'язнені починають із коробки з тим самим номером, що й на їхньому одязі, вони, за визначенням, потрапляють на ланцюжок, який містить їхню табличку (є лише одна табличка, яка вказує на цю коробку).

Досліджуючи коробки по цьому ланцюжку по колу, вони гарантовано зрештою знайдуть свою табличку.

Єдине питання залишається у тому, чи знайдуть вони свою табличку за 50 ходів.

Довжина ланцюжків

Якщо максимальна довжина найдовшого ланцюжка менша, ніж 50 коробок, тоді всі ув'язнені пройдуть випробування!

Подумайте про це на секунду. Виходить, що може бути тільки один ланцюжок, який довший за 50 коробок при будь-якому розкладі табличок (у нас всього 100 коробок, так що якщо один ланцюжок довший за 50, то решта буде коротшою, ніж 50 в результаті).

Шанси на розклад з довгим ланцюжком

Ще трохи математики

Для ланцюжка з довжиною l, ймовірність того, що коробки будуть поза цим ланцюжком дорівнює:

У цій колекції чисел існує (l-1)! способів розташувати таблички.

Таблички, що залишилися, можуть бути розташовані (100-l)! методами (не забуваємо, що довжина ланцюжка вбирається у 50).

З огляду на це число перестановок, які містять ланцюжок точної довжини l: (>50)

Виходить, є 100(!) способів розкладок табличок, тому ймовірність існування ланцюжка довжиною l дорівнює 1/l. До речі, цей результат залежить від кількості коробок.

Як ми вже знаємо, може бути тільки один варіант, при якому існує ланцюжок довжиною > 50, так що ймовірність успіху розраховується за цією формулою:

Результат

Імовірність того, що всі ув'язнені знайдуть свої таблички та пройдуть випробування 31.18%

Нижче наведено графік, що показує ймовірності (осі ординат) для всіх ланцюгів довжини l (на осі абсцис). Червоний колір означає всі "невдачі" (дана крива тут - це просто графік 1/l). Зелений колір означає «успіх» (розрахунок трохи складніший для цієї частини графіка, оскільки існує кілька способів визначення максимальної довжини<50). Общая вероятность складывается из зеленых столбцов в 31.18% шанс на спасение.

Гармонійне число (ця частина статті для гіків)

Порахуємо межу, якщо замість 100а коробок ми маємо довільну велику кількість коробок (давайте вважати, що у нас є 2n коробок у результаті).

Постійна Ейлера-Маскероні - константа, що визначається як межа різниці між частковою сумою гармонійного ряду та натуральним логарифмом числа.

Оскільки кількість ув'язнених збільшується, то за умови, якщо наглядач дозволяє ув'язненим відкривати половину всіх коробок, то шанс на порятунок прагне 30.685%.

(Якщо ви ухвалили рішення, при якому ув'язнені випадково вгадують коробки, то зі збільшенням кількості ув'язнених ймовірність порятунку прагне нуля!)

Додаткове питання

Зараз ми вже знаємо рішення, так що стратегія тут проста: він повинен вивчити всі таблички і знайти найдовший ланцюжок із коробок. Якщо найдовший ланцюжок менше 50-ти, то йому взагалі не потрібно міняти таблички, або поміняти їх так, щоб найдовший ланцюжок не став довшим за 50-ти. Тим не менш, якщо він знайшов ланцюжок довше 50 коробок, все, що йому потрібно - це поміняти вміст двох коробок з цього ланцюга, щоб розбити цей ланцюжок на два короткі ланцюги.

В результаті цієї стратегії не буде довгих ланцюжків і всі ув'язнені гарантовано знайдуть свою табличку та порятунок. Отже, помінявши місцями дві таблички, ми зводимо можливість порятунку до 100%!

Слід зазначити, що комбінаторика є самостійним розділом вищої математики (а не частиною тервера) і з цієї дисципліни написані важкі підручники, зміст яких часом анітрохи не легше абстрактної алгебри. Однак нам буде достатньо невеликої частки теоретичних знань, і в цій статті я постараюся у доступній формі розібрати основи теми з типовими комбінаторними завданнями. А багато хто з вас мені допоможуть;-)

Чим будемо займатися? У вузькому значенні комбінаторика - це підрахунок різних комбінацій, які можна скласти з деякої множини дискретнихоб'єктів. Під об'єктами розуміються якісь відокремлені предмети чи живі істоти – люди, звірі, гриби, рослини, комахи тощо. При цьому комбінаторику зовсім не хвилює, що безліч складається з тарілки манної каші, паяльника та болотяної жаби. Принципово важливо, що ці об'єкти піддаються перерахуванню – їх три (Дискретність)і суттєво те, що серед них немає однакових.

З безліччю розібралися, тепер про комбінації. Найпоширенішими видами комбінацій є перестановки об'єктів, їх вибірка з множини (поєднання) і розподіл (розміщення). Давайте прямо зараз подивимося, як це відбувається:

Перестановки, поєднання та розміщення без повторень

Не лякайтеся малозрозумілих термінів, тим більше деякі з них дійсно не дуже вдалі. Почнемо з хвоста заголовка – що означає « без повторень»? Це означає, що в даному параграфі будуть розглядатися множини, які складаються з різнихоб'єктів. Наприклад, … ні, кашу з паяльником і жабою пропонувати не буду, краще щось смачніше =) Уявіть, що перед вами на столі матеріалізувалося яблуко, груша і банан (за наявності таких ситуацію можна змоделювати і реально). Викладаємо фрукти зліва направо у такому порядку:

яблуко / груша / банан

Питання перше: Скільки способами їх можна переставити?

Одна комбінація вже записана вище та з іншими проблемами не виникає:

яблуко / банан / груша
груша / яблуко / банан
груша / банан / яблуко
банан / яблуко / груша
банан / груша / яблуко

Разом: 6 комбінацій або 6 перестановок.

Добре, тут не склало особливих труднощів перерахувати всі можливі випадки, але як бути, якщо предметів більше? Вже із чотирма різними фруктами кількість комбінацій значно зросте!

Будь ласка, відкрийте довідковий матеріал (методичку зручно роздрукувати)та у пункті № 2 знайдіть формулу кількості перестановок.

Жодних мук – 3 об'єкти можна переставити способами.

Питання друге: Скільки способами можна вибрати а) один фрукт, б) два фрукти, в) три фрукти, г) хоча б один фрукт?

Навіщо обирати? Так нагуляли апетит у попередньому пункті – для того, щоб з'їсти! =)

а) Один фрукт можна вибрати, очевидно, трьома способами - взяти або яблуко, грушу або банан. Формальний підрахунок проводиться за формулі кількості поєднань:

Запис у разі слід розуміти так: «скількими способами можна вибрати 1 фрукт з трьох?»

б) Перерахуємо всі можливі поєднання двох фруктів:

яблуко та груша;
яблуко та банан;
груші та банан.

Кількість комбінацій легко перевірити за тією самою формулою:

Запис розуміється аналогічно: «скільки можна вибрати 2 фрукти з трьох?».

в) І, нарешті, три фрукти можна вибрати єдиним способом:

До речі, формула кількості поєднань зберігає сенс і для порожньої вибірки:
способом можна вибрати жодного фрукта - власне, нічого не взяти і все.

г) Скільки способами можна взяти хоча б одинфрукт? Умова «хоча б один» передбачає, що нас влаштовує 1 фрукт (будь-який) або 2 будь-яких фрукти або всі 3 фрукти:
способами можна вибрати хоча б один фрукт.

Читачі, які уважно вивчили вступний урок з теорії ймовірностей, вже дещо здогадалися. Але про сенс знака "плюс" пізніше.

Для відповіді на наступне запитання мені потрібні два добровольці… …Ну що ж, якщо ніхто не хоче, тоді викликатиму до дошки =)

Питання третє: Скільки способами можна роздати по одному фрукту Даші та Наташі?

Для того, щоб роздати два фрукти, спочатку потрібно їх вибрати. Відповідно до пункту «бе» попереднього питання, зробити це можна засобами, перепишу їх заново:

яблуко та груша;
яблуко та банан;
груші та банан.

Але комбінацій зараз буде вдвічі більше. Розглянемо, наприклад, першу пару фруктів:
яблуком можна пригостити Дашу, а грушею – Наташу;
або навпаки – груша дістанеться Даші, а яблуко – Наталці.

І така перестановка можлива кожної пари фруктів.

Розглянемо ту саму студентську групу, яка пішла на танці. Скількими способами можна скласти пару з юнака та дівчини?

Способами можна вибрати 1 юнака;
способами можна вибрати 1 дівчину.

Таким чином, одного юнака іодну дівчину можна вибрати: методами.

Коли з кожної множини вибирається по 1 об'єкту, то справедливий наступний принцип підрахунку комбінацій: « коженоб'єкт з однієї множини може скласти пару з кожнимоб'єктом іншої множини».

Тобто Олег може запросити на танець будь-яку з 13 дівчат, Євген – теж будь-яку з тринадцяти, і аналогічний вибір має решта молодих людей. Разом: можливі пари.

Слід зазначити, що у цьому прикладі немає значення «історія» утворення пари; однак якщо взяти до уваги ініціативу, то кількість комбінацій треба подвоїти, оскільки кожна з 13 дівчат також може запросити на танець будь-якого юнака. Все залежить від умови того чи іншого завдання!

Схожий принцип справедливий і для складніших комбінацій, наприклад: скількома способами можна вибрати двох юнаків ідвох дівчат для участі у сценці КВК?

спілка Інедвозначно натякає, що комбінації необхідно перемножити:

Можливі групи артистів.

Іншими словами, кожнапара юнаків (45 унікальних пар) може виступати з будь-якийпарою дівчат (78 унікальних пар). А якщо розглянути розподіл ролей між учасниками, то комбінацій буде ще більше. …Дуже хочеться, але все-таки утримаюсь від продовження, щоб не прищепити вам огиду до студентського життя =).

Правило множення комбінацій поширюється і на більшу кількість множників:

Завдання 8

Скільки існує трицифрових чисел, які діляться на 5?

Рішення: для наочності позначимо це число трьома зірочками: ***

У розряд сотеньможна записати будь-яку з цифр (1, 2, 3, 4, 5, 6, 7, 8 чи 9). Нуль не годиться, тому що в цьому випадку число перестає бути тризначним.

А ось у розряд десятків(«посередині») можна вибрати будь-яку з 10 цифр: .

За умовою, число має ділитися на 5. Число ділиться на 5, якщо воно закінчується на 5 або на 0. Таким чином, у молодшому розряді нас влаштовують 2 цифри.

Отже, існує: трицифрових чисел, які діляться на 5.

При цьому твір розшифровується так: «9 способами можна вибрати цифру в розряд сотень і 10 способами вибрати цифру в розряд десятків і 2 способами в розряд одиниць»

Або ще простіше: « кожназ 9 цифр у розряді сотенькомбінується з кожноюз 10 цифр розряду десятків і з кожноюз двох цифр у розряд одиниць».

Відповідь: 180

А зараз…

Так, мало не забув про обіцяний коментар до завдання № 5, в якому Борі, Дімі та Володі можна здати за однією картою способами. Множення тут має той самий сенс: способами можна витягти 3 карти з колоди І в кожнійвибірці переставити їх засобами.

А тепер завдання для самостійного вирішення… зараз придумаю щось цікавіше, …нехай буде про ту ж російську версію блекджека:

Завдання 9

Скільки існує виграшних комбінацій з 2 карток при грі в «очко»?

Для тих, хто не знає: виграє комбінація 10 + ТУЗ (11 очок) = 21 очко і, давайте вважатимемо виграшною комбінацію з двох тузів.

(Порядок карт у будь-якій парі не має значення)

Коротке рішення та відповідь наприкінці уроку.

До речі, не слід вважати приклад примітивним. Блекджек - це чи не єдина гра, для якої існує математично обґрунтований алгоритм, що дозволяє вигравати у казино. Бажаючі можуть легко знайти масу інформації про оптимальну стратегію та тактику. Щоправда, такі майстри досить швидко потрапляють до чорного списку всіх закладів.

Настав час закріпити пройдений матеріал парою солідних завдань:

Завдання 10

У Васі вдома живуть 4 коти.

а) скільки можна розсадити котів по кутах кімнати?
б) скільки можна відпустити гуляти котів?
в) Скільки способами Вася може взяти на руки двох котів (одного на ліву, іншого - на праву)?

Вирішуємо: по-перше, знову слід звернути увагу на те, що в задачі йдеться про різнихоб'єктах (навіть якщо коти – однояйцеві близнюки). Це дуже важлива умова!

а) Мовчання котів. Цю кару зазнають відразу всі коти
+ важливе їх розташування, тому тут мають місце перестановки:
способами можна розсадити котів по кутах кімнати.

Повторюся, що з перестановках має значення лише кількість різних об'єктів та його взаємне розташування. Залежно від настрою Вася може розсаджувати тварин півколом на дивані, ряд на підвіконні і т.д. – перестановок у всіх випадках буде 24. Бажаючі можуть для зручності уявити, що коти різнокольорові (наприклад, білий, чорний, рудий та смугастий) та перерахувати всі можливі комбінації.

б) Скільки можна відпустити гуляти котів?

Передбачається, що коти ходять гуляти тільки через двері, при цьому питання має на увазі байдужість щодо кількості тварин – на прогулянку можуть вийти 1, 2, 3 або всі 4 коти.

Вважаємо всі можливі комбінації:

Способами можна відпустити гуляти одного кота (будь-якого з чотирьох);
способами можна відпустити гуляти двох котів (варіанти перерахуйте самостійно);
способами можна відпустити гуляти трьох котів (якийсь один із чотирьох сидить удома);
способом можна випустити всіх котів.

Напевно, ви здогадалися, що отримані значення слід підсумувати:
способами можна відпустити гуляти котів.

Ентузіастам пропоную ускладнену версію завдання – коли будь-який кіт у будь-якій вибірці випадково може вийти на вулицю як через двері, так і через вікно 10 поверху. Комбінацій помітно побільшає!

в) Скільки способами Вася може взяти на руки двох котів?

Ситуація передбачає не тільки вибір 2 тварин, а й їх розміщення по руках:
способами можна взяти на руки 2 коти.

Другий варіант вирішення: способами можна вибрати двох котів іспособами посадити кожнупару на руки:

Відповідь: а) 24, б) 15, в) 12

Ну і для очищення совісті щось конкретніше на збільшення комбінацій. Нехай у Васі додатково живе 5 котів =) Скільки способами можна відпустити гуляти 2 котів і 1 кішку?

Тобто, з кожноюпарою котів можна випустити кожнукішку.

Ще один баян для самостійного вирішення:

Завдання 11

У ліфт 12-поверхового будинку сіли 3 пасажири. Кожен, незалежно від інших, з однаковою ймовірністю може вийти на будь-якому (починаючи з 2-го) поверсі. Скількими способами:

1) пасажири можуть вийти на тому самому поверсі (Порядок виходу не має значення);
2) дві людини можуть вийти на одному поверсі, а третя – на іншому;
3) люди можуть вийти різних поверхах;
4) пасажири можуть вийти із ліфта?

І тут часто перепитують, уточнюю: якщо 2 чи 3 особи виходять на одному поверсі, то черговість виходу не має значення. ДУМАЙТЕ, використовуйте формули та правила додавання/множення комбінацій. У разі труднощів пасажирам корисно дати імена та поміркувати, у яких комбінаціях вони можуть вийти з ліфта. Не треба засмучуватися, якщо щось не вийде, наприклад, пункт № 2 досить підступний.

Повне рішення із докладними коментарями наприкінці уроку.

Заключний параграф присвячений комбінаціям, які теж зустрічаються досить часто – за моєю суб'єктивною оцінкою, приблизно 20-30% комбінаторних завдань:

Перестановки, поєднання та розміщення з повтореннями

Перелічені види комбінацій законспектовані у пункті № 5 довідкового матеріалу Основні формули комбінаторикиПроте деякі з них за першим прочитанням можуть бути не дуже зрозумілими. І тут спочатку доцільно ознайомитися з практичними прикладами, і лише потім осмислювати загальне формулювання. Поїхали:

Перестановки із повтореннями

У перестановках із повтореннями, як і в «звичайних» перестановках, бере участь відразу все безліч об'єктів, але є одне але: в даному множині один або більша кількість елементів (об'єктів) повторюються. Зустрічайте черговий стандарт:

Завдання 12

Скільки різних буквосполучень можна отримати перестановкою карток із наступними літерами: К, О, Л, О, К, О, Л, Ь, Ч, І, К?

Рішення: у тому випадку, якби всі літери були різні, то слід було б застосувати тривіальну формулу , проте цілком зрозуміло, що для запропонованого набору карток деякі маніпуляції спрацьовуватимуть «вхолосту», наприклад, якщо поміняти місцями будь-які дві картки з літерами «К » у будь-якому слові, то вийде те саме слово. Причому фізично картки можуть сильно відрізнятися: одна бути круглою з надрукованою літерою «К», інша – квадратною з намальованою літерою «К». Але за змістом завдання навіть такі картки вважаються однаковими, оскільки в умові питається про буквосполучення.

Все дуже просто – всього: 11 карток, серед яких літера:

К - повторюється 3 рази;
Про - повторюється 3 рази;
Л – повторюється двічі;
Ь - повторюється 1 раз;
Ч – повторюється 1 раз;
І – повторюється один раз.

Перевірка: 3 + 3 + 2 + 1 + 1 + 1 = 11, що потрібно перевірити.

За формулою кількості перестановок із повтореннями:
різних буквосполучень можна отримати. Більше півмільйона!

Для швидкого розрахунку великого факторіального значення зручно використовувати стандартну функцію Екселю: забиваємо в будь-яку комірку =ФАКТР(11)і тиснемо Enter.

На практиці цілком допустимо не записувати загальну формулу і, крім того, опускати поодинокі факторіали:

Але попередні коментарі про літери, що повторюються, обов'язкові!

Відповідь: 554400

Інший типовий приклад перестановок з повтореннями зустрічається в задачі про розміщення шахових фігур, яку можна знайти на складі готових рішеньу відповідній pdf-ці. А для самостійного рішення я вигадав менш шаблонне завдання:

Завдання 13

Олексій займається спортом, причому 4 дні на тиждень – легкою атлетикою, 2 дні – силовими вправами та 1 день відпочиває. Скільки способами він може скласти собі розклад занять на тиждень?

Формула тут не годиться, оскільки враховує збігаються перестановки (наприклад, коли міняються місцями силові вправи у середу із силовими вправами у четвер). І знову - за фактом ті ж 2 силові тренування можуть сильно відрізнятися один від одного, але за контекстом завдання (з точки зору розкладу) вони вважаються однаковими елементами.

Дворядкове рішення та відповідь наприкінці уроку.

Поєднання з повтореннями

Характерна риса цього виду комбінацій у тому, що вибірка проводиться із кількох груп, кожна у тому числі складається з однакових об'єктів.

Сьогодні всі добре попрацювали, тому настав час підкріпитись:

Завдання 14

У студентській їдальні продають сосиски в тесті, ватрушки та пончики. Скільки можна придбати п'ять пиріжків?

Рішення: відразу зверніть увагу на типовий критерій поєднань із повтореннями – за умовою на вибір запропоновано не безліч об'єктів як таке, а різні видиоб'єктів; при цьому передбачається, що у продажу є не менше п'яти хот-догів, 5 ватрушок та 5 пончиків. Тістечка в кожній групі, зрозуміло, відрізняються - бо абсолютно ідентичні пончики можна змоделювати хіба що на комп'ютері =) Проте фізичні характеристики пиріжків за змістом завдання не суттєві, і хот-доги/ватрушки/пончики у своїх групах вважаються однаковими.

Що може бути у вибірці? Насамперед, слід зазначити, що у вибірці обов'язково будуть однакові пиріжки (обираємо 5 штук, а на вибір запропоновано 3 види). Варіанти тут на будь-який смак: 5 хот-догів, 5 ватрушок, 5 пончиків, 3 хот-доги + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончики і т.д.

Як і при «звичайних» поєднаннях, порядок вибору та розміщення пиріжків у вибірці не має значення – просто вибрали 5 штук та все.

Використовуємо формулу кількості поєднань із повтореннями:
способом можна придбати 5 пиріжків.

Смачного!

Відповідь: 21

Який висновок можна зробити із багатьох комбінаторних завдань?

Іноді найважче – це розібратися в умові.

Аналогічний приклад для самостійного вирішення:

Завдання 15

У гаманці знаходиться досить велика кількість 1-, 2-, 5- та 10-рублевих монет. Скільки способами можна витягти три монети з гаманця?

З метою самоконтролю дайте відповідь на кілька простих питань:

1) Чи можуть у вибірці всі монети бути різними?
2) Назвіть найдешевшу і найдорожчу комбінацію монет.

Рішення та відповіді наприкінці уроку.

З мого особистого досвіду, можу сказати, що поєднання з повтореннями – найрідкісніший гість на практиці, чого не скажеш про такий вид комбінацій:

Розміщення з повтореннями

З множини, що складається з елементів, вибирається елементів, при цьому важливий порядок елементів у кожній вибірці. І все було б нічого, але досить несподіваний прикол полягає в тому, що будь-який об'єкт вихідної множини ми можемо вибирати скільки завгодно разів. Образно кажучи, від «багато не убуде».

Коли таке буває? Типовим прикладом є кодовий замок з кількома дисками, але через розвиток технологій актуальніше розглянути його цифрового нащадка:

Завдання 16

Скільки існує чотиризначних пін-кодів?

Рішення: насправді для розрулювання завдання достатньо знань правил комбінаторики: способами можна вибрати першу цифру пін-коду іспособами – другу цифру пін-коду істільки ж способами – третю істільки ж – четверту. Таким чином, за правилом множення комбінацій, чотиризначний пін-код можна скласти: способами.

А тепер за допомогою формули. За умовою нам запропоновано набір із цифр, з якого вибираються цифри та розташовуються у визначеному порядку, при цьому цифри у вибірці можуть повторюватися (тобто будь-якою цифрою вихідного набору можна користуватися довільну кількість разів). За формулою кількості розміщень із повтореннями:

Відповідь: 10000

Що тут спадає на думку… …якщо банкомат «з'їдає» картку після третьої невдалої спроби введення пін-коду, то шанси підібрати його навмання дуже примарні.

І хто сказав, що у комбінаториці немає жодного практичного сенсу? Пізнавальне завдання для всіх читачів сайт:

Завдання 17

Згідно з державним стандартом, автомобільний номерний знак складається з 3 цифр та 3 літер. При цьому неприпустимий номер із трьома нулями, а літери вибираються з набору А, В, Е, К, М, Н, О, Р, С, Т, У, Х (використовуються лише ті літери кирилиці, написання яких збігається з латинськими літерами).

Скільки номерних знаків можна скласти для регіону?

Не так їх, до речі, багато. У великих регіонах такої кількості не вистачає, і тому для них існує кілька кодів до напису RUS.

Рішення та відповідь наприкінці уроку. Не забуваємо використовувати правила комбінаторики;-) …Хотів похвалитися ексклюзивом, та виявилося не ексклюзивом =) Заглянув у Вікіпедію – там є розрахунки, щоправда, без коментарів. Хоча у навчальних цілях, напевно, мало хто вирішував.

Наше захоплююче заняття добігло кінця, і насамкінець я хочу сказати, що ви не дарма витратили час – з тієї причини, що формули комбінаторики знаходять ще одне насущне практичне застосування: вони зустрічаються в різних завданнях теорії ймовірностей,
і в завдання на класичне визначення ймовірності- Особливо часто =)

Дякую всім за активну участь і до швидких зустрічей!

Рішення та відповіді:

Завдання 2: Рішення: знайдемо кількість всіх можливих перестановок 4 карток:

Коли картка з нулем розташовується на 1-му місці, то число стає тризначним, тому ці комбінації слід виключити. Нехай нуль знаходиться на 1-му місці, тоді 3 цифри, що залишилися, в молодших розрядах можна переставити способами.

Примітка : т.к. карток небагато, то тут нескладно перерахувати всі такі варіанти:
0579
0597
0759
0795
0957
0975

Таким чином, із запропонованого набору можна скласти:
24 - 6 = 18 чотиризначних чисел
Відповідь : 18

Завдання 4: Рішення: способами можна вибрати 3 карти з 36
Відповідь : 7140

Завдання 6: Рішення: методами.
Інший варіант вирішення : способами можна вибрати двох осіб з групи та
2) «Найдешевший» набір містить 3 рублеві монети, а «найдорожчий» – 3 десятирублеві.

Завдання 17: Рішення: способами можна скласти цифрову комбінацію автомобільного номера, причому одну з них (000) слід виключити: .
способами можна скласти літерну комбінацію автомобільного номера.
За правилом множення комбінацій, всього можна скласти:
автомобільних номерів
(кожнацифрова комбінація поєднується з кожноюлітерною комбінацією).
Відповідь : 1726272

Комбінаторні завдання

1 . Катя, Маша та Іра грають із м'ячем. Кожна з них має по одному разу кинути м'яч у бік кожної подруги. Скільки разів кожна дівчинка повинна кидати м'яч? Скільки разів буде підкидатися м'яч? Визначте, скільки разів підкидатиметься м'яч, якщо у грі візьмуть участь: четверо дітей; п'ятеро дітей.

2 . Дано три фасади і два дахи, що мають однакову форму, але розфарбовані в різні кольори: фасади - у жовтий, синій та червоний кольори, а дахи - у синій та червоний кольори. Які будиночки можна звести? Скільки всього комбінацій?

3 . Дано три однакові за формою фасади будиночка: синій, жовтий і червоний - і три дахи: синій, жовтий і червоний. Які будиночки можна звести? Скільки всього комбінацій?

4 . Малюнки на прапорцях можуть мати вигляд кола, квадрата, трикутника чи зірки, причому їх можна розфарбувати у зелений чи червоний колір. Скільки всього може бути різних прапорців?

5. У шкільній їдальні на обід приготували як другі страви м'ясо, котлети та рибу. На солодке - морозиво, фрукти та пиріг. Можна вибрати одну другу страву та одну страву на десерт. Скільки є різних варіантів обіду?

6. У шкільній їдальні на обід приготували як перші страви суп з м'ясом і вегетаріанський суп, на друге - м'ясо, котлети та рибу, на солодке - морозиво, фрукти та пиріг. Скільки існує різних варіантів обіду із трьох страв?

7. Скільки можна розсадити в ряд на стільці трьох учнів? Виписати усі можливі випадки.

8 . Скільки способами можуть чотири (п'ять) чоловік стати в ряд?

9 . З різних боків на пагорб піднімаються три стежки та сходяться на вершині. Складіть безліч маршрутів, якими можна піднятися на пагорб і спуститися з нього. Розв'яжіть те саме завдання, якщо вгору і вниз треба йти різними стежками.

10 . З Акулово до Рибниці ведуть три дороги, а з Рибниці до Китового – чотири дороги. Скільки способами можна проїхати з Акулово в Китове через Рибницю?

11 . Склад називається відкритим, якщо він починається із приголосної літери, а закінчується голосною. Скільки відкритих дволітерних складів можна написати, використовуючи літери "а", "б", "в", "г", "е", "і", "о"? Випишіть ці склади.

12. Скільки різних варіантів костюмів з блузки та спідниці можна скласти, якщо є 4 блузки та 4 спідниці?

13. Коли Петя йде до школи, він іноді зустрічає одного чи кількох своїх приятелів: Васю, Леню, Толю. Перелічити всі можливі випадки, які можуть бути.

14 . Записати всі можливі двоцифрові числа, використовуючи цифри 7 і 4.

15 . Мишко запланував купити: олівець, лінійку, блокнот та зошит. Сьогодні він купив лише два різні предмети. Що міг купити Мишко, якщо вважати, що в магазині були всі необхідні йому навчальні приналежності?

16 . Чотири особи обмінялися рукостисканнями. Скільки було всього рукостискань?

17 . Скільки існує двоцифрових чисел, у запису яких відсутня цифра 0?

18 . Записати всі можливі трицифрові числа, які можна скласти з цифр 1 і 2.

19 . Виписати всі можливі парні трицифрові числа, складені з цифр 1 і 2.

20 . Записати всі можливі двоцифрові числа, при записі яких використовуються цифри 2, 8 і 5.

21 . Скільки існує різних двоцифрових чисел, усі цифри яких непарні?

22 . Які трицифрові числа можна записати за допомогою цифр 3, 7 та 1 за умови, що в записі числа не повинно бути однакових цифр? Скільки таких чисел?

23 . Скільки трицифрових чисел можна становити з цифр 1, 2, 4, 6, якщо жодну цифру не використовувати більше одного разу? Скільки серед цих чисел буде парних? Скільки непарних?

24 . В машині п'ять місць. Скільки способами п'ять людей можуть сісти в цю машину, якщо зайняти місце водія можуть лише двоє з них?

25. У класі 5 одномісних парт. Скількими способами можна розсадити на них двох (трьох) школярів, що знову прибули?

26 . Згадайте байку І. Крилова «Квартет»:

Проказниця Мавпа, Осел, Козел і клишоногий Ведмедик почали грати Квартет. Вдарили в смички, б'ють, а толку немає. «Стій, братики, стій! - кричить Мавпа. - Стривайте! Як йти музиці? Ви ж не так сидите». Скільки у різний спосіб можуть спробувати сісти ці музиканти? Чи може це покращити якість їхньої гри?

27 . Хлопчиків і дівчаток розсаджують у ряд на розташовані місця, причому хлопчики сідають на непарні місця, а дівчатка - на парні. Скільки способами можна це зробити, якщо:

а) на 6 місць розсаджують 3 хлопчиків та 3 дівчаток;

б) на 10 місць розсаджують 5 хлопчиків та 5 дівчаток?

28 . На порожню шашкову дошку треба помістити дві шашки – чорну та білу. Скільки різних положень можуть займати на дошці?

29. Нехай номер автомобіля складається з двох літер, за якими йдуть дві цифри, наприклад АВ-53. Скільки різних номерів можна скласти, якщо використовувати 5 літер та 6 цифр?

30 . Номер автомобіля складається з трьох літер та чотирьох цифр. Скільки існує різних автомобільних номерів (три літери беруться із 29 літер російського алфавіту)?

31 . Нехай вам потрібно було сходити до бібліотеки, ощадного банку, на пошту і віддати в ремонт черевики. Щоб вибрати найкоротший маршрут, необхідно розглянути всі можливі варіанти. Скільки існує варіантів шляху, якщо бібліотека, ощадна каса, пошта та шевська майстерня розташовані далеко один від одного?

32. Нехай вам потрібно було сходити до бібліотеки, ощадного банку, на пошту і віддати в ремонт черевики. Щоб вибрати найкоротший маршрут, необхідно розглянути всі можливі варіанти. Скільки існує розумних варіантів шляху, якщо бібліотека та пошта знаходяться поруч, але значно віддалені від ощадної каси та шевської майстерні, які розташовані далеко один від одного?

33. Серед пасажирів, що їдуть у вагоні, йшло жваве обговорення чотирьох журналів. Виявилося, що кожен виписує два журнали, причому кожна з можливих комбінацій двох журналів виписується однією людиною. Скільки людей було у цій групі?

34 . Є п'ять кубиків, які відрізняються один від одного лише кольором: 2 червоні, 1 білий і 2 чорні. Є два ящики А і Б, причому в А міститься 2 кубики, а в Б - 3. Скільки різними способами можна розмістити ці кубики в ящиках А і Б?

35. Щоб принести цареві-батюшці молодильні яблука, повинен Іван-царевич знайти єдиний вірний шлях до чарівного саду. Зустрів Іван-царевич на роздоріжжі трьох доріг старого ворона і ось які поради від нього почув:

1) йди зараз правою стежкою;

2) на наступному роздоріжжі не вибирай праву стежку;

3) на третій розвилці не ходи лівою стежкою.

Голуб, що пролітав повз, шепнув Івану-царевичу, що тільки одна порада ворона вірна і що обов'язково треба пройти стежками різних напрямків. Наш герой виконав завдання та потрапив у чарівний сад. Яким маршрутом він скористався?

Написати програму, яка порівнює два введені з клавіатури цілих числа. Програма повинна вказати, яке число більше, або якщо числа рівні, вивести відповідне повідомлення.

Введіть два цілих числа та натисніть Enter.
-> 34 67
34 менше 67

with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure main is A, B: Integer; begin Put_Line("Введіть в одному рядку два цілих числа і натисніть Enter."); Put("->"); Get(A); Get(B); --Вводимо 2 числа if A > B then Put(Item =>; A, Width =>; 1); Put("більше"); Put(Item => B, Width => 1); elsif A< B then Put(Item =>A, Width => 1); Put("менше"); Put(Item => B, Width => 1); else Put("Введені числа рівні!"); end if; end main;

Дано три цілих числа. Знайдіть найбільше з них (програма повинна вивести одне ціле число). Під найбільшим у цій задачі розуміється число, яке не менше, ніж будь-яке інше.

• 
  -> 1 2 3
  Максимальне із трьох чисел: 3

• with Ada.Text_IO ; use Ada.Text_IO ; with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; procedure main is A, B, C: Integer; max: Integer; begin Put_Line( "Введіть три рядки в одному рядку і натисніть клавішу Enter."); Put("->"); Get(A); Get(B); Get(C); --Вводимо три цілих числа max: = A; --за умовчанням вважаємо, що число A - максимальне if B > max then --Якщо B більше максимального, то max: = B; --максимальне число дорівнює B end if; if C > max then --Якщо C більше максимального, то max: = C; --максимальне число дорівнює C end if; Put( "Максимальне з трьох чисел:"& Integer"image(max) ) ; end main;

  with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure main is A, B, C: Integer; max: Integer; begin Put_Line("Введіть в одному рядку три цілих числа та натисніть Enter."); Put("->"); Get(A); Get(B); Get(C); --Вводимо три цілих числа max: = A; --за умовчанням вважаємо, що число A - максимальне if B > max then --Якщо B більше максимального, то max: = B; -максимальне число дорівнює B end if; if C > max then - Якщо C більше максимального, то max: = C; -максимальне число дорівнює C end if; Put("Максимальне з трьох чисел:" & Integer"image(max)); end main;

Дано три натуральні числа A, B, C. Визначте, чи існує трикутник з такими сторонами. Якщо трикутник існує, виведіть повідомлення про те, що трикутник з такими сторонами існує, інакше виведіть, що трикутник не існує.

• Введіть три сторони трикутника та натисніть Enter.
  -> 3 4 5
  Трикутник із сторонами 3, 4, 5 існує.

Трикутник - це три точки, що не лежать на одній прямій. Трикутник існує лише тоді, коли сума будь-яких двох сторін більша за третю.

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; --Для читання цілих чисел with Ada.Text_IO ; use Ada.Text_IO ; --Для виведення рядків procedure main is a, b, c: Integer; begin Put_Line( "Введіть три сторони трикутника та натисніть Enter.Enter."); Put("->"); Get(a) ; Get(b); Get(c) ; --Зчитуємо сторони трикутника if a + b > c and then b + c > a and then c + a > b then --Перевірка всіх умов в одному рядку Put( "Трикутник зі сторонами"& Integer"image(a) & "," & Integer"image(b) & "," & Integer"image(c) & "існує" ) ;else Put( "Трикутник зі сторонами"& Integer"image(a) & "," & Integer"image(b) & "," & Integer"image(c) & "не існує" ) ;end if ;end main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; --Для читання цілих чисел with Ada.Text_IO; use Ada.Text_IO; --Для виведення рядків procedure main is a, b, c: Integer; begin Put_Line("Введіть три сторони трикутника та натисніть Enter.Enter."); Put("->"); Get(a); Get(b); Get(c); --Зчитуємо сторони трикутника if a + b > c and then b + c > a and then c + a > b then --Перевірка всіх умов в одному рядку Put("Трикутник зі сторонами" & Integer"image(a) & " ," & Integer"image(b) & "," & Integer"image(c) & "існує");else Put("Трикутник зі сторонами" & Integer"image(a) & "," & Integer"image( b) & "," & Integer"image(c) & "не існує"); end if; end main;

Дано три цілих числа. Визначте, скільки з них збігаються. Програма повинна вивести одне з чисел: 3 (якщо всі збігаються), 2 (якщо два збігаються) або 0 (якщо всі числа є різними).

• Введіть три цілих числа та натисніть Enter.
  -> 1 2 3
  0

• with Ada.Text_IO ; use Ada.Text_IO ; with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; procedure Main is A, B, C: Integer; begin Put_Line( "Введіть три цілих числа та натисніть Enter."); Put("->"); Get(A); Get(B); Get(C); if A = B and then A = C then --Якщо збігаються всі три числа Put (Item => 3, Width => 1); elsif A = B або A = C або B = C then --Якщо збігаються два числа Put (Item => 2, Width => 1); else --Якщо однакових чисел немає Put (Item => 0, Width => 1); end if; end Main;

  with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Main is A, B, C: Integer; begin Put_Line("Введіть три цілих числа та натисніть Enter."); Put("->"); Get(A); Get(B); Get(C); if A = B and then A = C then - Якщо збігаються всі три числа Put (Item => 3, Width => 1); elsif A = B або A = C або B = C then --Якщо збігаються два числа Put(Item => 2, Width => 1); else - Якщо однакових чисел немає Put (Item => 0, Width => 1); end if; end Main;

Шахова тура ходить по горизонталі або вертикалі. Дано дві різні клітини шахової дошки, визначте, чи може тура потрапити з першої клітини на другу одним ходом. Програма отримує на вхід чотири числа від 1 до 8 кожне, що задають номер стовпця і рядок спочатку для першої клітини, потім для другої клітини. Програма повинна вивести "ТАК" якщо з першої клітини ходом човна можна потрапити в другу або "НІ" в іншому випадку.

• 
  4 4
  5 5
  НІ

• ); Put(); Get(A); Get(B); Put(); Get(C); Get(D); if A = C або B = D then Put("ТАК") ; else Put("НІ"); end if; end Main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure Main is subtype checkBoard is Integer range 1..8; A, B, C, D: checkBoard; begin Put_Line("Введіть номери стовпців та рядків для двох клітин:"); Put("Введіть номери стовпця та рядки для першої клітинки і натисніть: "); Get(A); Get(B); Put("Введіть номери стовпця та рядки для другої клітини і натисніть: "); Get(C); Get(D); if A = C або B = D then Put("ТАК"); else Put("НІ"); end if; end Main;

Шаховий король ходить по горизонталі, вертикалі та діагоналі, але тільки на 1 клітинку. Дано дві різні клітини шахівниці, визначте, чи може король потрапити з першої клітини на другу одним ходом. Програма отримує на вхід чотири числа від 1 до 8 кожне, що задають номер стовпця і рядок спочатку для першої клітини, потім для другої клітини. Програма повинна вивести "ТАК", якщо з першої клітини ходом короля можна потрапити в другу або "НІ" в іншому випадку.

• Введіть номери стовпців та рядків для двох клітинок:
  Введіть номери стовпця та рядки для першої клітинки та натисніть: 4 4
  Введіть номери стовпця та рядки для другої клітини та натисніть: 5 5
  ТАК

• "Введіть номери стовпців та рядків для двох клітинок:"); Put( "Введіть номери стовпця та рядки для першої клітинки та натисніть: "); Get(A); Get(B); Put( "Введіть номери стовпця та рядки для другої клітини та натисніть: "); Get(C); Get(D); if abs (A - C)<= 1 and then abs (B - D) <= 1 then -- команда abs() повертає абсолютне --значення (модуль) числа Put("ТАК"); else Put("НІ"); end if; end main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure main is subtype checkBoard is Integer range 1..8; A, B, C, D: checkBoard; begin Put_Line("Введіть номери стовпців та рядків для двох клітин:"); Put("Введіть номери стовпця та рядки для першої клітинки і натисніть: "); Get(A); Get(B); Put("Введіть номери стовпця та рядки для другої клітини і натисніть: "); Get(C); Get(D); if abs(A - C)<= 1 and then abs(B - D) <= 1 then -- команда abs() возвращает абсолютное --значение (модуль) числа Put("ДА"); else Put("НЕТ"); end if; end main;

Шаховий слон ходить по діагоналі. Дано дві різні клітини шахової дошки, визначте, чи може слон потрапити з першої клітини на другу одним ходом. Програма отримує на вхід чотири числа від 1 до 8 кожне, що задають номер стовпця і рядок спочатку для першої клітини, потім для другої клітини. Програма повинна вивести "ТАК", якщо з першої клітини ходом слона можна потрапити в другу або "Ні" в іншому випадку.

• Введіть номери стовпців та рядків для двох клітинок:
  Введіть номери стовпця та рядки для першої клітинки та натисніть: 4 4
  Введіть номери стовпця та рядки для другої клітини та натисніть: 5 5
  ТАК

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure main is subtype checkBoard is Integer range 1 ..8; A, B, C, D: checkBoard; begin Put_Line( "Введіть номери стовпців та рядків для двох клітинок:"); Put( "Введіть номери стовпця та рядки для першої клітинки та натисніть: "); Get(A); Get(B); Put( "Введіть номери стовпця та рядки для другої клітини та натисніть: "); Get(C); Get(D); if abs (a - c) = abs (b - d) then Put("ТАК"); else Put("НІ"); end if; end main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure main is subtype checkBoard is Integer range 1..8; A, B, C, D: checkBoard; begin Put_Line("Введіть номери стовпців та рядків для двох клітин:"); Put("Введіть номери стовпця та рядки для першої клітинки і натисніть: "); Get(A); Get(B); Put("Введіть номери стовпця та рядки для другої клітини і натисніть: "); Get(C); Get(D); if abs(a - c) = abs(b - d) then Put("ТАК"); else Put("НІ"); end if; end main;

Шаховий ферзь ходить по діагоналі, горизонталі чи вертикалі. Дано дві різні клітини шахової дошки, визначте, чи може ферзь потрапити з першої клітини на другу одним ходом.

Формат вхідних даних:
Програма отримує на вхід чотири числа від 1 до 8 кожне, що задають номер стовпця і рядок спочатку для першої клітини, потім для другої клітини.
Формат вихідних даних:
Програма повинна вивести YES, якщо з першої клітини ходом ферзя можна потрапити у другу чи NO інакше.

Приклад 1:
Введіть номери стовпців та рядків для двох клітинок:
Введіть номери стовпця та рядки для першої клітинки та натисніть: 1 1
Введіть номери стовпця та рядки для другої клітини та натисніть: 2 2
ТАК

Приклад 2:
Введіть номери стовпців та рядків для двох клітинок:
Введіть номери стовпця та рядки для першої клітинки та натисніть: 1 1
Введіть номери стовпця та рядки для другої клітини та натисніть: 2 3
НІ

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure Main is subtype checkBoard is Integer range 1 ..8 ; A, B, C, D: checkBoard; begin Put_Line( "Введіть номери стовпців та рядків для двох клітинок:"); Put( "Введіть номери стовпця та рядки для першої клітинки та натисніть: "); Get(A); Get(B); Put( "Введіть номери стовпця та рядки для другої клітини та натисніть: "); Get(C); Get(D); if abs (A - C) = abs (B - D) або A = D або B = C then Put ("ТАК") ; else Put("НІ"); end if; end Main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure Main is subtype checkBoard is Integer range 1..8; A, B, C, D: checkBoard; begin Put_Line("Введіть номери стовпців та рядків для двох клітин:"); Put("Введіть номери стовпця та рядки для першої клітинки і натисніть: "); Get(A); Get(B); Put("Введіть номери стовпця та рядки для другої клітини і натисніть: "); Get(C); Get(D); if abs (A - C) = abs (B - D) або A = D або B = C then Put ("ТАК"); else Put("НІ"); end if; end Main;

Шаховий кінь ходить буквою "Г" - на дві клітинки по вертикалі в будь-якому напрямку та на одну клітинку по горизонталі, або навпаки. Дано дві різні клітини шахової дошки, визначте, чи може кінь потрапити з першої клітини на другу одним ходом. Програма отримує на вхід чотири числа від 1 до 8 кожне, що задають номер стовпця і рядок спочатку для першої клітини, потім для другої клітини. Програма повинна вивести YES, якщо з першої клітини ходом коня можна потрапити у другу чи NO інакше.

Приклад 1:
Введіть номери стовпців та рядків для двох клітинок:
Введіть номери стовпця та рядки для першої клітинки та натисніть: 1 1
Введіть номери стовпця та рядки для другої клітини та натисніть: 1 4
НІ

Приклад 2:
Введіть номери стовпців та рядків для двох клітинок:
Введіть номери стовпця та рядки для першої клітинки та натисніть: 1 1
Введіть номери стовпця та рядки для другої клітини та натисніть: 8 8
НІ

• with Ada.Text_IO ; use Ada.Text_IO ; with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; procedure main is subtype checkBoard is Integer range 1 ..8; A, B, C, D: Integer; begin Put_Line( "Введіть номери стовпців та рядків для двох клітинок:"); Put( "Введіть номери стовпця та рядки для першої клітинки та натисніть: "); Get(A); Get(B); Put( "Введіть номери стовпця та рядки для другої клітини та натисніть: "); Get(C); Get(D); if abs (A - C) = 2 and then abs (B - D) = 1 then Put("ТАК") ; elsif abs (A - C) = 1 and then abs (B - D) = 2 then Put("ТАК") ; else Put("НІ"); end if; end main;

  with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure main is subtype checkBoard is Integer range 1..8; A, B, C, D: Integer; begin Put_Line("Введіть номери стовпців та рядків для двох клітин:"); Put("Введіть номери стовпця та рядки для першої клітинки і натисніть: "); Get(A); Get(B); Put("Введіть номери стовпця та рядки для другої клітини і натисніть: "); Get(C); Get(D); if abs(A - C) = 2 and then abs(B - D) = 1 then Put("ТАК"); elsif abs(A - C) = 1 and then abs(B - D) = 2 then Put("ТАК"); else Put("НІ"); end if; end main;

Шоколадка має вигляд прямокутника, розділеного на N×M часточок. Шоколадку можна один раз розламати по прямій на дві частини. Визначте, чи можна таким чином відламати від шоколадки рівно K часточок. Програма отримує на вхід три числа: N, M, K. Програма має вивести одне з двох слів: "ТАК" або "Ні".

Приклад 1:
4
2
6
ТАК

Приклад 2:
Кількість часточок по горизонталі: 2
Кількість часточок по вертикалі: 10
Скільки часточок потрібно відокремити: 7
НІ

• with Ada.Text_IO ; use Ada.Text_IO ; with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; procedure Main is N, M, K: Integer; begin Put( "Кількість часточок по горизонталі: "); Get(N); Put( "Кількість часточок по вертикалі: "); Get(M); Put( "Скільки часточок потрібно відокремити:"); Get(K); if K > M * N then --Якщо від шоколадки просять відламати більше, ніж сама шоколадка Put("НІ"); elsif K rem N = 0 and then K >= N then - Відламуємо по горизонталі Put("ТАК"); elsif K rem M = 0 and then K >= M then - Відламуємо по вертикалі Put("ТАК"); else Put("НІ"); end if; end Main;

  with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Main is N, M, K: Integer; begin Put("Кількість часточок по горизонталі:"); Get(N); Put("Кількість часточок по вертикалі: "); Get(M); Put("Скільки часточок потрібно відокремити:"); Get(K); if K > M * N then - Якщо від шоколадки просять відламати більше, ніж сама шоколадка Put ("НІ"); elsif K rem N = 0 and then K> = N then - Відламуємо по горизонталі Put ("ТАК"); elsif K rem M = 0 and then K> = M then - Відламуємо по вертикалі Put ("ТАК"); else Put("НІ"); end if; end Main;

Яша плавав у басейні розміром N×M метрів та втомився. У цей момент він виявив, що знаходиться на відстані X метрів від одного з довгих бортів (не обов'язково від найближчого) та Y метрів від одного з коротких бортів. Яку мінімальну відстань має пропливти Яша, щоб вибратися з басейну на борт? Програма отримує на вхід числа N, M, X, Y. Програма повинна вивести число метрів, яке потрібно пропливти Яше до борту.

• Ширина басейну: 23
  Довжина басейну: 52
  Відстань від Яші до довгого борту: 8
  Відстань від Яші до короткого борту: 43
  Потрібно пропливти мінімум, щоб вибратися з басейну: 8

Можливо, що для вирішення завдання Вам потрібно буде поміняти місцями 2 змінні. Цей алгоритм виглядає приблизно так:

a, b, tmp: Integer; --Оголошення змінних. Дві основні та одна допоміжна a:= 3; -Ініціалізація змінної a b: = 5; - Ініціалізація змінної b - Безпосередньо сам алгоритм: tmp: = a; --Тепер tmp = 3 та a = 3 a:= b; --Тепер a = 5 та b = 5; b: = tmp; --Тепер b = 3

• with Ada.Text_IO ; use Ada.Text_IO ; with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; procedure Main is N, M, X, Y: Integer; -- N - короткий бортик, M - довгий бортик: -- X - Відстань до одного з довгих бортиків -- Y - Відстань до одного з коротких бортиків Tmp: Integer; begin Put( "Ширина басейну:"); Get(N); Put( "Довжина басейну:"); Get(M); Put( "Відстань від Яші до довгого бортика:"); Get(X); Put( "Відстань від Яші до короткого борту:"); Get(Y); if N > M then --Якщо при введенні переплутані борти, то міняємо їх місцями: Tmp: = M; --Зберігаємо довжину M у тимчасову змінну M:= N; --Надаємо змінній M нове значення N: = Tmp; --Відновлюємо довжину M у змінній N end if; Tmp: = X; --Припустимо, що мінімальна відстань дорівнює X if abs (N - X)< X then --Якщо до другого довгого бортика відстань менша за X, то Tmp: = N - X; -Мінімальна відстань дорівнює відстані до другого довгого бортика end if; if Y< Tmp then --Якщо до короткого бортика відстань менша за знайдену вище -Мінімального, то Tmp: = Y; --Мінімальна відстань дорівнює Y end if; if abs (M - Y)< Tmp then --Якщо до другого короткого бортика плисти ближче, то Tmp: = abs (M - Y); -Мінімальна відстань дорівнює відстані до другого короткого бортика end if; Put( "Потрібно пропливти мінімум, щоб вибратися з басейну:"); Put (Item => Tmp, Width => 1); end Main;

  with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Main is N, M, X, Y: Integer; -- N - короткий бортик, M - довгий бортик: -- X - Відстань до одного з довгих бортиків -- Y - Відстань до одного з коротких бортиків Tmp: Integer; begin Put("Ширина басейну:"); Get(N); Put("Довжина басейну: "); Get(M); Put("Відстань від Яші до довгого бортика: "); Get(X); Put("Відстань від Яші до короткого бортика: "); Get(Y); if N > M then - Якщо при введенні переплутані бортики, то міняємо їх місцями: Tmp: = M; --Зберігаємо довжину M у тимчасову змінну M:= N; --Привласнюємо змінною M нове значення N:= Tmp; --Відновлюємо довжину M у змінній N end if; Tmp: = X; --Припустимо, що мінімальна відстань дорівнює X if abs(N - X)< X then --Если до второго длинного бортика расстояние меньше X, то Tmp:= N - X; --минимальное расстояние равно расстоянию до второго длинного бортика end if; if Y < Tmp then --Если до короткого бортика расстояние меньше найденного выше --минимального, то Tmp:= Y; --Минимальное расстояние равно Y end if; if abs(M - Y) < Tmp then --Если до второго короткого бортика плыть ближе, то Tmp:= abs(M - Y); --минимальное расстояние равно расстоянию до второго короткого бортика end if; Put("Нужно проплыть минимум, чтобы выбраться из бассейна: "); Put(Item =>Tmp, Width => 1); end Main;

Електронний годинник показує час у форматі h:mm:ss (від 0:00:00 до 23:59:59), тобто спочатку записується кількість годин, потім обов'язково двозначна кількість хвилин, потім обов'язково двозначна кількість секунд. Кількість хвилин та секунд при необхідності доповнюються до двозначного числа нулями. З початку доби минуло N секунд. Виведіть, що покаже годинник. На вхід дається натурально число N, що не перевищує 107 (10000000). Виведіть відповідь на завдання.

Приклад введення 1:
3602
Приклад виведення 1:
1:00:02

Приклад введення 2:
129700
Приклад виведення 2:
12:01:40

• with Ada.Long_Integer_Text_IO ; use Ada.Long_Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure Main is subtype Sub_LI is Long_Integer range 1 ..10000000 ; N: Sub_LI; h, m, s: Long_Integer; begin Get(N) ; h:= N / 3600; -Отримуємо годинник. Залишок від розподілу відкидається N:= N - h * 3600; --Отримуємо секунди, що залишилися (за вирахуванням годин) if h > 24 then --Оскільки годинник не може показувати > 24, наводимо все в легкочитаний вигляд h:= h rem 24; - Залишок від розподілу на 24 дасть точну кількість годин elsif h = 24 then h:= 0; end if; m:= N/60; --Отримуємо хвилини s:= N rem 60; --Отримуємо секунди Put (Item => h, Width => 1); Put(":"); --Виведення годинника і ":" if m< 10 then --Якщо кількість хвилин менше 10, виводимо ведучий 0 Put (Item => 0, Width => 1); end if; Put (Item => m, Width => 1); Put(":"); --Виведення хвилин і ":" if s< 10 then --Якщо кількість секунд менше 10, виводимо ведучий 0 Put (Item => 0, Width => 1); end if; Put (Item => s, Width => 1); --Виведення секунд end Main;

  with Ada.Long_Integer_Text_IO; use Ada.Long_Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure Main is subtype Sub_LI is Long_Integer range 1..10000000; N: Sub_LI; h, m, s: Long_Integer; begin Get(N); h:= N/3600; -Отримуємо годинник. Залишок від розподілу відкидається N: = N - h * 3600; --Отримуємо секунди, що залишилися (за вирахуванням годин) if h > 24 then --Так як годинник не можуть показувати > 24, наводимо все в легкозчитуваний вигляд h: = h rem 24; --Залишок від розподілу на 24 дасть точну кількість годин elsif h = 24 then h:= 0; end if; m:= N/60; --Отримуємо хвилини s: = N rem 60; --Отримуємо секунди Put(Item => h, Width => 1); Put(":"); --Виведення годинника і ":" if m< 10 then --Если количество минут меньше 10, выводим ведущий 0 Put(Item =>0, Width => 1); end if; Put(Item => m, Width => 1); Put(":"); --Виведення хвилин і ":" if s< 10 then --Если количество секунд меньше 10, выводим ведущий 0 Put(Item =>0, Width => 1); end if; Put(Item => s, Width => 1); --Виведення секунд end Main;

• Дано три числа. Розташуйте їх у порядку зростання.
• Приклад введення:
  1 2 1
  Приклад висновку:
  1 1 2

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure Main is A, B, C: Integer; min, mid, max: Integer; begin Get(A) ; Get(B); Get(C); --Шукаємо мінімальне значення min: = A; if B< min then min:= B; end if ; if C < min then min:= C; end if ; --Шукаємо максимальне значення max: = A; if B > max then max:= B; end if; if C > max then max:= C; end if; --Шукаємо середнє значення mid: = A; якщо B > min and B< max then mid:= B; end if ; if C >min and C< max then mid:= C; end if ; Put(Item =>min, Width => 1); Put(""); Put(Item => mid, width => 1); Put(""); Put(Item => max, Width => 1); end Main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure Main is A, B, C: Integer; min, mid, max: Integer; begin Get(A); Get(B); Get(C); --Шукаємо мінімальне значення min: = A; if B< min then min:= B; end if; if C < min then min:= C; end if; --Ищем максимальное значение max:= A; if B >max then max:= B; end if; if C > max then max:= C; end if; --Шукаємо середнє значення mid: = A; якщо B > min and B< max then mid:= B; end if; if C >min and C< max then mid:= C; end if; Put(Item =>min, Width => 1); Put(" "); Put(Item => mid, width => 1); Put(" "); Put(Item => max, Width => 1); end Main;

Є дві коробки, перша розміром A1×B1×C1, друга розміром A2×B2×C2. Визначте, чи можна розмістити одну з цих коробок усередині іншої за умови, що повертати коробки можна лише на 90 градусів навколо ребер. Програма отримує вхід числа A1, B1, C1, A2, B2, C2. Програма повинна вивести один із наступних рядків:
- "Коробки рівні", якщо коробки однакові,
- "Перша коробка менша за другу", якщо перша коробка може бути покладена в другу,
- "Перша коробка більша за другу", якщо друга коробка може бути покладена в першу.

Приклад 1:
Розміри першої коробки: 1 2 3
Розміри другої коробки: 3 2 1
Коробки рівні

Приклад 2:
Розміри першої коробки: 2 2 3
Розміри другої коробки: 3 2 1
Перша коробка більша за другу

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure main is A1, B1, C1, A2, B2, C2: Integer; min, max, mid, tmp: Integer; begin Get(A1); Get(B1); Get(C1); Get(A2); Get(B2); Get(C2); --Наводимо грані у відповідність за довжинами A1 => A2, B1 => B2, C1 => C2: --A1 і A2 - найдовші, C1 і C2 - найкоротші - "Крутим" перший ящик: min: = A1; mid: = B1; max: = C1; if B1< min then mid:= min; min:= B1; end if ; if C1 < min then max:= min; min:= C1; end if ; if mid >max then tmp:= mid; mid: = max; max: = tmp; end if; A1: = min; B1: = mid; C1: = max; - "Крутим" другий ящик: min: = A2; mid:= B2; max: = C2; if B2< min then mid:= min; min:= B2; end if ; if C2 < min then max:= min; min:= C2; end if ; if mid >max then tmp:= mid; mid: = max; max: = tmp; end if; A2: = min; B2: = mid; C2: = max; --Перевірка відповідності ящиків та виведення результату: if A1 = A2 and then B1 = B2 and then C1 = C2 then Put_Line("Коробки рівні"); elsif A1 >= A2 and then B1 >= B2 and then C1 >= C2 then Put_Line( "Перша коробка більша за другу"); elsif A1<= A2 and then B1 <= B2 and then C1 <= C2 then Put_Line("Перша коробка менша за другу"); end if; end main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure main is A1, B1, C1, A2, B2, C2: Integer; min, max, mid, tmp: Integer; begin Get(A1); Get(B1); Get(C1); Get(A2); Get(B2); Get(C2); --Наводимо грані у відповідність за довжинами A1 => A2, B1 => B2, C1 => C2: --A1 і A2 - найдовші, C1 і C2 - найкоротші - "Крутимо" перший ящик: min:= A1 ; mid: = B1; max: = C1; if B1< min then mid:= min; min:= B1; end if; if C1 < min then max:= min; min:= C1; end if; if mid >max then tmp:= mid; mid: = max; max: = tmp; end if; A1: = min; B1: = mid; C1: = max; - "Крутимо" другий ящик: min: = A2; mid:= B2; max: = C2; if B2< min then mid:= min; min:= B2; end if; if C2 < min then max:= min; min:= C2; end if; if mid >max then tmp:= mid; mid: = max; max: = tmp; end if; A2: = min; B2: = mid; C2: = max; --Перевірка відповідності ящиків і виведення результату: if A1 = A2 і B1 = B2 і C1 = C2 Put_Line ("Коробки рівні"); elsif A1 >= A2 and then B1 >= B2 and then C1 >= C2 then Put_Line("Перша коробка більша за другу"); elsif A1<= A2 and then B1 <= B2 and then C1 <= C2 then Put_Line("Первая коробка меньше второй"); end if; end main;

Написати програму, яка обчислює вартість міжміської телефонної розмови (ціна однієї хвилини визначається відстанню до міста, в якому знаходиться абонент). Вихідними даними для програми є код міста та тривалість розмови. Нижче наведено коди деяких міст та рекомендований вигляд екрана під час роботи програми:

• Обчислення вартості розмови телефоном.
  Введіть вихідні дані:
  Код міста -> 423
  Тривалість (ціла кількість хвилин) -> 3
  Постачальник: Владивосток
  Ціна хвилини: 4 руб.
  Вартість розмови: 12 руб.

• with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO ; with Ada.Text_IO ; use Ada.Text_IO ; procedure Main is Code, Len: Integer; begin Put_Line ("Обчислення вартості розмови по телефону.") ; Put_Line ("Введіть вихідні дані:") ; Put ("Код міста ->") ; Get ( Code ) ; Put ("Тривалість (ціла кількість хвилин) ->") ; Get ( len ) ; case Code is when 423 => Put_Line ("Місто: Владивосток") ; Put_Line ("Ціна хвилини: 4 руб.") ; Put ("Вартість розмови:") ; Put ( Item => len * 4 , Width => 1 ) ; Put_Line ("Руб.") ; when 095 => Put_Line ("Місто Москва") ; Put_Line ("Ціна хвилини: 2 руб.") ; Put ("Вартість розмови:") ; Put ( Item => len * 2 , Width => 1 ) ; Put_Line ("Руб.") ; when 815 => Put_Line ("Місто: Мурманськ") ; Put_Line ("Ціна хвилини: 3 руб.") ; Put ("Вартість розмови:") ; Put ( Item => len * 3 , Width => 1 ) ; Put_Line ("Руб.") ; when 846 => Put_Line ("Місто Самара") ; Put_Line ("Ціна хвилини: 1 руб.") ; Put ("Вартість розмови:") ; Put ( Item => len, Width => 1 ) ; Put_Line ("Руб.") ; when others=> Put ("Міста з таким кодом у базі немає! Спробуйте ще.") ; end case; end Main;

  with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; with Ada.Text_IO; use Ada.Text_IO; procedure Main is Code, Len: Integer; begin Put_Line("Обчислення вартості розмови по телефону."); Put_Line("Введіть вихідні дані:"); Put("Код міста ->"); Get(Code); Put("Тривалість (ціла кількість хвилин) -> "); Get(len); case Code is when 423 => Put_Line("Місто: Владивосток"); Put_Line("Ціна хвилини: 4 руб."); Put("Вартість розмови: "); Put(Item => len * 4, Width => 1); Put_Line(" руб. "); when 095 => Put_Line("Місто: Москва"); Put_Line("Ціна хвилини: 2 руб."); Put("Вартість розмови: "); Put(Item => len * 2, Width => 1); Put_Line(" руб. "); when 815 => Put_Line("Місто: Мурманськ"); Put_Line("Ціна хвилини: 3 руб."); Put("Вартість розмови: "); Put(Item => len * 3, Width => 1); Put_Line(" руб. "); when 846 => Put_Line("Місто: Самара"); Put_Line("Ціна хвилини: 1 руб."); Put("Вартість розмови: "); Put(Item => len, Width => 1); Put_Line(" руб. "); when others => Put("Міста з таким кодом у базі немає! Спробуйте ще."); end case; end Main;

У розділі коротко описані оператори ifі case, функція abs()та алгоритм обміну змінних місцями.