Автомат получает на вход трехзначное десятичное число
Автор Mr.Mind задал вопрос в разделе Другие языки и технологии
помогите решить, эту задачу и получил лучший ответ
Ответ от Алексей Кузьминов[гуру]
Если в этом разделе, то сразу в лоб: перебрать программно все трёхзначные числа (100…999), отсортировать результаты и проверить.
Но есть и другой вариант:
Можно попробовать декодировать из записанного числа суммы из пункта 1:
- результат будет 2…4-значный
- если результат 2- или 4-значный, то делим его пополам
- если результат 3-значный, то имеем 2 варианта деления, различающиеся тем, к старшему или младшему разряду присоединим средний
Получим 2 числа: старшее и младшее. Проверим критерии:
1. Старшее в диапазоне 1…18, младшее - 0…18
2. Старшее => младшее
3. Перебрать все числа 0…9 (кандидаты на среднее число) , от вычитания которого от обоих получатся 1…9 для старшего и 0…9 для младшего
Если критерии не сошлись, то нет решения:
+1616: 16 16 - среднее например 8, исходное 888
+169: 1 69 - не по 1. 16 9 - среднее 8, исходное 881
-163: 1 63 - не по 1. 16 3 - не по 3 (нет кандидата)
-1916: 19 16 - не по 1
-1619: 16 19 - не по 1
-316: 3 16 - не по 2. 31 6 - не по 1
-916: 9 16 - не по 2. 91 6 - не по 1
+116: 1 16 - не по 2. 11 6 - среднее 2, исходное 924
22 ответа
Считаем:
16 16
16 9
11 6
====
3 числа
Алексей Кузьминов дал хороший развернутый и, главное, правильный ответ.
Но реализовать все можно проще, если получше развернуть теорию.
Обозначим цифры трехзначного числа а, b, c (по убыванию разрядов) , тогда число запишется как 100а+10b+c.
Теперь рассмотрим операции, которая выполняет машина.
Цифры (по определению) не могут быть больше 9 и меньше 0.
Обозначим получаемое на выходе число как N. Тогда операции машины можно записать так:
1) а+b
2) b+c
3) if ( (a+b) > (b+c) ) { if ((b+c)>=10) N=100(a+b)+(b+c); else N=10(a+b)+(b+c); }
4) if ( (a+b) < (b+c) ) { if ((a+b)>=10) N=100(b+c)+(a+b); else N=10(b+c)+(a+b); }
Что из этого следует?
Первое, на выходе могут получиться только трехзначные числа и четырехзначные.
Второе, если число трехзначное, то первые две его цифры есть сумма двух цифр исходного числа (по другому быть не может, т. к. большую сумму мы всегда перемещаем перед меньшей, при этом никакое положительное однозначное число не может быть больше положительного двухзначного) . И нам не интересно, делала машина перестановку сумм цифр, когда вычисляла его, т. к. мы будем исходить из того, что оно всегда меньше или равно 18. Если нет, то такое число образоваться не может. Таким образом мы автоматически отсеиваем все трехзначные числа большие чем 189 (и четырехзначные, у которых числа, образованные первыми и последними двумя цифрами больше 18).
Третье, если число четырехзначное, то число, образованное первыми двумя его цифрами всегда больше или равно числу, образованному двумя последними.
И, наконец, четвертое условие, не менее важное - разность чисел, образованными цифрами исходного числа не должна превышать 9 (это можно доказать, исходя из представления чисел. Действительно, (а+b)-(b+c)=a-c, а т. к. а, c-цифры, то их разность не может быть больше 9.
Теперь определяем, какое из чисел удовлетворяет требованиям:
{1616, 169, 163, 1916, 1619, 316, 916, 116}
{ да, да, нет, нет, нет, нет, нет, да}
Реализовать на С++ можно, например, так
