Логічні завдання - Стор 2
Графом називають схему, в якій позначаються лише наявність об'єктів (елементів системи) та наявність та вид зв'язку між об'єктами. Об'єкти представляються у графі вершинами (на схемі вони позначаються кружальцями, прямокутниками тощо). Зв'язки між об'єктами представляються, якщо зв'язок односпрямований (позначається на схемі лініями зі стрілками) або ребрами, якщо зв'язок між об'єктами двосторонній (позначається на схемі лініями без стрілок). Наприклад, якщо потрібно уявити в графі, що зі стану А в стан В можливий перехід під впливом V, то це можна зобразити так: Якщо потрібно уявити, що к-тий учасник змагання зайняв n-е місце (або, що те саме, n-е місце зайняв к-тим учасником), це можна зобразити так:
Завдання 5.Марина, Лариса, Жанна та Катя вміють грати на різних інструментах (піаніно, віолончелі, гітарі, скрипці), але кожна лише на одному. Вони ж знають іноземні мови (англійська, французька, німецька та іспанська), але кожна лише одна. Відомо:
Дівчина, яка грає на гітарі, говорить іспанською.
Лариса не грає ні на скрипці, ні на віолончелі і не знає англійської мови.
Марина не грає ні на скрипці, ні на віолончелі і не знає ні німецької, ні англійської.
Дівчина, яка говорить німецькою, не грає на віолончелі.
Жанна знає французьку мову, але не грає на скрипці.
Хто на якому інструменті грає і яку іноземну мову знає?
Метод шостий: Метод блок-схем
У розділі розглядається ще один тип логічних завдань. Це завдання, в яких за допомогою судин відомих ємностей потрібно відміряти деяку кількість рідини, а також завдання, пов'язані з операцією зважування на вагах. Найпростіший прийом розв'язання завдань цього класу полягає у переборі можливих варіантів. Зрозуміло, що такий метод рішення не зовсім вдалий, у ньому важко виділити будь-який загальний підхід до вирішення інших подібних завдань.
Більш систематичний підхід до вирішення завдань "на переливання" полягає у використанні блок-схем. Суть цього методу полягає у наступному. Спочатку виділяються операції, які дозволяють нам точно вимірювати рідину. Ці операції називаються командами. Потім встановлюється послідовність виконання виділених команд. Ця послідовність оформляється як схеми. Подібні схеми називаються блок-схемами та широко використовуються у програмуванні. Складена блок-схема є програмою, виконання якої може призвести до вирішення поставленого завдання. Для цього достатньо зазначати, які кількості рідини вдається отримати під час роботи складеної програми. При цьому зазвичай заповнюють окрему таблицю, в яку заносять кількість рідини в кожному з судин.
Завдання 6.Є дві судини — трилітровий і п'ятилітровий. Потрібно, користуючись цими судинами, отримати 1, 2, 3, 4,5, 6, 7 та 8 літрів води. У нашому розпорядженні водопровідний кран та раковина, куди можна виливати воду.
Рішення.Перерахуємо всі можливі операції, які можуть бути використані нами, і введемо для них такі скорочені позначення: НБ - наповнити більшу посудину водою з-під крана; НМ - наповнити меншу посудину водою з-під крана; ПРО - спорожнити більшу посудину, вилив воду в раковину; ОМ - випорожнити меншу посудину, вилив воду в раковину; Б→М — перелити з більшого до меншого, доки більша посудина не спорожніє або менша посудина не наповниться; М→Б — перелити з меншого до більшого, доки менша посудина не спорожніє або більша посудина не наповниться. Виділимо серед перерахованих команд лише три: НБ, Б→М, ЗМ. Крім цих трьох команд розглянемо ще дві допоміжні команди: Б = 0? — подивитися, чи більша посудина; М = З? — подивитися, чи наповнена мала посудина. Залежно від результатів цього огляду ми переходимо до виконання наступної команди за одним із двох ключів - "так" чи "ні". Такі команди у програмуванні прийнято називати командами " умовного переходу " і зображати в блок-схемах як ромбика з двома ключами-выходами. Домовимося тепер про послідовність виконання виділених команд. Після Б→М будемо виконувати ОМ щоразу, як менша посудина виявляється наповненою, і НБ щоразу, як більша посудина буде випорожнена. Послідовність команд зобразимо як блок-схеми (Рис. 1). Почнемо виконання програми. Фіксуватимемо, як змінюється кількість води в судинах, якщо діяти за наведеною схемою. Результати оформимо у вигляді таблиці (табл.)
Далі ця послідовність повністю повторюватиметься. З таблиці бачимо, що кількість води в обох судинах разом утворює таку послідовність: 0, 5, 2, 7, 4, 1,6, 3, 0 і т.д. Таким чином, діючи за наведеною схемою, можна відміряти будь-яку кількість літрів від 1 до 7. Щоб відміряти ще й 8 літрів, треба наповнити обидві судини.
Завдання 7.Серед чотирьох монет одна фальшива. Вона відрізняється масою, проте невідомо, легша вона чи важча. Маса справжньої монети 5 г. Як за допомогою двох зважувань на чашкових вагах виявити фальшиву монету, якщо є одна гира масою 5 г? Чи можна за цих умов упізнати, легша фальшива монета чи важча?
Рішення.Нехай m1, m2, m3, m4 - маси чотирьох монет відповідно, Г - маса гирі. Оформимо рішення як блок-схеми (див. рис.). Наведена схема задає програму, здійснення якої дозволяє встановити фальшиву монету та визначити, легша вона чи важча. Зважуванням у блок-схемі відповідають прямокутники – оператори умовного переходу. У схемі виділено перше та друге зважування горизонтальними лініями.
Сподіваємося, що Вам відома гра більярд за прямокутним столом із лузами. З'явившись до нашої ери в Індії та Китаї, більярд через багато століть перекочував до європейських країн – згадка про нього є в англійських літописах VI століття. В Україні більярд став відомий і поширився за Петра I.
Подібно до того, як азартна гра в кістки викликала до життя "обчислення" ймовірностей, гра в більярд послужила предметом серйозних наукових досліджень з механіки та математики. Уявіть горизонтальний більярдний стіл довільної форми, але без луз. По цьому столу без тертя рухається точкова куля, абсолютно пружно відбиваючись від бортів столу. Постає питання, якою може бути траєкторія цієї кульки? Пошуки відповіді це питання і послужили появі теорії математичного більярду чи теорії траєкторій.
Завдання на переливання рідин можна дуже легко вирішувати, викреслюючи більярдну траєкторію кулі, що відбивається від бортів столу, що має форму паралелограма. Розглянемо ту ж задачу, що й у попередньому розділі (Метод блок-схем).Завдання 8.Є дві судини — трилітровий і п'ятилітровий. Потрібно, користуючись цими судинами, одержати 1, 2, 3, 4, 5, 6, 7 та 8 літрів води. У нашому розпорядженні водопровідний кран та раковина, куди можна виливати воду.
Рішення.У розглянутій задачі сторони паралелограма повинні мати довжини 3 і 5 одиниць. По горизонталі відкладатимемо кількість води в літрах у 5-літровій посудині, а по вертикалі – у 3-літровій посудині. На всій паралелограмі нанесена сітка з однакових рівносторонніх трикутників (див. рис.1)
Більярдна куля може переміщатися лише вздовж прямих, що утворюють сітку на паралелограмі. Після удару з боку паралелограма куля відбивається і продовжує рух уздовж борту, що виходить з точки, де сталося зіткнення. При цьому кожна точка паралелограма, в якій відбувається зіткнення, повністю характеризує, скільки води знаходиться в кожній з судин. Нехай куля знаходиться в лівому нижньому кутку і після удару почне переміщатися вгору вздовж лівої бокової сторони паралелограма доти, доки не досягне верхньої сторони в точці А. Це означає, що ми повністю наповнили водою малу посудину. Відбивши пружно, куля покотиться вправо вниз і вдариться об нижній борт у точці, координати якої 3 по горизонталі і 0 по вертикалі. Це означає, що у великій посудині 3 літри води, а в малій посудині води немає, тобто ми перелили воду з малої посудини у велику посудину. Простежуючи подальший шлях кулі, і записуючи всі етапи його руху у вигляді окремої таблиці (табл.1),зрештою, ми потрапляємо в точку Н, яка відповідає стану, коли мала посудина порожня, а у великій посудині 4 літри води. Таким чином, отримано відповідь та вказано послідовність переливань, що дозволяють відміряти 4 літри води. Усі 8 переливань зображені схематично у таблиці. Чи є це рішення найкоротшим? Ні, існує другий шлях, коли воду спочатку наливають у п'ятилітрову посудину. Якщо на діаграмі куля з точки Про покотиться вправо по нижній стороні паралелограма і потім, відбившись від правої бічної сторони, точку 2 на верхній стороні паралелограма і т.д., то отримаємо більш коротке рішення задачі. Можна показати, що отримане рішення з 6 переливання вже є найкоротшим.
Скарбничка цікавих завдань
Левін, Мітерєв, Набатов працюють у банку, як бухгалтер, касир і економіст. Якщо Набатов – економіст, Мітерєв – бухгалтер. Якщо Мітерєв – не касир, то Левін – не економіст. Якщо Левін – бухгалтер, то Набатов – економіст. Хто яку посаду обіймає?
У змаганнях з гімнастики беруть участь: Аня, Валя, Таня та Даша. Уболівальники будують прогнози: 1) Таня займе І місце, Валя – ІІ; 2) Таня займе ІІ місце, Даша – ІІІ; 3) Аня займе II місце, Даша – IV. Після закінчення змагань виявилося, що у кожному припущенні лише одне з висловлювань кожного вболівальника істинно, інше – хибно. Якими є результати змагань, якщо на кожному місці по одній дівчині?
Незнайко почув розмову Сиропчика, Пилюлькіна, Торопижки та Знайки. Відомо, що кожен із них або завжди бреше, або завжди говорить правду. 1) Сиропчик звинуватив Пилюлькина у цьому, що він – брехун. 2) Знайка сказав Сиропчику: «Сам ти брехун!». 3) Поспіх помітив: «Обидва вони брехуни». 4) Знайка запитав Зірку «А я?». 5) На що Торопижка відповів «Іти теж брехун! Хто ж із них говорить правду? - здивувався Незнайко. Допоможіть йому.
У класі 36 осіб. 18 осіб відвідують математичний гурток, 14 фізичний, 10 хімічний, 2 особи відвідують усі три гуртки, 8 – математичний та фізичний, 5 – математичний та хімічний, 3 – фізичний та хімічний гуртки. Скільки учнів класу не відвідують гуртки?
На змаганнях з легкої атлетики Андрій, Боря, Сергій та Володя посіли перші чотири місця. Але коли дівчатка почали згадувати, як ці місця розподілилися між переможцями, то думки розійшлися: Даша: Андрій був першим, а Володя – другим Галя: Андрій був другим, а Борис – третім Олена: Боря був четвертим, а Сергій другим Ася: кожна дівчинка зробила одну правильну та одну неправильну заяву
Як з повної посудини ємністю 12 л відлити половину, користуючись двома порожніми судинами ємністю 8 і 5 л?
Серед 101 однакових на вигляд монет одна фальшива, що відрізняється за вагою. Як за допомогою чашкових ваг без гирь за два зважування визначити, легша чи важча фальшива монета? Знаходити фальшиву монету не потрібно.
Умови завдання. 1. Є 5 будинків кожен різного кольору. 2. У кожному будинку живе одна людина, яка відрізняється від сусідньої за національністю: німець, англієць, швед, данець, норвежець. 3. Кожен п'є лише один певний напій, палить певну марку сигарет і тримає певну тварину. 4. Ніхто з 5 осіб не п'є однакові з іншими напоями, не палить однакові сигарети та не тримає однакову тварину. Запитання: кому належить риба? Підказки: 1. Англієць живе в червоному будинку. 2. Швед тримає собаку. 3. Данець п'є чай. 4. Зелений будинок стоїть ліворуч від білого. 5. Житель зеленого будинку п'є каву. 6. Людина, яка палить Pall Mall, тримає птаха. 7.Житель із середнього будинку п'є молоко. 8. Житель із жовтого будинку палить Dunhill. 9. Норвежець живе у першому будинку. 10. Курець Marlboro живе біля того, хто тримає кішку. 11. Людина, яка тримає коня, живе біля того, хто палить Dunhill. 12. Курець сигарет Winfield п'є пиво. 13. Норвежець живе біля блакитного будинку. 14. Німець палить Rothmans. 15. Курець Marlboro живе поруч із людиною, яка п'є воду.