Требуется обновление браузера.

Алгоритм Бома


Просмотров: 1073
10 апреля 2016 года
Цитата
Ну, если я чего решил — я выпью-то обязательно

Вот какую задачку по информатике (начальная школа) мне вчера дали посмотреть:

На заметку
Бим загадывает число. Бом просит его выполнить с ним действия по алгоритму и всегда отгадывает результат.
Почему Бому удаётся этот фокус? Выполни действия для трёх разных чисел и запиши, что получится.

123456
Начало
Загадай и запиши трёхзначное число A, у которого первая цифра не совпадает с последней
Запиши число A наоборот
Из большего числа вычти меньшее
Выпиши из полученного результата цифру, стоящую на месте десятков
Конец

Вторая часть задания не взывает вопросов: формально прогнать числа через алгоритм, выписывая промежуточные значения.
Что по-настоящему заняло меня: почему фокус удаётся? Нетрудно заметить, что на выходе алгоритма всегда будет "9", но почему?

Рассмотрим число A, поступающее на вход алгоритма. Так как далее я буду оперировать как самой величиной, так и её представлением, то сразу оговорюсь: все числа в решении записываются в десятичной позиционной системе счисления.

Число A может быть представлено тройкой цифр a1, a2, a3 - запишем этот факт следующим образом: A={a1 a2 a3}. Например: 123={1 2 3}.

Итак, дано некоторое число A={a1 a2 a3}, причём a1a3.

Записываем число наоборот. Пусть это будет A'={a3 a2 a1}.

Пусть a1>a3. Эта конкретика не повлияет на решение, так как в алгоритме указано, что в противном случае - порядок операндов меняется. Данное условие нужно только для того, чтобы не получить в результате отрицательное число, однако самому алгоритму важен только модуль числа.

При a1>a3, необходимо найти разность: A-A'.

Вот тут необходимо вспомнить принцип кодирования чисел в позиционных системах счисления. Этот принцип зазубривается в младших классах и забывается к старшим (так как используется формально, на автомате).

A-A'=
= {a1 a2 a3} - {a3 a2 a1} =
= a1*100 + a2*10 + a3 - ( a3*100 + a2*10 + a1 ) =
= a1*(100-1) + a2*(10-10) + a3*(1-100) =
Ой-ой-ой: при третьем коэффициенте вот-вот получится отрицательное число! Хотя, используя другую формальную запись, этого, вероятно, можно было бы избежать - у меня стали закрадываться сомнения, что в задаче требуется доказать выход алгоритма аналитически. Но меня было уже не остановить.
= 99*a1 - 99*a3 =
= 99*(a1 - a3).

Фух! Так как a1>a3, и a1, a3 числа (то есть: не меньше 0 и не больше 9) то:

1 ⩽ (a1 - a3) ⩽ 9

Обозначим, для удобства, получившийся результат новой буквой: B = 99*(a1 - a3) = {b1 b2 b3}.

Что делать дальше - непонятно. Я обнаружил, что у окружающих уже пропал интерес к задаче, а у меня - только подогрелся.

Судя по известному нам результату работы алгоритма, необходимо доказать, что b2 = 9, для всех возможных значений a1 и a3.

Учитывая конечность множества допустимых значений, задачу можно было бы свести к брутфорсу (полному перебору), но это "не спортивно". К этому моменту я уже понял, что правильный ответ, на поставленный в задаче вопрос: "алгоритм всегда даёт 9 в результате". Я отхлебнул чая из кружки и продолжил решение.

Предположим, что мы производим операцию умножения над числами U и V, получая C. Слегка конкретизируем под данную ситуацию, чтобы совсем не закопаться:

{u1 u2} × {v1} = {c1 c2 c3}

Чему равно c2? Если представить себе умножение в столбик, выполняемое над нашими коэффициентами, то:

c2 = ( floor( (u2*v1)/10 ) + (u1*v1) ) mod 10 ,

где floor - округление в меньшую сторону (взятие целой части), а mod 10 - остаток от деления на 10. Обе операции нелинейны, а значит дальше упростить выражение не получится. Всё стало ещё "лучше", чем было.

Подумав ещё, и вспомнив семантику операций, я понял, что удобнее переписать выражение для c2 следующим образом:

{q1 q2} = u2*v1
{w1 w2} = u1*v1 + q1,
c2 = w2

Выглядит страшно, но легко понять на примере: допустим Вы умножаете 65 на 8 - в ответе получится 520. Цифра 2 получилась из результата умножения 6*8 (u1*v1) к которому вы прибавили 4 (q1, перенос, от умножения 5*8 (u2*v1)), притом Вы оставили только последнюю цифру (w2).

Запомним пока этот результат и отвлечёмся на одно свойство, позволяющее легко запомнить таблицу умножения на 9.

На заметку
Расположите перед собой две (свои) руки, ладонями вниз (левую руку - слева). Пронумеруем пальцы от мизинца левой руки до мизинца правой - от 1 до 10. Загните, например, палец №5 (большой палец левой руки): слева от загнутого у Вас будет 4 пальца, а справа - 5. Пальцы слева - это десятки, справа - единицы. Иными словами: 9*5=45.


По мере увеличения множителя при 9, цифра в разряде десятков в ответе увеличивается, а цифра в разряде единиц - убывает. Иными словами:

n*9 = Z = {z1 z2} = {(n-1) (10-n)}.

Возвращаемся к B = 99*(a1 - a3):

{q1 q2} = 9*(a1 - a3)
{w1 w2} = 9*(a1 - a3) + q1
b2 = w2

Используем рассмотренное свойство:

q1 = (a1 - a3) - 1,

тогда

{w1 w2} = 9*(a1 - a3) + a1 - a3 - 1,
{w1 w2} = 10*(a1 - a3) - 1

Так как a1, a3 - цифры , то 10*(a1 - a3) является числом кратным десяти. При вычитании из такого числа единицы, последний разряд становится равным 9:

w2 = 9.

Последнее усилие:

b2 = w2,
b2 = 9

что и требовалось доказать.

Ужас. Пожалуй, лучше ограничиться ответом: "результат работы алгоритма всегда равен девяти".

Простое решение


Стоило только поделиться своими сомнениями, как мне подсказали более простое решение.

Суть в том, чтобы даже и не начинать расписывать выражение (A-A'), а сразу вывести формулу для b2 - это, к тому же, проще, чем заниматься аналогичным для умножения. Итак:

A-A'=
= {a1 a2 a3} - {a3 a2 a1} =
= {b1 b2 b3} =
= B.

Так как по условию вычитать надо из большего меньшее, мы приняли a1>a3, а отсюда логично вытекает, что: a3<a1. Из этого факта можно сделать вывод, что при вычислении разности a3 и a1 (в процессе подсчёта младшего разряда результата A-A'), мы займём десяток из второго разряда. Как раз формулу для второго разряда мы и ищем (запишем только её):

b2 = (a2 - 1) - a2.

Занятый десяток выливается в вычитание единицы из разряда десятков в числе A. Теперь, очевидно, наступает ситуация, когда из меньшего ( a2 - 1 ) вычитают большее ( a2 ). Займём десяток в следующем разряде (по-прежнему, рассматриваем формулу для b2):

b2 = (a2 - 1 + 10) - a2.

Если раскрыть скобки, то:

b2 = a2 - 1 + 10 - a2 =
+a2 и -a2 уничтожаются
= 10 - 1 =
= 9.

Всё.

Запись опубликована в категориях:

ЕГЭ и прочие радости Цифры и числа  
 

Комментарии

Инкогнито
  Загружаем captcha