kafinfo КАФЕДРА ІНФОРМАТИКИ

Baner_abiturient_5_prichin

Zadacha_tyzhnya_khopka_zadacha_tyzhnyaZadacha_tyzhnya_khopka_2_analiz_rezultativZadacha_tyzhnya_khopka_3_reytyngZadacha_tyzhnya_khopka_4_arhiv

 

 

Аналіз розв'язку задачі «Двоякі числа»

 

Для вирішення задачі скористаємося методом послідовного перебору. Будемо перевіряти числа, починаючи з N і поступово віддаляючись від N: спочатку такі, що відрізняються від N на 1 (менше на -1, більше на +1), потім на 2 (менше на -2, більше на +2), потім на 3 і т.д.

Введемо допоміжні змінні:

M - поточне число, яке піддається перевірці;

модуль різниці між M і N зберігатимемо у змінній d, знак різниці - у змінній sign, яка набуватиме значень -1 (M < N) або +1 (M > N);

с[1] і с[2] - змінні для зберігання двох різних цифр двоякого числа;

k - кількість знайдених різних цифр у числі M;

a - допоміжна змінна, використовувана для виділення цифр числа M;

F - змінна-прапорець, яка зберігає значення 0, доки двояке число не знайдене, і набуває значення 1, якщо таке число знайдене.

Шукане значення M можна знайти за допомогою такого алгоритму:

{надаємо початкових значень змінним; враховуємо, що числа, які менші 100, є двоякими}
M:= N;
якщо M < 100 то F:= 1
інакше
початок
F := 0;
d := 0;
sign := 1;
кінець
{розпочинаємо цикл перебору чисел до знаходження двоякого числа}
повторювати
M := N+ sign *d;
a := M;
k := 0;
{перевіряємо в циклі, чи є поточне число M (тобто a) двояким}
поки k 0
початок циклу
r := a mod 10;
якщо (k=0) or (k=1) and (r c[1]) то
початок
k := k+1;
c[k] := r;
кінець
якщо (k=2) and (r c[1]) and (r c[2]) то k := k+1;
a := a div 10;
кінець циклу;
якщо k<3 то F := 1
інакше
початок
d := d+(sign+1) div 2;
sign := -sign;
кінець
до F = 1;

{виводимо M - двояке число, найближче до заданого N}

Наведемо пояснення щодо роботи операторів d:= d+(sign+1)div2; sign:=-sign. Значення d зростає на 1, якщо sign дорівнює +1, і не змінюється, якщо sign дорівнює -1. Знак sign кожного разу змінюється на протилежний.

Отже, послідовність значень M, що перевіряються на двоякість у циклі repeat-until, є такою: M=N (d = 0, sign =+1), M=N-1 (d = 1, sign = -1), M=N+1 (d = 1, sign =+1), M=N-2 (d = 2, sign = -1), M=N+2 (d = 2, sign = +1) і т.д.

 

Тестова таблиця з результатами роботи програми: 

 

Номер

тесту

N
M
1 123 122
2 51 51
3 7777 7777
4 1299 1311
5 9867 9888
6 9043 9009
7 9050 9090
8 10632 11000
9 26354 26266
10 998877 998888

 

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

 

Учасник Кількість балів
1 Сергій Сальніков 4