Matematické Fórum

zkusil bych prohledávání do hloubky. ale nevim, jestli je to zrovna efektivní

Rozdělme čokoládu na "komponenty souvislosti" - každá komponenta je maximální souvislá plocha bez rozinky. Pak stačí vyšetřovat každou komponentu zvlášť a počet možných dělení je součin možných dělení u jednotlivých komponent.

↑ check_drummer:A na každou komponentu souvislosti se můžeme dívat jako na bipartitní graf. Partity jsou indukovány "šachovnicovým" obarvením. Potom jde o to najít POČET úplných (někdy se jim říká perfektní) párování v bipartitním grafu (ne nutně pravidelném).
Řekl bych, že naprogramování algoritmu, který hledaný počet určí, bude jednodušší, než pokusit se sestavit obecný vzorec.

↑ Luky10:JPřiblížím tu grafovou formulaci.
Každému čtverečku bez hrozinky odpovídá vrchol grafu. Každý vrchol je spojen hranou s jiným vrcholem, pokud spolu na čokoládě sousedí hranou. Pokud by čokoláda byla barevná jako šachovnice, tak vždy sousedí černé čtverečky s bílými a naopak, nikdy černé s černými nebo bílé s bílými. Proto je graf bipartitní (jedna partita černé, druhá bílé čtverečky).
Pokud má některá komponenta lichý počet vrcholů, úloha nemá řešení. Pokud mají všechny komponenty sudý počet vrcholů, je potřeba pro každou komponentu najít (nejlépe rekurzívním algoritmem, nebo prohledáváním) počet různých párování a celkový počet je (jak už bylo řečeno) pak součinem počtu řešení pro jenotlivé komponenty.

↑ Luky10:

Dej vědět jestli si to už pořešil nebo ne...
Jinak přikláním se k tomu co říkal Stýv na začátku. Efektivita podle mě nemá smysl vůbec řešit, jestli nebudeš mít čokoládu 3x10000 tak výsledek dostaneš skoro okamžitě.

Algoritmus ↑ petrkovar: je zřejmě korektní, ale jeho implementace vyžaduje přemýšlení. 

Proto navrhnu "brute force" alternativu: uvažme tabulku o sedmi sloupcích, sloupce odpovídají podmnožinám množiny {1,2,3} o 0,1 a 2 prvcích. Na i-tém řádku ve sloupci P je počet způsobů, jimiž lze rozdělit prvních i-1 řad čokolády tak, že v i-té řadě je přesahujícími obdélníky pokryta podmnožina P. Každý řádek spočteme rekurzivně z předchozího. Stačí nám pamatovat si dva poslední řádky.

Jistě jde o polynomiální algoritmus.

↑ Lumikodlak: S tou linearitou ... při běžném přístupu "do integeru se vleze vše", ano. Ale pokud by byly opravdu stovky tisíc řádků a na nich (téměř) žádné hrozinky, může mít výsledek stovky tisíc cifer, bylo by proto poctivější mluvit o kvadratické složitosti. Předpokládám, že ty jsi měl hrozinek hodně, pokud jsi nenarazil na omezení intu :)

↑ Lumikodlak:
Mohl bys ten kód prosíém někam umístit? (třeba sem na forum)
Sice už termín odevzdání vypršel, ale stejně mě velice zajímá, jak to vyřešit.
Dík

Díky moc ;)
Měl jsem potíž s funkcemi memset() a memcopy(), našel jsem si jejich princip a myslím, že jsem ho pochopil - daly by se ty funkce (popořadě) nahradit tímto?:

    for (i=0;i<=3;i++) { for (y=0;y<=3;y++) { for (x=0;x<=3;x++) { SoucasneMoznosti[i][y][x]=0;}}}
          for (i=1;i<=3;i++) {DocasnyRadek[i]=Cokolada [CisloRadku][i];}
     for (i=0;i<=3;i++) { for (y=0;y<=3;y++) { for (x=0;x<=3;x++) {MinuleMoznosti[i][y][x]=SoucasneMoznosti[i][y][x];}}}

Dále bych se chtěl zeptat, jestli by jsi mi nemohl vysvětlit jak generuješ obsah polí Rozvrzeni a MinuleMoznosti na základě pole Cokolada.
Děkuji předem za další odpovědi

Někde asi bude chyba, tento kód:

#include <stdio.h>

typedef struct{
  int PocetMoznosti;
  int VysledneRozvrzeni [3][3];
} Rozmisteni;

int Cokolada [1000][3];

int CelkovyPocetMoznosti, IndexRozmisteni, IndexMoznosti, PocetRadek;
int DocasnyRadek [3];
int MinuleMoznosti [2][2][2]  = {0,0,0,0,0,0,0,1};
int SoucasneMoznosti [2][2][2];

Rozmisteni Rozvrzeni [2][2][2] = {{{
  {3, 1,1,1 , 1,0,0 , 0,0,1 },                         //  0 0 0
  {2, 1,1,0 , 0,0,0 }},{                               //  0 0 1
  {1, 1,0,1 },                                         //  0 1 0
  {1, 1,0,0 }}},{{                                     //  0 1 1
  {2, 0,1,1 , 0,0,0 },                                 //  1 0 0
  {1, 0,1,0 }},{                                       //  1 0 1
  {1, 0,0,1 },                                         //  1 1 0
  {1, 0,0,0 }                                          //  1 1 1
  }}};

int main(){
    int i,y,x;
PocetRadek=5;
for (i=0;i<PocetRadek;i++){for (y=0;y<=2;y++){ Cokolada[i][y]=0;}}
Cokolada[2][0]=1;
Cokolada[2][1]=1;
Cokolada[2][2]=1;



  int CisloRadku;
  for (CisloRadku = 0; CisloRadku < PocetRadek; CisloRadku ++){
for (i=0;i<2;i++) { for (y=0;y<2;y++) { for (x=0;x<2;x++) { SoucasneMoznosti[i][y][x]=0;}}}
    for (IndexRozmisteni = 0; IndexRozmisteni < 8; IndexRozmisteni ++){
      if (MinuleMoznosti [0][0][IndexRozmisteni]){
        for (IndexMoznosti = 0; IndexMoznosti < Rozvrzeni [0][0][IndexRozmisteni].PocetMoznosti; IndexMoznosti ++){
                   for (i=1;i<3;i++) {DocasnyRadek[i]=Cokolada [CisloRadku][i];}
          DocasnyRadek [0] += Rozvrzeni [0][0][IndexRozmisteni] . VysledneRozvrzeni [IndexMoznosti][0];
          DocasnyRadek [1] += Rozvrzeni [0][0][IndexRozmisteni] . VysledneRozvrzeni [IndexMoznosti][1];
          DocasnyRadek [2] += Rozvrzeni [0][0][IndexRozmisteni] . VysledneRozvrzeni [IndexMoznosti][2];
          if (DocasnyRadek [0] > 1 || DocasnyRadek [1] > 1 || DocasnyRadek [2] > 1) continue;
          SoucasneMoznosti [DocasnyRadek [0]] [DocasnyRadek [1]] [DocasnyRadek [2]] += MinuleMoznosti [0][0][IndexRozmisteni];
        }
      }
    }

      for (i=0;i<2;i++) { for (y=0;y<2;y++) { for (x=0;x<2;x++) {MinuleMoznosti[i][y][x]=SoucasneMoznosti[i][y][x];}}}
  }
  CelkovyPocetMoznosti = MinuleMoznosti[0][0][1] + MinuleMoznosti[1][0][0] + MinuleMoznosti[1][1][1];
  printf("Moznosti: %i",CelkovyPocetMoznosti);
}

Mi vypíše "Moznosti: 0" :(