Составить всевозможные числа из цифр введенного числа.

[Alexu007]

Алгритм для любого введённого числа что-то никак придумать не могу. Ясно только, что нужна будет рекурсия.

То есть по отдельности составить 2-х, 3-х, 4-х и т.д. числа из имеющихся цифр труда не составляет - для этого достаточно вложенных циклов. Но вложенность циклов на этапе написания програмы закладывается, а для произвольного введённого числа такой алгоритм не годится.

[EtCetera]

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

[Circiter]

2Alexu007
Ну а в дополнение к словам EtCetera привожу ссылки на уже существующие соседние темы по этим самым размещениям: Алгоритм генерации множеств с повторениями и как заменить вложенные циклы на с++.

[Alexu007]

Задача оказалась не так проста, как кажется на первый взгляд.

Первая проблема - количественная, очевидно, что количество результатов будет расти с такой скоростью, что очень быстро гарантировано подвесит комп.
Вторая - "качественная", не указывается никаких ограничений на вводимое число, при этом число 1234567890 слишком велико, а например 1111111111 в результате должно дать всего 9 цифр.

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

Алгоритм следующий: на этапе инициализации заполнить список двухразрядными результатами, затем брать по очереди элементы списка начиная с наименьшего, последовательно прибавлять к ним по одной цифре из исходного числа, и после необходимых проверок добавлять полученное число в список. Продолжать до тех пор, пока разрядность полученного числа не превысит разрядность исходного. Ничего лучшего придумать не удалось.

[arseniiv]

А вам нужны числа или их количество?

-- Чт дек 22, 2011 02:07:32 --

Alexu007 в сообщении #518214 писал(а):

Вторая - "качественная", не указывается никаких ограничений на вводимое число, при этом число 1234567890 слишком велико, а например 1111111111 в результате должно дать всего 9 цифр.

9864101 (именно столько у 1234567890 получается «подчисел») — не так уж и много.

[Alexu007]

Фигасе, а чего так мало? Я думал будут астрономические числа, миллионы лет вычислений...

[arseniiv]

Странно вы. Ограничьте это сверху суммой $1! + 2! + \ldots + n!$ и радуйтесь. Будет равно ей при всех разных цифрах и меньше при повторяющихся.

[Alexu007]

Ну да, я просто математику забыл уже, а может и прогулял когда-то этот урок... Инициализацию, т.е. двухзначные числа в списке я сделал, и пока застрял: надо сделать, чтобы по списку в обе стороны гулять можно было. Чапай думает.

[arseniiv]

В обе стороны? Ну так двусвязный список сделайте, если у вас односвязный. Указатели не только на следующий, но и на предыдущий элемент.

[Alexu007]

Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.

[arseniiv]

Alexu007 в сообщении #519067 писал(а):

Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.

И вы ещё мне в ассемблере говорили, что «компьютер не умеет работать с десятичными числами». Про двусвязные списки полно литературы!

Что вам на сейчас надо сделать конкретно?

[Alexu007]

arseniiv в сообщении #519133 писал(а):

Alexu007 в сообщении #519067 писал(а):

Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.

И вы ещё мне в ассемблере говорили, что «компьютер не умеет работать с десятичными числами». Про двусвязные списки полно литературы!
Что вам на сейчас надо сделать конкретно?

Да не, всё уже почти готово и даже работает. Только немного "неправильно", потому что ещё не написана функция проверки трёх- и более- значных чисел. То есть если в исходном числе одна единица, то она должна быть одна и в результирующих числах, этого пока не отслеживается. А так список создаётся, когда нужно разбухает до необходимых размеров, и затем уничтожается.



Работа со списками (сосбенно с двусвязанными) сложнее работы с массивами, но я вроде разобрался. Спасибо.

[Circiter]

2Alexu007

Цитата:

То есть если в исходном числе одна единица, то она должна быть одна и в результирующих числах

А, т.е. вам нужны размещения без повторений? Вот оно что, а то я гляжу, что не то... :) Ну так это вам проще будет наверное сделать через предварительное наложение всевозможных бинарных масок (поиск сочетаний) с последующим перечислением всех перестановок для каждого результата.

Если вам проще работать с массивами, то почему-бы сначала не написать реализацию для них, а потом просто не провести рефакторинг? (или наоборот, в восходящем стиле -- сначала разобраться со списками, а уже потом на основе этих наработок реализовывать интересующие алгоритмы.)

[arseniiv]

Кстати говоря, очень просто задача решается в Mathematica (8). Моё число оттуда, хотя я бы мог и руками посчитать. Находила список меньше чем за минуту.

Но, конечно, кому-то может показаться, что это не очень «программистский» подход. Зато там всего две функции используется: генератор перестановок (в т. ч. и с повторениями) и фильтр.

[Alexu007]

Circiter в сообщении #519192 писал(а):

А, т.е. вам нужны размещения без повторений?

Ну это как бы само собой разумеется, если условия задачи не подразумевают обратное. Если спросить, какие цифры в числе 1923533981 делятся на три без остатка, вы же ответите 3 и 9, а не 9, 3, 3, 3, 9.

Цитата:

Ну так это вам проще будет наверное сделать через предварительное наложение всевозможных бинарных масок (поиск сочетаний) с последующим перечислением всех перестановок для каждого результата.

Я хотел придумать алгоритм, работающий с входными числами любого размера. Вполне возможно, что задача решается разными способами, что мой не оптимальный, что я изобрёл велосипед и т.п.

Цитата:

Если вам проще работать с массивами, то почему-бы сначала не написать реализацию для них, а потом просто не провести рефакторинг?

Потому что массив не подходит для решения такой задачи, его размер однозначно задаётся при написании программы. Нужно ограничивать максимальный размер вводимого числа, чтобы результат уместился в массиве.

-- Сб дек 24, 2011 17:03:43 --

arseniiv в сообщении #519235 писал(а):

Но, конечно, кому-то может показаться, что это не очень «программистский» подход.

Это (горе)студентик на программистском форуме просил написать такую программу. Как они обычно это делают: помогите, ну очень очень надо, напишите бесплатно програму за меня. Ему опять же традиционно предложили в помощь сылочку: http://cplusplus.com/doc/tutorial/
Я заинтересовался заданием, т.к. оно показалось мне несколько сложноватым для начинающего... Не, ну конечно я не собирался и не собираюсь писать программу для кого бы то ни было, да ещё и бесплатно. Так, для себя. А может потом впарить кому- нить ещё получится.