Задача
Индийский математик Д. Р. Капрекар известен своими работами по теории чисел. Одна из его работ посвящена так называемому преобразованию Капрекара. Рассмотрим следующую операцию. Пусть задано число $x$. Пусть $M$ — наибольшее число, которое можно получить из $x$ перестановкой его цифр, а $m$ — наименьшее число (это число может содержать ведущие нули). Обозначим как $K(x)$ разность $M$ — $m$, дополненную при необходимости ведущими нулями так, чтобы число цифр в ней было равно числу цифр в $x$.
Например $K(100) = 100 — 001 = 099$, $K(2414) = 4421 — 1244 = 3177$.
Капрекар доказал, что если начать с некоторого четырехзначного числа $x$, в котором не все цифры равны между собой, и последовательно применять к нему эту операцию (вычислять $K(x)$, $K(K(x))$, . . . ), то рано или поздно получится число $6174$. Для него верно равенство $K(6174) = 7641 — 1467 = 6174$, поэтому на нем процесс зациклится.
Ваша задача состоит в том, чтобы написать программу, вычисляющую $K(x)$ по числу $x.$
Входные данные
Одно целое число без ведущих нулей $x$ ($1$ ≤ $x$ ≤ $10^9$).
Выходные данные
Выведите $K(x)$.
Тесты
| Входные данные | Выходные данные |
| 100 | 099 |
| 1000000000 | 0999999999 |
| 2414 | 3177 |
| 6174 | 6174 |
| 5 | 0 |
| 7272 | 5445 |
| 142857 | 750843 |
| 495 | 495 |
| 55 | 00 |
| 56 | 09 |
| 554 | 099 |
| 12345 | 41976 |
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <algorithm> using namespace std; int main() { long long x, K = 0, xm = 0, xM = 0; //Вводимое число, искомое число, максимальное и минимальное из комбинации цифр cin >> x; int N[11]; int n = 0; while(x != 0){//Количество цифр в числе, запись их в массив цифр N[n] = abs(x % 10); n++; x /= 10; } bool t = true; sort(N , N+n);//Сортировка цифр по возрастанию long long ten = 1; for(int j = 0; j < n-1; j++){ ten *= 10; } long long ten_copy = ten; for(int i = 0; i < n; i++){//Преобразование цифр в наименьшее число xm += N[i] * ten; ten /= 10; } for(int i = n-1; i >= 0; i--){//Преобразование цифр в наибольшее число xM += N[i] * ten_copy; ten_copy /= 10; } K = xM - xm; int c = 0; long long K_tmp = K; //Проверка на равенство количества цифр исходного числа и числа K while(K_tmp != 0){ c++; K_tmp /= 10; } //Добавление недостающих ведущих нулей for(int i = 0; i < n-c; i++) cout << 0; if(K!=0)//Если K==0, то нули были выведены предыдущим циклом cout << K;//Вывод числа K return 0; } |
Объяснение
Поскольку нужно находить минимальную и максимальную комбинацию из цифр числа, удобно в самом начале записать это число в виде массива и отсортировать. Далее найти, собственно, искомые числа, и получить из них само $K(x)$. Потом остаётся проверить количество цифр и вывести, при недостатке, соответствующее количество нулей.
Код на ideone
Зачтено на e-olymp
int *N = new int [11]; Выделять память можно не из кучи, а из стека. int N[11]; Это работает быстрее и удалять в явном виде потом не придется.
Вы вычисляете все степени
двойкидесятки от 0 до n-1 фактически за n2. Можно явно быстрее.Сортировка пузырьком устарела с тех пор, как появилась быстрая сортировка, сортировка кучей и слиянием, а также сортировка из стандартной библиотеки. Стоит применить один из этих вариантов.
Данный участок кода в объяснении по сути пропущен, однако он представляет собой наибольшую загадку. Зачем шифровать число 0 выражением (K_tmp * 10) % 10?
По поводу первой рекомендации было немного неясно, но, вроде, разобрался. Оказалось, что я несколько не так представлял разницу между этими способами объявления, чем и был обусловлен выбор. По поводу сортировки и числа 0 всё понял и согласен, спасибо. По поводу двойки, не совсем понял, но, подозреваю, что имелась ввиду 10 и поэтому исправил там.
Да, имелось в виду 10.
Есть кстати красивый способ собрать число из цифр. Может быть, он Вам тоже понравится:
Исправили обфускацию, но не везде.
Да, спасибо, на верху в цикле не заметил. Способ действительно логичнее, понравился. Только не знаю, нужно ли вставлять его в код самой публикации, чтобы не потерялся фрагмент, к которому это было адресовано. То есть, чтобы потенциальному читателю оставалось понятно что к чему написано. Так что пока оставил без изменений. Но постараюсь запомнить, спасибо.