Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Mozgalica - Dolazak proleca

[es] :: Baze podataka :: Mozgalica - Dolazak proleca

[ Pregleda: 3203 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Zidar
Canada

Član broj: 15387
Poruke: 3085
*.100.46-69.q9.net.



+79 Profil

icon Mozgalica - Dolazak proleca22.02.2008. u 16:38 - pre 161 meseci
Zima polako prolazi i dolazi nam prolece. Uskoro pocinju sportka takmicenja. Evo i jedna sportske mozgalice.

Imamom paran broj timova koji treba da igraju po liga sistemu, svako sa svakim. Za primer, uzmimo 6 timova. Timovi su dati u tabeli
CRAETE Timovi
(RedniBroj int UNIQUE CHECK (RedniBroj BETWEEN 1 and 6)
, Tim varchar(15) PRIMARY KEY)

Treba napraviti raspored utakmica, po kolima. Za 6 timova, bice 5 kola. Svako igra sa svakim tacno jednom. U svakom kolu svaki tim se pojavljuje samo jednom.

Treba ispisati raspored, nesto ovako:

Kolo Domacin Gost
-------------------
1 1 4
1 2 5
1 3 6

2 1 5
2 4 6
2 2 3

3 1 6
3 5 3
3 4 2

4 1 3
4 6 2
4 5 4

5 1 2
5 3 4
5 6 5

Prazne redove izmedju kola sam ja ubacio, zbog lakseg citanja.

Nemam SQL kveri koji bi odradio ovo, pa smatram da je mozgalica izuzetno teska.
Imam relativno jednostavan kod koji moze da ispise raspored za zadato N (N=2k, paran broj).
Ako pogledate kako sam napravio raspored, shvaticete sta kod radi.
Algoritam koji ja koristim ide ovako "Drzi broj "1" na fiksnoj poziciji i "rotiraj" ostale brojeve oko jedne tacke (jedinice)

To je jedini algoritam koji znam i na koji sam nadosao sam, nisam ga nasao nigde u nekoj literaturi.
Ne znam ni gde bih trebao da trazim. kad sam pre neku godinu iz radoznalosti postavio slicno pitanej na forumu matematika, moderator mi je obrisao post s obrazlozenjem "ne radimo domace zadatke na forumu "

Ovo nije domaci zadatak, niti nesto sto mi treba. kad mi je trebalo, napisao sam kod i izradio tablice za lige od 4 do 20 timova koje cuvam u tabelama i koristim kad mi treba. Pitanje je cisto akademsko, da vidimo moze li ovo u SQL-u da se uradi, po mogucstvu bez kursora ili DO WHILE. Ako imate resenej sa DO WHILE, slobodno ga ponudite, a onda cemo probati pomocu rekurzivnog WITH da eliminisemo WHILE.

Nadam se da ce me neko napraviti smesnim i pokazati da je ovo lako resivo u SQL-u.




 
Odgovor na temu

sasas
Saša Slavnić
radim za neke švabe

Član broj: 35478
Poruke: 617
*.dynamic.sbb.co.yu.



Profil

icon Re: Mozgalica - Dolazak proleca23.02.2008. u 08:17 - pre 161 meseci
Ne da je teška, nego je do zla boga teška :)
Ja ne uspevam da nađem neko pametno rešenje, ali evo par razmišljanja, ako će nekom dati ideju:

Code:

    SELECT t1.id AS id1, t2.id AS id2
    FROM Timovi AS t1 CROSS JOIN Timovi AS t2
    WHERE t1.id < t2.id


Ovaj kod gore će dati spisak parova, za slučaj od šest timova sam proverio i rezultati su korektni. Problem je naravno sortiranje po kolima. Uslov WHERE je tu da se parovi ne bi ponavljali (1-2 i 2-1). Sledeći upit je za specijalni slučaj (kada je šest timova u pitanju):

Code:

SELECT * FROM 
(
    SELECT t1.id AS id1, t2.id AS id2
    FROM Timovi AS t1 CROSS JOIN Timovi AS t2
    WHERE t1.id < t2.id

AS par1 INNER JOIN 
(
    SELECT t1.id AS id1, t2.id AS id2
    FROM Timovi AS t1 CROSS JOIN Timovi AS t2
    WHERE t1.id < t2.id

AS par2 ON 
    par1.id1 <> par2.id1 AND par1.id1 <> par2.id2 AND
    par1.id2 <> par2.id1 AND par1.id2 <> par2.id2 
INNER JOIN 
(
    SELECT t1.id AS id1, t2.id AS id2
    FROM Timovi AS t1 CROSS JOIN Timovi AS t2
    WHERE t1.id < t2.id

AS par3 ON 
    par3.id1 <> par1.id1 AND par3.id1 <> par1.id2 AND par3.id1 <> par2.id1 AND par3.id1 <> par2.id2 AND
    par3.id2 <> par1.id1 AND par3.id2 <> par1.id2 AND par3.id2 <> par2.id1 AND par3.id2 <> par2.id2


Upit takođe ne rešava problem, ali daje spisak svih mogućih kombinacija između timova. Problem je naravno izabrati listu jedinstvenih utakmica. U svakom slučaju ovo ne bi bilo u duhu postavke zadatka zbog ograničenja na tri para, ali možda nekome pomogne...

Zidar, svaka čast na ovom problemu, jedva čekam da vidim rešenja :)

Pozdrav svima!
When something is hard to do, then it's not worth doing.
 
Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
77.46.194.*



+171 Profil

icon Re: Mozgalica - Dolazak proleca23.02.2008. u 14:35 - pre 161 meseci
Zidar, skidam kapu
Ova je bas teska. gde li smo nadje za vikend da postujes

Code:

WITH Temp (BrojTimova, Kolo, RB, Reset, T1, T2) AS 
(    
    SELECT (SELECT COUNT(*) FROM Timovi), 1, 1, (SELECT COUNT(*) FROM Timovi), 1, (SELECT COUNT(*) FROM Timovi)

    UNION ALL

    SELECT 
        BrojTimova,

        CASE
            WHEN RB = (BrojTimova / 2) THEN Kolo + 1
            ELSE Kolo
        END AS Kolo,

        CASE
            WHEN RB = (BrojTimova / 2) THEN  1
            ELSE RB + 1
        END AS RB,

        CASE
            WHEN RB = (BrojTimova / 2) THEN Reset - 1
            ELSE Reset
        END AS RB,

        CASE 
            WHEN RB = (BrojTimova / 2) THEN 1
            WHEN RB = 1 AND Reset < BrojTimova THEN Reset + 1
            WHEN T1 = BrojTimova THEN 2
            ELSE T1 + 1
        END AS T1,        
    
        CASE            
            WHEN RB >= (BrojTimova / 2) THEN Reset - 1
            WHEN T2 = 2 THEN BrojTimova        
            ELSE T2 - 1
        END AS T2
                
    FROM 
        Temp 
    WHERE 
        NOT (Kolo = BrojTimova - 1 AND RB = BrojTimova / 2)

SELECT 
    Kolo, RB, T1, TM1.Tim, T2, TM2.Tim
FROM 
    Temp
    LEFT JOIN Timovi AS TM1 ON TM1.RedniBroj = T1
    LEFT JOIN Timovi AS TM2 ON TM2.RedniBroj = T2



Evo sta sam uspeo da izgulim, ali ovo je samo implementacija Zidarevog resenja. Drugi nacin je bio preko eleminicija, ali to bi bilo sporije resenje (dobro, na ovim malim podacima ne bi bio problem ali sa vise podataka...), uglavnom, odustao sam jer trazi dosta mozganja, ovo je za sada jedini nacin koji sam uspeo da implementiram, nadam se da ce neko dati neko elegantnije resenje, jer ovo je radjeno na "misice", vise je u duhu imperativnih nego deklarativnih jezika

Da, trebalo bi da radi nad bilo kojom kolicinom podataka, samo mora biti paran broj timova
 
Odgovor na temu

Zidar
Canada

Član broj: 15387
Poruke: 3085
*.100.46-69.q9.net.



+79 Profil

icon Re: Mozgalica - Dolazak proleca25.02.2008. u 17:58 - pre 161 meseci
@negyxo: nema razloga za skromnost, tvoj kod radi, provereno. Cestitamm

Samo sam povecao broj iteracija na kraju i dodao ORDER BY, da rezultat lepse izgleda.

Code:

CREATE TABLE Timovi 
(RedniBroj int UNIQUE CHECK (RedniBroj BETWEEN 1 and 20)
, Tim varchar(15) PRIMARY KEY)

INSERT INTO Timovi VALUES (1, 'Zvezda')
INSERT INTO Timovi VALUES (2, 'Partizan')
INSERT INTO Timovi VALUES (3, 'Radnicki')
INSERT INTO Timovi VALUES (4, 'Vojvodina')
INSERT INTO Timovi VALUES (5, 'Spartak')
INSERT INTO Timovi VALUES (6, 'Hajduk sa Liona')

-- Evo ga raspored utakmica za 6 timova:
       Kolo          RB          T1 Tim                      T2 Tim
----------- ----------- ----------- --------------- ----------- ---------------
          1           1           1 Zvezda                    6 Hajduk sa Liona
          1           2           2 Partizan                  5 Spartak
          1           3           3 Radnicki                  4 Vojvodina

          2           1           1 Zvezda                    5 Spartak
          2           2           6 Hajduk sa Liona           4 Vojvodina
          2           3           2 Partizan                  3 Radnicki

          3           1           1 Zvezda                    4 Vojvodina
          3           2           5 Spartak                   3 Radnicki
          3           3           6 Hajduk sa Liona           2 Partizan

          4           1           1 Zvezda                    3 Radnicki
          4           2           4 Vojvodina                 2 Partizan
          4           3           5 Spartak                   6 Hajduk sa Liona

          5           1           1 Zvezda                    2 Partizan
          5           2           3 Radnicki                  6 Hajduk sa Liona
          5           3           4 Vojvodina                 5 Spartak

(15 row(s) affected)


-- Zidar dodao prazne redove izmedju kola rucno, da bi bilo preglednije :-)

-- raspored je rezultat SELECT iskaza koji je napiso negyxo:
WITH Temp (BrojTimova, Kolo, RB, Reset, T1, T2) AS 
(    
    SELECT (SELECT COUNT(*) FROM Timovi), 1, 1, (SELECT COUNT(*) FROM Timovi), 1, (SELECT COUNT(*) FROM Timovi)

    UNION ALL

    SELECT 
        BrojTimova,

        CASE
            WHEN RB = (BrojTimova / 2) THEN Kolo + 1
            ELSE Kolo
        END AS Kolo,

        CASE
            WHEN RB = (BrojTimova / 2) THEN  1
            ELSE RB + 1
        END AS RB,

        CASE
            WHEN RB = (BrojTimova / 2) THEN Reset - 1
            ELSE Reset
        END AS RB,

        CASE 
            WHEN RB = (BrojTimova / 2) THEN 1
            WHEN RB = 1 AND Reset < BrojTimova THEN Reset + 1
            WHEN T1 = BrojTimova THEN 2
            ELSE T1 + 1
        END AS T1,        
    
        CASE            
            WHEN RB >= (BrojTimova / 2) THEN Reset - 1
            WHEN T2 = 2 THEN BrojTimova        
            ELSE T2 - 1
        END AS T2
                
    FROM 
        Temp 
    WHERE 
        NOT (Kolo = BrojTimova - 1 AND RB = BrojTimova / 2)

SELECT 
    Kolo, RB, T1, TM1.Tim, T2, TM2.Tim
FROM 
    Temp  
    LEFT JOIN Timovi AS TM1 ON TM1.RedniBroj = T1
    LEFT JOIN Timovi AS TM2 ON TM2.RedniBroj = T2
ORDER BY Kolo
OPTION (MAXRECURSION 10000);


 
Odgovor na temu

negyxo
Aleksandar Perkuchin

Član broj: 29751
Poruke: 898
79.101.148.*



+171 Profil

icon Re: Mozgalica - Dolazak proleca25.02.2008. u 20:58 - pre 161 meseci
A ne, nije skromnost, u pocetku je bio poraz a posle trijumf
Pokusao sam na my way da resim ali posle dva sata sam digao ruke, zatim sam presao na ovu tvoju ideju i uradio implementaciju.
 
Odgovor na temu

Zidar
Canada

Član broj: 15387
Poruke: 3085
*.100.46-69.q9.net.



+79 Profil

icon Re: Mozgalica - Dolazak proleca25.02.2008. u 21:14 - pre 161 meseci
Evo i moje resenje, radi i u MS SQL 2000. Lici mi da je prilicno standardan SQL, pa bi trebalo da radi i kojekuda drugo.

Radio sam od kuce, bez gledanja u originalni tekst mozgalice pa se moje tabele neznatno razlikuju od originalnih.

Kreirao sam dve tabele, Timovi i Brojevi:
Code:

CREATE TABLE Timovi
(TimID int PRIMARY KEY
, ImeTima varchar(50) UNIQUE
)
GO

INSERT INTO Timovi VALUES (1,'Zvesda')
INSERT INTO Timovi VALUES (2,'Partizan')
INSERT INTO Timovi VALUES (3,'Radnicki Nis')
INSERT INTO Timovi VALUES (4,'Sloboda Tuzla')
INSERT INTO Timovi VALUES (5,'Hajduk sa Liona')
INSERT INTO Timovi VALUES (6,'OFK Beograd')
INSERT INTO Timovi VALUES (7,'Barcelona')
INSERT INTO Timovi VALUES (8,'Inter')

CREATE TABLE BRojevi (Broj int PRIMARY KEY)


U brojeve sam uneo brojeve od 0 do 1000. vazno je da je od nule, a ne od jedinice.

Isti algoritam koji je negyxo resio sa WITH, ja sma resio sa dva-tri view-a.

Code:

CREATE VIEW Sablon AS
SELECT 
      Utakmica = Pos + 1
    , Domacin_Pos = Pos
    , Gost_Pos = (SELECt COUNT(*) FROM Timovi) - Pos - 1
FROM
(
SELECT Broj AS Pos FROM Brojevi
WHERE Broj <= ((SELECT COUNT(*) FROM Timovi)-1)
) AS P
WHERE Pos < (SELECt COUNT(*) FROM Timovi)/2
GO

SELECT 
S.*
FROM Sablon AS S

   Utakmica Domacin_Pos    Gost_Pos
----------- ----------- -----------
          1           0           7
          2           1           6
          3           2           5
          4           3           4

(4 row(s) affected)

Timovo od2 do 8 treba da se rotiraju na pozicijama 0 do 7. Za svako kolo odnos pozicija timova ostaje isti, i to nam daje view "Sablon".
Rotiranje obezbedjuje view "Pozicije"
Code:

CREATEVIEW Pozicije AS
-- pozicije po kolima: 
SELECT Kolo, Tim, Pos =      CASE 
                                WHEN Pos >= (SELECT COUNT(*) FROM Timovi) 
                                    THEN Pos + 1 - (SELECT COUNT(*) FROM Timovi) 
                                    ELSE Pos
                            END
FROM
    (
    --- Pozicija za im 1 je uvek Pos(Tim=1) = 0:
    SELECT Kolo = Broj, Tim=1, Pos = 0
    FROM Brojevi
    WHERE Broj <= (SELECt COUNT(*) FROM Timovi)-1
        AND Broj > 0
    UNION
    -- Pozicije ostalih timova
    SELECT Kolo = Broj, Tim= TimID, Pos = TimID + Broj-2
    FROM Timovi AS T, Brojevi AS B
    WHERE TimID > 1
        AND Broj <= (SELECt COUNT(*) FROM Timovi)-1
        AND Broj > 0
    ) AS U
GO

SELECT * FROM Pozicije

       Kolo         Tim         Pos
----------- ----------- -----------
          1           1           0
          2           1           0
          3           1           0
          4           1           0
          5           1           0
          6           1           0
          7           1           0
          1           2           1
          1           3           2
          1           4           3
          1           5           4
          1           6           5
          1           7           6
          1           8           7
          2           2           2
          2           3           3
          2           4           4
          2           5           5
          2           6           6
          2           7           7
          2           8           1

Napisite na papiru rezultat kverija "Sablon". Tmove sa rezultata kverija "Pozicije" smestite na odgovarajuce pozicije u ispisanom sablonu. Ako pazljivo posmatrate rezultat videcete da tim 1 ostale u levom gornjem uglu sablona, a ostali timovi su se pomerili kruzno za po jednu poziciju u smeru suprotnom od kazaljke na satu.

Sada je potrebno da od view-a "Pozicije" napravimo raspored utakmica u poznatom obliku:
Code:

CREATE VIEW Utakmice AS
(
SELECT
    D.Kolo, D.Utakmica, D.imeTima AS Domacin, G.ImeTima AS Gost
FROM
(
--- domacini po kolima:
SELECT 
    P.Kolo
    , S.Utakmica
    , P.Pos
    , P.Tim 
    , T.ImeTima 
FROM Pozicije AS P
JOIN Sablon AS S ON P.Pos = S.Domacin_Pos
JOIN Timovi AS T ON P.Tim = T.TimID

) AS D
JOIN
(
-- Gosti po kolima ---
SELECT 
    P.Kolo
    , S.Utakmica
    , P.Pos
    , P.Tim 
    , T.ImeTima 
FROM Pozicije AS P
JOIN Sablon AS S ON P.Pos = S.Gost_Pos
JOIN Timovi AS T ON P.Tim = T.TimID

) AS G
ON D.Kolo = G.Kolo AND D.Utakmica = G.Utakmica
)
GO


SELECT * FROM Utakmice
ORDER BY Kolo, Utakmica

       Kolo    Utakmica Domacin                                            Gost
----------- ----------- -------------------------------------------------- --------------------------------------------------
          1           1 Zvesda                                             Inter
          1           2 Partizan                                           Barcelona
          1           3 Radnicki Nis                                       OFK Beograd
          1           4 Sloboda Tuzla                                      Hajduk sa Liona
          2           1 Zvesda                                             Barcelona
          2           2 Inter                                              OFK Beograd
          2           3 Partizan                                           Hajduk sa Liona
          2           4 Radnicki Nis                                       Sloboda Tuzla
          3           1 Zvesda                                             OFK Beograd
          3           2 Barcelona                                          Hajduk sa Liona
          3           3 Inter                                              Sloboda Tuzla
          3           4 Partizan                                           Radnicki Nis

Ovo vec izgleda jako blizu pravom resenju. Pravo resenje zahteva da timovi budu naizmenicno gosti i domacini, ako je moguce. Posto je broj kola neparan, neko ce morati da bude gost vise puta a neko ce biti domacin vise puta. A u drugom delu sezone sbve se menja. Sa porastom broja timova, odnos broja gostovanja i broja utakmica na svom terenu tezi da se uproseci. Za 16-18 timova prakticno s cini da je broj gostovanja gotovo isti za sve timove. Da probamo:
Code:

SELECT
    Kolo
    , Utakmica
    , Parnepar = Kolo % 2
    , Tim_Domacin      = CASE WHEN  Kolo % 2 = 0 THEN Gost ELSE Domacin END
    , Tim_Gost        = CASE WHEN  Kolo % 2 = 0 THEN Domacin ELSE Gost END
FROM Utakmice
ORDER BY     
    Kolo
    , Utakmica

-- rezultat:

       Kolo    Utakmica    Parnepar Tim_Domacin                                        Tim_Gost
----------- ----------- ----------- -------------------------------------------------- -----------------------------------
          1           1           1 Zvesda                                             Inter
          1           2           1 Partizan                                           Barcelona
          1           3           1 Radnicki Nis                                       OFK Beograd
          1           4           1 Sloboda Tuzla                                      Hajduk sa Liona

          2           1           0 Barcelona                                          Zvesda
          2           2           0 OFK Beograd                                        Inter
          2           3           0 Hajduk sa Liona                                    Partizan
          2           4           0 Sloboda Tuzla                                      Radnicki Nis

          3           1           1 Zvesda                                             OFK Beograd
          3           2           1 Barcelona                                          Hajduk sa Liona
          3           3           1 Inter                                              Sloboda Tuzla
          3           4           1 Partizan                                           Radnicki Nis

          4           1           0 Hajduk sa Liona                                    Zvesda
          4           2           0 Sloboda Tuzla                                      OFK Beograd
          4           3           0 Radnicki Nis                                       Barcelona
          4           4           0 Partizan                                           Inter



Prazne linije izmedju kola sam ubacio rucno, da se bolje vidi. Naravno da to moze i kroz kveri, ali to nije poenta mozgalice.

Ima li drugih pokusaja? Cini mi se da je najveci problem naci algoritam za rotiranje timova koji daje ono sto nam treba - da se u svakom kolu svaki tim pojavi tacno jednom. Mozda kolege sa foruma Matematika mogu da pomognu oko algoritma za rotiranje?

:-)
 
Odgovor na temu

[es] :: Baze podataka :: Mozgalica - Dolazak proleca

[ Pregleda: 3203 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.