Sql , Pl/sql , Задача На Комбинаторику

Тема в разделе "Другие задачи", создана пользователем ShaoKahn, 5 дек 2014.

  1. ShaoKahn

    ShaoKahn New Member

    Регистрация:
    5 дек 2014
    Сообщения:
    1
    Симпатии:
    0
    Добрый день, есть такая задача:

    В таблице содержится информация о произвольном наборе косточек домино (левое число косточки, правое число косточки). Создать программу для определения списка “рыбных” ситуаций (т.е. ситуаций, когда остается одна или более косточек исходного набора, которые некуда положить) и количества таких ситуаций.
    Например, если в таблице содержится информация о наборе из трех косточек:
    левое число косточки правое число косточки
    2 0
    2 6
    1 5
    то список рыбных ситуаций:
    (6,2) -> (2,0) Осталась кость (1,5)
    (1,5) Остались кости (2,6) , (2,0)
    Количество рыбных ситуаций: 2
    Примечание: программа должна предусматривать проверку правильности заполнения таблицы.


    Вот в чем собственно сам вопрос:
    Я делаю эту задачу по такому алгоритму, создаю 3 индексных таблицы, в 1 записываю костяшки(отдельно право и лево) и номер вершины, во 2 записываю просто костяшки(право и лево), в 3 записываю номер костяшки из первой таблицы и посищенность(тоесть если костяшка уже использована, то записываю 1, если нет то 0). Потом начинается сам перебор, внешний цикл перебирает начальные вершины(костяшки), внутренний перебирает вершины из второго массива, если есть совпадение, то начинает сравниваться уже эта вершина со всеми остальными, если весь второй массив перебран, то возвращаемся по порядку вершины на 1 назад и ищем вершины, которые ещё не использовались, но возможны для использования(например была такая комбинация 02-26-63, а возможно ещё и 02-26-61, и нам как раз и надо найти 61) и вот тут и начинается загвоздка, ведь если есть такая ситуация где у костяшки есть 3 или более продолжения, причем одно или несколько из них использованы в предыдущей комбинации, то мне никак не дойти до последнего продолжения, тоесть до того, которое стоит самым последним во второй индексной таблице, подскажите пожалуйста, как это победить?

    Вот мой код, в нем конечно много лишнего, просто несколько вариантов в одном файле делал:
    DECLARE
    TYPE one_tab IS RECORD (lev INTEGER(1) , prav INTEGER(1), ver INTEGER(2) );
    TYPE one_tabplus IS RECORD (lev INTEGER(1) , prav INTEGER(1), porjadok INTEGER(2));
    TYPE schet IS RECORD(nom INTEGER(2) , kol INTEGER(2));
    TYPE vershini IS RECORD(ind INTEGER(2) , ind2 INTEGER(2) , shod INTEGER(2));
    TYPE vershini_mat IS TABLE OF vershini INDEX BY PLS_INTEGER;
    TYPE soot IS TABLE OF schet INDEX BY PLS_INTEGER;
    TYPE cep_of IS TABLE OF one_tabplus INDEX BY PLS_INTEGER;
    TYPE pos IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
    TYPE cep IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
    TYPE tab_f IS RECORD (pod one_tab , nad one_tab , assoc integer(1));
    TYPE tab_is IS TABLE OF tab_f INDEX BY PLS_INTEGER;
    TYPE domin IS TABLE OF one_tab INDEX BY PLS_INTEGER;
    TYPE stack IS TABLE OF one_tab INDEX BY PLS_INTEGER;
    CURSOR perv IS SELECT pravo , levo FROM domino;
    CURSOR vtor IS SELECT pravo , levo FROM domino;
    per domin;
    vto domin;
    vto1 domin;
    vto2 domin;
    tre domin;
    matr tab_is;
    nomer soot;
    tab_ver vershini_mat;
    num INTEGER:=0;
    num2 INTEGER:=0;
    num3 INTEGER:=0;
    num4 INTEGER:=0;
    n INTEGER:=0;
    m INTEGER:=0;
    f INTEGER:=0;
    q INTEGER:=0;
    k INTEGER:=0;
    b INTEGER:=0;
    a INTEGER:=0;
    c INTEGER:=1;
    j INTEGER:=1;
    l INTEGER:=0;
    s INTEGER:=0;
    h INTEGER:=0;
    g INTEGER:=0;
    u INTEGER:=0;
    d INTEGER:=0;
    o INTEGER:=0;
    br INTEGER:=0;
    aw INTEGER:=0;
    z INTEGER:=0;
    z2 INTEGER:=0;
    zl INTEGER:=0;
    zp INTEGER:=0;
    bm INTEGER:=0;
    ty INTEGER:=0;
    cep1 cep;
    position pos;
    porad cep_of;
    stak stack;
    BEGIN


    porad(1).porjadok:=0;

    FOR i IN perv LOOP -- заполнение главного массива
    num:=num+1;
    per(num).lev:=i.levo;
    per(num).prav:=i.pravo;
    per(num).ver:=num;
    END LOOP;

    vto:=per; -- заполнение второго массива
    vto1:=per; -- заполнение третьего массива

    WHILE(o!=num) LOOP -- массив вершин и метки на них
    o:=o+1;
    nomer(o).nom:=o;
    nomer(o).kol:=0;

    END LOOP;

    LOOP --Массив матрицы сходимости
    exit when g=num;
    g:=g+1;
    aw:=0;
    LOOP
    EXIT WHEN aw=num;
    aw:=aw+1;
    if per(g).lev = per(aw).lev OR per(g).lev = per(aw).prav OR per(g).prav = per(aw).lev OR per(g).prav = per(aw).prav THEN
    tab_ver(aw).ind:=g;
    tab_ver(aw).ind2:=aw;
    tab_ver(aw).shod:=1;
    --DBMS_OUTPUT.PUT_LINE(tab_ver(aw).ind ||' '|| tab_ver(aw).ind2 ||' '|| tab_ver(aw).shod);
    ELSE
    tab_ver(aw).ind:=g;
    tab_ver(aw).ind2:=aw;
    tab_ver(aw).shod:=0;
    --DBMS_OUTPUT.PUT_LINE(tab_ver(aw).ind ||' '|| tab_ver(aw).ind2 ||' '|| tab_ver(aw).shod);
    END IF;
    END LOOP;
    END LOOP;



    FOR i IN 1..num LOOP --массив позиции вершины
    position(i):=0;

    END LOOP;






    LOOP -- цикл перебора правого числа
    n:=n+1; --корневая вершина графа
    nomer(n).kol:=1; --метка посещенности
    f:=1; --счетчик количества смежных вершин (не работает как надо)

    exit when n=0;
    q:=0; --счетчик смещения по второму массиву
    DBMS_OUTPUT.PUT_LINE('1n='||n);
    LOOP
    EXIT WHEN f=0;
    q:=q+1;

    IF q>num THEN
    a:=a+1;
    n:=b-a;
    q:=0;
    exit;
    ELSIF (per(n).lev = vto(q).lev) AND q!=n AND nomer(q).kol!=1 AND f!=0 THEN
    f:=f-1;

    DBMS_OUTPUT.PUT_LINE(per(n).prav||' '||per(n).lev ||' '||' --> '||vto(q).lev ||' '||vto(q).prav);
    b:=q;
    FOR i IN 1..num LOOP

    IF (per(i).lev=per(q).prav OR per(i).prav=per(q).prav ) AND i!=q THEN

    vto(i).lev:=per(i).lev;
    vto(i).prav:=per(i).prav;
    f:=f+1;
    ELSE
    vto(i).lev:=9;
    vto(i).prav:=9;

    END IF;

    END LOOP;

    FOR i IN 1..num LOOP
    DBMS_OUTPUT.PUT_LINE(vto(i).lev||vto(i).prav);
    END LOOP;


    n:=q;

    nomer(q).kol:=1;
    q:=0;
    CONTINUE;
    ELSIF (per(n).lev = vto(q).prav) AND q!=n AND nomer(q).kol!=1 AND f!=0 THEN
    DBMS_OUTPUT.PUT_LINE(per(n).prav||' '||per(n).lev ||' --> '||vto(q).prav ||' '||vto(q).lev);
    b:=q;
    f:=f-1;
    FOR i IN 1..num LOOP

    IF (per(i).lev=per(q).lev OR per(i).prav=per(q).lev ) AND i!=q THEN

    vto(i).lev:=per(i).lev;
    vto(i).prav:=per(i).prav;
    f:=f+1;
    ELSE
    vto(i).lev:=9;
    vto(i).prav:=9;

    END IF;

    END LOOP;
    FOR i IN 1..num LOOP
    DBMS_OUTPUT.PUT_LINE(vto(i).lev||vto(i).prav);
    END LOOP;

    nomer(q).kol:=1;

    n:=q;

    q:=0;
    CONTINUE;

    ELSIF(per(n).prav = vto(q).prav) AND q!=n AND nomer(q).kol!=1 AND f!=0 THEN
    DBMS_OUTPUT.PUT_LINE(per(n).lev||' '||per(n).prav ||' '||' --> '||vto(q).prav ||' '||vto(q).lev);
    b:=q;

    f:=f-1;

    FOR i IN 1..num LOOP

    IF (per(i).lev=per(q).lev OR per(i).prav=per(q).lev ) AND i!=q THEN

    vto(i).lev:=per(i).lev;
    vto(i).prav:=per(i).prav;
    f:=f+1;
    ELSE
    vto(i).lev:=9;
    vto(i).prav:=9;

    END IF;

    END LOOP;


    FOR i IN 1..num LOOP
    DBMS_OUTPUT.PUT_LINE(vto(i).lev||vto(i).prav);
    END LOOP;
    nomer(q).kol:=1;

    n:=q;

    q:=0;

    CONTINUE;


    ELSIF(per(n).prav = vto(q).lev) AND q!=n AND nomer(q).kol!=1 AND f!=0 THEN
    DBMS_OUTPUT.PUT_LINE(per(n).lev||' '||per(n).prav ||' '||' --> '|| vto(q).lev||' '||vto(q).prav );
    b:=q;

    f:=f-1;
    FOR i IN 1..num LOOP

    IF (per(i).lev=per(q).prav OR per(i).prav=per(q).prav ) AND i!=q THEN

    vto(i).lev:=per(i).lev;
    vto(i).prav:=per(i).prav;
    f:=f+1;
    ELSE
    vto(i).lev:=9;
    vto(i).prav:=9;

    END IF;

    END LOOP;
    FOR i IN 1..num LOOP
    DBMS_OUTPUT.PUT_LINE(vto(i).lev||vto(i).prav);
    END LOOP;

    nomer(q).kol:=1;

    n:=q;


    q:=0;

    CONTINUE;
    END IF;

    END LOOP;

    exit when n=num ;

    END LOOP;





    END;
     
  2. vasvas

    vasvas New Member

    Регистрация:
    Понедельник
    Сообщения:
    1
    Симпатии:
    0
Загрузка...
Похожие Темы - Sql sql Задача
  1. mrtg
    Ответов:
    1
    Просмотров:
    60
  2. mrtg
    Ответов:
    14
    Просмотров:
    222
  3. Allegro
    Ответов:
    3
    Просмотров:
    120
  4. rhino101
    Ответов:
    0
    Просмотров:
    351
  5. karitsa
    Ответов:
    1
    Просмотров:
    461

Поделиться этой страницей