2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Составить всевозможные числа из цифр введенного числа.
Сообщение18.12.2011, 23:15 
Алгритм для любого введённого числа что-то никак придумать не могу. Ясно только, что нужна будет рекурсия.

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

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение19.12.2011, 12:48 
2Alexu007
Ну а в дополнение к словам EtCetera привожу ссылки на уже существующие соседние темы по этим самым размещениям: Алгоритм генерации множеств с повторениями и как заменить вложенные циклы на с++.

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение21.12.2011, 21:24 
Задача оказалась не так проста, как кажется на первый взгляд.

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

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

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение21.12.2011, 22:44 
А вам нужны числа или их количество?

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

Alexu007 в сообщении #518214 писал(а):
Вторая - "качественная", не указывается никаких ограничений на вводимое число, при этом число 1234567890 слишком велико, а например 1111111111 в результате должно дать всего 9 цифр.
9864101 (именно столько у 1234567890 получается «подчисел») — не так уж и много.

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение22.12.2011, 20:43 
Фигасе, а чего так мало? Я думал будут астрономические числа, миллионы лет вычислений...

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

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение23.12.2011, 16:46 
В обе стороны? Ну так двусвязный список сделайте, если у вас односвязный. Указатели не только на следующий, но и на предыдущий элемент.

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение23.12.2011, 22:36 
Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 00:40 
Alexu007 в сообщении #519067 писал(а):
Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.
И вы ещё мне в ассемблере говорили, что «компьютер не умеет работать с десятичными числами». Про двусвязные списки полно литературы!

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 07:01 
arseniiv в сообщении #519133 писал(а):
Alexu007 в сообщении #519067 писал(а):
Связные списки намного сложнее массивов. Пока научился выводить с первого элемента списка до последнего и наоборот.

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


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

Изображение

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 10:03 
2Alexu007
Цитата:
То есть если в исходном числе одна единица, то она должна быть одна и в результирующих числах

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

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 13:59 
Кстати говоря, очень просто задача решается в Mathematica (8). :D Моё число оттуда, хотя я бы мог и руками посчитать. Находила список меньше чем за минуту.

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

 
 
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 15:49 
Circiter в сообщении #519192 писал(а):
А, т.е. вам нужны размещения без повторений?

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

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

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

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

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

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

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

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

 
 
 [ Сообщений: 25 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group