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

[469] jenei.attila2006-09-07 19:13:30

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.

Előzmény: [468] HoA, 2006-09-05 11:44:38
[468] HoA2006-09-05 11:44:38

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 20o -os csúcsszögű egyenlőszárú háromszög. Legyen D a BC szárnak az a pontja, melyre BAD \angle = 50o , E az AC szárnak az a pontja, melyre EBA \angle = 60o . 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.

Előzmény: [467] rizsesz, 2006-09-05 09:41:19
[467] rizsesz2006-09-05 09:41:19

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.

[466] Csimby2006-08-29 20:12:49

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!

Előzmény: [465] jonas, 2006-08-29 00:40:45
[465] jonas2006-08-29 00:40:45

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

Az éles határ c-re  1/\sqrt 3 . 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  1/\sqrt 3 az arány), aztán veszed a ponthalmaz minden három pontjára azon pontok halmazát, amelyektől mindhárom pont legfeljebb  d/\sqrt 3 távolságra van, majd erre a halmazrendszerre alkalmazod a Helly-tételt.

Előzmény: [462] Csimby, 2006-08-28 14:46:02
[464] Csimby2006-08-28 22:31:19

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

Előzmény: [463] jonas, 2006-08-28 19:01:13
[463] jonas2006-08-28 19:01:13

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.

Előzmény: [462] Csimby, 2006-08-28 14:46:02

  [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]