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

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

З теоретичними задачами проблем поки немає – там тести пройти. Якщо дивилися лекції – проблем не буде. Деякі питання просто на логіку вирішуються. З програмними задачами теж, здавалося б, немає проблем.  Написати реалізацію QuickSort алгоритму, посортувати заданий файлик, вивести кількість порівнянь. По-перше – для чого нам цей QuickSort? Всі ж вміємо сортувати “”булькою”? “. Так от, повірте на слово – на невеликій кількості чисел – використовуйте що хочете, але чим більша вибірка, тим гірша ефективність. Тут і показує свої переваги алгоритм швидкого сортування.

Тривалий час бложик був поза ефіром через те, що я забув пере делегувати домен org.ua. Потім була дещо епічна історія з його відновленням. Зараз вже все добре, тому варто було б щось написати.
Тема виплила якось сама собою. Я інколи читаю деякі книжечки по С++ і розважаю мозок задачками деякими. Ніколи не вважав себе прогармістом, напевне, варто переключитися на щось інше. Власне, потроху переключаюся, але поки ще трошки пишу всякі такі примітивні задачки.

Сьогодні поговоримо про одну з таких – шахматна задача коня Евкліда. Приклад такої задачки описано Полом та Харві Дейтелами у своїй книжечці по с++. В чому суть задачі? Є шахматна дошка і кінь. Потрібно пройти конем всі клітинки дошки, побувавши на кожній лише один раз.

З чого почати? Ну, щоб краще уявити ситуацію, візьміть листок і спробуйте зробити максимум ходів, закреслюючи відвідані клітинки. Мені вдалося зробити близько 30 ходів. Гадаю, така кількість ходів – буде приблизно однаковою при старті з різних позицій та випадковій стратегій ходів. Ок, давайте напишемо програмку, яка буде генерувати ходи коня випадково. Доречі, про ходи – їх є 8 типів. Не думаю, що люди, які цікавляться на такому мінімальному рівні програмуванням не цікавилися ніколи шахматами.