Муніципальне освітній заклад
ГІМНАЗІЯ № 64
Програмування різних типів завдань
Екзаменаційний реферат з інформатики
Медведєв Олександр Валерійович, 11Б
Кушнікова Валерія Петрівна, вчитель
Липецьк 2007
Зміст
I. Введення
II. Основна частина:
1.Способами сортування
2. Теорія чисел
3. Завдання «Красиві числа»
III. Список використаної літератури
Вступ
При програмуванні дуже важливо зрозуміти, наскільки потужним є те, що ви знаєте. У принципі будь-який цікавий алгоритм / програму можна написати, грунтуючись на тих знаннях, які ви отримали на самому початку навчання програмування. Всі потужні здатності сучасних мов не обов'язкові для побудови цікавих речей - вони потрібні тільки для того, щоб побудувати їх більш чітко і зручно. Кажучи іншими словами, гарним письменником стає не той, хто вивчив багато слів з словника, а той, хто знайшов, про що розповісти.
Для написання якісних програм, можна дати декілька простих порад:
- Пишіть спочатку коментарі. Починайте ваші програми та процедури з декількох пропозицій, які пояснюють те, що вони мають робити. Це важливо, тому що якщо ви не зможете з легкістю написати ці коментарі, то, найімовірніше, ви не розумієте, що робить програма. Редагувати коментарі набагато простіше, ніж редагувати програму, тому час, витрачений на додаткове друкування, витрачено з великою вигодою. Звичайно через те, що на змаганнях зазвичай піджимає час, з'являється звичка бути недбалим, але в цьому немає нічого хорошого.
- Документуйте кожну змінну. Напишіть один рядок коментарю для кожної змінної, щоб б ви знали, що вона робить. І знову, якщо ви не можете чітко це написати, то ви не розумієте, що вона тут робить. Ви будете спілкуватися з програмою, принаймні, кілька циклів налагодження, і ви оціните це скромне вкладення в її читабельність.
- Використовуйте символьні константи. Коли б вам не потрібна константа в вашій програмі (розмір вхідних даних, математична константа, розмір структури даних і т.д.), оголошуйте її на самому початку програми. Використання суперечливих констант може призвести до дуже складних та труднообнаружіваемим помилок. Звичайно, символьне ім'я потрібно тільки тоді, коли ви збираєтеся його використовувати в тому місці, де повинна бути константа
- Використовуйте підпрограми, щоб уникнути зайвого коду. Набагато безпечніше написати одну підпрограму і викликати її з відповідними параметрами, ніж повторювати одне і теж з різними змінними.
Сортування
Сортування є найбільш фундаментальною алгоритмічної завданням в теорії обчислювальних машин і систем за двома різних причин. По-перше, сортування - це корисна операція, яка ефективно вирішує багато завдань, з якими зустрічається кожен програміст. По-друге, були розроблені буквально десятки різних алгоритмів сортування, кожен з яких грунтується на певній хитрою ідеї чи спостереженні. Більшість прикладів розробки алгоритмів веде до цікавих алгоритмам, які мають «розділяй і володарюй», рандомізацію, інкрементний вставку і просунуті структури даних. З властивостей цих алгоритмів слід безліч цікавих завдань з програмування.
Ключем до розуміння сортування є розуміння того, як вона може бути використана для вирішення багатьох важливих завдань програмування. Розглянемо деякі випадки застосування сортування.
· Перевірка унікальності. Як ми можемо перевірити, чи всі елементи даного набору об'єктів S є різними? Відсортуємо їх або у зростаючому, або в порядку спадання, так що будь-які повторюються об'єкти будуть слідувати один за одним. Після цього один прохід по всіх елементах з перевіркою рівності S [i] = s [i +1] для будь-якого 1 ≤ i <n вирішує поставлене завдання.
· Видалення повторюваних елементів. Як ми можемо видалити всі копії, крім однієї, будь-якого з повторюваних елементів S? Сортування і чищення знову вирішують завдання. Зверніть увагу, що чистку простіше всього виробляти, використовую два індекси - back, який вказує на останній елемент у очищеної частини масиву, і i, який вказує на наступний елемент, який потрібно розглянути. Якщо S [back] <> S [i], збільшуємо back і копіюємо S [i] в S [back].
· Розподіл пріоритетів подій. Припустимо, що у нас є список робіт, які необхідно зробити, і для кожної визначений свій власний термін здачі. Сортування об'єктів за часом здачі (або за аналогічним критерієм) розташує роботи в тому порядку, в якому їх необхідно робити. Черги за пріоритетами зручні для роботи з календарями і розкладами, коли є операції вставки і видалення, але сортування зручна в тому випадку, коли набір подій не змінюється в ході виконання.
· Медіана / вибір. Припустимо, що ми хочемо знайти k-й за величиною об'єкт у S. Після сортування об'єктів у порядку зростання потрібний нам буде знаходиться в комірці S [k]. У певних випадках цей підхід може бути використаний для знаходження найменшого, найбільшого і медіанного об'єкта.
· Розрахунок частоти. Який елемент найчастіше зустрічається в S? Після сортування лінійний прохід дозволяє нам порахувати кількість разів, що зустрічається кожен елемент.
· Відновлення початкового порядку. Як ми можемо відновити первісне розташування набору об'єктів, після того як ми переставили їх для деяких цілей? Додамо додаткове поле до запису даних об'єкта, таке що i-й запису це поле дорівнює i. Зберігши це поле під час всіх перестановок, ми зможемо відсортувати за нього тоді, коли нам буде потрібно відновити початковий порядок.
· Створення перетину / об 'єднання. Як ми можемо розрахувати перетинання або об'єднання двох контейнерів? Якщо вони обоє відсортовані, ми може об'єднати їх, якщо будемо вибирати найменший з двох провідних елементів, поміщати його в нову множину, якщо хочемо, а потім видаляти з відповідного списку.
· Пошук необхідної пари. Як ми можемо перевірити, чи існують два цілих числа x, y
· Ефективний пошук. Як ми можемо ефективно перевірити, чи належить елемент s безлічі S? Звичайно, упорядкування множини з метою застосування ефективного бінарного пошуку - це, напевно, найбільш стандартний додаток сортування. Просто не забувайте інші!
Розглянемо кілька досить повчальних алгоритмів сортування
Сортування бульбашкою
Розташуємо масив зверху вниз, від нульового елемента - до останнього. Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого згори елемента, таким чином другий за величиною елемент піднімається на правильну позицію ... Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність упорядкована за зростанням.
Type
arrType = Array [1 .. n] Of Integer;
Procedure Bubble (Var ar: arrType; n: integer);
Var i, j, T: Integer;
Begin
For i: = 1 To n Do
For j: = n DownTo i +1 Do
If ar [Pred (j)]> ar [j] Then Begin {<}
T: = ar [Pred (j)]; ar [Pred (j)]: = ar [j]; ar [j]: = T
End
End;
Складність цього методу сортування складає О (n ^ 2)
Бульбашкова сортування з просіюванням
Аналогічний методу бульбашкової сортування, але після перестановки пари сусідніх елементів виконується просіювання: найменший лівий елемент просувається на початок масиву наскільки це можливо, поки не виконується умова впорядкованості.
Перевага: простий метод бульбашки працює вкрай повільно, коли хв / макс (в залежності від напрямку сортування) елемент масиву стоїть в кінці, цей алгоритм - набагато швидше.
const n = 10;
var
x: array [1 .. n] of integer;
i, j, t: integer;
flagsort: boolean;
procedure bubble_P;
begin
repeat
flagsort: = true;
for i: = 1 to n-1 do
if not (x [i] <= x [i +1]) then begin
t: = x [i];
x [i]: = x [i +1];
x [i +1]: = t;
j: = i;
while (j> 1) and not (x [j-1] <= x [j]) do begin
t: = x [j];
x [j]: = x [j-1];
x [j-1]: = t;
dec (j);
end;
flagsort: = false;
end;
until flagsort;
end;
Тестувалося на масиві цілих чисел (25000 елементів).
Приріст швидкості відносно простий бульбашкової сортування - близько 75% ...
Метод послідовного пошуку мінімумів
Теорія: Проглядається весь масив, шукається мінімальний елемент і ставиться на місце першого, "старий" перший елемент ставиться на місце знайденого
type
TArr = array [1 .. 100] of integer;
var
mass1: TArr;
n: integer;
procedure NextMinSearchSort (var mass: TArr; size: integer);
var i, j, Nmin, temp: integer;
begin
for i: = 1 to size-1 do begin
nmin: = i;
for j: = i +1 to size do
if mass [j] <mass [Nmin] then Nmin: = j;
temp: = mass [i];
mass [i]: = mass [Nmin];
mass [Nmin]: = temp;
end;
end;
Сортування вставками
Сортування простими вставками в чомусь схожа на вищевикладені методи. Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку "виростає" відсортована послідовність ... Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] ... a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] ... a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назва методу) все нові елементи. Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] ... a [i] і невпорядковану a [i +1] ... a [n]. На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву. Пошук відповідного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементом, що стоять перед ним. У залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється.
Таким чином, в процесі вставки ми "просіваємо" елемент x до початку масиву, зупиняючись у разі, коли
1. Знайдіть елемент, менший x або
2. Досягнуто початок послідовності.
Type
arrType = Array [1 .. n] Of Integer;
Procedure Insert (Var ar: arrType; n: Integer);
Var i, j, T: Integer;
Begin
For i: = 1 To n Do Begin
T: = ar [i];
j: = Pred (i);
While (T <ar [j]) and (j> 0) Do Begin
ar [Succ (j)]: = ar [j]; Dec (j);
End;
ar [Succ (j)]: = T;
End;
End;
Складність О (n ^ 2)
Розподіляє сортування - RadixSort - цифрова - поразрядное
Нехай маємо максимум по k байт у кожному ключі (хоча за елемент сортування цілком можна прийняти і що-небудь інше, наприклад, слово - подвійний байт, або букви, якщо сортуються рядки). K повинно бути відомо заздалегідь, до сортування.
Розрядність даних (кількість можливих значень елементів) - m - також повинна бути відома заздалегідь і постійна. Якщо ми сортуємо слова, то елемент сортування - літера, m = 33. Якщо на самому довгому слові 10 літер, k = 10. Зазвичай ми будемо сортувати дані за ключами з k байт, m = 256.
Нехай у нас є масив source з n елементів по одному байту в кожному.
Для прикладу можете виписати на листочок масив source = <7, 9, 8, 5, 4, 7, 7>, і проробити з ним всі операції, маючи на увазі m = 9.
I. Складемо таблицю розподілу. У ній буде m (256) значень і заповнюватися вона буде так:
for i: = 0 to Pred (255) Do distr [i]: = 0;
for i: = 0 to Pred (n) Do distr [source [i]]: = distr [[i]] + 1;
Для нашого прикладу будемо мати distr = <0, 0, 0, 0, 1, 1, 0, 3, 1, 1>, тобто i-ий елемент distr [] - кількість ключів зі значенням i.
II. Заповнимо таблицю індексів:
index: array [0 .. 255] of integer;
index [0]: = 0;
for i: = 1 to Pred (255) Do index [i] = index [i-1] + distr [i-1];
У index [i] ми помістили інформацію про майбутнє кількості символів у відсортованому масиві до символу з ключем i.
Hаприклад, index [8] = 5: маємо <4, 5, 7, 7, 7, 8>.
III. А тепер заповнюємо новостворений масив sorted розміру n:
for i: = 0 to Pred (n) Do Begin
sorted [index [source [i]]]: = source [i];
{
попутно змінюємо index вже вставлених символів, щоб
однакові ключі йшли один за іншим:
}
index [source [i]]: = index [source [i]] +1;
End;
Отже, ми навчилися за O (n) сортувати байти. А від байтів до рядків і чисел - 1 крок. Нехай у нас в кожному числі - k байт.
Будемо діяти в десятковій системі і сортувати звичайні числа (m = 10).
спочатку вони в сортуємо по молодшому на один безладді: розряду: вище: і ще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554
Hу ось ми і відсортували за O (k * n) кроків. Якщо кількість можливих різних ключів ненабагато перевищує загальне їх число, то 'поразрядное сортування'; виявляється набагато швидше навіть 'швидкого сортування'!
Реалізація алгоритму "розподіляє" сортування:
Const
n = 8;
Type
arrType = Array [0 .. Pred (n)] Of Byte;
Const
m = 256;
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);
Procedure RadixSort (Var source, sorted: arrType);
Type
indexType = Array [0 .. Pred (m)] Of Byte;
Var
distr, index: indexType;
i: integer;
begin
fillchar (distr, sizeof (distr), 0);
for i: = 0 to Pred (n) do
inc (distr [source [i]]);
index [0]: = 0;
for i: = 1 to Pred (m) do
index [i]: = index [Pred (i)] + distr [Pred (i)];
for i: = 0 to Pred (n) do
begin
sorted [index [source [i]]]: = source [i];
index [source [i]]: = index [source [i]] +1;
end;
end;
var
b: arrType;
begin
RadixSort (a, b);
end.
Теорія чисел.
Теорія чисел є, можливо, самим цікавим і красивим розділом математики. Доказ Евклідом існування нескінченної кількості простих чисел залишається таким же чітким і ясним сьогодні, яким воно було більше двох тисяч років тому. Такі невинні питання, як існують рішення рівняння а n + b n = c n для цілих a, b, c і n> 2, часто виявляється зовсім не такими безневинними. Більш того, це формулювання великої теореми Ферма!
ГІМНАЗІЯ № 64
Програмування різних типів завдань
Екзаменаційний реферат з інформатики
Медведєв Олександр Валерійович, 11Б
Кушнікова Валерія Петрівна, вчитель
Липецьк 2007
Зміст
I. Введення
II. Основна частина:
1.Способами сортування
2. Теорія чисел
3. Завдання «Красиві числа»
III. Список використаної літератури
Вступ
При програмуванні дуже важливо зрозуміти, наскільки потужним є те, що ви знаєте. У принципі будь-який цікавий алгоритм / програму можна написати, грунтуючись на тих знаннях, які ви отримали на самому початку навчання програмування. Всі потужні здатності сучасних мов не обов'язкові для побудови цікавих речей - вони потрібні тільки для того, щоб побудувати їх більш чітко і зручно. Кажучи іншими словами, гарним письменником стає не той, хто вивчив багато слів з словника, а той, хто знайшов, про що розповісти.
Для написання якісних програм, можна дати декілька простих порад:
- Пишіть спочатку коментарі. Починайте ваші програми та процедури з декількох пропозицій, які пояснюють те, що вони мають робити. Це важливо, тому що якщо ви не зможете з легкістю написати ці коментарі, то, найімовірніше, ви не розумієте, що робить програма. Редагувати коментарі набагато простіше, ніж редагувати програму, тому час, витрачений на додаткове друкування, витрачено з великою вигодою. Звичайно через те, що на змаганнях зазвичай піджимає час, з'являється звичка бути недбалим, але в цьому немає нічого хорошого.
- Документуйте кожну змінну. Напишіть один рядок коментарю для кожної змінної, щоб б ви знали, що вона робить. І знову, якщо ви не можете чітко це написати, то ви не розумієте, що вона тут робить. Ви будете спілкуватися з програмою, принаймні, кілька циклів налагодження, і ви оціните це скромне вкладення в її читабельність.
- Використовуйте символьні константи. Коли б вам не потрібна константа в вашій програмі (розмір вхідних даних, математична константа, розмір структури даних і т.д.), оголошуйте її на самому початку програми. Використання суперечливих констант може призвести до дуже складних та труднообнаружіваемим помилок. Звичайно, символьне ім'я потрібно тільки тоді, коли ви збираєтеся його використовувати в тому місці, де повинна бути константа
- Використовуйте підпрограми, щоб уникнути зайвого коду. Набагато безпечніше написати одну підпрограму і викликати її з відповідними параметрами, ніж повторювати одне і теж з різними змінними.
Сортування
Сортування є найбільш фундаментальною алгоритмічної завданням в теорії обчислювальних машин і систем за двома різних причин. По-перше, сортування - це корисна операція, яка ефективно вирішує багато завдань, з якими зустрічається кожен програміст. По-друге, були розроблені буквально десятки різних алгоритмів сортування, кожен з яких грунтується на певній хитрою ідеї чи спостереженні. Більшість прикладів розробки алгоритмів веде до цікавих алгоритмам, які мають «розділяй і володарюй», рандомізацію, інкрементний вставку і просунуті структури даних. З властивостей цих алгоритмів слід безліч цікавих завдань з програмування.
Ключем до розуміння сортування є розуміння того, як вона може бути використана для вирішення багатьох важливих завдань програмування. Розглянемо деякі випадки застосування сортування.
· Перевірка унікальності. Як ми можемо перевірити, чи всі елементи даного набору об'єктів S є різними? Відсортуємо їх або у зростаючому, або в порядку спадання, так що будь-які повторюються об'єкти будуть слідувати один за одним. Після цього один прохід по всіх елементах з перевіркою рівності S [i] = s [i +1] для будь-якого 1 ≤ i <n вирішує поставлене завдання.
· Видалення повторюваних елементів. Як ми можемо видалити всі копії, крім однієї, будь-якого з повторюваних елементів S? Сортування і чищення знову вирішують завдання. Зверніть увагу, що чистку простіше всього виробляти, використовую два індекси - back, який вказує на останній елемент у очищеної частини масиву, і i, який вказує на наступний елемент, який потрібно розглянути. Якщо S [back] <> S [i], збільшуємо back і копіюємо S [i] в S [back].
· Розподіл пріоритетів подій. Припустимо, що у нас є список робіт, які необхідно зробити, і для кожної визначений свій власний термін здачі. Сортування об'єктів за часом здачі (або за аналогічним критерієм) розташує роботи в тому порядку, в якому їх необхідно робити. Черги за пріоритетами зручні для роботи з календарями і розкладами, коли є операції вставки і видалення, але сортування зручна в тому випадку, коли набір подій не змінюється в ході виконання.
· Медіана / вибір. Припустимо, що ми хочемо знайти k-й за величиною об'єкт у S. Після сортування об'єктів у порядку зростання потрібний нам буде знаходиться в комірці S [k]. У певних випадках цей підхід може бути використаний для знаходження найменшого, найбільшого і медіанного об'єкта.
· Розрахунок частоти. Який елемент найчастіше зустрічається в S? Після сортування лінійний прохід дозволяє нам порахувати кількість разів, що зустрічається кожен елемент.
· Відновлення початкового порядку. Як ми можемо відновити первісне розташування набору об'єктів, після того як ми переставили їх для деяких цілей? Додамо додаткове поле до запису даних об'єкта, таке що i-й запису це поле дорівнює i. Зберігши це поле під час всіх перестановок, ми зможемо відсортувати за нього тоді, коли нам буде потрібно відновити початковий порядок.
· Створення перетину / об 'єднання. Як ми можемо розрахувати перетинання або об'єднання двох контейнерів? Якщо вони обоє відсортовані, ми може об'єднати їх, якщо будемо вибирати найменший з двох провідних елементів, поміщати його в нову множину, якщо хочемо, а потім видаляти з відповідного списку.
· Пошук необхідної пари. Як ми можемо перевірити, чи існують два цілих числа x, y
· Ефективний пошук. Як ми можемо ефективно перевірити, чи належить елемент s безлічі S? Звичайно, упорядкування множини з метою застосування ефективного бінарного пошуку - це, напевно, найбільш стандартний додаток сортування. Просто не забувайте інші!
Розглянемо кілька досить повчальних алгоритмів сортування
Сортування бульбашкою
Розташуємо масив зверху вниз, від нульового елемента - до останнього. Ідея методу: крок сортування полягає в проході знизу вгору по масиву. По дорозі проглядаються пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву "вгорі" виявляється самий "легкий" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого згори елемента, таким чином другий за величиною елемент піднімається на правильну позицію ... Робимо проходи по все зменшується нижній частині масиву до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, так як послідовність упорядкована за зростанням.
Type
arrType = Array [1 .. n] Of Integer;
Procedure Bubble (Var ar: arrType; n: integer);
Var i, j, T: Integer;
Begin
For i: = 1 To n Do
For j: = n DownTo i +1 Do
If ar [Pred (j)]> ar [j] Then Begin {<}
T: = ar [Pred (j)]; ar [Pred (j)]: = ar [j]; ar [j]: = T
End
End;
Складність цього методу сортування складає О (n ^ 2)
Бульбашкова сортування з просіюванням
Аналогічний методу бульбашкової сортування, але після перестановки пари сусідніх елементів виконується просіювання: найменший лівий елемент просувається на початок масиву наскільки це можливо, поки не виконується умова впорядкованості.
Перевага: простий метод бульбашки працює вкрай повільно, коли хв / макс (в залежності від напрямку сортування) елемент масиву стоїть в кінці, цей алгоритм - набагато швидше.
const n = 10;
var
x: array [1 .. n] of integer;
i, j, t: integer;
flagsort: boolean;
procedure bubble_P;
begin
repeat
flagsort: = true;
for i: = 1 to n-1 do
if not (x [i] <= x [i +1]) then begin
t: = x [i];
x [i]: = x [i +1];
x [i +1]: = t;
j: = i;
while (j> 1) and not (x [j-1] <= x [j]) do begin
t: = x [j];
x [j]: = x [j-1];
x [j-1]: = t;
dec (j);
end;
flagsort: = false;
end;
until flagsort;
end;
Тестувалося на масиві цілих чисел (25000 елементів).
Приріст швидкості відносно простий бульбашкової сортування - близько 75% ...
Метод послідовного пошуку мінімумів
Теорія: Проглядається весь масив, шукається мінімальний елемент і ставиться на місце першого, "старий" перший елемент ставиться на місце знайденого
type
TArr = array [1 .. 100] of integer;
var
mass1: TArr;
n: integer;
procedure NextMinSearchSort (var mass: TArr; size: integer);
var i, j, Nmin, temp: integer;
begin
for i: = 1 to size-1 do begin
nmin: = i;
for j: = i +1 to size do
if mass [j] <mass [Nmin] then Nmin: = j;
temp: = mass [i];
mass [i]: = mass [Nmin];
mass [Nmin]: = temp;
end;
end;
Сортування вставками
Сортування простими вставками в чомусь схожа на вищевикладені методи. Аналогічним чином робляться проходи по частині масиву, і аналогічним же чином на його початку "виростає" відсортована послідовність ... Однак у сортуванні бульбашкою або вибором можна було чітко заявити, що на i-му кроці елементи a [0] ... a [i] стоять на правильних місцях і нікуди більше не перемістяться. Тут же подібне твердження буде більш слабким: послідовність a [0] ... a [i] впорядкована. При цьому по ходу алгоритму в неї будуть вставлятися (див. назва методу) все нові елементи. Будемо розбирати алгоритм, розглядаючи його дії на i-му кроці. Як говорилося вище, послідовність до цього моменту розділена на дві частини: готову a [0] ... a [i] і невпорядковану a [i +1] ... a [n]. На наступному, (i +1)-м кожному кроці алгоритму беремо a [i +1] і вставляємо на потрібне місце в готову частину масиву. Пошук відповідного місця для чергового елемента вхідної послідовності здійснюється шляхом послідовних порівнянь з елементом, що стоять перед ним. У залежності від результату порівняння елемент або залишається на поточному місці (вставка завершена), або вони міняються місцями і процес повторюється.
Таким чином, в процесі вставки ми "просіваємо" елемент x до початку масиву, зупиняючись у разі, коли
1. Знайдіть елемент, менший x або
2. Досягнуто початок послідовності.
Type
arrType = Array [1 .. n] Of Integer;
Procedure Insert (Var ar: arrType; n: Integer);
Var i, j, T: Integer;
Begin
For i: = 1 To n Do Begin
T: = ar [i];
j: = Pred (i);
While (T <ar [j]) and (j> 0) Do Begin
ar [Succ (j)]: = ar [j]; Dec (j);
End;
ar [Succ (j)]: = T;
End;
End;
Складність О (n ^ 2)
Розподіляє сортування - RadixSort - цифрова - поразрядное
Нехай маємо максимум по k байт у кожному ключі (хоча за елемент сортування цілком можна прийняти і що-небудь інше, наприклад, слово - подвійний байт, або букви, якщо сортуються рядки). K повинно бути відомо заздалегідь, до сортування.
Розрядність даних (кількість можливих значень елементів) - m - також повинна бути відома заздалегідь і постійна. Якщо ми сортуємо слова, то елемент сортування - літера, m = 33. Якщо на самому довгому слові 10 літер, k = 10. Зазвичай ми будемо сортувати дані за ключами з k байт, m = 256.
Нехай у нас є масив source з n елементів по одному байту в кожному.
Для прикладу можете виписати на листочок масив source = <7, 9, 8, 5, 4, 7, 7>, і проробити з ним всі операції, маючи на увазі m = 9.
I. Складемо таблицю розподілу. У ній буде m (256) значень і заповнюватися вона буде так:
for i: = 0 to Pred (255) Do distr [i]: = 0;
for i: = 0 to Pred (n) Do distr [source [i]]: = distr [[i]] + 1;
Для нашого прикладу будемо мати distr = <0, 0, 0, 0, 1, 1, 0, 3, 1, 1>, тобто i-ий елемент distr [] - кількість ключів зі значенням i.
II. Заповнимо таблицю індексів:
index: array [0 .. 255] of integer;
index [0]: = 0;
for i: = 1 to Pred (255) Do index [i] = index [i-1] + distr [i-1];
У index [i] ми помістили інформацію про майбутнє кількості символів у відсортованому масиві до символу з ключем i.
Hаприклад, index [8] = 5: маємо <4, 5, 7, 7, 7, 8>.
III. А тепер заповнюємо новостворений масив sorted розміру n:
for i: = 0 to Pred (n) Do Begin
sorted [index [source [i]]]: = source [i];
{
попутно змінюємо index вже вставлених символів, щоб
однакові ключі йшли один за іншим:
}
index [source [i]]: = index [source [i]] +1;
End;
Отже, ми навчилися за O (n) сортувати байти. А від байтів до рядків і чисел - 1 крок. Нехай у нас в кожному числі - k байт.
Будемо діяти в десятковій системі і сортувати звичайні числа (m = 10).
спочатку вони в сортуємо по молодшому на один безладді: розряду: вище: і ще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554
Hу ось ми і відсортували за O (k * n) кроків. Якщо кількість можливих різних ключів ненабагато перевищує загальне їх число, то 'поразрядное сортування'; виявляється набагато швидше навіть 'швидкого сортування'!
Реалізація алгоритму "розподіляє" сортування:
Const
n = 8;
Type
arrType = Array [0 .. Pred (n)] Of Byte;
Const
m = 256;
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);
Procedure RadixSort (Var source, sorted: arrType);
Type
indexType = Array [0 .. Pred (m)] Of Byte;
Var
distr, index: indexType;
i: integer;
begin
fillchar (distr, sizeof (distr), 0);
for i: = 0 to Pred (n) do
inc (distr [source [i]]);
index [0]: = 0;
for i: = 1 to Pred (m) do
index [i]: = index [Pred (i)] + distr [Pred (i)];
for i: = 0 to Pred (n) do
begin
sorted [index [source [i]]]: = source [i];
index [source [i]]: = index [source [i]] +1;
end;
end;
var
b: arrType;
begin
RadixSort (a, b);
end.
Теорія чисел.
Теорія чисел є, можливо, самим цікавим і красивим розділом математики. Доказ Евклідом існування нескінченної кількості простих чисел залишається таким же чітким і ясним сьогодні, яким воно було більше двох тисяч років тому. Такі невинні питання, як існують рішення рівняння а n + b n = c n для цілих a, b, c і n> 2, часто виявляється зовсім не такими безневинними. Більш того, це формулювання великої теореми Ферма!
Комп'ютери вже довгий час використовують у дослідженнях теорії чисел. Проведення деяких обчислень, пов'язаних з теорією, для великих чисел вимагає значної ефективності. На щастя, існує безліч алгоритмів, які можуть допомогти в цьому.
Прості числа
Ціле число р> 1 називають простим, якщо воно ділиться тільки на 1 і на саме себе. Кажучи іншими словами, якщо р - просте число, то рівність р = a * b для цілих a ≤ b еквівалентно тому, що a = 1 і b = p. Перші десять простих чисел: 2, 3, 5, 7,11, 13, 17, 19, 23 і 29.
Ми говоримо, що число р є множником числа х, якщо воно входить до його розкладання на прості множники. Будь-яке число не є простим, називається складеним.
Знаходження кількості дільників і самих дільники числа а.
Для цього будемо перебирати всі числа i, що підходять на роль дільника. Очевидно, що 1 <= i <= a. Щоб прискорити роботу алгоритму зауважимо, що якщо i - дільник а, то a / i - теж дільник a, і до того ж одне з чисел i та a / i не перевищує Sqrt (a) (якщо припустити противне, то отримаємо a = i * (a / i)> Sqrt (a) * Sqrt (a) = a - протиріччя). Тому досить перебирати числа i в межах від 1 до Trunc (Sqrt (a)) і при знаходженні, що деякий i - дільник видавати, що a / i - теж дільник і збільшувати кількість дільників на 2. Цей алгоритм не буде працювати, коли a - точний квадрат, що легко виправляється.
Наведені міркування реалізовані в алгоритмі (2):
c: = 0;
For i: = 1 to Trunc (Sqrt (a)) do
If a mod i = 0 then begin
If i * i = a then begin
c: = c +1;
WriteLn ('Знайдено дільник', i);
end
else begin
c: = c +2;
if i = a div i then c: = c-1;
WriteLn ('Знайдено дільник', i);
WriteLn ('Знайдено дільник', a div i);
end;
end;
WriteLn ('Кількість дільників', c);
Для того, щоб перевірити, чи є число простим, потрібно порахувати кількість його дільників, використовуючи алгоритм 2.
Знаходження всіх простих чисел, що не перевищують заданий число N.
Можливі кілька підходів до вирішення цього завдання:
1) Метод Ератосфена. Випишемо всі числа від 2 до N. Потім, поки є числа, які не викреслені і не обведені, робимо наступний набір операцій: обводимо мінімальне з чисел, що залишилися, викреслюємо всі числа, кратні йому. Після закінчення роботи алгоритму всі прості числа будуть виділені.
Доказ. Даний алгоритм не може викреслити просте число, тому що якщо число викреслюється, то воно явно ділиться на якесь інше, не рівне йому. Тепер доведемо по індукції, що для будь-якого N алгоритм обводить всі прості числа, не перевершують N. База: при N = 2 твердження вірне, оскільки 2 буде обведено на 1-му кроці. Індуктивний перехід: нехай твердження вірне при 2 <= N <= k-1. Розглянемо N = k. Якщо N - складене, то у числа N є простий дільник t, за який можна взяти, наприклад, його мінімальний дільник (чому?). За індукції, на якомусь кроці число t буде обведено, на цьому ж кроці буде викреслено N. Якщо ж N - просте, то воно не може бути викреслене, тому на якомусь кроці стане мінімальним з решти і буде обведено. Затвердження доведено.
Наведені міркування реалізовані в алгоритмі:
FillChar (B, SizeOf (B), True);
For j: = 2 to N do
If B [j] then
Begin
WriteLn (j, '- просте');
i: = 2 * j;
While i <= N do begin
B [i]: = False;
i: = i + j;
End;
end;
2) Будемо зберігати в масиві вже знайдені прості числа. Розглядаючи чергове число X, будемо ділити його на все вже отримані прості числа, не перевершують Trunc (Sqrt (X)).
Доказ. Коректність роботи алгоритму випливає з того, що, якщо число - складене, то воно обов'язково має простий дільник, не переважаючий кореня з цього числа.
Основна теорема алгебри.
Будь-яке число N представимо у вигляді добутку простих співмножників, причому таке подання єдино з точністю до порядку співмножників.
Доказ. Для доказу існування розкладання скористаємося індукцією по N з урахуванням, що будь-яке число або є простим, або має простий дільник (проведіть самі). Доведемо єдиність. Припустимо, що N = p1p2 ... pk = t1t2 ... tl, де всі співмножники - прості числа, причому p1 <= ... <= pk і t1 <= ... <= tl. З урахуванням міркувань індукції, достатньо довести, що p1 = t1 (чому?). Припустимо гидке й нехай, для визначеності, p1 <t1. Так як t1, ..., tl - прості, то p1 не є дільником кожного з цих чисел. Тим не менш p1 - дільник їхні твори. Тому повинні існувати числа a1, b1, ..., al, bl такі, що a1b1 = t1, ..., albl = tl, a1a2 ... ak = p1. Але, оскільки будь-ai = 1 або ai = ti (адже ti - просте число), то a1a2 ... ak або дорівнює 1, або не менше t1, що свідомо менше, ніж p1. Протиріччя.
З доведення теореми слідує наступний алгоритм знаходження розкладання числа на прості множники:
D: = 2;
While d <= Trunc (Sqrt (N)) do begin
While N mod d = 0 do begin
WriteLn (d);
N: = N div d;
end;
If d = 2 then d: = 3
else d: = d +2;
end;
If N <> 1 then WriteLn (N);
НОД і НОК
Якщо число c є дільником a і b, то говорять, що число c є загальним дільником чисел a і b. Число d називають найбільшим загальним дільником (НОД) чисел a і b, якщо d - загальний дільник a та b і будь-який загальний дільник a та b є дільником d.
Якщо числа a і b є дільниками числа c, то говорять, що число c є спільним кратним чисел a і b. Число d називають найменшим спільним кратним (НОК) чисел a і b, якщо d - спільне кратне a та b і d - дільник будь-якого загального кратного a і b.
Якщо a =
, B = 
, Де ai, bi> = 0, то, очевидно, що НОД (a, b) = 
і НОК (a, b) = 
. Звідси, враховуючи, що max {x, y} + min {x, y} = x + y, отримуємо ab = НСД (a, b) НОК (a, b).
Знайдемо НОД (a, b). Вірні такі рівності:
1) НОД (a, b) = НСД (b, a) - випливає з визначення.
2) НОД (a, 0) = a - очевидно.
3) НОД (a, b) = НСД (a mod b, b).
Доказ. Доведемо спочатку, що НОД (a, b) = НСД (ab, b). Нехай c - загальний дільник a та b. Тоді a = kc, b = lc, ab = (kl) c, тому з - загальний дільник ab і b. Аналогічно показується, що якщо c - загальний дільник (ab) і b, то з - загальний дільник a та b. Тому безлічі загальних дільників пар (a, b) і (ab, b) збігаються. А значить НОД (a, b) = НСД (ab, b). Застосовуючи цю формулу a div b разів, отримаємо необхідний.
Для знаходження НОД можна використовувати наступний алгоритм Евкліда:
While (a <> 0) and (b <> 0) do
If a> b then a: = a mod b
else b: = b mod a;
nod: = a + b;
Коректність цього алгоритму випливає з вищевказаних властивостей ПОРА.
Справедливо наступне твердження: існує цілі числа u і v такі, що au + bv = НСД (a, b).
Доказ. Знаходячи НОД за алгоритмом Евкліда, ми, по суті справи, записали такі рівняння: a = q1b + r1, b = q2r1 + r2, ..., rn = qn +2 rn +1 + rn +2, rn +1 = qn +3 rn + 2. Причому НОД (a, b) = rn +2. Розгорнемо цей ланцюжок рівностей в інший бік: НОД (a, b) = rn +2 = rn-qn +2 rn +1 = rn-qn +2 (rn-1-qn +1 rn) =-qn +2 rn-1 + ( 1 + qn +2 qn +1) rn = krn-1 + lrn = ... = Ab + Br1 = Ab + B (a-q1b) = Ba + (A-Bq1) b = au + bv, що й потрібно було довести.
З цього докази слід алгоритм знаходження u і v по a і b.
І на завершення розглянемо завдання, пропоновану на одній з олімпіад минулих років.
Красиві числа
Саша вважає красивими числа, десятковий запис яких не містить інших цифр, крім 0 і k (1 ≤ k ≤ 9). Наприклад, якщо k = 2, то такими числами будуть 2, 20, 22, 2002 і т.п. Решта числа Сашкові не подобаються, тому він представляє їх у вигляді суми красивих чисел. Наприклад, якщо k = 3, то число 69 можна представити так: 69 = 33 + 30 + 3 + 3.
Однак, не будь-яке натуральне число можна розкласти в суму красивих цілих чисел. Наприклад, при k = 5 число 6 можна представити в такому вигляді. Але якщо використовувати красиві десяткові дробу, то це можна зробити: 6 = 5.5 + 0.5.
Нещодавно Сашко вивчив періодичні десяткові дроби і почав використовувати і їх в якості доданків. Наприклад, якщо k = 3, то число 43 можна розкласти так: 43 = 33. (3) + 3. (3) + 3 + 3. (3).
Виявляється, будь-яке натуральне число можна представити у вигляді суми позитивних красивих чисел. Але таке розкладання не єдино - наприклад, число 69 можна також представити й як 69 = 33 + 33 + 3. Сашу зацікавило, яку мінімальну кількість доданків потрібно для представлення числа n у вигляді суми красивих чисел.
Потрібно написати програму, яка для заданих чисел n і k знаходить розкладання числа n у суму позитивних красивих чисел з мінімальною кількістю доданків.
Формат вхідних даних
У вхідному файлі записані два натуральних числа n та k (1 ≤ n ≤ 10 вересня, 1 ≤ k ≤ 9).
Формат вихідних даних
У вихідний файл виведіть розкладання числа n у суму позитивних чисел, які містять лише цифри 0 і k, кількість доданків у якому мінімально. Розкладання повинно бути представлено у вигляді:
n = a 1 + a 2 +...+ a m
Складові a 1, a 2, ..., a m повинні бути виведені без провідних нулів, без зайвих нулів наприкінці дробової частини. Запис кожного доданка повинна бути такою, що довжини періоду і передперіодом дробової частини мають мінімально можливу довжину. Наприклад, неправильно виведені числа: 07.7; 2.20; 55.5 (5); 0. (66); 7. (0); 7. ; .5; 0.33 (03). Їх слід виводити так: 7.7; 2.2; 55. (5); 0. (6); 7; 7; 0.5; 0.3 (30).
Передперіодом і період кожного із виведених чисел повинні складатися не більше ніж з 100 цифр. Гарантується, що хоча б одне таке рішення існує. Якщо шуканих рішень декілька, виведіть будь-яке. Порядок доданків може бути довільним.
Вихідний файл не повинен містити пробілів.
Приклади
n = a 1 + a 2 + ... + A m,
де кожен a i складається тільки з цифр 0 і k.
Розділимо обидві частини на k. Зрозуміло, що при цьому в числах a i всі цифри k заміняться на одиниці, а нулі залишаться нулями.
Виходить нове формулювання завдання: представити число n / k як суму чисел, що складаються тільки з цифр 0 і 1. Стверджується, що відповідь на неї такий: мінімальна кількість доданків одно максимальної цифри в десятковому запису числа n / k.
Доведемо спочатку, що меншим числом доданків обійтися не можна. Будемо діяти від протилежного: припустимо, що можна обійтися меншим числом доданків. При цьому, так як максимальна цифра в n / k не перевищує 9, то ми припускаємо, що можна обійтися не більше ніж вісьмома доданками. Випишемо ці складові один під одним (навіть якщо вони нескінченні) і складемо «у стовпчик». При цьому переносів не буде (всі цифри 0 або 1, і цифр у кожному стовпці не більше 8). Розглянемо той стовпець, в якому при підсумовуванні повинна вийти максимальна цифра з десяткової запису n / k. Навіть якщо у всіх доданків у цьому стовпці стоять одиниці, все одно потрібна сума не набирається. Отримали протиріччя; твердження доведено.
Тепер, мабуть, зрозуміло, як домогтися описаного вище відповіді: треба просто в кожному стовпці розставити стільки одиниць, скільки потрібно отримати в сумі - це відповідна фігура з n / k.
Приклад. Нехай n = 15, k = 7.
15 / 7 = 2, (142 857)
Максимальна цифра - 8. Підберемо відповідні вісім доданків.
1, (111111)
1, (011111)
0, (010111)
0, (010111)
0, (000 111) +
0, (000101)
0, (000101)
0, (000100)
----------
2, (142 857)
Тепер помножимо ці числа на 7, і отримаємо наступне вірне рівність:
15 = 7, (7) + 7 (077 777) + 0, (070 777) + 0, (070 777) + 0, (000 777) + 0, (000 707) + 0, (000 707) + 0, (000700)
Таким чином, правильне рішення складається з наступних етапів: представлення числа n / k в зручному для обробки форматі (з акуратним урахуванням періоду), складання шуканих доданків і їх висновок з урахуванням наявних вимог.
Список використовуваної літератури:
1. Стівен С. Скіена, Мігель А. Ревілла Олімпіадні завдання з програмування, Москва Кудиц-Образ, 2005
2. Немнюгин С.А. Turbo Pascal, видавничий дім «Пітер», 2004
Прості числа
Ціле число р> 1 називають простим, якщо воно ділиться тільки на 1 і на саме себе. Кажучи іншими словами, якщо р - просте число, то рівність р = a * b для цілих a ≤ b еквівалентно тому, що a = 1 і b = p. Перші десять простих чисел: 2, 3, 5, 7,11, 13, 17, 19, 23 і 29.
Ми говоримо, що число р є множником числа х, якщо воно входить до його розкладання на прості множники. Будь-яке число не є простим, називається складеним.
Знаходження кількості дільників і самих дільники числа а.
Для цього будемо перебирати всі числа i, що підходять на роль дільника. Очевидно, що 1 <= i <= a. Щоб прискорити роботу алгоритму зауважимо, що якщо i - дільник а, то a / i - теж дільник a, і до того ж одне з чисел i та a / i не перевищує Sqrt (a) (якщо припустити противне, то отримаємо a = i * (a / i)> Sqrt (a) * Sqrt (a) = a - протиріччя). Тому досить перебирати числа i в межах від 1 до Trunc (Sqrt (a)) і при знаходженні, що деякий i - дільник видавати, що a / i - теж дільник і збільшувати кількість дільників на 2. Цей алгоритм не буде працювати, коли a - точний квадрат, що легко виправляється.
Наведені міркування реалізовані в алгоритмі (2):
c: = 0;
For i: = 1 to Trunc (Sqrt (a)) do
If a mod i = 0 then begin
If i * i = a then begin
c: = c +1;
WriteLn ('Знайдено дільник', i);
end
else begin
c: = c +2;
if i = a div i then c: = c-1;
WriteLn ('Знайдено дільник', i);
WriteLn ('Знайдено дільник', a div i);
end;
end;
WriteLn ('Кількість дільників', c);
Для того, щоб перевірити, чи є число простим, потрібно порахувати кількість його дільників, використовуючи алгоритм 2.
Знаходження всіх простих чисел, що не перевищують заданий число N.
Можливі кілька підходів до вирішення цього завдання:
1) Метод Ератосфена. Випишемо всі числа від 2 до N. Потім, поки є числа, які не викреслені і не обведені, робимо наступний набір операцій: обводимо мінімальне з чисел, що залишилися, викреслюємо всі числа, кратні йому. Після закінчення роботи алгоритму всі прості числа будуть виділені.
Доказ. Даний алгоритм не може викреслити просте число, тому що якщо число викреслюється, то воно явно ділиться на якесь інше, не рівне йому. Тепер доведемо по індукції, що для будь-якого N алгоритм обводить всі прості числа, не перевершують N. База: при N = 2 твердження вірне, оскільки 2 буде обведено на 1-му кроці. Індуктивний перехід: нехай твердження вірне при 2 <= N <= k-1. Розглянемо N = k. Якщо N - складене, то у числа N є простий дільник t, за який можна взяти, наприклад, його мінімальний дільник (чому?). За індукції, на якомусь кроці число t буде обведено, на цьому ж кроці буде викреслено N. Якщо ж N - просте, то воно не може бути викреслене, тому на якомусь кроці стане мінімальним з решти і буде обведено. Затвердження доведено.
Наведені міркування реалізовані в алгоритмі:
FillChar (B, SizeOf (B), True);
For j: = 2 to N do
If B [j] then
Begin
WriteLn (j, '- просте');
i: = 2 * j;
While i <= N do begin
B [i]: = False;
i: = i + j;
End;
end;
2) Будемо зберігати в масиві вже знайдені прості числа. Розглядаючи чергове число X, будемо ділити його на все вже отримані прості числа, не перевершують Trunc (Sqrt (X)).
Доказ. Коректність роботи алгоритму випливає з того, що, якщо число - складене, то воно обов'язково має простий дільник, не переважаючий кореня з цього числа.
Основна теорема алгебри.
Будь-яке число N представимо у вигляді добутку простих співмножників, причому таке подання єдино з точністю до порядку співмножників.
Доказ. Для доказу існування розкладання скористаємося індукцією по N з урахуванням, що будь-яке число або є простим, або має простий дільник (проведіть самі). Доведемо єдиність. Припустимо, що N = p1p2 ... pk = t1t2 ... tl, де всі співмножники - прості числа, причому p1 <= ... <= pk і t1 <= ... <= tl. З урахуванням міркувань індукції, достатньо довести, що p1 = t1 (чому?). Припустимо гидке й нехай, для визначеності, p1 <t1. Так як t1, ..., tl - прості, то p1 не є дільником кожного з цих чисел. Тим не менш p1 - дільник їхні твори. Тому повинні існувати числа a1, b1, ..., al, bl такі, що a1b1 = t1, ..., albl = tl, a1a2 ... ak = p1. Але, оскільки будь-ai = 1 або ai = ti (адже ti - просте число), то a1a2 ... ak або дорівнює 1, або не менше t1, що свідомо менше, ніж p1. Протиріччя.
З доведення теореми слідує наступний алгоритм знаходження розкладання числа на прості множники:
D: = 2;
While d <= Trunc (Sqrt (N)) do begin
While N mod d = 0 do begin
WriteLn (d);
N: = N div d;
end;
If d = 2 then d: = 3
else d: = d +2;
end;
If N <> 1 then WriteLn (N);
НОД і НОК
Якщо число c є дільником a і b, то говорять, що число c є загальним дільником чисел a і b. Число d називають найбільшим загальним дільником (НОД) чисел a і b, якщо d - загальний дільник a та b і будь-який загальний дільник a та b є дільником d.
Якщо числа a і b є дільниками числа c, то говорять, що число c є спільним кратним чисел a і b. Число d називають найменшим спільним кратним (НОК) чисел a і b, якщо d - спільне кратне a та b і d - дільник будь-якого загального кратного a і b.
Якщо a =
Знайдемо НОД (a, b). Вірні такі рівності:
1) НОД (a, b) = НСД (b, a) - випливає з визначення.
2) НОД (a, 0) = a - очевидно.
3) НОД (a, b) = НСД (a mod b, b).
Доказ. Доведемо спочатку, що НОД (a, b) = НСД (ab, b). Нехай c - загальний дільник a та b. Тоді a = kc, b = lc, ab = (kl) c, тому з - загальний дільник ab і b. Аналогічно показується, що якщо c - загальний дільник (ab) і b, то з - загальний дільник a та b. Тому безлічі загальних дільників пар (a, b) і (ab, b) збігаються. А значить НОД (a, b) = НСД (ab, b). Застосовуючи цю формулу a div b разів, отримаємо необхідний.
Для знаходження НОД можна використовувати наступний алгоритм Евкліда:
While (a <> 0) and (b <> 0) do
If a> b then a: = a mod b
else b: = b mod a;
nod: = a + b;
Коректність цього алгоритму випливає з вищевказаних властивостей ПОРА.
Справедливо наступне твердження: існує цілі числа u і v такі, що au + bv = НСД (a, b).
Доказ. Знаходячи НОД за алгоритмом Евкліда, ми, по суті справи, записали такі рівняння: a = q1b + r1, b = q2r1 + r2, ..., rn = qn +2 rn +1 + rn +2, rn +1 = qn +3 rn + 2. Причому НОД (a, b) = rn +2. Розгорнемо цей ланцюжок рівностей в інший бік: НОД (a, b) = rn +2 = rn-qn +2 rn +1 = rn-qn +2 (rn-1-qn +1 rn) =-qn +2 rn-1 + ( 1 + qn +2 qn +1) rn = krn-1 + lrn = ... = Ab + Br1 = Ab + B (a-q1b) = Ba + (A-Bq1) b = au + bv, що й потрібно було довести.
З цього докази слід алгоритм знаходження u і v по a і b.
І на завершення розглянемо завдання, пропоновану на одній з олімпіад минулих років.
Красиві числа
| Ім'я вхідного файлу: | numbers.in |
| Ім'я вихідного файлу: | numbers.out |
| Максимальний час роботи на одному тесті: | 1 секунда |
| Максимальний об'єм використовуваної пам'яті: | 64 мегабайта |
Однак, не будь-яке натуральне число можна розкласти в суму красивих цілих чисел. Наприклад, при k = 5 число 6 можна представити в такому вигляді. Але якщо використовувати красиві десяткові дробу, то це можна зробити: 6 = 5.5 + 0.5.
Нещодавно Сашко вивчив періодичні десяткові дроби і почав використовувати і їх в якості доданків. Наприклад, якщо k = 3, то число 43 можна розкласти так: 43 = 33. (3) + 3. (3) + 3 + 3. (3).
Виявляється, будь-яке натуральне число можна представити у вигляді суми позитивних красивих чисел. Але таке розкладання не єдино - наприклад, число 69 можна також представити й як 69 = 33 + 33 + 3. Сашу зацікавило, яку мінімальну кількість доданків потрібно для представлення числа n у вигляді суми красивих чисел.
Потрібно написати програму, яка для заданих чисел n і k знаходить розкладання числа n у суму позитивних красивих чисел з мінімальною кількістю доданків.
Формат вхідних даних
У вхідному файлі записані два натуральних числа n та k (1 ≤ n ≤ 10 вересня, 1 ≤ k ≤ 9).
Формат вихідних даних
У вихідний файл виведіть розкладання числа n у суму позитивних чисел, які містять лише цифри 0 і k, кількість доданків у якому мінімально. Розкладання повинно бути представлено у вигляді:
n = a 1 + a 2 +...+ a m
Складові a 1, a 2, ..., a m повинні бути виведені без провідних нулів, без зайвих нулів наприкінці дробової частини. Запис кожного доданка повинна бути такою, що довжини періоду і передперіодом дробової частини мають мінімально можливу довжину. Наприклад, неправильно виведені числа: 07.7; 2.20; 55.5 (5); 0. (66); 7. (0); 7. ; .5; 0.33 (03). Їх слід виводити так: 7.7; 2.2; 55. (5); 0. (6); 7; 7; 0.5; 0.3 (30).
Передперіодом і період кожного із виведених чисел повинні складатися не більше ніж з 100 цифр. Гарантується, що хоча б одне таке рішення існує. Якщо шуканих рішень декілька, виведіть будь-яке. Порядок доданків може бути довільним.
Вихідний файл не повинен містити пробілів.
Приклади
| numbers.in | numbers.out |
| 69 3 | 69 = 33 +33 +3 |
| 5 червня | 6 = 5.5 +0.5 |
| 10 вересня | 10 = 9. (9) |
Розбір завдання «Гарні числа»
Розглянемо шукане рівність:n = a 1 + a 2 + ... + A m,
де кожен a i складається тільки з цифр 0 і k.
Розділимо обидві частини на k. Зрозуміло, що при цьому в числах a i всі цифри k заміняться на одиниці, а нулі залишаться нулями.
Виходить нове формулювання завдання: представити число n / k як суму чисел, що складаються тільки з цифр 0 і 1. Стверджується, що відповідь на неї такий: мінімальна кількість доданків одно максимальної цифри в десятковому запису числа n / k.
Доведемо спочатку, що меншим числом доданків обійтися не можна. Будемо діяти від протилежного: припустимо, що можна обійтися меншим числом доданків. При цьому, так як максимальна цифра в n / k не перевищує 9, то ми припускаємо, що можна обійтися не більше ніж вісьмома доданками. Випишемо ці складові один під одним (навіть якщо вони нескінченні) і складемо «у стовпчик». При цьому переносів не буде (всі цифри 0 або 1, і цифр у кожному стовпці не більше 8). Розглянемо той стовпець, в якому при підсумовуванні повинна вийти максимальна цифра з десяткової запису n / k. Навіть якщо у всіх доданків у цьому стовпці стоять одиниці, все одно потрібна сума не набирається. Отримали протиріччя; твердження доведено.
Тепер, мабуть, зрозуміло, як домогтися описаного вище відповіді: треба просто в кожному стовпці розставити стільки одиниць, скільки потрібно отримати в сумі - це відповідна фігура з n / k.
Приклад. Нехай n = 15, k = 7.
15 / 7 = 2, (142 857)
Максимальна цифра - 8. Підберемо відповідні вісім доданків.
1, (111111)
1, (011111)
0, (010111)
0, (010111)
0, (000 111) +
0, (000101)
0, (000101)
0, (000100)
----------
2, (142 857)
Тепер помножимо ці числа на 7, і отримаємо наступне вірне рівність:
15 = 7, (7) + 7 (077 777) + 0, (070 777) + 0, (070 777) + 0, (000 777) + 0, (000 707) + 0, (000 707) + 0, (000700)
Таким чином, правильне рішення складається з наступних етапів: представлення числа n / k в зручному для обробки форматі (з акуратним урахуванням періоду), складання шуканих доданків і їх висновок з урахуванням наявних вимог.
Список використовуваної літератури:
1. Стівен С. Скіена, Мігель А. Ревілла Олімпіадні завдання з програмування, Москва Кудиц-Образ, 2005
2. Немнюгин С.А. Turbo Pascal, видавничий дім «Пітер», 2004