Fórum: GEOMETRIA

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.

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.

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.

A keresett szög 30 fok, egyébként lásd az "érdekes matek feladatok" téma 80., 66. és előzményei hozzászólásokat.

Bár néha elmarad a feladatszámozás, vegyük úgy hogy a tied volt a 78-as, én most feladom a 79. feladatot, hátha valaki nem ismeri. Adott az ABC , C-nél 20^o -os csúcsszögű egyenlőszárú háromszög. Legyen D a BC szárnak az a pontja, melyre BAD = 50^o , E az AC szárnak az a pontja, melyre EBA = 60^o . Mekkora szöget zár be az ED egyenes az AB egyenessel?

Mivel a feladat a 70-es 80-as években egy KöMaL cikkben példaként szerepelt - ott a megoldás kulcsa az volt, hogy az ábrát a szabályos 18-szög és összes átlói által kifeszített hálózat részeként tekintjük - most legyen az a cél, hogy minél kevesebb új pont felvételével adjunk elemi geometriai megoldást.

Egy újabb remek feladat: adott egy kör alapú henger alakú tortánk, és ezt kellene 12 vágással 80 szeletre (részre) vágni. Semelyik 3 vágás nem mehet át egy ponton, viszont bármelyik kettőnek van közös metszéspontja.

Nálam cd a kör átmérője volt, nálad gondolom a sugara, mert úgy kijön amit írsz. Köszönöm, tetszik!

Bocs, a 77. feladatot tényleg nem intézi el. Nos, c=1 triviálisan jó.

Az éles határ c-re . Ennek a bizonyítása a Reiman: Geometria és határterületei könyv 15.3. (Helly tételes) fejezetében van benne. A bizonyítás a következőn múlik. Először belátod, hogy a korlát jó háromszögekre (szabályos háromszögre pont az arány), aztán veszed a ponthalmaz minden három pontjára azon pontok halmazát, amelyektől mindhárom pont legfeljebb távolságra van, majd erre a halmazrendszerre alkalmazod a Helly-tételt.

Köszi! Ez 76.-ot tényleg elintézi, de 77.-et szerintem nem.

76., 77. feladatokra. Ha a töröttvonal egy nagyon lapos egyenlőszárú tompaszögű háromszög, akkor a kört csak egyféleképpen lehet kiválasztani, és a háromszög kerületéhez képest ez akármilyen nagy lehet. Tehár nem igaz az állítás.