Re^2: Ладно.

From

Mike Girkin (2:5055/177.22)

To

Soldatenkov Mitea ()

Date

2003-03-06T19:45:06Z

Area

RU.ALGORITHMS

    Да пребудет с тобой тьма, Soldatenkov !


06 Мар 03 00:13, Soldatenkov Mitea закинул письмецо для Aleksey Zelenin:
 MG>>> Засем здесь pекуpсия? Самая задача под двоичный пеpебоp. Если у
 MG>>> тебя количество данных умещается в ln(MaxInt,2), тогда пpоще
 MG>>> делать числами.
 AZ>>  Это как?
 SM> Если я правильно понял, то читать надо так: если максимальное
 SM> количество бит в целом числе не превышает n (здесь и далее n - число
 SM> чисел в твоем наборе, массиве - ну вобщем думаю понятно о чем я:))...
Абсолютно точно. Если допустим у тебя число всех предметов 32 - можно сделать
численно, т.е. число типа long(ANSI C) вмещает 32 бита. Больше - нужно думать.
 MG>>> Если нет пpидется подумать еще над длинной аpифметикой.
 AZ>>  А это как?
 SM> Опять-же, если я правильно понял, то речь идет о такой ситуации, когда
 SM> по той, или иной причине удобней задействовать нестандартный формат
 SM> чисел. Например, 256 байтовое целое.
И опять все верно. Но опять же численной арифметики может не хватить. Допустим
у тебя будет 1000, а то и 10000 предметов. Тогда классической длинной
арифметикой. Т.е. ручками, загоняем двоичное число в массив, допустим char (чтоб
меньше занимал), хотя можно конечно еще извратиться c числовым представлением, и
начинаем к нему прибавлять каждый раз по единице. Конечно будет долго, и
несколько гемморойно, но работать будет практически для ьюбого количества
предметов.
 SM> На асме, насколько я помню, есть команды полуфабрикаты
 SM> для сложения/вычитания между такими числами. С этими полуфабрикатами,
 SM> реализация сложения/вычитания предельно проста. С умножением, делением
 SM> и извлечением корней мароки будет больше, но тоже не проблемма.
И это тоже можно, но только умножения и деления в улсловиях данной задачи нэ
трэба.
 MG>>> А количество ячеек... Ну во пеpвых, если памяти не жалко можно
 MG>>> под максимум отвести, во втоpых можно не хpанить эти сочетания -
 MG>>> зная его номеp, его можно найти. Ну уж если совсем пpипеpло,
 MG>>> тогда смотpи в стоpону динамического выделения памяти.
 AZ>>  А зачем динамическое выдиление памяти? Мне пpосто нужен
 AZ>> алгоpитм,
 SM> А кто тебя знает, может у тебя памяти в притык, а охота где-нить
 SM> сохранить все найденные комбинации.
В парвом письме AZ писал, что надо их хранить, вот я и предложил способы их
хранения.

                                       Тьма за нас. Mike .

... legem brevem esse oportet - закон должен быть кратким
--- GoldED+/W32 1.1.5-030118
 * Origin:  (2:5055/177.22)