|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Konstantin Sedanov 2:5004/84.11 13 Jan 2002 06:39:40
To : Kartohin Ruslan
Subject : Интеpесная задачка. Хочется интеpесных pешений :)
--------------------------------------------------------------------------------
Приветствую, *Kartohin*
08 Янв 02 22:43, _Kartohin Ruslan_ писАл /All/:
KR> Задача заключается в следующем:
KR>
KR> Опpеделить число, кpатное 5, котоpое пpи пеpеносе (не копиpовании!)
KR> его последней цифpы (то есть опять таки 5) в начало числа,
KR> увеличивается в 10 pаз.
KR>
KR> ХХХХ....ХХХХ5/5ХХХХ....ХХХХ=10
Такая задача (похожая) давалась на олимпиаде СибАДИ 2000-го года...
Сейчас поясню принцип ее решения.
Представим исходное число как набор цифр:
X(i), X(i-1), ... , X(2), X(1), N
Для твоего случая N=5
Число само по себе равно
X(i)*10^i + X(i-1)*10^(i-1) + ... + X(2)*100 + X(1)*10 + N
Если произвести ротацию на один разряд вправо (или другими словами,
переставить последнюю цифру вперед), то число увеличится ровно в k раз. Для
твоего случая k=10.
Суть решения заключается в том, что мы, зная N и k, сначала находим X(1),
потом, зная X(1) и k, находим X(2) и т.д.
Если мы умножим число на k, то получим:
k*X(i)*10^i + k*X(i-1)*10^(i-1) + ... + k*X(2)*100 + k*X(1)*10 + k*N
Бесспорно, что последняя цифра этого числа есть остаток от деления на 10 и
равна (k*N) mod 10.
С другой стороны, это число есть ничто иное как исходное число у которого
переставили последнюю цифру на первое место (исходя из условия задачи).
Т.е.:
k*X(i)*10^i + k*X(i-1)*10^(i-1) + ... + k*X(2)*100 + k*X(1)*10 + k*N =
= N*10^i + X(i)*10^(i-1) + X(i-1)*10^(i-2) + ... + X(2)*10 + X(1)
Из правой части равенства видно (впрочем об этом можно и так догадаться - из
условия задачи), что последняя цифра равна X(1).
Итак, последнюю цифру мы описали двумя способами, поэтому можем написать
равенство:
X(1) = (k*N) mod 10
В принципе, получить X(2) несложно. По той же формуле:
X(2) = (k*X(1) + pred) mod 10
Только здесь нужно учитывать, что k*N может быть больше 10, поэтому вводится
pred = (k*N) div 10, которое добавляется к k*X(1).
Далее:
pred' = (k*X(2) + pred) div 10
X(3) = (k*X(2) + pred) mod 10
pred = pred'
Здесь введено pred'. Это нужно, чтоб рассчитанный pred не влиял на расчет
X(3).
Впрочем, надеюсь дальнейшее понятно. Остается определить, когда нужно
остановиться. Это не сложно: 1 условие, это чтобы X(next) = N - это следует из
условия задачи, 2 условие pred=0. Если оба условия выполняются, то число
найдено.
Прошу прощения, за такое сумбурное объяснение, но в пол-шестого утра мозги
работают со скрипом... :-l
Вот для проверки накатал программку для любых k и N... Писано на паскале,
писано не красиво (впрочем, я не гнался за красивостью), зато работает. Просто
времени не хотелось тратить слишком много...
>> Это файл R_A.PAS <<
var k,n,t,p,pred:byte;
s:string;
begin
write('k: ');readln(k);
write('N: ');readln(n);
t:=n;pred:=0;s:=chr(t+48);
repeat
p:=(k*t+pred) div 10;
t:=(k*t+pred) mod 10;
pred:=p;
s:=chr(t+48)+s;
until (t=n) and (pred=0);
writeln(copy(s,2,length(s)-1));
end.
>> Это был файл R_A.PAS <<
KR> ЗЫ. Могу сказать заpанее, что это число по длине пpевосходит
KR> стандаpтные типы данных.
Да. Многие на олимпиаде пытались решить ее в лоб - однако ни один тип не
позволял этого. Решение состояло из числа, содержащего более 40 цифр.
Отмечу, правда, что решение для конкретно твоей задачи - короткое. Это "05".
Всё, пока хватит слов.
... Долго жить впотьмах привыкали мы.
--- ъ (C) Высоцкий В.С.
* Origin: Ты живешь - сильно, ты жизни - достоин! (2:5004/84.11)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
