Нетривиальный способ перевёртывания числа
Запись от kuppp размещена 26.10.2021 в 13:43
Показов 2664
Комментарии 5
|
Большинство решений базируются на перестановке разрядов в обратном порядке. Я захотел найти какой-нибудь чисто математический способ, и у меня почти это получилось. Далее идёт объяснение этого метода, если вам неинтересно, можете перейти сразу к коду. Для начала проанализируем двухзначные числа. Возьмём, например, 14. Перевёрнутое число 41. Для того чтобы перевернуть число 14 без использования банальной перестановки разрядов, а лишь используя простую математику, нужно к 14 прибавить 27, очевидно. Назовём 27 за k: 14+k=41 Как ни странно, у разных двухзначных чисел будет разное число k. Но есть у всех этих k одно общее: они все кратны 9. Это происходит из-за того, что мы работаем в 10-ой системе счисления. Вот несколько примеров: 38;83 k=83-38=45 10;1 k=10-1=9 47;74 k=74-47=27 И тут я понял, что чем больше разница между цифрой десятка и цифрой единиц, тем больше наша k. В примерах выше это отчётливо видно. Как я уже говорил, все k кратны 9, так давайте поделим k на 9 и назовём получившееся число за kdop: 38;83 k=83-38=45 kdop=k/9=5 10;1 k=10-1=9 kdop=1 47;74 k=74-47=27 kdop=3 И о чудо, мы получаем, что kdop равен разнице между цифрой десятка и цифрой единиц. И наша конечная формула для двухзначного числа будет выглядеть как: x=N+9*kdop, где N - вводимое число, которое нужно перевернуть; x - выводимое перевёрнутое число Для трёхзначного числа всё будет идентично, т.е. мы берём разряд сотен и разряд единиц и находим их разницу. Средний разряд не играет никакой роли. Важное уточнее по поводу формулы x=N+9*kdop: Знак сложения здесь будет лишь в том случае, когда цифра высшего разряда меньше цифры низшего. Поэтому для обобщения в коде я буду использовать не разницу между этими цифрами, а разность. В объяснении я буду использовать лишь "+" для понятности Для четырёхзначного и далее алгоритм будет сложнее, ибо местами меняются все разряды, т.е. наша kdop будет получаться не в одно действие, как раньше. Учитывать придётся не только перестановку низшего и высшего разрядов, но и всех остальных. Не буду мучить разъяснениями, сразу приведу алгоритм действий на примере 123456: 1. Даётся число 123456 2. Находится разница между высшим и низшим разрядами, kdop1=5 3. Находится разница между вторым и предпоследним разрядами, kdop2=3 4. Находится разница между оставшимися двумя разрядами, kdop3=1 5. суммируем все получившиеся kdopi в виде: 55555 + 3330 + 100 Получаем 58985. Это наша kdop 6. Вычисляем перевёрнутое число по формуле: x=N+9*kdop x=123456+9*58985=654321 Ну и теперь к реализации этого алгоритма на с++
По сути, этот алгоритм можно немного подкорректировать для любой системы счисления, но мне лень это делать) | |||||
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 5
Комментарии
-
Уважаемый kuppp,
вы очень интересно пишите. Но здесь я хочу обратить ваше внимание вот ещё на что.
Пусть А и В два, как вы их называете, перевёрнутых числа. И пусть их сумма равна S
Тогда А + В = S. Отсюда зная S и одно из чисел (А или В) можно найти второе число.
Вот ваш пример.
Для чисел 14 и 41 (их сумма равна 55) имеем
55 - 14 = 41
55 - 41 = 14
примечание
это верно для любых чисел, а не только двузначных.Запись от wer1 размещена 26.10.2021 в 14:58 
-
Сумма двух перевёрнутых чисел делится на 11. Вот простой пример
abcd + dcba = (1000a + 100b + 10c + d) + (1000d + 100c + 10b + a) = 1001a + 110b + 110c + 1001d = 11(91a + 10b + 10c + 91d)Запись от wer1 размещена 26.10.2021 в 18:35
-
Да, так тоже можно. Но здесь придётся вычислять S с помощью цифр заданного числа, ведь само S состоит из A+B, где B у нас неизвестное число. Алгоритм в этом случае будет сводиться к нахождению S с помощью суммы цифр разрядов, а не разности, как в посте. Но в целом, этот способ даже легче будет. Вот код набросал
C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
#include <iostream> using namespace std; int Ten(int b) { int c = 1; for (int i = 0; i < b; i++) c = c * 10; return c; } int main() { int N, N2, sim = 0, k = 0, raz, sum; cin >> N; //само число N2 = N; //нахождение количества цифр в числе while (N2) { N2 = N2 / 10; sim++; } for (int i = 1; i <= (1+sim) / 2; i++) { sum = (N / Ten(sim - i) % 10 + ((N % Ten(i)) / Ten(i - 1))); k += sum * Ten(sim - i) + sum * Ten(i - 1); } if (sim % 2 != 0) k -= 2*(N / Ten(sim / 2) % 10)*Ten(sim/2); //вычитаем повторяющийся средний символ N2 = k-N; cout << N2; }
Запись от kuppp размещена 26.10.2021 в 18:57
-
А про сумму двух перевёрнутых чисел, делящейся на 11 не уверен. Это работает только с числами, в которых количество разрядов чётно
Запись от kuppp размещена 26.10.2021 в 19:01
-
О, эта магия чисел! Нет ничего более интересного и таинственного!
Запись от MrCrown размещена 26.10.2021 в 22:23
