Question

На вход программе поступает натуральное число не превышающее 10^30 Требуется написать программу, которая, используя все цифры этого числа, формирует новое натуральное число, причем самое маленькое из всех возможных той же разрядности. На любом языке (лучше конечно на C++ либо Pascal ABC)

Answer 1

Посчитаем количество раз, когда встречается каждая цифра в исходном числе. Тогда ответ – либо все цифры, расположенные в порядке возрастания (если в исходном числе не было нулей), либо сначала одна наименьшая цифра, потом все нули, потом все остальные цифры в порядке возрастания.

С++:

#include <iostream>

int main() {

   int count[10];

   char digit;

   for (digit = 0; digit < 10; digit++) {

       count[digit] = 0;

   }

   while (std::cin.get(digit)) {

       digit -= '0';

       if ((digit < 0) || (digit > 9)) {

           break;

       }

       count[digit]++;

   }

   digit = 1;

   while (count[digit] == 0) {

       digit++;

   }

   std::cout << int(digit);

   count[digit]--;

   for (digit = 0; digit < 10; digit++) {

       for (int i = 0; i < count[digit]; i++) {

           std::cout << int(digit);

       }

   }

   return 0;

}

Пример ввода: 11111111112345678098765422

Пример вывода: 10111111111222344556677889

Answer 2

Для решения этой задачи можно воспользоваться следующим алгоритмом на языке C++:

cppCopy code
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Ввод числа
    string num_str;
    cin >> num_str;

    // Преобразование строки в вектор цифр
    vector<int> digits;
    for (char digit_char : num_str) {
        int digit = digit_char - '0';
        digits.push_back(digit);
    }

    // Сортировка цифр по возрастанию
    sort(digits.begin(), digits.end());

    // Исключение нулей из начала числа (самое маленькое число не должно начинаться с нуля)
    int zero_count = 0;
    while (zero_count < digits.size() && digits[zero_count] == 0) {
        zero_count++;
    }
    if (zero_count > 0) {
        swap(digits[0], digits[zero_count]);
    }

    // Вывод результата
    for (int digit : digits) {
        cout << digit;
    }
    cout << endl;

    return 0;
}

Программа считывает натуральное число в виде строки, затем преобразует его в вектор цифр. Далее вектор цифр сортируется по возрастанию, и при необходимости исключаются нули из начала числа (чтобы самое маленькое число не начиналось с нуля). Затем полученные цифры объединяются в новое число и выводятся на экран.