сложная задача

← →
race1 (2002-10-22 18:22) [0]

есть массив буленов (length=1000,length=2000) нужно узнать ВСЕ возможные комбинации истны и ложи, например,
array[0]=true, array[1]=true
array[0]=false, array[1]=false
array[0]=true, array[1]=false
array[0]=false, arrat[1]=true
и т.д.

← →
han_malign (2002-10-22 18:24) [1]

2^length

← →
race1 (2002-10-22 18:32) [2]

>han_malign
мне нужно их подсчитать все и сохранить :)

← →
han_malign (2002-10-22 18:39) [3]

примерно так
....................................
var _bool: array[0..cLength-1]: boolean;
procedure Deeper(aDepth: integer);
begin
if(aDepth=cLength)then Save(_bool)
else begin
_bool[aDepth]:=true ;Deeper(aDepth+1);
_bool[aDepth]:=false;Deeper(aDepth+1);
end;
end;
begin
Deeper(0);
.......................................

← →
han_malign (2002-10-22 18:42) [4]

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

← →
han_malign (2002-10-23 09:41) [5]

Вот я вчера поймался на подколку, я тут прикинул реализацию алгоритма для 1000 элементов:

возьмем length=1000

Размер памяти для хранения:
При храннении битовой маски, длинна 1-го значения 1000/8=125 байт
2^1000=10^(1000*log10(2))~10^301.
То есть для хранения всех значений нужно 125*10^301 ~ 10^303 ~ 10^291 террабайт. Если предположить что наступило счастливое будущее и на каждого человека на земле приходится компъютер со средней емкостью 1 террабайт, то для хранения этого объема информации понадобится еще 10^291/(6*10^9)~ 10^281 подобных планет - в нашей галактике столько нет.

Время вычисления
Если предположить что сделан специальный 1000-битовый регистр, и одно значение вычисляется за один такт процессора, и что у нас 10ГГц процессор, то только на перебор значений уйдет 10^301/10^7=10^294 секунд.
Для сравнения со времени формирования Земли из газо-пылевого облака прошле меньше 10^23 секунд, так что если не успеем до тепловой смерти вселенной, есть шанс успеть до следущего большого взрыва.

З.Ы. Максимальная глубина стека в рекурсивном алгоритме 8*length (sizeof(integer)+sizeof(указатель точки возврата))
З.З.Ы. Ради разминки простейшая бинарное инкрементирование
FillChar(BoolArray,sizeof(BoolArray),0) repeat Save(BoolArray);//Все false i:=0; while((i<length(BoolArray)and BoolArray[i])do begin BoolArray[i]:=False; inc(i) end; if(i<length(BoolArray))then BoolArray[i]:=true; until(i>=length(BoolArray)); Save(BoolArray);//Все true

← →
race1 (2002-10-24 11:17) [6]

а если предположим, что длинна массива не 1000 (это всё детские шалости) а 10 000-20 000 элементов? Это вполне реальная ситуация! И мне НУЖНО все возможные истины и ложи пересчитать! :)

← →
Anatoly Podgoretsky (2002-10-24 12:24) [7]

← →
Separator (2002-10-24 12:47) [8]

Прикиньте у меня такая же задача была на олимпиаде 4 года назад с усложненым заданием, т.е.:
1) true true false
2) true false true
3) false true true

1 и 3 строки считались одинаковыми и такие строки не нужно было учитывать. Так что такая задача по сложности расчитана на 10 - 11 классы, во всяком случае так думают наши чиновники. Поэтому я думаю, что ты ее сможешь решить, хотя я ее тогда не решил :)

← →
race1 (2002-10-24 15:25) [9]

то что чиновники оценили в 2 и 3 балла наши десятиклассники (могие, процентов 90-95) сами решить не могут; могут только решить в случае если им дать отправную точку - код, где нужно заменить одну-две переменные плюс написать одно-два новых слова... я конечно к ним не принадлежу :), но всё-таки, как мне кажется, эта задачка не такая простая....

Кстати, к вопросу об памяти, к han_malign - а если можно не сохранять все возможные варианты, а просто узнать их и обработать? Такое по ресурсам возможно?, например, посмотреть что
true true true
и поработать с ними, посмотреть что
true false true
и поработать с ними...

сложная задача Найти похожие ветки