Викотився ЧОРНІ ШАРИКИ
У вузькому і дуже довгому жолобі знаходяться 8 кульок, чотири чорних зліва і чотири білих трохи більшого діаметра справа. У середній частині жолоби в стінці є невелика ніша, в якій може поміститися тільки
Так визріває дитяче зарозумілість на рахунок власного інтелекту, який завжди вище середнього рівня. ; (
Це дуже стара завдання, її вирішували на Русі ще в IX столітті. Як завжди, цікаве те, що грунтовно забуте.
Цікаво, що Б.А. Кордемский в рішенні зазначає тільки другий варіант і з якоїсь причини не згадує перший. Загадка? Загадка.
Дуже цікавим є питання про час виникнення даної головоломки і її першоджерелі. Б.А. Кордемский в книзі "Математична кмітливість" говорить мимохіть: "Це. старовинна завдання; зустрічається в творах VIII століття ".
Спочатку може здатися, що ми маємо справу з помилкою, адже перша або одна з перших вітчизняних публікацій завдання "Вовк, коза і капуста" датована кінцем ХVIII століття. У фондах Російської Історичної бібліотеки збереглася книга "Ворожильна арифметика для забави і задоволення" (СПб. 1789). На титульному аркуші зазначається: "На іжд. изд. І. Краснопільського ", що означає" на утриманні видавця І. Краснопільського ". У раритет на 62 сторінках, сорок і одна цікава задача. На с. 42-43 читаємо: "Деякий мужик віз з собою вовка, козу і капусту приїхав до річки, у березі якої знайшов настільки малу човен, що вона крім його і одного чого-небудь з везомих їм, піднімати не могла. І так питається, яким чином переправити оних через річку так, щоб вовк не з'їв той кози, а коза капусти? "Далі наводиться один варіант рішення (перший).
(-массівамі даних)
(-отображаемих як масиви даних) операції над множинами В результаті стає ясно: завдання (по суті)
з себе являє
(-спіскамі) впорядкованими
множинами (А в Ханойські вежі вже оперують з
множинами - там важливий ще і порядок (дисків). Тобто (там оперують) з
Але як це рішення (сам процес. А не результат) отримати (а
головне - записати) формально?
Або хоча б як довести, що дане рішення - вірне?
(Хоча, можливо, і неєдиний)
Але що є правильність такого рішення? Крім що не
підсумковий результат? (Точніше: отримана в результаті знайденої
послідовності дій (необхідна) кінцева ситуація)
Адже (фактично) він вислизає з уваги тільки коли
алгоритм - не кінцевий
(-а точніше - циклічний. Коли довжину його передбачити
((Навіть) для даних вихідних умов)
неможливо (або (дуже) важко)
Ось тоді і зростає актуальність докази
правильності алгоритму.
(Наприклад, чисельне рішення рівняння. Як довести, що
даний алгоритм сходиться?)
Однак дане (вищенаведене) рішення отримано методом
симуляції (-проб і помилок) задачний моделі. (- А2д) І доведено безпосередньо до
бажаного результату (ситуації)
Однак не завжди такий метод (симуляції) ефективний. ось для
цього (-у цьому випадку) і потрібні відповідні (алгоритмічні) теореми.
Типу «як швидше це зробити».
Звідси висновок: теореми в програмуванні -
це (оптимізовані) алгоритми вирішення конкретних (типових) завдань.
наприклад,
як упорядкувати масив по зростанню?
або
вирішити квадратне рівняння. Або трансцендентне - методом ітерацій (хорд і
дотичних)
Однак оскільки комп'ютер має продуктивність багато
велику (чим людина), йому можна доручити вирішувати і методом перебору (-повної
симуляції. Задачний моделі).
Але тільки дискретні
(Тобто на кінцевій множині (-області) визначення.
Функції, закладеної в задачу.)
Отже,
виходить, що Вовк, коза і капуста (а також Ханойська вежа) - це (по
формальної суті) перебір (-підбор) операцій, які вирішують задачу. Тобто
перетворюють вихідний масив даних (-отображающій вихідну ситуацію) в
бажаний.
які
ще можна помислити завдання з програмування? Ну наприклад:
1.Отисканіе
мінімального елемента масиву - обробка (-обчислення функціоналу) масиву. (то
ж саме - обчислення суми ряду)
2.Упорядоченіе
масиву (по зростанню) - перетворення масиву.
3.Геометріческіе
побудови - генерація масиву даних (за певним правилом. І виходячи з
початкової ситуації)
Виходить, що суть завдань з програмування (-их Задачного
ситуацій) - це не тільки перебір варіантів (дій над вихідною ситуацією) (з
метою перевірки (результатів) на певну умову), але і обробка
масивів даних. (Обчислення ряду - відноситься сюди ж)
Або і те, і інше разом.
які
ще типи завдань зустрічаються в програмуванні?
Для відповіді на це питання розберемо кілька завдань більш
детально. Може, знайдуться ще якісь типи.
С.А.Абрамов, Г.Г.Гнезділова,
Е.Н.Капустіна, М.І.Селюн. Завдання по программірованіюВозьмем
завдання зі збірки
1.Дані
натуральне число n.
Отримати всі піфагорові трійки (тобто
задовольняють співвідношенню a ^ 1 + b ^ 2 = c ^ 2) натуральних чисел, що не перевершують n.
А раптом це Алкуин через століття задумав пожартувати над нами? Нічим іншим я не можу пояснити ту обставину, що і сам спочатку при поясненні другого варіанту рішення вказав не 7 рейсів, а 11, причому помітив свою помилку в самий останній момент.
Завдання 1. У Кістки є тільки монети вартістю 3 копа, а у Діми - тільки 2-хкоповие. Костя повинен Дімі 7 копів. Як йому розплатитися?
Чи пов'язана ця задача як-небудь з коником?
Завдання 2Заставьте Кузнечика побувати по одному разу в кожній з точок 1, 2, 3, 4, 5, не виходячи 'за межі відрізка від 0 до 5.
Завдання 3Кузнечік розпочав виконання програми в точці 0 і закінчив в точці 2. Потім та ж програма була виконана ще раз. Де тепер опинився Коник?
Завдання 4Может чи Коник дістатися до будь-якої точки на прямій? Як? (Зрозуміло, ми запитуємо тільки про точки, відповідні цілим числам, а не про дроби.)
Завдання 5Поменяем трошки список команд Кузнечика. Звичайно, зміна списку команд, навіть найменше, означає, що ми отримали іншого Виконавця. Але ми все одно будемо називати його коником. Новий список для цього Кузнечика складається також з двох команд:
Чи може новий Коник дістатися до будь-якої точки прямої, наприклад до точки 1?
Ще більше добірних загадок знайдеш тут: