1.5: Деякі алгоритми елементарної теорії чисел
- Page ID
- 64929
Алгоритм - це просто набір чітких інструкцій для досягнення якоїсь задачі. Перський математик і астроном Аль-Хорізмі 1 був вченим в Будинку мудрості в Багдаді, який жив у\(8^{\text{th}}\) і\(9^{\text{th}}\) століттях нашої ери, його пам'ятають за його алгебри трактат Хісаб аль-джабр w'al-muqabala, з якого ми виходимо саме слово» алгебра» та текст на схемі індуїстсько-арабських цифр.
Аль-Хорізмі також написав трактат про індуїстсько-арабські цифри. Арабський текст втрачено, але латинський переклад, Algoritmi de numero Indorum (англійською мовою Al-Khwarizmi на індуїстське мистецтво розплати) породив алгоритм слова, що походить від його імені в назві. [12]
Хоча вивчення алгоритмів є більш правильним предметом в інформатиці, студент математики може отримати значну користь від цього.
Існує велика різниця між описом алгоритму, призначеного для споживання людиною, і описом, призначеним для комп'ютера 2. Дві сприятливі для читання людини форми для опису алгоритмів - це псевдокод та блок-схеми. Перший - текстовий, а другий - візуальний. Існує безліч різних модулів, з яких можна будувати алгоритмічні структури: цикли for-next, цикли do-while, оператори if-then, оператори goto, структури switch-case тощо Ми будемо використовувати мінімальну підмножину доступних варіантів.
- Виписки про присвоєння
- Якщо-тоді контрольні заяви
- Перейти заяви
- Повернення
Ми вважаємо, що алгоритм є чимось на зразок функції, він приймає для його введення список параметрів, які описують конкретний випадок якоїсь загальної проблеми, і виробляє як вихід рішення цієї задачі. (Слід зазначити, що є й інші можливості — деякі програми вимагають, щоб змінна, в яку повинен бути розміщений висновок, передавалася їм як вхідний параметр, інші не мають конкретного виходу, їх призначення досягається як побічний ефект.) Посередником між входом та виходом є самі інструкції алгоритму та набір так званих локальних змінних, які використовуються в значній мірі так, як використовується скрап-папір при ручному обчисленні - проміжні обчислення записуються на них, але вони відкидаються в сторону після обчислення остаточної відповіді.
Оператори присвоєння дозволяють нам робити всі види арифметичних операцій (а точніше думати про ці типи операцій як атомні.) Насправді навіть проста процедура, як додавання двох чисел, вимагає свого роду алгоритму, ми уникнемо такого тонкого рівня деталізації. Призначення складаються з оцінки деякої (можливо, досить складної) формули у входах та локальних змінних та присвоєння цього значення деякій локальній змінній. Два використання фрази «локальна змінна» у попередньому реченні не повинні бути різними, таким чином,\(x = x + 1\) є цілком законним присвоєнням.
Якщо-тоді контрольні заяви є особами, які приймають рішення. Вони спочатку обчислюють логічний вираз (це просто фантазії спосіб сказати щось, що є або істинним або помилковим), і відправити потік програми в різні місця в залежності від цього результату. Маленький приклад послужить ілюстрацією. Припустимо, що в тілі алгоритму ми хочемо перевірити, якщо\(2\) змінні,\(x\) і\(y\) рівні, і якщо вони є, збільшення\(x\) на\(1\). Це проілюстровано на малюнку\(1.5.1\) як в псевдокоді, так і у вигляді блок-схеми.
Зверніть увагу на використання відступу в прикладі псевдокоду для позначення операторів, які виконуються, якщо логічний вираз true. Ці приклади також підкреслюють різницю між двома почуттями, які має слово «дорівнює» (і символ\(=\)). У логічному виразі сенс полягає в перевірці рівності, в операторах присвоєння (як випливає з назви) робиться присвоєння. У багатьох мовах програмування ця відмінність робиться явною, наприклад, у мові C тестування рівності проводиться за допомогою символу «\(==\)», тоді як присвоєння виконується за допомогою одного знака рівності (\(=\)). У математиці знак рівності зазвичай вказує на перевірку рівності, коли бажаний сенс призначення слово «нехай», як правило, передує рівності.
Хоча цей короткий вступ до засобів нотування алгоритмів аж ніяк не є повним, ми сподіваємось, достатньо для нашої мети, яка полягає лише у впровадженні двох алгоритмів, важливих в елементарній теорії чисел. Алгоритм поділу, як представлений тут, є просто явною версією процесу, який слід, щоб обчислити частку та залишок за допомогою довгого ділення. Процедура, яку ми даємо, надзвичайно неефективна - з дуже невеликою кількістю роздумів можна розробити алгоритм, який би дав бажану відповідь, використовуючи набагато меншу кількість операцій, - однак головним моментом тут є чисто показати, що поділ може бути здійснений по суті механічними засобами. Алгоритм Евкліда набагато цікавіший як з теоретичної, так і з практичної точки зору. Алгоритм Евкліда обчислює найбільший спільний дільник (\(\text{gcd}\)) двох цілих чисел. \(\text{gcd}\)З двох чисел\(a\) і\(b\)\(\text{gcd}(a, b)\) позначається і є найбільшим цілим числом, яке ділить обидва\(a\) і\(b\) рівномірно.
Псевдокодовий контур алгоритму поділу виглядає наступним чином:
Алгоритм: Розподіл
Входи: цілі числа\(n\) і\(d\).
Локальні змінні:\(q\) і\(r\).
Нехай\(q = 0\).
Нехай\(r = n\).
Етикетка\(1\).
Якщо\(r < d\) тоді
Повернення\(q\) і\(r\).
Закінчити, якщо
Нехай\(q = q + 1\).
Нехай\(r = r − d\).
Годо\(1\).
Цей же алгоритм наведено у вигляді блок-схеми на рис\(1.5.2\).
Зауважте, що в блок-схемі дія оператора «Goto» зрозуміла, оскільки стрілка вказує на місце, де відбувається перенаправлення потоку програми. У псевдокоді потрібна операція «Label», яка вказує на місце, куди потік може бути перенаправлений за допомогою наступних операторів «Goto». Через потенціал плутанини в складних алгоритмах, які включають безліч висловлювань Goto та відповідних їм міток, таке перенаправлення зараз застаріло практично у всіх популярних середовищах програмування.
Перш ніж ми перейдемо до опису алгоритму Евкліда, це може бути корисно описати більш чітко, для чого саме він потрібен. Задано пару цілих чисел,\(a\) і\(b\), є дві величини, які важливо мати можливість обчислити, найменше спільне кратне або\(\text{lcm}\), і найбільший спільний дільник або\(\text{gcd}\). Він\(\text{lcm}\) також йде найменшим загальним знаменником, оскільки це найменший знаменник, який можна використовувати як загальний знаменник у процесі додавання двох дробів, які мали\(a\) і\(b\) в їх знаменниках. The\(\text{gcd}\) і\(\text{lcm}\) пов'язані за формулою
\[\text{lcm}(a,b) = \dfrac{ab}{\text{gcd}(a, b)} \]
тому вони по суті еквівалентні, наскільки представляють обчислювальну проблему.
Алгоритм Евкліда залежить від досить екстраординарного властивості\(\text{gcd}\). Припустимо, що ми намагаємося обчислити,\(\text{gcd}(a, b)\) і\(a\) це більше з двох чисел. Ми спочатку подаємо\(a\) і\(b\) в алгоритм поділу знайти\(q\) і\(r\) таке, що\(a = qb + r\). Виявляється, що\(b\) і\(r\) мають ті ж НСД, що\(a\) і\(b\). Іншими словами, крім того\(\text{gcd}(a, b) = \text{gcd}(b, r)\), ці цифри менші, ніж ті, з яких ми почали! Це приємно, тому що це означає, що ми зараз маємо справу з простішою версією тієї ж проблеми. При розробці алгоритму важливо сформулювати чіткий критерій закінчення, умова, яка говорить вам про те, що ви закінчили. У випадку з евклідовим алгоритмом, ми знаємо, що ми закінчили, коли решта\(r\) виходить\(0\).
Отже, тут, без зайвих прихильностей є евклідовим алгоритмом в псевдокоді.
Алгоритм: Евклідів
Входи: цілі числа\(a\) і\(b\).
Локальні змінні:\(q\) і\(r\).
Етикетка\(1\).
Нехай\((q, r)\) = поділ\((a, b)\).
Якщо\(r = 0\) тоді
Повернення\(b\).
Закінчити, якщо
Нехай\(a = b\).
Нехай\(b = r\).
Годо\(1\).
Слід зазначити, що для невеликих чисел можна знайти\(\text{gcd}\) і\(\text{lcm}\) досить легко, розглядаючи їх множники на прості числа. На даний момент розглянемо числа, які чинять на прості числа, але не на прості сили (тобто їх факторизації не включають експоненти). The\(\text{gcd}\) є добутком простих чисел, які є спільними між цими факторизаціями (якщо немає загальних простих чисел, це є\(1\)). The\(\text{lcm}\) є добутком усіх чітких простих чисел, які з'являються у факторизаціях. Як приклад розглянемо\(30\) і\(42\). Факторизації є\(30 = 2 · 3 · 5\) і\(42 = 2 · 3 · 7\). Прості числа, які є загальними для обох факторизацій, є\(2\) і\(3\), таким чином\(\text{gcd}(30, 42) = 2 · 3 = 6\). Набір усіх простих чисел, які з'являються в будь-якій факторизації,\(\{2, 3, 5, 7\}\) такий\(\text{lcm}(30, 42) = 2 · 3 · 5 · 7 = 210\).
Щойно описана техніка має мало значення для чисел, що мають більше\(50\) десяткових цифр, оскільки вона апріорі спирається на здатність знаходити прості множники задіяних чисел. Факторингові числа досить прості, якщо вони досить малі, особливо якщо деякі їх прості множники невеликі, але загалом проблема вважається настільки складною, що багато криптографічних схем засновані на ній.
Вправи
Простежте алгоритм поділу з входами\(n = 27\) і кожен раз\(d = 5\), коли зустрічається оператор присвоєння, випишіть його. Скільки завдань задіяно в цьому конкретному обчисленні?
Знайти\(\text{gcd}\) 's і\(\text{lcm}\)' s наступних пар чисел.
| \(a\) | \(b\) | \(\text{gcd}(a, b)\) | \(\text{lcm}(a, b)\) |
| 110 | 273 | ||
| 105 | 42 | ||
| 168 | 189 |
Сформулювати опис НСД двох чисел з точки зору їх простих множників в загальному випадку (коли множники можуть включати повноваження задіяних простих чисел).
Простежуйте алгоритм Евкліда з входами\(a = 3731\) і кожен раз\(b = 2730\), коли оператор присвоєння, який викликає алгоритм поділу зустрічається, випишіть вираз\(a = qb + r\). (З фактичними значеннями!)