Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Где достать алгоритм минимизации булевой функции


Автор: neutrino 11.6.2003, 17:05
Приветствую!

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

Ваш покойный слуга smile.gif.

Автор: akul 12.6.2003, 14:01
Ить Карты Карно - это для человека метод, графически-визуальный, чтобы удобнее было. Машинный метод - это построить дерево и применять к нему упрощающие подстановки рекурсивно, пока применяются.

Автор: neutrino 12.6.2003, 15:54
Я все понимаю. Сам алгоритм составить могу, но времени нет. Вот я и спрашиваю Где достать а не Как сделать.

Автор: stab 14.6.2003, 20:36
слушай, я тут нашел курсовик свой давнишний, чего-там про метод КМК ... не помню чего это, но кажется что-то близкое по теме, если надо могу выслать

Автор: stab 14.6.2003, 20:37
ага, вот еще... там про импликанты и про кубы разные упоминается

Автор: neutrino 18.6.2003, 12:29
Ой, давай, давай...
Кубы? Это если количество булевых переменных больше 4-х....

Автор: <Spawn> 19.6.2003, 20:59
http://www.etel.dn.ua/~shurik/carno

Если сайт не будет активным, то могу выслать прогу на мыло smile.gif

Автор: stab 20.6.2003, 10:01
neutrino выслал

Автор: dm9 21.6.2003, 14:22
Как обычно, открываем Апорт. Делаем запрос "минимизация булевой функции методом карт Карно".

http://kai4x03.narod.ru/files/files.html

Правда, ссылка, которая на страничке, у меня не работает. Но можно связаться с автором...

Автор: Zeriod 12.7.2007, 14:15
Помню когда-то давным давно (3 года назад) писал диплом. Одним из его пунктов было "создание алгоритма минимизации булевых функций". Метод был изобретён свой, адаптированный под вычислительные машины. Критерий минимизации - минимум операций. Базис: дизъюнкция, конъюнкция, отрицание и сложение по модулю два. Число булевых переменных и сложность функций - любая. Язык программирования quick basic.

Есть исходники. Но хотелось бы переписать прогу на что-нибудь современное (C#, C++, php или delphi).
У самого времени нет этим заниматься. Если кому интересно, могу выслать код (ICQ: 459-783-892).

Автор: Scorp_Freeman 16.1.2008, 20:21
Привет! Помогите плиз)) Я тоже с этим столкнулся) только я не сс картами карно , а с Квайном)) Помжет кто нить чемто помочь? Интересует алгоритм (поиск покрытий)

Автор: Dude03 19.1.2008, 18:53
Цитата(Zeriod @  12.7.2007,  14:15 Найти цитируемый пост)
Базис: дизъюнкция, конъюнкция, отрицание и сложение по модулю два. 


конъюнкция - *
дизъюнкция - +
отрицание - !
сложение по модулю два - (+)

В итоге: 

x1 (+) x2 = ((!x1) * x2) + (x1 * (!x2))

Скобки расставил для того чтобы не задавать приоритеты.

Но вот беда, никак не пойму, где здесь базис. Если одна функция может быть получена через комбинацию(линейную) других, то базисом никаким и не пахнет. Мммм.... Или я может быть путаюсь в понятиях?

Автор: AndreyK 29.1.2008, 17:09
Надо исключить лишние операторы (дизьюнкцию и отрицание или сложение) и получишь одно из представлений: полином Жигалкина или совершенную дизъюнктивную нормальную форму (ДНф) - вот там базисы и ищи.

Автор: Дамаскин 21.11.2008, 20:18
Наверно, не  совсем то, что Вам нужно, но может пригодиться.

 Минимизация булевых функций по совпадению множеств

В  "Представление информации булевой формулой" ( http://moiidei.com/nauka-estestvennyie/predstavlenie-informatsii-bulevoy-formuloy-2.html ) уже упоминалось, что одной из проблем представления информации булевой формулой является проблема формирования формулы по крайней мере с минимальным числом букв в ней.
Эта  проблема часто стоит и перед разработчиками логических схем для различных устройств, включая  конечные  автоматы и микросхемы для компьтеров. Ведь  число букв в формуле булевой функции, реализуемой логической схемой, определяет число элементов в схеме.

"Существуют несколько  способов минимизации булевых функций.Прежде всего,это аналитический 
символьный и аналитический кодовый методы,метод Квайна  -  Мак-Класки,метод  
Блека  -  Порецкого, метод обобщенных  кодов[11]  и  графическая  минимизация с помощью 
карт Карно[12].
Пример для демонстрации аналитических методов:
z = x_y+xy_+xy = (x_y+xy)+(xy_+xy) = y(x_+x) + x(y_+y) = x+y.
z = 01+10+11 = (01+11)+(10+11) = -1+1- = x+y.
Первые четыре метода чрезвычайно громоздки и  малоэффективны уже при количестве аргументов 
более четырёх. Метод обобщенных кодов  ориентирован  на  использование ЭВМ,однако может 
использоваться и при ручном синтезе для функций от большого числа  переменных."
(http://ruslogic.narod.ru/lectures/3.htm )


         Я бы  добавил  к этому высказыванию несколько субъективных замечений.
1. Большинство методов  фактически минимизируют  функцию только на уровне ДНФ (дизъюнктивной нормальной формы), т.е. в отсутствии скобок, которые то и дают реальное уменьшение числа букв в формуле.
2. Сокращение числа букв осуществляется по правилам булевой алгебры (метод Блейка) и зависит от от вашего опыта.
(http://www.sgu.ru/ie/mehmat/odfka/r3/R3-1.htm)
3. Практически нет гарантий, что полученная  формула, если она достаточно сложна, является  минимальной, что её нельзя сократить ещё.
  Я в своё время принимал участие в разработке автоматических устройств (в теории - конечные автоматы)  для ракетной техники, и могу сказать, что большинство проектировщиков составляли схемы устройств, руководствуясь не столько теорией, сколько здравым смыслом.  Я думаю, это происходило потому, что  теория  достаточно сложна и недостаточно проработана для практического применения.
          Идеи, которые я хочу здесь представить, зародились именно в те времена.
                                                         Суть метода
     Коротко,  суть предлагаемого метода заключается в следующем.
На основании таблицы истинности, которая, как правило, является основой проектирования логической схемы, для искомой функции составляется множество из нулей и единиц.  Множество разбивается на определённое число пар взаимнонепересекающихся подмножеств. Число пар равно числу входных переменных, и каждой паре сответствует  пара букв, одна из которых обозначает переменную, а вторая её отрицание.  Задача сводится к тому, чтобы на этом множестве сформировать множество, которое включает только единицы. Формула этого множества как раз и будет искомой функцией. Формирование множества осуществляется посредством пошаговой процедуры, на каждом шаге которой в формулу множества добавляется одна буква таким образом, чтобы полученное множество имело наибольшее совпадение с искомым множеством, т.е. имело бы как можно больше единиц и как можно меньше нулей. Величина совпадения определяется как sov = s1(i)/s1 - s0(i)/s0, где s1 и s0 - число единиц и нулей в исходном множестве, а s1(i) и s0(i) - соответственно число единиц и нулей в множестве,  полученном на i - том шаге. Так как на каждом шаге в формулу добавляется только одна буква, то на каждом i  - том шаге мы будем получать формулу из  минимального числа i  букв, определяющей множество с максимальным совпадением. Процедура будет закончена, когда будет получено множество с совпадением sov(i) =1. Формула будет иметь i букв.

                                                          Результаты
Предлагаемый  метод был применён при определения системы функций для реализаций логической сети "Мышь в лабиринте" , синтез которых приведен в книге "Н.Е. Кобринский и Б.А. Трахтенброт   Введение в теорию конечных автоматов. 1962 г."  Всего надо найти 5 функций z1, z2, f1(t+1), f2(t+1), f3(t+1) от 5 переменных  x1, x2, f1(t), f2(t), f3(t) , каждая из которых задаётся таблицей истинности.  Таблица истинности для всех пяти функций приведена на Рис. 1. Таблица взята из упомянутой книги с некоторыми корректировками для удобства записи.

                                       Таблица истинности для системы функций "Мышь в лабиринте"
   
№стр.     код  входа        код входного состояния    код выхода      код выходного состояния
                              ---------------       ----------------------------------    ----------------      ------------------------------------
            № кол    1      2                 3           4            5                 6        7                8           9             10

                       x1     x2              f1(t)       f2(t)       f3(t)              z1      z2            f1(t+1)   f2(t+1)       f3(t+1)
            0           0       0                0            0            0                 0        0                 0          1              0
            1           0       0                0            0            1                 1        0                 0          0              0
            2           0       0                0            1            0                 1        0                 0          0              0
            3           0       0                0            1            1                 1        0                 0          0              0
            4           0       0                1            0            0                 1        0                 0          0              0
            5           0       0                1            0            1                 1        0                 0          0              0     
            6           0       0                1            1            0                 1        0                 0          0              0
            7           0       0                1            1            1                (1)      (0)               (0)        (0)            (0)
            8           0       1                0            0            0                 0        1                 1          1              0
            9           0       1                0            0            1                 0        0                 1          1              0
          10           0       1                0            1            0                 0        0                 1          1              0
          11           0       1                0            1            1                 0        0                 1          0              1
          12           0        1                1            0            0                 1        0                 0          1              1
          13           0        1                1            0            1                (1)      (0)               (0)        (1)            (1)
          14           0        1                1            1            0                 1        0                 0          1              1
          15           0        1                1            1            1                (1)      (0)               (0)        (1)            (1)
          16           1        0                0            0            0                 0        0                 0          0              1
          17           1        0                0            0            1                 0        0                 1          1              0
          18           1        0                0            1            0                 0        1                 1          1              0
          19           1        0                0            1            1                 0        0                 1          0              0
          20           1        0                1            0            0                 1        1                 1          1              1
          21           1        0                1            0            1                 0        1                 1          1              0
          22           1        0                1            1            0                (1)      (1)               (1)        (1)            (1)           
          23           1        0                1            1            1                  1       1                 1          1              1   
          24           1        1                0            0            0                  1       1                 1          1              1
          25           1        1                0            0            1                 (1)    (1)               ( 1)        (1)            (1)
          26           1        1                0            1            0                 (1)    (1)               ( 1)        (1)            (1)                 
          27           1        1                0            1            1                 (1)    (1)               ( 1)        (1)            (1)
          28           1        1                1            0            0                 (1)    (1)               ( 1)        (1)            (1)
          29           1        1                1            0            1                 (1)    (1)               ( 1)        (1)            (1)
          30           1        1                1            1            0                 (1)    (1)               ( 1)        (1)            (1)
          31           1        1                1            1            1                  1       1                 1          1              1
     
                                                                                     Рис. 1

    Для этой таблицы истинности в книге методом графов была найдена следующая система уравнений
для пяти функций, реализующих автомат "Мышь в лабиринте" . 

                                                     Система уравнений  1   

     z1 = -x1{-x2[f2(t) + f3(t)] + f1(t)} + x1{f1(t)[f2(t) + -f3(t)] + x2}                                                    (1)    10

     z2 = x2[-f1(t)-f2(t)-f3(t) + x1] + x1[f2(t)-f3(t) + f1(t)]                                                                   (2)      9

      f1(t+1) = x2[x1 + -f1(t)] + x1[f1(t) + f2(t) + f3(t)]                                                                       (3)      7

      f2(t+1) = -x1{x2[f1(t) + -f2(t) + -f3(t)] + -f1(t)-f2(t)-f3(t)} + x1[x2 + f1(t)+ -f2(t)f3(t) + f2(t)-f3(t)]         (4)    15

      f3(t+1) = -x1{x2[f2(t)f3(t) + f1(t)]} + x1{-f2(t)-f3(t) + f1(t)[f2(t)+f3(t)] +x2}                                       (5)    12

  Цифры, приведенные в конце каждой строки с формулами (1) - (5) показывают число  букв (входных переменных) в 
каждой формуле   

     С помощью предлагаемого метода была получена
 Система уравнений 2

     z1 = f1(t)[-f3(t)+f2(t)] + -x1-x2[f2(t)+f3(t)] + x2x1                                                                     (6)      9

     z2 = x1{f1(t)+ -f3(t)[x2+f2(t)]} + x2-f2(t)-f1(t)-f3(t)                                                                     (7)      9

      f1(t+1) = x1[f1(t)+f3(t)+f2(t)] + x2-f1(t)                                                                                   (8)      6
 
      f2(t+1) = [x2+x1]{f1(t) + [-f2(t)+ -f3(t)][x2+f3(t)+f2(t)]} + -f2-f1-x1-f3                                            (9)     12

      f3(t+1) =  x2[f1(t)+f2(t)f3(t)] + x1[-f3(t)-f2(t)+f1(t)f2(t)]                                                               (10)      9

В этой системе уравнений (6) - (10), как и в системе уравнений 1 (1) - (5), цифры в конце строк показывают
число букв в каждой формуле.     В четырёх формулах из пяти предлагаемый метод позволил сократить число
букв. Общее число букв сократилось с  53 до 45.
        
Подробнее:
 http://obdamaskin.livejournal.com/4035.html  
или                           
http://moiidei.com/nauka-estestvennyie/minimizatsiya-bulevyih-funktsiy-po-sovpadeniyu-mnozhestv.html
  

Автор: sNicker 22.11.2008, 01:21
<Spawn>, если не трудно и не стёр ешё програмку, может и мне пришлёш? smile 

Автор: BalmaR 22.11.2008, 01:22
оО помогли с прогой такая же беда была.

Автор: sNicker 22.11.2008, 10:39
BalmaR,  может ты поможешь? "плиз"  smile   

Автор: x0123456789 28.7.2009, 14:13
Вот программа моего  smile собственного изготовления. http://files.mail.ru/6ZSJ4H

В программе реализован алгоритм минимизации булевых функций методом Харриса.
В файле Harris.adb приведён исходный код на языке Ada.
Программа выдаёт все лучшие варианты оптимизации.
Максимальная разрядность комбинаций - 16.
Максимальное число комбинаций - 2 ** 16 = 65536.
О всех обнаруженных недостатках сообщать автору на е-mail: [email protected]

Исходные данные
---------------

Исходные данные для работы пометить в файл parm.txt.
Там перечислить все комбинации для минимизации в десятичной системе счисления. В качестве разделителей использовать символ пробела или символ перевода строки.
См. примеры в файлах parm0.txt, parm1.txt, parm2.txt.

    Например, пусть в файле parm.txt имеем строку: "1 3 4 6 9 11 12"
    В двоичной форме это комбинации: 0001, 0011, 0100, 0110, 1001, 1011, 1100.
    Число комбинаций - 7, разрядность комбинаций - 4.

Программа автоматически определит число и разрядность комбинаций.
Результат работы выдаётся на консоль в стандартный поток вывода.
Если есть необходимость перенаправить вывод в файл, запустить программу так:

harris.exe > filename.txt

Интерпретация результатов
-------------------------

qqq = 7    nnn = 4    mmm = 14                    <----- qqq - число комбинаций, nnn - разрядность, mmm - размер стека для работы = qqq * 2 

#    fak    ves    cod    img                <----- демонстрация размещения исходных данных в стеке в стеке    (#-позиция, fak-факультатив, ves-вес Хэминга, cod-код, img-двоичное представление)
 0     0     1     1    0001
 1     0     1     4    0100
 2     0     2     3    0011
 3     0     2     6    0110
 4     0     2     9    1001
 5     0     2     12    1100
 6     0     3     11    1011
                                <----- Начало перебора
1100     1
    01*0     2
        *0*1     3[1100,01*0,*0*1]            <----- 1-й результат оптимизации (*-отмечены факультативы) [в квадратных скобках выдаётся лучший на данный момент результат]

    00*1     2
        01*0     3
            10*1     4
1001     1
    1100     2
        1011     3
            00*1     4
                01*0     5
0110     1
    *100     2
        *0*1     3(0110,*100,*0*1)            <----- 2-й вариант оптимизации (в круглых скобках - результат не хуже чем в []-скобках)

    00*1     2
        *100     3
            10*1     4
    1001     2
        1011     3
            00*1     4
                *100     5
0100     1
    0110     2
        1100     3
            *0*1     4
            00*1     4
                10*1     5
        1001     3
            1100     4
                1011     5
                    00*1     6
1100     1
    01*0     2
        *0*1     3(1100,01*0,*0*1)            <----- 3-й вариант оптимизации

    *001     2
        01*0     3
            *011     4
0011     1
    1100     2
        1011     3
            *001     4
                01*0     5
0110     1
    *100     2
        *0*1     3(0110,*100,*0*1)            <----- 4-й вариант оптимизации

    *001     2
        *100     3
            *011     4
0011     1
    0110     2
        1011     3
            *001     4
                *100     5
0100     1
    0110     2
        1100     3
            *0*1     4
            *001     4
                *011     5
    0011     2
        0110     3
            1100     4
                1011     5
                    *001     6
0001     1
    1001     2
        1100     3
            01*0     4
                *011     5
    0011     2
        1100     3
            01*0     4
                10*1     5
        1001     3
            1100     4
                1011     5
                    01*0     6
    0110     2
        1001     3
            *100     4
                *011     5
    0011     2
        0110     3
            *100     4
                10*1     5
            1001     4
                1011     5
                    *100     6
    0100     2
        0110     3
            1001     4
                1100     5
                    *011     6
        0011     3
            0110     4
                1100     5
                    10*1     6
                1001     5
                    1100     6
                        1011     7
Ok!                                <----- конец перебора


Автор: x0123456789 28.7.2009, 14:33
На всякий случай, если ссылка не будет работать привожу полный теХст программы:

with Interfaces; use Interfaces;
with Ada.Text_IO; use Ada.Text_IO;

-------------------
procedure Harris is
-------------------

-- максимальная разрядность комбинации
IMG_MAX : constant := 16;

-- изображение комбинации
type img_type is array (0 .. IMG_MAX-1) of character;

-- комбинация
type cmb_type is
    record
        ves : integer; -- вес Хеминга
        fak : integer; -- факультатив
        cod : integer; -- комбинация
        img : img_type; -- изображение
    end record;

-- стек комбинаций
type cmb_arr_type is array (natural range <>) of cmb_type;
type cmb_arr_ref_type is access cmb_arr_type;
cmb : cmb_arr_ref_type;

-- стек результата
type img_arr_type is array (natural range <>) of img_type;
type img_arr_ref_type is access img_arr_type;
img : img_arr_ref_type;

qqq : integer; -- число комбинаций
nnn : integer; -- разрядность сомбинации
mmm : integer; -- р-р стека комбинаций
cntBest : integer := 32767; -- лучшее число комбинаций

-- отображение комбинации
procedure put_img (img : img_type) is
begin
    for i in reverse 0 .. nnn-1 loop
        put (img (i));
    end loop;
end put_img;

-- дамп стека комбинаций
procedure Dump (ttt : integer) is
begin
    new_line;
    put ("#"   & ascii.ht);
    put ("fak" & ascii.ht);
    put ("ves" & ascii.ht);
    put ("cod" & ascii.ht);
    put ("img" & ascii.ht);
    for i in 0 .. ttt-1 loop
        new_line;
        put (integer'image (i) & ascii.ht);
        put (integer'image (cmb (i).fak) & ascii.ht);
        put (integer'image (cmb (i).ves) & ascii.ht);
        put (integer'image (cmb (i).cod) & ascii.ht);
        put_img (cmb (i).img);
    end loop;
    new_line;
end Dump;

-- ввод исходных данных
function Get_Data return boolean is
    e, emax : integer;
    f : Ada.Text_IO.file_type;
    package IIO is new Ada.Text_IO.Integer_IO (integer);
begin
    -- 1-й проход, определение числа комбинаций и разрядности
    qqq := 0;
    emax := 0;
    Open (f, Ada.Text_IO.in_file, "parm.txt");
    while not end_of_file (f) loop
        IIO.Get (f, e);
        if emax < e then emax := e; end if;
        qqq := qqq + 1;
    end loop;
    Close (f);

    -- р-р стека комбинаций
    mmm := 2 * qqq;

    -- разрядность
    nnn := 0;
    while 2 ** nnn < emax loop
        nnn := nnn + 1;
    end loop;

    new_line;
    put_line ("qqq =" & integer'image (qqq) & ascii.ht & "nnn =" & integer'image (nnn) & ascii.ht & "mmm =" & integer'image (mmm));

    if IMG_MAX < nnn then
        put_line ("*** RANGE ERROR *** " & integer'image (IMG_MAX) & " < nnn");
        return false;
    end if;

    -- размещение стека комбинаций
    cmb := new cmb_arr_type (0 .. mmm-1);
    -- размещение стека результата
    img := new img_arr_type (0 .. qqq-1);

    -- 2-й проход, загрузка стека
    Open (f, Ada.Text_IO.in_file, "parm.txt");
    for i in 0 .. qqq-1 loop
        IIO.Get (f, e);
        cmb (i).cod := e;
        cmb (i).fak := 0;
        cmb (i).ves := 0;
        for j in 0 .. nnn-1 loop
            if (shift_right (unsigned_32 (e), j) and 1) = 0 then
                cmb (i).img (j) := '0';
            else
                cmb (i).img (j) := '1';
                cmb (i).ves := cmb (i).ves + 1;
            end if;
        end loop;
    end loop;
    Close (f);

    -- Dump (qqq);

    return true;
end Get_Data;

-- сортировка по весу Хеминга (внутри веса - по коду (хотя, по коду можно и не сортировать))
procedure Sortir is
    swap : cmb_type;
    nnn2p : integer;
    ives, jves, kves : integer;
begin
    nnn2p := 2 ** nnn;
    for i in 0 .. qqq-2 loop
        ives := cmb (i).ves * nnn2p + cmb (i).cod;
        for j in i+1 .. qqq-1 loop
            jves := cmb (j).ves * nnn2p + cmb (j).cod;
            if jves < ives then
                kves := ives; ives := jves; jves := kves;
                swap := cmb (i); cmb (i) := cmb (j); cmb (j) := swap;
            end if;
        end loop;
    end loop;
end Sortir;

-- Дерево разбора
procedure Tree (ott, doo, dno, cnt : integer) is -- от и до и дно и текущий счстчик стека результата
    p : integer;
    head : integer; -- голова стека комбинаций
    cntCmb : integer; -- голова стека результата
begin
    head := dno;
    cntCmb := cnt;
    for i in ott .. doo-1 loop -- 1-й кандидат для склейки
        if 0 <= cmb (i).fak then -- если ещс не склеен
            for j in i+1 .. doo-1 loop -- 2-й кандидат для склейки
                if cmb (i).fak = cmb (j).fak then -- если одинаковые факультативы
                    if abs (cmb (i).ves - cmb (j).ves) = 1 then -- если разница весов = 1
                        p := -1;
                        for k in 0 .. nnn-1 loop -- поиск позиции для склейки
                            if cmb (i).img (k) /= cmb (j).img (k) then
                                if p = -1 then p := k; else p := -1; exit; end if;
                            end if;
                        end loop;
                        if 0 <= p then
                            -- склейка
                            cmb (head).fak := cmb (i).fak + 2 ** p; -- конфигурация факультативов
                            cmb (head).cod := cmb (i).cod; -- нафиг не нужно, но жалко выкинуть (был нужен при сортировке, но не особо)
                            cmb (head).ves := cmb (i).ves;
                            cmb (head).img := cmb (i).img;
                            cmb (head).img (p) := '*'; -- позиция факультатива
                            cmb (j).fak := -(cmb (j).fak + 1); -- выкидываю из рассмотрения
                            Tree (i+1, doo, head+1, cntCmb);
                            cmb (j).fak := -(cmb (j).fak + 1); -- возвращаю в строй
                        end if;
                    end if;
                end if;
            end loop;

            -- стек результата
            img (cntCmb) := cmb (i).img;
            cntCmb := cntCmb + 1;

            -- выдаю не склеевшиеся
            new_line;
            for j in 2 .. cntCmb loop
                put (ascii.ht); -- оЦтуп
            end loop;
            put_img (cmb (i).img);
            put (ascii.ht & integer'image (cntCmb));
        end if;
    end loop;

    -- если была хоть одна склейка
    if doo < head then
        Tree (doo, head, head, cntCmb); -- начинаю новый уровень
    else
        -- не было склеек - конец цепочки
        if cntCmb < cntBest then
            cntBest := cntCmb;
            put ("["); -- лучше
            for i in 0 .. cntBest-1 loop
                if 0 < i then put (","); end if;
                put_img (img (i));
            end loop;
            put_line ("]");
        elsif cntCmb = cntBest then
            put ("("); -- не хуже
            for i in 0 .. cntBest-1 loop
                if 0 < i then put (","); end if;
                put_img (img (i));
            end loop;
            put_line (")");
        end if;
    end if;

end Tree;

-----
begin
-----

if Get_Data then
    Sortir;
    Dump (qqq);
    Tree (0, qqq, qqq, 0);
    new_line; put ("Ok!");
end if;

----------
end Harris;
----------

Автор: x0123456789 30.7.2009, 18:41
smile Блин, обнаружил ошибку в прграмме! smile Исправляю.....  

Автор: x0123456789 31.7.2009, 11:02
Исправил http://files.mail.ru/LZJ65O
---
Краткое описание алгоритма
---
Булевы комбинации сначала клеятся по 1 биту затем по 2, по 3 и т.д.
И так до тех пор пока комбинации больше не клеятся.
Затем стек комбинаций перетасовывается случайным образом и алгоритм склейки повторяется уже в ином порядке.
Лучшие склейки помещаются в файл промежуточных результатов.
Эти данные сортируются, исключаются повторения и выдаются в качестве конечного результата.
---
qqq = 7    nnn = 4    mmm = 14        <----- qqq - число комбинаций, nnn - разрядность, mmm - размер стека для работы = qqq * 2 

#    fak    ves    cod    img    <----- размещение исходных данных в стеке (#-позиция, fak-факультатив, ves-вес Хэминга, cod-код, img-двоичное представление)
 0     0     1     1    0001
 1     0     2     3    0011
 2     0     1     4    0100
 3     0     2     6    0110
 4     0     2     9    1001
 5     0     3     11    1011
 6     0     2     12    1100
 +                    <----- Промежуточные результаты
(*0*1,01*0,1100)
(*0*1,01*0,1100)
(*0*1,01*0,1100)
(*0*1,01*0,1100)
(*0*1,01*0,1100)
(*0*1,01*0,1100)
(*0*1,*100,0110)
(*0*1,01*0,1100)
(*0*1,*100,0110)
(*0*1,*100,0110)
(*0*1,*100,0110)
...
(*0*1,01*0,1100)
=                    <----- Итоговые результаты
[*0*1,*100,0110]
[*0*1,01*0,1100]
Ok!                    <----- конец

Автор: neutrino 2.8.2009, 10:58
А что за языk такой?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)