Форум: "Прочее";
Текущий архив: 2006.12.24;
Скачать: [xml.tar.bz2];
ВнизМозгопромывающая задача на перебор... Найти похожие ветки
← →
q10nik (2006-11-30 09:11) [0]Есть динамический массив записей
ObjBase=record
//имя объекта
ObjName:string[200];
//свойства объекта заполн. не все
ObjProp:array[1..10] of string[80];
//рассчитанное значение значимости объекта на основе ответов пользователей
ObjValu:real;
// zn:=(ObjValu*PropCh)/PropCount-1; //рассчитанное значение уровня защищенности
zn:real;
//реальное количество свойств 0,1,2...10 объекта
PropCount:byte;
//номер выбранного свойства данного объекта (для рассчета zn)
PropCh:SmallInt;
end;
AR:array of ObjBase;
длинна массива определяется количеством введенных в файл объектов
SetLength(ar,ObjectsCount);
А ЗАДАЧА ТАКАЯ: вводится суммарный уровень безопасности Z=СУММ(AR[n].zn), => мне по всем элементам массива ar нужно перебирать допустимые PropCh и вычислять zn, складывать все полученные AR[n].zn и если они примерно равны Z то записывать полученную комбинацию элементов AR и продолжать поиск пока
не будут перебраны все комбинации
P.S. если не лень то хотя бы небольшой фрагмент...
всем заранее спасибо.
← →
Ганна Юхимівна (2006-11-30 09:15) [1]Небольшой фрагмент :)
procedure MindAblutionTask();
begin
// Начало вычислений...
end;
← →
novill © (2006-11-30 10:53) [2]Получается, что зафиксировав значения PropCh в массиве тебе придется перебрать (2^n) комбинаций элементов массива.
В худшем случае таких фиксированных наборов 10^n.(PropCount, если у всех объектов заполнены все поля. Если заполнены не все то надо перемножить все ненулевые PropCount элементов массива)
Таким образом в пессимистическом варианте получается 2^n*10^n=20^n.
Ну, или если очень грубо (например в среднем в объектах заполнено 5 свойств) 10^n итераций.
Помножь на стоимость одной итерации, которая тоже зависит от n, получишь время выполнения :)
Оно тебе надо?
Ну если сильно надо, то реши сначала отдельно задачу перебора всех комбинаций элементов массива, потом отдельно задачу получения всех возможных наборов значений PropCh, вложи одну в другую и добавь вычисление суммы и сравнение с заданной точностью.
Удачи :)
← →
q10nik (2006-11-30 17:46) [3]Это система моделирования объектов защиты информации, тестовый экземпляр.
Реальная ситуация - будет порядка 200 объектов у каждого от 5 до 300 свойств, причем можно добавлять и удалять объекты.
Методом парного сравнения каждого объекта устанавливается значение для каждого из них - ObjValue
Т.е. учитвая сложность реализации тех или иных объектов защиты можно будет строить гибкие и дешевые модели с заданным уровнем безопасности
за основу конечно стоит брать OpenBSD =)
to novill спасибо за идею правда реализовать пока не смог
кстати PropCh<=PropCount в любом случае
кто с реализацией перебора помочь может???
← →
novill © (2006-12-01 10:44) [4]> PropCh<=PropCount в любом случае
это и так понятно.
1. алгоритм перебора всех сочетаний элементов есть в инете (я, правда, видел только в качестве блок-схемы)
2. алгоритм перебора всех вариантов значений PropCh проще всего сделать с помощью простого пересчета в неоднородной позиционной системы счисления (как в десятичной, но максимальное значение у каждого разряда своё) т.е. увеличиваешь значение PropCh у первого элемента до тех пор пока оно не достигнет PropCount, как достигло - обнуляешь и увеличиваешь значение в следующем разряде, если достигло максимума там, то обнуляешь, и увеличиваешь в следующем... алгоритм простой.
> 200 объектов у каждого от 5
у тебя получается 5^200 вариантов = 10^100
Если задачу функционально не ограничить, она не разрешима :)
Если конечно у тебя нет под рукой сверхмощной системы :)
Надо разбираться с условиями.
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2006.12.24;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.039 c