| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
сложная задача [D5]
race1 © (2002-10-22 18:22:00)есть массив буленов (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
и т.д.
race1 (2002-10-24 15:25:00) [1]то что чиновники оценили в 2 и 3 балла наши десятиклассники (могие, процентов 90-95) сами решить не могут; могут только решить в случае если им дать отправную точку - код, где нужно заменить одну-две переменные плюс написать одно-два новых слова... я конечно к ним не принадлежу :), но всё-таки, как мне кажется, эта задачка не такая простая....
Кстати, к вопросу об памяти, к han_malign - а если можно не сохранять все возможные варианты, а просто узнать их и обработать? Такое по ресурсам возможно?, например, посмотреть что
true true true
и поработать с ними, посмотреть что
true false true
и поработать с ними...
Separator (2002-10-24 12:47:00) [2]Прикиньте у меня такая же задача была на олимпиаде 4 года назад с усложненым заданием, т.е.:
1) true true false
2) true false true
3) false true true
1 и 3 строки считались одинаковыми и такие строки не нужно было учитывать. Так что такая задача по сложности расчитана на 10 - 11 классы, во всяком случае так думают наши чиновники. Поэтому я думаю, что ты ее сможешь решить, хотя я ее тогда не решил :)
Anatoly Podgoretsky (2002-10-24 12:24:00) [3]4
race1 (2002-10-24 11:17:00) [4]а если предположим, что длинна массива не 1000 (это всё детские шалости) а 10 000-20 000 элементов? Это вполне реальная ситуация! И мне НУЖНО все возможные истины и ложи пересчитать! :)
han_malign (2002-10-23 09:41:00) [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
han_malign (2002-10-22 18:42:00) [6]есть мене ресурсоемкий алгоритм - добавлением переноса (по аналогии с инкрементом целого, но вынесенного на более длительные последовательности), предыдущий алгоритм стек жрать будет как незнамо что.
han_malign (2002-10-22 18:39:00) [7]примерно так
....................................
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);
.......................................
race1 (2002-10-22 18:32:00) [8]>han_malign
мне нужно их подсчитать все и сохранить :)
han_malign (2002-10-22 18:24:00) [9]2^length
| |
