Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: GEOMETRIA

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]  

Szeretnél hozzászólni? Jelentkezz be.
[494] jonas2006-10-03 19:06:19

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

Előzmény: [493] jonas, 2006-10-03 19:02:00
[493] jonas2006-10-03 19:02:00

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.

[492] jonas2006-10-03 18:36:03

Akkor itt van: vag.bmp.

Előzmény: [491] jonas, 2006-10-03 18:34:35
[491] jonas2006-10-03 18:34:35

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

Akkor feltöltöm valahova.

Előzmény: [490] jonas, 2006-10-03 18:33:40
[490] jonas2006-10-03 18:33:40

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.)

Előzmény: [487] jonas, 2006-10-03 13:41:47
[489] Hajba Károly2006-10-03 14:33:08

Mivel nem tudok programot írni, felszerkesztettem:

Előzmény: [487] jonas, 2006-10-03 13:41:47
[488] Sirpi2006-10-03 13:43:08

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.

Előzmény: [486] Porter, 2006-10-03 13:33:54
[487] jonas2006-10-03 13:41:47

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.

Előzmény: [483] Sirpi, 2006-10-03 12:28:19
[486] Porter2006-10-03 13:33:54

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.

[485] Sirpi2006-10-03 12:56:30

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 ;-)

Előzmény: [484] 2501, 2006-10-03 12:49:31
[484] 25012006-10-03 12:49:31

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).

Előzmény: [471] Sirpi, 2006-10-02 21:53:21
[483] Sirpi2006-10-03 12:28:19

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

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

Előzmény: [481] jonas, 2006-10-03 11:47:50
[482] jonas2006-10-03 11:52:16

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.

Előzmény: [479] Sanyi, 2006-10-03 11:09:11
[481] jonas2006-10-03 11:47:50

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

Előzmény: [472] Sirpi, 2006-10-02 22:11:06
[480] jonas2006-10-03 11:46:37

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?)

Előzmény: [479] Sanyi, 2006-10-03 11:09:11
[479] Sanyi2006-10-03 11:09:11

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.

[478] Porter2006-10-03 11:05:49

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

[477] Sirpi2006-10-03 09:40:05

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.

Előzmény: [476] Porter, 2006-10-03 09:25:12
[476] Porter2006-10-03 09:25:12

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?

[475] Porter2006-10-03 09:01:13

É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???????????

[474] Porter2006-10-03 08:26:55

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????

[473] Hajba Károly2006-10-02 23:05:37

Jelenleg 14-nél tartok.

Előzmény: [472] Sirpi, 2006-10-02 22:11:06
[472] Sirpi2006-10-02 22:11:06

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.

Előzmény: [471] Sirpi, 2006-10-02 21:53:21
[471] Sirpi2006-10-02 21:53:21

Ez egy sima kétdimenziós dinamikus programozási feladat. C-ben valahogy így néz ki (bocs a tördelésért, de nem nagyon lehet kódot írni ide...):

// ---------------------------------------------

int negyzetekrebont (int k, int l) {

if (k == 1 || l == 1) return (k+l-1);

if (k == l) return 1;

int mindarabszam = 1000000, i, j;

for (i = 1; i < k; i++) { j = negyzetekrebont (i, l) + negyzetekrebont (k-i,l);

if (j < mindarabszam) mindarabszam = j; }

for (i = 1; i < l; i++) { j = negyzetekrebont (k, i) + negyzetekrebont (k,l-i);

if (j < mindarabszam) mindarabszam = j; }

return mindarabszam; }

// ---------------------------------------------

Itt ugye a függvény rekurzívan meghívja önmegát, minden vágást végigpróbálva, egészen addig, amíg 1 szélességű csíkok nem keletkeznek. Nagyobb számoknál a verem hamar betelhet, ezért érdemes egy 2-dimenziós tömböt is csinálni, melyet kezdetben feltöltünk -1 értékekkel, meg ha k=1 vagy l=1, akkor a triviális minimumokkal, és ha valamilyen k,l-re már tudjuk az optimumot, akkor azt nem számoljuk ki rekurzívan újra, hanem beírjuk a tömb megfelelő helyére, és legközelebb csak ki kell onnan olvasni.

Meg is írtam, és próbaképp azt kaptam, hogy 19,23-as téglalapot 9 négyzetre fel lehet vágni.

Előzmény: [470] Porter, 2006-10-02 18:01:28
[470] Porter2006-10-02 18:01:28

Ebben a problémában várok segítségeket:

Adott egy téglalap alakú fémlap, amit a lehető legkevesebb négyzetre kell darabolni. A darabolásra olyan vágógépet használhatunk, amely csak ketté tudja vágni a lapot valamelyik oldalával párhuzamosan. A keletkezett darabokat külön-külön darabolhatjuk tovább. A téglalap oldalainak hossza egész szám centiméter mértékegységben mérve, és a darabolás eredményeként is olyan négyzeteket kell kapni, amelyek oldalhosszai egész számok. Egy darabolás akkor optimális, ha a lehető legkevesebb négyzet keletkezik.

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]    [15]    [16]    [17]    [18]    [19]    [20]    [21]    [22]    [23]    [24]    [25]    [26]    [27]    [28]    [29]    [30]    [31]    [32]    [33]    [34]    [35]    [36]    [37]    [38]    [39]    [40]    [41]    [42]    [43]    [44]    [45]    [46]    [47]    [48]    [49]    [50]    [51]    [52]    [53]    [54]    [55]    [56]    [57]    [58]    [59]    [60]    [61]    [62]    [63]    [64]    [65]    [66]    [67]    [68]    [69]    [70]    [71]    [72]    [73]    [74]    [75]    [76]    [77]    [78]