Programozás

[Valezius]

Originally Posted by Redback

2009/2010-es OKTV-ről két feladatra lennék kíváncsi :

1. Írj programot (jarda.pas, …), amely kiszámítja, hogy hány féleképpen lehet kikövezni egy 2*N egység méretű járdát 1*1 és 1*2 méretű lapokkal!

Nekem az jött ki, hogy ezt rekurzióval kell megcsinálni.

Ezután egy 2*N-es járdát úgy számolnék ki, hogy a vágósíkokat végigfuttatnám rajta.
Először felteszem, hogy 1+N-1 -re van szétvágva, aztán 2+N-2-re és így tovább.

A gond, hogy ezeket nem lehet összeadni, mert van közte átfedés.
De mindenképp úgy számolnék, hogy letenném a vágósíkokat minden lehetséges módon, aztán csak össze kell adogatni az eredményt.

Az egyes szétvágott daraboknak olyannak kell lennie, hogy belül már ne legyen vágósík. Ez akkor van, ha egy darab 1 széles (2elrendezés) vagy 2 széles (3 elrendezés) vagy 2x széles ekkor megint 2 elrendezés van.

Vagyis az N-et fel kell osztani minden lehetséges módon 1,2,4,6,8... összegére. A sorrend is számít.
De ezt leprogramozni nem tűnik vészesnek.

Például a 2x2-esnél ha nincs felosztva az 3 elrendezés, ha fel van, akkor még 2*2 és kijön a 7.

2x3-asnál 1+1+1 , 1+2, 2+1 a lehetséges sorrendek, szépek ki lehet számolni, hogy ez 2*2*2+2*3+3*2=20 lefedést jelent.

[Redback]

Originally Posted by Valezius

Nekem az jött ki, hogy ezt rekurzióval kell megcsinálni.

Ezután egy 2*N-es járdát úgy számolnék ki, hogy a vágósíkokat végigfuttatnám rajta.
Először felteszem, hogy 1+N-1 -re van szétvágva, aztán 2+N-2-re és így tovább.

A gond, hogy ezeket nem lehet összeadni, mert van közte átfedés.
De mindenképp úgy számolnék, hogy letenném a vágósíkokat minden lehetséges módon, aztán csak össze kell adogatni az eredményt.

Az egyes szétvágott daraboknak olyannak kell lennie, hogy belül már ne legyen vágósík. Ez akkor van, ha egy darab 1 széles (2elrendezés) vagy 2 széles (3 elrendezés) vagy 2x széles ekkor megint 2 elrendezés van.

Vagyis az N-et fel kell osztani minden lehetséges módon 1,2,4,6,8... összegére. A sorrend is számít.
De ezt leprogramozni nem tűnik vészesnek.

Például a 2x2-esnél ha nincs felosztva az 3 elrendezés, ha fel van, akkor még 2*2 és kijön a 7.

2x3-asnál 1+1+1 , 1+2, 2+1 a lehetséges sorrendek, szépek ki lehet számolni, hogy ez 2*2*2+2*3+3*2=20 lefedést jelent.

igen, így belegondolva tényleg igazad lehet

[vityu]

Originally Posted by Valezius

Nekem az jött ki, hogy ezt rekurzióval kell megcsinálni.

Ezután egy 2*N-es járdát úgy számolnék ki, hogy a vágósíkokat végigfuttatnám rajta.
Először felteszem, hogy 1+N-1 -re van szétvágva, aztán 2+N-2-re és így tovább.

A gond, hogy ezeket nem lehet összeadni, mert van közte átfedés.
De mindenképp úgy számolnék, hogy letenném a vágósíkokat minden lehetséges módon, aztán csak össze kell adogatni az eredményt.

Az egyes szétvágott daraboknak olyannak kell lennie, hogy belül már ne legyen vágósík. Ez akkor van, ha egy darab 1 széles (2elrendezés) vagy 2 széles (3 elrendezés) vagy 2x széles ekkor megint 2 elrendezés van.

Vagyis az N-et fel kell osztani minden lehetséges módon 1,2,4,6,8... összegére. A sorrend is számít.
De ezt leprogramozni nem tűnik vészesnek.

Például a 2x2-esnél ha nincs felosztva az 3 elrendezés, ha fel van, akkor még 2*2 és kijön a 7.

2x3-asnál 1+1+1 , 1+2, 2+1 a lehetséges sorrendek, szépek ki lehet számolni, hogy ez 2*2*2+2*3+3*2=20 lefedést jelent.

Így belegondolva tippem sincs, hogy mit jelent, amit írtál.

[Valezius]

Originally Posted by vityu

Így belegondolva tippem sincs, hogy mit jelent, amit írtál.

Akkor most bajban lennék, ha te tetted volna föl az eredeti kérdést

[Redback]

A 2x2-esnél milyen 3 elrendezésre gondolsz?

[Valezius]

Originally Posted by Redback

A 2x2-esnél milyen 3 elrendezésre gondolsz?

Ha nincs benne függőleges vágósík, akkor lehet vízszintesen 2db kettes tégla.
Aztán vagy az alsó vagy a felső becserélhető egyesekre.
(Mindkettő nem, mert akkor mégis van benne vágósík.)

Egyébként mégse kell semmiféle rekurzió. Csak elkezdtem írni, aztán láttam, hogy nem teljesen jó, úgyhogy újra kellett gondolnom.

[Redback]

Originally Posted by Valezius

Ha nincs benne függőleges vágósík, akkor lehet vízszintesen 2db kettes tégla.
Aztán vagy az alsó vagy a felső becserélhető egyesekre.
(Mindkettő nem, mert akkor mégis van benne vágósík.)

Egyébként mégse kell semmiféle rekurzió. Csak elkezdtem írni, aztán láttam, hogy nem teljesen jó, úgyhogy újra kellett gondolnom.

Az nem volt tiszta, hogy a vágósík csak függőleges lehet, de mostmár stimm Köszi szépen Vale

[Cpt Balu]

A második feladat cseles
Amiből kiindultam, hogy a gépeknek minimum szum(A műveletek időigénye) ill. szum(B műveletek időigénye) ideig dolgoznak, ezen nincs mit faragni. Az egyetlen lehetőségünk a minimalizálásra a gépek üresjáratának csökkentése.
Vegyünk egy olyan elemet, ahol A kicsi, B nagy. Ha az első gép A-val végez, mehet B-re, ahol sok időt fog tölteni, ezalatt egy másik terméken is elvégezhetjük A lépést, majd várólistára tehetjük, hogy a második gép rögtön tudjon tovább dolgozni.
Amire kell figyelni, hogy az első x elem A műveletidejének összege ne haladja meg a B műveletidők összegét (mínusz az első elem A ideje, ennyi előnyt kap az első gép), így nem kell a második gépnek az elsőre várakozni.
Ha az adatok olyanra sikerülnek, nyilván valóan akadni fog üresjárat, ezt úgy tudjuk minimalizálni, ha az input elemeket B idő-A idő szerint csökkenő sorrendbe tesszük (ezáltal az elején sok A lépéssel végzett elemet felhalmozunk, a második gép folyamatosan dolgozik)
Ettől már csak egy lépés a tökéletes megoldás, meg kell találni azt az első elemet, amelynél B-A kellőpen nagy, hogy utána mindig legyen legalább egy elem, amin A-t már befejeztük, de a második gépre még várnia kell, viszont ugyanakkor, A ideje ne legyen túl nagy, hogy a második gép is minél előbb dolgozni tudjon. Az ideális, ha az első elemnél A ideje 1, B pedig elég nagy ahhoz, hogy más (szintén B>A tulajdonságú) elemen elvégezzük az első lépést, és várakozzon a másodikra.