Консультация № 63673
22.11.2006, 08:58
0.00 руб.
0 1 1
Здравствуйте, уважаемые эксперты!!!
Не поможите ли Вы мне вот стакой задачкой?
В двузначном числе на каждом шаге разрешается заменить любую цифру этого числа на остаток от деления на 10 сумму его цифр. По 2 заданным числам можно ли получить одно число из другого и за какое наименьшее количество шагов.
Например, из числа 47 на 1 шаге можно получить 17 либо 41 и т. д.
Заранее спасибо. Денис

Обсуждение

Неизвестный
22.11.2006, 13:15
общий
это ответ
Здравствуйте, Гусев Денис!
Вам поможет динамическое программирование/рекурсия.
Надо перебирать числа, до которых мы можем добраться таким образом. По-хорошему, это надо делать через стек/очередь, сохраняя в них числа, до которых мы уже добрались. Но я вам приведу пример с рекурсией.
Назовем расстоянием между числами - кол-во ходов, за кторое можно добраться указанными в условии преобразованиями от одного до другого. В массив мы будем сохранять расстояния от числа n1.
Код с комментариями в приложении.

PS: При преобразовании чисел у вас может получиться остаток от деления = 0. И если записать нуль в старший разряд, то получится уже не двухзначное число. Как решить эту проблему, я оставляю подумать вам.

Приложение:
const INFINITY_DISTANCE: byte = 255;// Т.к. двухзначных чисел всего 90, то любое расстояние не может быть больше 90. Следовательно, можно считать 255 - бесконечно большим расстоянием, т.к. оно больше любого, которое нам может встретиться.var dist: array [10..99] of byte; // создаете массив "расстояний" - то, за сколько шагов можно добраться подобными преобразованиями до данного числа.pocedure calcDistances(number, distance: byte);var r1, r2, ost, m1, m2: byte;begin // итак, мы добрались до числа number за distance ходов. dist[number] := distance; r1 := number div 10; // старший разряд r2 := number mod 10; // младший разряд ost := (r1 + r2) mod 10; m1 := r1 * 10 + ost; // заменяем младший разряд m2 := r1 * ost + r2; // заменяем старший разряд// Посмотрим, будут ли среди только что полученных чисел те, до которых мы еще не добирались или добирались, но за большее число ходов.// Если текущее кол-во ходов меньше, чем то, как если бы мы добирались другим способом, то отметием, что можно добраться за меньшее. if (dist[m1] > distance) then calcDistances(m1, distance+1); if (dist[m2] > distance) then calcDistances(m2, distance+1);end;BEGIN Read(n1, n2); // читаете эти два числа for i := 10 to 99 do begin dist[i] := INFINITY_DISTANCE; // инициализируете массив calcDistances(n1, 0); // делаете первый тривиальный вызов рекурсии - до самого числа можно добраться за 0 ходов. Дальше она сама за вас все сделает =)// после выхода из самого первого вызова рекурсивной процедуры, в dist[n2] уже записано, за какое число шагов до n2 можно добраться от n1. if dist[n2] = INFINITY_DISTANCE then writeln(‘добраться до другого числа невозможно‘) else writeln(‘Можно добраться за ‘, dist[n2], ‘ ходов‘);END.
Форма ответа