2
1

Есть алгоритм 1: На вход подается трехзначное число X. К нему прибавляется первая цифра, а в полученном числе меняются местами третья и вторая цифра. Результат работы алгоритма 1 - число Y. Нужно описать алгоритм, который получает Y и отдает X, отправив который в алгоритм 1, можно получить Y, или определяет, что это невозможно.

задан 24 Сен '14 20:42

изменен 24 Сен '14 21:01

10|600 символов нужно символов осталось
1
  1. Пусть $%999 < Y < 1009$%, тогда $%X=Y-9$%.
  2. Пусть $%Y< 1000$%. Обозначим через $%Z$% число, полученное из $%Y$% перестановкой второй и третьей цифр и через $%x$% число $%[Y/100]=[Z/100]$%. Если $%[(Z-x)/100]=[Z/100]$%, то $%X=Z-x$%.
  3. Пусть $%Y< 1000$%, $%[(Z-x+1)/100]\neq[Z/100]$% и $%[(Z-x)/100]\neq[Z/100]$%, то $%X=Z-x+1$%.
  4. В остальных случаях таких $%X$% не существует.
ссылка

отвечен 24 Сен '14 21:33

изменен 24 Сен '14 23:13

10|600 символов нужно символов осталось
0

Выразить Y через X достаточно легко при помощи операторов div и mod. Оказывается, что значениями Y не могут быть девять трёхзначных чисел: 100, 210, 320, 430, 540, 650, 760, 870, 980. При этом может получиться одно из девяти четырёхзначных чисел: 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008. У всех чисел, которые могут получиться, прообраз только один, что следует из совпадения количества.

Проверить надо два факта. Первый -- что из указанных девяти исключений ни одно получиться не могло. Это делается просто: если до перестановки цифр было 100, 201, 302, ... , 908, то такой результат не мог возникнуть в результате прибавления к трёхзначному числу его первой цифры -- как при смене старшего разряда, так и при его сохранении. Оба варианта ведут к противоречию. Например, число 403 теоретически могло получиться из числа, начинающегося с 3 или 4, но тогда в первом варианте до прибавления было 400, а во втором 399.

Второй факт состоит в том, что все остальные числа имеют хотя бы один прообраз. Опишем способ его получения. Пусть $%Y=\overline{pqr}=100p+10q+r$%, где значение $%p$% условно может принимать значение $%10$% для указанных выше вариантов.

Допустим, что $%p\le q$%. Рассмотрим трёхзначное число $%X=100p+10r+(q-p)$%. Ясно, что после прибавления цифры $%p$% и перестановки двух последних цифр получится в точности $%Y$%.

Пусть теперь $%p > q$%. Разберём два подслучая. Если $%r\ge1$%, то положим $%X=100a+10b+c$%, где $%a=p$%, $%b=r-1$%, $%c=10+q-p$%. Из условия ясно, что это десятичные цифры. После прибавления цифры $%p$% в младшем разряде оказывается цифра $%q$%, а единица переходит в следующий разряд, который становится равен $%r$%. После перестановки цифр имеет место то, что нужно.

Пусть теперь $%p > q$%, $%r=0$% (включая случай $%p=10$%). Для начала пусть $%p\le9$%. Равенство $%p=q+1$% соответствует тем вариантам, которые были выше рассмотрены как невозможные, поэтому $%p\ge q+2$%. Полагаем $%X=100a+10b+c$%, где $%a=p-1\ge1$%, $%b=9$%, $%c=11+q-p$%. Из условия вытекает, что $%1\le c\le9$% будет десятичной цифрой. После прибавления первой цифры, равной $%p-1$%, на конце получится $%q$%, а единица перейдёт в разряд десятков, прибавляясь к цифре $%9$%. Поэтому в разряде десятков окажется $%0=r$%, а к разряду сотен прибавится единица, и там получится $%p$%. Переставляем две поcледние цифры, получая $%Y$%.

Если $%p=10$%, то рассмотрению подлежат числа $%Y$% от $%1000$% до $%1008$%. Для них $%X=Y-9$%.

ссылка

отвечен 24 Сен '14 22:17

изменен 24 Сен '14 23:26

@falcao, разве для четырехзначных чисел не должны меняться местами средние цифры?

(24 Сен '14 23:13) cartesius

@cartesius: я сейчас перечитал условие -- да, Ваше замечание справедливо. Я поначалу мыслил число $%Y$% трёхзначным, поэтому запомнил условие в такой форме, как будто бы две последних цифры меняются. Сейчас внесу исправление; спасибо за замечание.

(24 Сен '14 23:22) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×179
×131
×84

задан
24 Сен '14 20:42

показан
617 раз

обновлен
24 Сен '14 23:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru