[es] - Kombinacije koje je tesko objasniti

emiraga

Član broj: 54285
Poruke: 32
80.65.172.*

Profil

Kombinacije koje je tesko objasniti

^{20.02.2006. u 21:52 - pre 230 meseci}

Zdravo,

Definisimo

to je skup ciji elementi predstavljaju sve skupove koji su kombinacije brojeva

i koji imaju ukupno

razlicitih brojeva.
Broj elemenata skupa

, dok svaki element skupa

ima ukupno

elemenata.

Primjer:

= { {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} }

Zadati su

Zadatak nam je pronaci

, tako da skup

ima minimalan broj elemenata i da za svaki element

postoji bar jedan element

tako da je

.

---

Slobodno govoreci

se moze interpretirati kao "a od c" uz onaj dodatni uslov koji se vezuje za broj

.

Primjer:za

Code:

1 2 3 4 5 6
1 2 3       7 8 9
1 2   4     7     10 11
1 2             9    11 12 13
1   3   5     8      11       14
1   3     6 7   9             14
1   3       7     10    12 13
1     4 5       9 10          14
1       5 6             12 13 14
1       5     8 9 10 11
1         6 7 8   10          14
  2 3 4                 12 13 14
  2 3     6     9 10          14
  2   4   6   8      11       14
  2     5   7   9    11       14
  2     5     8   10    12 13
    3 4 5   7 8   10
    3 4       8 9 10 11
    3   5 6 7     10 11
    3     6   8      11 12 13
      4 5 6 7 8 9
      4 5   7        11 12 13
      4   6     9 10    12 13
            7 8 9       12 13 14

(ovo sam ovako poravnao da ljepse izgleda, uklonite duple razmake ako Vam trebaju samo brojevi)

Imam jos nekoliko primjera za razlicite vrijednosti

. Trazim pomoc oko odredjivanja algoritma za generisanje/odabiranje ovakvih kombinacija.

Edit: prijasnji primjer nije bio potpun.

_{[Ovu poruku je menjao emiraga dana 21.02.2006. u 00:30 GMT+1]}

Odgovor na temu

DDMM
Dejan D. M. Milosavljevic
Danguba
Gajba, ali ne piva.

Član broj: 2544
Poruke: 89
*.vdial.verat.net.

Sajt: www.ddmrm.com

Profil

Re: Kombinacije koje je tesko objasniti

^{26.02.2006. u 17:02 - pre 230 meseci}

Meni vec izgleda da je S vec takav skup.

Cini mise da bi trebalo da trazis poskup od P koji je minimalan a sadrzi S.

Odgovor na temu

emiraga

Član broj: 54285
Poruke: 32
*.europronet.ba.

Profil

Re: Kombinacije koje je tesko objasniti

^{26.02.2006. u 17:09 - pre 230 meseci}

Citat:

tako da skup

ima minimalan broj elemenata

To sam napisao u uslovu, mozda sam to trebao malo vise naglasiti, jer je to upravo kljucni dio.

Odgovor na temu

DDMM
Dejan D. M. Milosavljevic
Danguba
Gajba, ali ne piva.

Član broj: 2544
Poruke: 89
*.vdial.verat.net.

Sajt: www.ddmrm.com

Profil

Re: Kombinacije koje je tesko objasniti

^{27.02.2006. u 00:49 - pre 230 meseci}

Ipak S nije takav skup kao sto sam mislio.

evo neki pseudo kod koji resava problem, grubom silom.

Code:

napuni P;
T={}; // je prazan
// prodjes sve skupove od P
for( p=H(b,c).begin(); p != H(b,c).end(); p++ )
{
  // probas dali je svaki t iz T podskup od p iz P
  for( t = T.begin(); t != T.end(); t++ )
   if( t posskup p ) break;

   // nije sledi ubacivanje
   if( t == T.end() )
    {
     // generises sve podkombinacije od p-a.
     // malo nezgodan zapis H(p)
    // npr:  a=2, p={4,5,6} H(p)={ {4,5},{4,6},{5,6} }

     for( tt=H(p).begin();  tt=H(p).end() ; tt++ )
      {
       if( tt nije element od T ) // eto ga nov clan
        {
          tt.inset( tt ); break; //jer dovoljan je samo jedan
         }
      }
    }
}

Nego da te pitam.
Pravis program za LOTO? A?

_{[Ovu poruku je menjao DDMM dana 27.02.2006. u 01:51 GMT+1]}

Odgovor na temu