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: Algoritmusok

  [1]    [2]    [3]    [4]  

Szeretnél hozzászólni? Jelentkezz be.
[75] 25012006-06-15 14:01:23

Igen, de tegnap este már csak olyat volt időm csinálni, amelyik mindig végignézi a teljes kört. Ez azzal a megkötéssel, hogy a nullvektorok rendezéskor előre kerülnek, működni látszik. A [66]-ban általam felvetett kilépési feltétel viszont úgy néz ki, hogy nem működik.

Előzmény: [74] Hajba Károly, 2006-06-15 12:18:13
[74] Hajba Károly2006-06-15 12:18:13

A [70]-es hsz-t néztétek?

[73] lorantfy2006-06-15 12:14:13

Igazad van!

Előzmény: [72] 2501, 2006-06-15 00:25:08
[72] 25012006-06-15 00:25:08

Nem működik jól, hogyha az összes vektor összege 0, mivel utána bármelyik kivonásával növekedni fog a hossz, tehát sosem találunk "jó" vektort.

Előzmény: [71] lorantfy, 2006-06-15 00:18:27
[71] lorantfy2006-06-15 00:18:27

Tfh. hogy az n db vektor között van k db melyek összege a max. hosszúságú vektor adja. A vektorösszeadás eredménye nem függ a sorrendtől. Tegyük fel, hogy összeadtuk ezt a k db vektort és megvan a max. hosszúságú vektor. A többi vektort egyenként hozzáadva ehhez a max. vektorhoz ezek csak csökkenthetik az összeg hosszát, különben nem ez lenne a maxvektor. Tehát egyenként kivonva öket, az összeg hosszának növekednie kell.

Adjuk össze az összes vektort és számoljuk ki az összeg hosszát. Ebben az összegben benne van a k db "jó" vektor, csak meg kell találni melyek ezek.

Sorbamegyünk az n db vektoron és mindegyikkel a következőket végezzük:

Kivonjuk az eredeti összegvektorból és kiszámoljuk az eredményvektor hosszát, ha csökkent a hosszúság akkor ez egy "jó" vektor volt és ezt hozzáadjuk az ujösszeg-hez ( amit legelőször lenulláztunk).

Kiszámoljuk az ujösszeg vektor hosszát, ezt kérdezték. Bingó!

Szóljatok ha nem jó!

Előzmény: [65] egykerdes, 2006-06-14 14:42:03
[70] Hajba Károly2006-06-14 23:05:16

Minden vektort indítsunk az origóból. Így irányultságuk szerint körkörösen sorbarendeztük őket. Minden vektorra végezzük el a következő műveletsort:

Az éppen aktuálisan első vektor helyben marad, majd a következőt jobbra (vagy balra, de mindig azonosan) a csúcspontjába toljuk, majd a következőt ennek az eltolt csúcspontjába és így tovább egészen 180 fokig. Megkeressünk az origótól legtávolabbi pontott. Adott egy jelölt.

Így minden vektorra kapunk egy jelöltet, s a leghosszabb jelölt a megoldás.

Ha nem tévedek. :o)

S talán lehet még rajta csiszolni is.

Előzmény: [65] egykerdes, 2006-06-14 14:42:03
[69] 25012006-06-14 17:09:02

Igazad van, ez cáfolja a [67]-ben írtakat, úgyhogy már csak a [66]-ban írt lehet jó, ha az sem, akkor más után kell néznem. :)

Előzmény: [68] egykerdes, 2006-06-14 16:27:26
[68] egykerdes2006-06-14 16:27:26

Derékszögnél kitérhet jobban pl (10,0) vektorhoz, érdemes hozzávenni a (-1,10) et.

Bar a tag es az összeg különbsége részt nem nagyon értem.

[67] 25012006-06-14 15:54:39

Nem jól írtam. Helyesen: azzal a tulajdonsággal, hogy egyik tagja sem tér ki az összeg és a tag különbségétől derékszögnél jobban.

Előzmény: [66] 2501, 2006-06-14 15:41:13
[66] 25012006-06-14 15:41:13

Az a sejtésem (így első ránézésre), hogy a leghosszabb összegnek rendelkeznie kell azzal a tulajdonsággal, hogy egyik tagja sem tér ki tőle derékszögnél jobban (egyikkel vett skaláris szorzata sem negatív), különben tagok elhagyásával konstruálható nála hosszabb, de még nem tudom bizonyítani. :)

Ha ez így van, akkor ennek használatával (és a vektorok irány szerinti rendezésével) lineáris futásidejű, mohó algoritmus adható. Bár ez megint csak "megérzés". :)

Előzmény: [65] egykerdes, 2006-06-14 14:42:03
[65] egykerdes2006-06-14 14:42:03

Sziasztok, szoktam olvasgatni a fórumotokat, most azonban egy feladatot szeretnék feladni, amivel a google coding versenyen talalkoztam. Akit esetleg érdekel : http://www.topcoder.com/pl/ itt pedig a Google Code Jam Europe

A feladat:

Adott n db (a feladat szerint max 50) síkvektor, ezek közül a valogassuk ki azokat amelyeknek az összegvektora a lehető leghosszabb vektort adja. (a versenyen ezt a hosszat kérték)

Kíváncsi lennék hogy van e rá gyorsabb algoritmus mint az hogy, az összeset lehetséges kombinációt megnézem.

[64] 25012006-05-22 16:44:46

A problema altalanositasa egyebkent a memorizalasos rekurzio illetve a dinamikus programozas iskolapeldaja.

Előzmény: [61] V Laci, 2006-05-21 19:23:28
[63] V Laci2006-05-22 16:05:18

Köszi, valóban 292 a lehetőségek száma!

[62] jonas2006-05-21 23:32:51

Ezt nyilván úgy kell érteni, hogy 1 dollárt akarsz előállítani 1, 5, 10, 25, 50 centesekkel.

Nos, erre egy rekurziót kell felírni, ami valahogy így néz ki:

an=an-50+bn ha 0\len

bn=bn-25+cn ha 0\len

cn=cn-10+dn ha 0\len

dn=dn-5+en ha 0\len

en=en-1+fn ha 0\len

fn=0 ha 0<n

f0=1

an=bn=cn=dn=en=fn=0 ha n<0

majd a100 értékét keresni.

Ez az an sorozat A001300 névre hallgat, és a leírása meg is adja a két definitív referenciát arról, hogyan kell explicit alakra hozni az ilyen függvényeket: a Konkrét matematikát, és a Pólya--Szegő első kötetét -- mindkettő magyarul is elérhető.

Másrészt ha csak a100-at akarod kiértékelni, akkor nincs szükség az explicit képletre, egyszerűbb a rekurziót kiszámolni addig. Az eredmény 292, ha nem számoltam el.

Előzmény: [61] V Laci, 2006-05-21 19:23:28
[61] V Laci2006-05-21 19:23:28

Sziasztok!

Nemrég újból összefutottam az alábbi problémával: Hányféleképpen lehet kirakni 100 Ft-ot elegendő mennyiségű 1,5,10,25,50 Ft-os pénzérmékkel? Erre szeretnék egy programot készíteni, amely elegendő mennyiségű a1, a2, a3 ... an különböző értékű pénzérmékkel kirakja az X forintot, és megszámolja, hogy ezt hányféleképpen tette meg. Milyen algoritmussal oldanátok meg?

Köszi szépen a segítséget!

[60] Sheriwoyama2006-05-17 09:21:24

A sors fintora, hogy Katona Gyula is foglalkozott a körmérkőzések szervezésével a Mindentudás Egyetemén tartott előadásában - ami nem teljesen véletlen, hiszen ő is tagja volt a BEAC sakkszakosztályának.

Előzmény: [59] Sheriwoyama, 2006-05-16 16:16:31
[59] Sheriwoyama2006-05-16 16:16:31

A körmérkőzések szervezését Pascal már megoldotta - valamikor az ókorban a KÖMAL feladatként ki is tűzte - s véletlenül meg is oldottam.

Előbb a pontos képleteket írom le, aztán a szemléletes leírás következik.

Legyenek 1-től (2n-1)-ig számozva az indulók (bár a 0-tól kezdődő számozásnak némi előnye volna).

i és j játszik egymás ellen az f-edik fordulóban, ha i+j==f+1 mod (2n-1) i+j==f, ha mindent 0-tól számozunk /bocs, de a kongruenciát most == jelöli, TEX-ben nem vagyok járatos/

Akinek nem jut pár, az szabad, de minden fordulóban pontosan egy ilyen van - és az pont az, akire i=j adódna - magával mégsem játszik az ember :-).

Ha i-j páratlan, akkor a kisebbik, egyébként a nagyobbik a pályaválasztó /vagy sakkberkekben: világos/

2n induló esetén természetesen a fentiekben facér versenyző a párja a (2n) sorszámúnak, aki a mezőny első feléhez utazik, a második fele hozzá megy.

Ellentétes a sorsolása azon pároknak, amelyek különbsége pontosan n (!), tehát k<=n esetén a speciális kívánságok teljesíthetők. /Meg kell jegyeznem, hogy sakkcsapat intézőjeként számtalanszor voltam tanúja, amint a sorsoláskor az efféle igényeket, no meg kacifántosabbakat is, ügyesen kielégítették./

Üdv a friss fórumozótól Sheriwoyama

[58] denebleo2006-05-16 11:04:46

Szia!

Jól működik az algoritmus, köszi szépen! Lenne még két kérdésem: Az adott n csapatból 2k (2k<n) csapat k db városból nevezett, mindegyik városból 2-2 csapat. Szeretnénk olyan sorsolást készíteni, hogy az azonos városból érkező 2 csapat ellentétes sorsolást kapjon (ha az egyik otthon játszik, akkor a másik idegenben és fordítva). Mit kell ekkor módosítani az algoritmuson?

Tudsz olyan linkeket ahol lehet a bajnokság sorsolás matematikai hátteréről olvasni?

Előzmény: [56] Sirpi, 2006-05-10 15:05:29
[57] Sirpi2006-05-10 16:56:10

Na, itt egy ábra 8 csapat esetén az első 2 fordulóhoz.

Előzmény: [56] Sirpi, 2006-05-10 15:05:29
[56] Sirpi2006-05-10 15:05:29

Két részre bontanám a dolgot:

1) tournament szervezése teljes fordulókkal

2) oly módon, hogy ne játsszon senki 3x egymás után otthon, vagy egymás után idegenben

És mielőtt továbbmennék, megjegyezném, hogy elég az "őszi" fordulót megkonstruálni, mert a "tavaszi" (vagyis amikor másodszor játszik mindenki az adott ellenfelével) megkapható úgy, hogy a fordulókat átörökítjük az ősziből, csak éppen az ellentétes pályán.

Akkor nézzük a megvalósítást:

Tegyük fel, hogy páros sok csapat van, mondjuk 2k. Helyezzük el az elsőt egy szabályos 2k-1 szög középpontjában, a sokszög csúcsai alkotják a többi csapatot. A sokszög álljon "álló helyzetben", azaz úgy, hogy az egyik csúcsa éppen a középpont felett helyezkedjen el. Az első fordulót pedig bonyolítsuk ezután úgy, hogy a legfelső csapat játsszon a középsővel, a többi pedig azzal a másik csapattal, aki ugyanolyan magasságban helyezkedik el, mint ő (azaz az őket összekötő szakasz vízszintes). Ekkor mindenkinek pontosan egy párja adódik. Kössük is össze a párokat. A többi fordulót pedig úgy kapjuk, hogy a behúzott átlórendszert elforgatjuk óramutató járás szerint 360o/(2k-1) szöggel, vagyis minden csúcs átmegy a következőbe. Hasonlóan kapjuk a 3.-at a 2.-ból stb. Erről könnyű látni, hogy valóban tournamentet generál, azaz minden átló pontosan egyszer lesz lefedve.

Ha páratlan sok (2k-1) csapat van, akkor egészítsük ki a mezőnyt egy virtuálissal (ő legyen középen), és ismételjük meg az előző konstrukciót a 2k csapatra. Aki épp a középsővel játszana, az abban a fordulóban pihen. Muszáj is, hogy legyen minden fordulóban pihenő csapat, mert meccsenként 2 csapat van, azaz egynek legalább mindig ki kell maradnia fordulónként, épp azért, mert páratlan sokan vannak.

* * *

2) Ahhoz, hogy megmondjuk, ki játszik otthon és ki idegenben, irányítsuk a behúzott éleket: a nyíl mutasson mindig a hazai csapat felé. Tegyük ezt úgy, hogy a vízszintes éleket lefelé haladva váltott irányítással húzzuk be (kezdve bal -> jobb, jobb -> bal, bal -> jobb...), és ezen a köv. fordulókban se változtassunk. A (kezdetben) függőleges él viszont kezdetben mutasson pl. a középpontba, és minden fordulóban váltsa az irányát (befelé->kifelé->befelé...).

Ekkor a középső csapat mindig váltott helyszínen fog játszani, és a többiek is max egyszer kényszerülnek arra, hogy 2x játszanak ugyanolyan körülmények között két egymás utáni meccsen.

Ennél jobbat szerintem nem igazán lehet csinálni, remélem, megfelel, amit leírtam. Ha kérdés van, szívesen fogadom.

Előzmény: [55] denebleo, 2006-05-10 12:52:37
[55] denebleo2006-05-10 12:52:37

Adott n db csapat, akik egy bajnokságban szerepelnek. Szeretnénk elkészíteni a bajnokság sorsolását. Mindenki játszik mindenkivel 2-szer, egyszer otthon egyszer idegenben pl. A-B meccsen az A játszik otthon B-A meccsen a B játszik otthon. Azt is szeretnénk, hogy a csapatok felvátva játszanak otthon és idegenben, max 2 otthoni vagy idegenbeli meccs egymás után engedélyezett. Minden fordulóban játszik minden csapat. Milyen algoritmussal lehetne elkészíteni a fentieknek megfelelő sorsolást?

[54] lgdt2005-10-04 01:35:27

minden nemvesztő megoldás egyforma jó.

Előzmény: [51] lgdt, 2005-08-09 18:21:29
[53] 25012005-08-10 10:24:33

Valamelyik - talán Borland? - Pascal referenciában azt olvastam, hogy a writeln automatikusan kényszeríti a buffer ürítését, a beállított módtól függetlenül.

U.I.: Most csak potyanetezem, egyébként két hétig nem vagyok gépközelben.

[52] lgdt2005-08-09 19:51:30

pascal példa

[51] lgdt2005-08-09 18:21:29

nemvesztő megoldást viszonylag könnyű generálni, ha az egyenlőtlenségből egyenletet csinálsz a képletben.

most vettem a 256mb RAMom mellé még 256-ot, így befér a memóriába az összes együttható, gyorsan megoldathatom a géppel az egyenletrendszert. lehet, hogy még 1 picit félreteszem a lustaságomat, és csinálok egy nemvesztő megoldást.

de a nemvesztő megoldás nem elég! még sajnos nem sikerült rájönnöm, hogy van-e legjobb (amivel a legtöbb nem nemvesztőt meg lehet verni). elméletileg azt is elképzelhetőnek tartom, hogy van. az a baj, hogy a lehetséges eloszlások száma (megszámlálhatóan) végtelen. majd még gondolkozom 1 kicsit rajta.

(én is szoktam pascalban is kódolni. talán megnézem, a példaprogival mit tudok kezdeni, de gyanítom, hogy a (free)pascal bufferkezelése automatikusan megfelelő, nem kell állítgatni semmit.)

PS: ha valaki ért a perl-hez, a java-hoz, a ruby-hoz, meg az egyéb ilyen gusztustalanságokhoz, csinálhatna hozzájuk példaprogit, hogy teljes legyen a csomag. :)

Előzmény: [50] zeus, 2005-08-08 23:08:39

  [1]    [2]    [3]    [4]