Ima li neko ideju za ovaj problem?

Odgovori Nova tema

2 odgovora
2.094 pregleda

Ima li neko ideju za ovaj problem? 04.04.2007. u 20:07 · pre 238 meseci #1

Tekst je prost, ali cini mi se da je resenje malo mnogo komplikovanije...

Zadan je papir na kvadratice dimenzija NxM. (N,M<=100)
Na koliko raznih nacina ga mozemo ispresavijati tako da na kraju dobijemo jedan kvadratic ako je dozvoljeno presavijanje po bilo kojoj liniji? Nikakvo dijagonalno savijanje, polu-uvijanje, cepkanje i slicne kreativnosti nisu dozvoljeni. Dva nacina se smatraju jednakim ako je razlika samo u (2D :-) rotaciji papira (ili je prevrnut pa sklopljen).

Dakle, ako bilo kome padne nesto na pamet, svaka sugestija je dobrodosla, posto ja stvarno ne znam gde da pocnem

Hvala unapred!

Re: Ima li neko ideju za ovaj problem? 04.04.2007. u 21:04 · pre 238 meseci #2

Ako sam dobro ukapirao zadatak, mozes da ga resis dinamicki: $d [i][j]$ ti je broj nacina da dobijes kavdratic od papira dimenzije $i x j$ . I onda ti je
$d [n][m] = \sum_{i=1}^{n} d[i][m] + \sum_{i=1}^{m} d[n][i]$ . E ako treba da razlikujes to oko rotiranja onda to treba da delis sa 2 ako je parno ili -1 pa podelis sa 2 ako je neparno... Slozenost ti je $O(nm)$ ako ove sume pamtis u nekom nizu.

Potpis

Math is like love. A simple idea but it can get complicated.

Re: Ima li neko ideju za ovaj problem? 04.04.2007. u 22:29 · pre 238 meseci #3

Hvala, cassey. I ja sam se vrteo oko dinamickog, ali sam imao gresku u logici pa su me bunila nekakva preklapanja slucajeva i gluposti. Ustedeo si mi prilicno vremena...
Veliki pozdrav

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Srodne teme