Fórum: GEOMETRIA

Vagy épp jóval nehezebb. Nem tudom.

Most esett le, hogy mit mond ez a feladat. Figyelmesebben kéne olvasnom. Tehát a kockákat csak sorban lehet felhasználni. Így, azt hiszem, jóval könnyebb.

Viszont az átlatános táblázat benne van: A113881.

Ha megnézzük, hogy egy n+1 x n méretű téglalapot hány részre kell a szabályok szerint szétvágni, akkor egy ilyen sorozat jön ki.

2, 3, 4, 5, 5, 5, 7, 7, 6, 6, 7, 7, 7, 7, 7, 9, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 11, 9, 9, 9, 9, 10, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 10, 10, 12, 10, 10, 10, 10, 10, 10, 10, 11, 10, 10, 11, 12, 11, 11, 11, 12, 12, 11, 11, 11, 11, 11, 11, 12, 12, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 11, 11, 11, 11, 11, 11, 11, 12, 12, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 15, 12, 12, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 13, 13, 12, 12, 12, 12, 12, 12, 13, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 13, 13, 13, 13, 13, 13, 13, 14, 14, 13, 13, 13, 13, 13, 13, 13, 14, 13, 13, 14, 13, 13, 13, 13, 13, 13, 13, 14, 13, 13, 13, 14, 13, 13, 13, 13, 13, 13, ...

Ez a sorozat (még) nincs benne az OEIS-ben.

Akkor itt van: vag.bmp.

Jaj. Így sem lehet, mert a fórum átalakítja jpeg-gé.

Akkor feltöltöm valahova.

Feltöltöm a programot is, ha valakit érdekel. Ez már egy módosított változat, 2501 [484] hozzászólásából elloptam az ötletet, valamint képbe ágyaztam.

Ez egy ruby program. Ha ki akarod próbálni, mentsd le vag.bmp néven, majd indítsd el a ruby vag.bmp paranccsal. (Bocs, de másképpen nem lehet ide programkódot feltölteni.)

Mivel nem tudok programot írni, felszerkesztettem:

Bele :-) Asszem tényleg átírom nemrekurzívra, ahogy 2501 mondta, és akkor ilyen finomságokat is bele lehet tenni. Nemsoká jelentkezem. Bár ugye a felbontás nem mindig egyértelmű, a progam max egy megoldást fog kiadni a sok közül.

Közben megírtam a programot, és lefuttattam 99x98-ra, csak valami technikai gond miatt nem sikerült post-olnom ide a hozzászólást.

Az jött ki, hogy legkevesebb 11 kis négyzet kell.

Ezt a következőképp kell megcsinálni. (Visszafele mondom, mert úgy könnyebb követni.)

Először két 6-os és egy 12-es négyzetből csinálunk egy 12x18-asat, amit két 18-as négyzettel kibővítünk 18x48-assá. Utána csináljunk két 16-os és egy 32-es négyzetből egy 32x48-asat. Most a 18x48-as és a 32x48-asat összerakjuk a közös oldal mentén 50x48-assá. Eddig elhasználtunk 8 négyzetet.

Most az 50x48-asunkat egy 50x50-es négyzet mellé tapasztjuk, hogy egy 50x98-as téglalapot kapjunk. Végül ennek a 98-as oldala mellé még két 49-es négyzetet rakunk egymás mellé, így egy 99x98-ast kapunk. Három négyzet kellett a befejezéshez, tehát ez összesen 11 négyzet.

Mondjátok csak, olyan opciót bele lehetne építeni valahogy, hogy a program azt is számolja hogy milyen négyzetből hány darabot használt fel???

Mondjuk az 5*6-os téglalphoz kell kettő darab 3*3-as, mag három darab 2*2.

Jójó tudom, de köszi hogy szóltál :-) 98x99-re így is lefut úgy, hogy nem veszem észre, hogy eltelt volna bármi idő is, de átírom nemsoká, hogy még frappánsabb legyen ;-)

Te gondolom tudod, de azert leirom, hogy ez a gondolatmenet hogyan viheto tovabb.

Mivel a tablazat minden eleme csak a vele azonos sorban elotte, illetve azonos oszlopban folotte levo elemektol fugg, es az elso sor es oszlop, illetve az atlo tartalma trivialis, a tablazat kitoltheto iterativan (rekurzio nelkul).

Meg egy apro eszrevetel (ertsd: kakan is csomot kereses :D) a ciklusokban i-nek nem kell k-1-ig (l-1-ig) mennie, csak a "feleig" (C szintaxissal k/2 vagy k>>1).

Lásd #473 :-) És még az se optimális...

Amúgy 99-et én is tudtam fejből :-)

Még valami. Mivel úgy adtad fel, hogy "készítsen programot", ezért feltételezem, hogy ez nem matematikai hanem számtech feladat. Ezért aztán jó lenne, ha megmondanád a limiteket a bemenet adataira, mert némelyik Nemes példát azzal tesznek könnyűvé (de becsapóssá), hogy megszorítják a bemenetet.

99-re tippelek programozás nélkül. Az nagyon rossz?

Igen, ez a fogós feladat még nagyon sok évvel ezelőtt Nemes Tihamér feladat volt. Én akkor, azt hiszem, kilencedikes voltam, de szerintem még tizenkettedikes koromban sem tudtam volna megoldani.

(P.S. Van ennek köze a geometriához?)

Nekem a következő problémám van:

Építőkockákból úgy lehet stabil tornyot építeni, hogy kisebb kockára nem lehet nagyobbat, illetve könnyebb kockára nem lehet nehezebbet tenni. Kezdetben a kockák egy sorban lerakva vannak az asztalon. A soron következő kockát csak egy megépített torony tetejére rakhatjuk, ha kihagyjuk, akkor azt a kockát később sem használhatjuk fel. Készítsen programot, amely adott n kocka alapján megadja a belőlük építhető legmagasabb tornyot! Bemenetként megkapjuk a kockák darabszámát, illetve azt, hogy melyik milyen széles illetve milyen súlyú, és nincs két kocka amelynek a mérete és a súlya is megegyezne.

Hűűűűű Köszönöm szépen :)

A tömb azért kell, hogy ha egyszer egy részeredmény már megvan, akkor azt ne számolja ki a progi újra és újra, mert egyrészt nagy számokra lassú lesz, másrészt ilyenkor a rekurzív hívások miatt egy veremben tárolja, hogy éppen milyen mélységben hívódott meg a rutin, és ilyenkor veremtúlcsordulás esetén a progi szépen fejreáll.

Kicsit kicsinosítottam a progit, a teljes forráskód letölthető innen.

már látom miért van ez a mindarabszámos értékadás, mert ugye itt tároljuk a legkisebb j-t.... Ok. A dinamikussá átalakítást még mindig nem vágom. Annak a segítségével meg lehetne adni szebben a mindarabszam értékét?

És még egy a programmal kapcsolatabn. Az is jó, ha a mindarabszám nevű változó kezdőértéke nulla, és nem vizsgáljuk h j kisebb-e nála, csak simán eltároljuk benne az értéket? Miért van szükség erre a vizsgálatra???????????

Köszönöm a gyors választ Sirpinek. Ki is próbáltam. Nagyon tuti :-)...

Az érdekelne még h pontosan h kell átalakítani dinamikus programmá... Hová építsem be pontosan azt a kétdimenziós tömböt????

Jelenleg 14-nél tartok.

Hm, kipróbáltam még pár értéket, próbáljátok megtippelni (programozni nem ér :-P), hogy egy 98x99-es téglalap legkevesebb hány négyzetre vágható fel.