Задача тижня 19.03.12 – 25.03.12

Числовий млин

На числовому млині є жорно, яке перемелює числа наступним чином:

1. Подане число розбирається на цифри.

2. Отримані цифри сортуються спочатку в порядку спадання, і з отриманої послідовності цифр формується перше число;

3. Ці ж цифри сортуються в порядку зростання, і з отриманої послідовності цифр формується друге число;

4. З першого числа віднімається друге. Нуль на початку числа зберігається (дивись приклад).

5. Одержане значення піддається аналізу. Якщо в результаті описаної обробки число не змінилося, то воно вважається перемеленим і потрапляє в окремий відсік; інакше одержане число подається на жорно, і процедура перемелювання повторюється, починаючи з п.1.

6. Перемелене число залишається у відсіку, якщо воно відрізняється від тих, що там є.

Приклад. 1000 →  1,0,0,0   →  (1000-0001)   →  0999 →  0,9,9,9   →  (9990-0999) →  8991 →  …

1. Створіть програму, що реалізує описану процедуру.

2. Перемеліть всі цілі числа від 100 до 9999.

3. Знайдіть числа, які залишились у відсіку після перемелювання.

Аналіз розв’язку задачі «Числовий млин»

За умовою задачі ми розглядаємо числа в діапазоні [100..9999], тому з кожним таким числом потрібно виконати наступні дії:

1. Позначимо число з заданого діапазону як Х.
2. Знайдемо цифри числа Х та збережемо їх у масиві A [1..m] (m = 3 у випадку трьохзначного числа, m = 4 у випадку чотирьохзначного числа; якщо Х div 1000 = 0, то m = 3, інакше m = 4).
3. Впорядкуємо отриманий масив за зростанням. При виборі способу впорядкування слід враховувати, що для масивів невеликої розмірності найбільш доречним буде використання «бульбашкового» алгоритму (послідовне порівняння пари сусідніх елементів масиву та обмін значеннями відповідно до умови впорядкування). Перегляд елементів масиву повторюються до тих пір, поки на черговому перегляді не відбудеться жодного обміну.
4. Із упорядкованих за зростанням елементів масиву формуємо 2 числа: максимальне (maxX) та мінімальне (minX) числа.
5. Знаходимо різницю k = maxX – minX.
6. Якщо різниця не співпадає з числом Х, то перевизначимо Х: Х = k та повторимо дії пп.2-5.
7. Якщо різниця співпадає з числом Х, то число «перемелено». Перевіряємо, чи є таке число у відсіку (масиві або файлі); якщо немає, то зберігаємо його у відсіку (масиві або файлі).

кінець циклу

Результати роботи програми – числа, які залишились у відсіку після перемелювання: 0, 495, 6174

Журі оцінило надіслані розв’язки наступним чином:

Довідка.

Кожен математичний об’єкт по-своєму є оригінальним, і це повною мірою стосується такого фундаментального математичного об’єкту, яким є цілі числа. Серед них зустрічаються і просто цікаві, і такі, що мають дивовижні й несподівані властивості, які спонукають математиків до нових досліджень.

Індійський математик Капрекар відомий за межами Індії своїм відкриттям, здійсненим 55 років тому. Він винайшов число, що увійшло до теорії чисел як “постійна Капрекара”. Капрекар виявив, що будь-яке чотиризначне число x, в якому не всі цифри однакові, має таку властивість: якщо цифри числа розташувати за спаданням, а потім за зростанням та знайти різницю отриманих чисел, і з цією різницею повторити описану процедуру, то не більше ніж за сім ітерацій цей процес приведе до числа 6174, яке потім відтворюватиме саме себе. Це нерухоме число і є постійна Капрекара. Наприклад, для величини 3412 застосуємо описану вище процедуру: 4321 – 1234 = 3087 → 8730 – 378 = 8352 → 8532 – 2358 = 6174. Серед тризначних чисел нерухомим є число 495 (процедура сходиться до нього максимум за шість ітерацій для будь-якого тризначного числа, що у своєму запису не має однакових цифр).

Для чисел з великою кількістю знаків подібна процедура рано чи пізно приводить до циклічних повторень або до нерухомого числа K(n).

Для п’ятизначних та семизначних чисел нерухомого числа не існує, проте є два нерухомих шестизначних числа: 549945 і 631764, два восьмизначних: 97508421 і 63317664, два дев’ятизначних: 864197532 і 554999445, три десятизначних: 9753086421, 6333176664, 9975084201.

Більш детальну інформацію можна одержати за посиланням: http://www.trinitas.ru/rus/doc/0016/001c/1686-vs.pdf