Дві гарні завдання по алгоритмам

    На цьому тижні я почав читати бакалаврам Академічного університету базовий курс по алгоритмам. Починав я зовсім з основ, і щоб тим, хто з базовими алгоритмами вже знаком, було чим зайнятися, я на початку пари сформулював дві, напевно, самі свої улюблені задачки по алгоритмам. Давайте і з вами ними поділюся. Рішення однієї з них навіть під катом детально розповім. Але не відмовляйте собі в задоволенні і не заглядайте відразу під кат, а спробуйте вирішити завдання самостійно. Обіцяю, що у обох завдань є достатньо прості рішення, не мають на увазі ніяких спеціальних знань з алгоритмам. Це, звичайно, не означає, що ці рішення просто знайти, але після пари один із студентів підійшов і розповів правильне рішення першого завдання. =) Якщо ж вам цікаво подивитися на початок курсу або повирішувати більше різних задач — приходьте до нас на (безкоштовний) онлайн-курс , який розпочнеться 15 вересня.
 
 
Задача 1 Дан масив A довжини (n + 1), що містить натуральні числа від 1 до n. Знайти будь повторюваний елемент за час O (n), не змінюючи масив і не використовуючи додаткової пам'яті.
 
Відразу поясню. У умови не говориться, що кожне число від 1 до n зустрічається в масиві, тому повторюваних елементів там може бути скільки завгодно (якби всі числа входили по разу, а одне & nbsp; & mdash; двічі, то завдання було б набагато простіше). Обмеження на використання додаткової пам'яті означає, що не можна заводити додатковий масив лінійної довжини, але можна заводити змінні.
 
 
Задача 2 Дана матриця nxn, що містить різні натуральні числа. Потрібно знайти в ній локальний мінімум за час O (n).
 
Локальним мінімумом матриці називається елемент, який менше всіх своїх чотирьох сусідів (або трьох, якщо цей елемент лежить на кордоні; або двох, якщо це кутовий елемент). Зверніть увагу, що від нас вимагається лінійне по n час, хоча в матриці квадратичне по n число елементів. Тому ми припускаємо, що матриця вже зчитана в пам'ять. І нам потрібно знайти в ній локальний мінімум, звернувшись лише до лінійного кількістю її осередків.
 
Під катом & nbsp; & mdash; рішення першого завдання. Ще раз закликаю вас заглядати під кат тільки після того, як повирішувати задачу. За другою завданню можу якусь підказку сказати. =)
 
Спробую розповісти не тільки рішення, але і те, як до нього можна було б здогадатися. Пояснювати буду відразу на прикладі. З нього, сподіваюся, буде зрозуміло, як алгоритм працює в загальному випадку. Робочий приклад:
 
 
Тобто нам дан масив довжини 9, що містить числа від 1 до 8, і наша мета & nbsp; & mdash; знайти двійку або п'ятірку.
 
Як ми пам'ятаємо, використовувати додаткову пам'ять в умові завдання заборонено. Давайте, однак, зрозуміємо, чим вона могла б нам допомогти. Ми б тоді завели новий масив розміру n і одним проходом по вихідного масиву A порахували б, скільки разів кожне з чисел від 1 до n входить в A. За цього масиву було б відразу видно, хто в A повторюється.
 
Це надалі не особливо нам допоможе, але все ж.
 
Обмеження на додаткову пам'ять не дає нам зібрати і записати допоміжну інформацію про масиві. Значить, повторюваний елемент нам потрібно знайти, як-то «гуляючи» по масиву. Гуляти по масиву можна зліва направо, наприклад, але незрозуміло, яку інформацію можна при цьому витягти. Тому спробуємо гуляти по-іншому. Встанемо в перший елемент нашого масиву і подивимося, що там написано. Написано там число 7, тому давайте подивимося на сьомий елемент масиву. Там записано число 1. Прогулянка вийшла недовгою, ми зациклилися. Те, що в масиві є якісь цикли, дуже нам допоможе надалі. Для прикладу давайте ще спробуємо прогулятися з другого елементу: звідти ми підемо в елемент номер 5, з нього & nbsp; & mdash; в елемент номер 3, а з елемента номер 3 знову повернемося назад в елемент номер 2. Тобто знайшли ще один цикл. Давайте зобразимо знайдені нами два циклу:
 
І раз вже ми усвідомили, що наш масив неявно задає деякий граф, то давайте явно цей граф намалюємо. Формально, вершини графа & nbsp; & mdash; це числа від 1 до n + 1; ми проводимо орієнтоване ребро з i в j, якщо A [i] = j.
 Цікавлять нас в цьому графі вершини, в які входять хоча б два ребра (якщо в вершину j входять ребра з вершин i та k, то A [i] = A [k] = j, тобто j повторюється в масиві A ). Нам і так ясно, що така вершина в графі є, але давайте це усвідомлюємо ще раз, в термінах графів. У нашому графі з кожної вершини виходить рівно одне ребро (і значить, в графі (n + 1) ребро), але є одна вершина, в яку нічого не входить: це вершина (n + 1). Значить, знайдеться вершина, до якої входить хоча б два ребра. В общем-то, це і так було ясно, але от зауваження про вершину (n + 1) нам в подальшому допоможе.
 
Давайте встанемо в вершину (n + 1) і будемо переходити в нашому графі по виходить ребрам. Коли-небудь ми зациклилися, звичайно, але важливо те, що ми не повернемося в вершину (n + 1). В нашому робочому прикладі ми вийдемо з вершини 9 і дійдемо до циклу (5,2,3). Видно, що точка входу в цей цикл & nbsp; & mdash; це і є повторюваний елемент: адже в цю точку і по ребру циклу можна увійти, і по ребру на шляху з вершини (n + 1) в цикл. У нашому прикладі така точка входу & nbsp; & mdash; це вершина 5.
 
Знаходження цієї точки & nbsp; & mdash; окрема не надто просте завдання, але її рішення дуже схоже на рішення стандартної задачі про зацикленості списку. Довжину циклу знайти нескладно. Наприклад, зробимо n + 1 крок з вершини n + 1. Після цього ми обов'язково опинимося в вершині на циклі. Запам'ятаємо цю вершину і продовжуватимемо крокувати, поки не повернемося в неї. Тим самим дізнаємося довжину циклу k. Тепер зробимо наступне. Поставимо два покажчика в вершину n + 1. Першим покажчиком зробимо k кроків. Після цього будемо рухати кожен з покажчиків на один крок вперед, поки вони не зустрінуться (таким чином, перший покажчик завжди буде обганяти другий на k кроків). Ясно, що зустрінуться ці хлопці якраз в потрібній нам точці вході. У нашому прикладі довжина циклу дорівнює трьом. Після трьох кроків перший покажчик виявиться в вершині 2. В цей момент ми почнемо рухати і другий покажчик. Через два кроки покажчики зустрінуться в вершині 5.
 
На закуску. Ми не обговорили, чому ж було заборонено модифікувати масив (і наш алгоритм масив, дійсно, не чіпав). Придумайте більш просте рішення, якщо дозволяється псувати масив.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.