Задача: десятичное число (Си)

[Ezhuk]

Подскажите в каком направлении думать,а то никак не могу понять как делать

Задача: Написать программу выводящую десятизначное число, которое удовлетворяет следующим условиям:
первая цифра соответствует количеству нулей в числе;
вторая цифра - количеству единиц;
третья цифра - количеству двоек;
...
десятая цифра - количеству девяток.

[Serge_Bliznykov]

думать в эту сторону:

Заводите массив Массив_Счётчик  от нуля до 9.  
                    (массив-счётчиков, в нём хранить сколько встретилась каждая цифра).
Иницилизация массива - Записываете начально в этот массив нули.
Ввод числа.
цикл, пока Число>0 делать
  Получить очередную цифру числа 
       как остаток от целочисленного деления Число на 10
  Массив_Счётчик[ очередная цифра числа ]++
  Число равняется Число целочисленно разделить на 10
конец цикла
Вывод содержимого Массив_Счётчик

Конец.

[Ezhuk]

Я видимо не очень точно сформулировал...
У вас считает количество каждой цифры во вводимом числе, а надо чтобы условия выполнялись в самом десятизначном числе.

У меня пока что получается вот так:
Первоначально пусть число будет 0 0 0 0 0 0 0 0 0 0
Считается количество нулей - 10, но т.к. 10 будет записываться в первую цифру нулей уже станет 9:
9 0 0 0 0 0 0 0 0 0
Дальше считает кол-во 9 - 1, записывается в последнюю
9 0 0 0 0 0 0 0 1 0
Нулей становиться 8 и девятки уже нет а есть 8;
8 0 0 0 0 0 0 0 1 0
Считаем единицы - 1
7 1 0 0 0 0 0 1 0 0
Единиц стало две записываем
7 2 0 0 0 0 1 0 0 0
Записываем, количество двоек в третье число
6 2 1 0 0 0 1 0 0 0
Собственно получаем искомое число.

Но такой путь у меня не получается реализовать.

[Stilet]

Считаем единицы - 1
7 1 0 0 0 0 0 1 0 0
Единиц стало две записываем
7 2 0 0 0 0 1 0 0 0

А с какого это перепугу расчет единиц идет два раза?
По твоей логике должно быть так:

Считаем единицы - 1
7 1 0 0 0 0 0 1 0 0
Единиц стало две записываем
7 2 0 0 0 0 1 0 0 0
Считаем единицы - 1
Единица осталась одна. записываем
7 1 0 0 0 0 0 1 0 0
...
На столбе мочало-начинай сначала...

Это ерунда какая то...

[Ezhuk]

Ааа... и правда чушь получилась.
Все пропало...

[q_proger]

Можно конечно подумать, как решить эту задачу по-настоящему, но на полный перебор уходит всего 20ms, так что есть ли смысл

int a[10];
void f(int left, int pos)
{
    if (pos == 10) {
        if (left == 0) {
            int b[11];
            memset(b, 0, sizeof(a));
            for(int i = 0; i < 10; i++) {
                ++b[a[i]];
            }
            if (memcmp(a, b, sizeof(a)) == 0) {
                for (int i = 0; i < 10; i++) {
                    cout << a[i];
                }
                cout << "\n";
            }
        }
    }
    else {
        for (int i = 0; i <= left; i++) {
            a[pos] = i;
            f(left - i, pos + 1);
        }
    }
}

int main()
{
    f(10, 0);
    return 0;
}

[Ezhuk]

Спасибо, q_proger.
Не могли бы вы объяснить алгоритм выполнения и поконкретнее остановиться на этих строчках

memset(b, 0, sizeof(a));
for(int i = 0; i < 10; i++) {
++b[a[i]];
}
if (memcmp(a, b, sizeof(a)) == 0) {
for (int i = 0; i < 10; i++) {
cout << a[i];
}

Зачем буферу на один элемент больше? Что записывается в него?
И как работает функция memcmp?

[q_proger]

a[0] бывает равно 10, это конечно так не должно быть, но ничего страшного из за этого не произойдет, так что пусть будет место и для 10ого элемента.

memcmp - memopy compare, сравнивает два блока памяти, т. е. одинаковы ли массивы.

memset(b, 0, sizeof(a)); // обнуление первых десяти элементов массива b, а то там мусор
for(int i = 0; i < 10; i++) { // после этого в каждой позиции массива "b" будет сколько раз эта "позиция" встречалась в массива "а"
    ++b[a[i]]; 
}
if (memcmp(a, b, sizeof(a)) == 0) { // если массивы в результате равны, то условие задачи выполнено, число найдено
    for (int i = 0; i < 10; i++) {
    cout << a[i];
}

А смысл такой. Сумма цифр в вашем числе всегда должна быть 10, так как число 10изначное, и если каждая цифра числа будет показывать количество каких-то цифр в этом числе, то в сумме и наберется эти самые 10 знаков.
Для перебора всех вариантов 10значных чисел с суммой цифр 10 пишем функцию f, которая распределяет "left" начиная с позиции "pos", в самом первом вызове надо распределить 10 начиная с 0й позиции f(10, 0). А уже эта функция перебирает циклом от 0 до 10 сколько бы она поставила в 0ю позицию и вызывает сама себя для распределения остатка начиная с первой(след.) позиции и такой рекурсивный цикл идет до тех пор, пока функция не получает задание распределять что-то начиная с 10й позиции (а они всего с 0й до 9й), тогда идет проверка - все распределено? (left == 0) если да, то проверяет соответствует ли это 10изначное число условию задачи, если да то выводит его на экран. Если бы таких чисел было несколько, то вывелись бы все.

[Ezhuk]

Огромное спасибо.
Если бы не помогли я бы долго еще думал как и что...