2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 16:35 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Alexu007 в сообщении #519261 писал(а):
Потому что массив не подходит для решения такой задачи, его размер однозначно задаётся при написании программы. Нужно ограничивать максимальный размер вводимого числа, чтобы результат уместился в массиве.
Ну тогда можно устроить некую композицию из массивов. Даже в языке, где поддерживаются только статические массивы, но есть ещё и доступ к динамической памяти (а как вообще можно без него?). Берём один достаточно большой массив и храним в нём с начала до некоторого индекса адреса уже созданных нами массивов фиксированной большой длины. Индексирование, хоть и немного сложнее,ч ем с одним массивом, но тоже выполняется; произвольный доступ, т. е., имеем. Если не хватает массивов, создаём новый и помещаем его адрес в соответствующее место массива-«оглавления». И всякие вариации в том же духе. В языке же с динамическими массивами (кстати, то ли вы не сказали, на чём пишете, то ли проглядел) такие возможны размера более гигабайта, чего должно хватить. При больших размерах лучше уж использовать файл, откуда и куда грузить большие временные куски работы. Кстати,
Alexu007 в сообщении #519261 писал(а):
Я хотел придумать алгоритм, работающий с входными числами любого размера. Вполне возможно, что задача решается разными способами, что мой не оптимальный, что я изобрёл велосипед и т.п.
алгоритм не путайте с программой. На программу всё равно будут наложены системные всякие ограничения, так что для чисел любой длины вам придётся извращаться с временными файлами и, далее, если не хватит места на локальном диске, с сетью (а вдруг её нет!). Кстати, по существу: бинарную маску можно сделать любой длины, не забывайте о массивах, см. чуть выше. Алгоритм поиска сочетаний тоже никак не завязан на конкретных размерах чисел. Так что совет Circiterа очень даже подходит.

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 16:53 


24/05/09

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

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

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 16:58 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Список не единственная динамическая структура. И со списком у вас нет произвольного доступа за $O(1)$! А даже с кучей массивов и указателями на массивы, но только «регулярно расположенными» — есть. (Ещё можно хеш-таблицы…)

Если вам надо туда-сюда ездить по списку, вам это обойдётся сильным замедлением работы.

-- Сб дек 24, 2011 20:01:25 --

Alexu007 в сообщении #519291 писал(а):
Программа всё равно аварийно завершится, если пользователь введёт число большее, чем уместится в int.
Кстати говоря, т. к. нам не важна числовая природа наших чисел, можно вполне хранить их как строки из цифр (ну, массивы, притом фиксированного размера: мы же знаем, где у нас сколькизначные числа начинаются-кончаются; смешивать их в одном контейнере вообще нет смысла). Получите заодно пущую универсальность.

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 17:17 


24/05/09

2054
Это, так скажем, учебная задача (без особого практического смысла), и решаю я её для собственного удовольствия. int достаточно, с ума сходить не будем. Реализация получится компактной и на мой взгляд элегантной: поочерёдно перебираются элементы списка, при этом каждый раз этот же список удлинняется максимум на количество цифр входного числа. То есть программа как бы сама себя тянет за волосы, как Мюнхаузен из болота. И никаких вложенных циклов с неизвестной заранее степенью вложенности...

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


27/04/09
27145
Alexu007 в сообщении #519301 писал(а):
И никаких вложенных циклов с неизвестной заранее степенью вложенности...
А кто-то о них упоминал? :?

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 20:07 


24/05/09

2054
Вы можете дать простенький алгоритм вашего решения? Простенький - это в терминах программирования. То есть если нужна битовая маска (нет такого готового оператора, который снимал бы посмертные битовые маски) - то массивы, циклы, списки, математика и последовательность действий, чтобы эту маску получить. То же и с самой программой: ввёл пользователь число, что дальше? Умножаем, делим или разлагаем на атомы?

У меня, кстати, всё заработало. Ессно пока в сыром виде, никакой проверки на правильность ввода и т.п. Но уже считает, и по-моему правильно:

Изображение

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 20:45 
Заслуженный участник
Аватара пользователя


27/04/09
27145
(В этом случае считает правильно.)

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 21:29 


24/05/09

2054
Что значит "В этом случае"? Вы думаете, что если ввести другое число - программа начнёт врать? Предложите число для тестирования.

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение24.12.2011, 23:13 
Заслуженный участник
Аватара пользователя


27/04/09
27145
Я просто, бывает, стараюсь излишне не обобщать. Мало ли.

 Профиль  
                  
 
 Re: Составить всевозможные числа из цифр введенного числа.
Сообщение25.12.2011, 07:19 


24/05/09

2054
При десяти введённых двойках выдала ошибку "это число не int". 2 147 483 647 - предел программы. Можно конечно переделать под unsigned или long int - но смысла нет, потому что с числом 12345678 уже расправляется в течении более 10 минут, а дальше я и пробовать не стал, там потребуются часы, а то и дни. Это если оперативки хватит...

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу Пред.  1, 2

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group