оО помогли с прогой такая же беда была.

BalmaR,  может ты поможешь? "плиз"     

Это сообщение отредактировал(а) sNicker - 22.11.2008, 11:55

Вот программа моего   собственного изготовления. 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:36

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

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 - 28.7.2009, 14:35

 Блин, обнаружил ошибку в прграмме!  Исправляю.....  

Исправил 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!                    <----- конец

А что за языk такой?