a Pi ilyen pontos szamitasa erdekes, de azt hiszem elegge komplikalt. Eloszor is keves olyan programnyelv van amely tamogatja az 'indefinit precision', azaz tetszoleges pontossagu aritmetikat (pl Lisp).
Én mondjuk C-re, vagy Pascalra gondoltam, de jó lesz valami hasonló nyelv is, ami nem támogatja a tetszőleges pontosságot.
Majd keresni kell egy olyan sort amelyik minnel gyorsabban konvergal - itt a matikusok segithetnek -,
A sebesség nem annyira fontos, a lényeg, hogy 30000 számjegyig számoljon. Jó lesz a
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 ...
is. (Bár persze nem baj, ha gyorsabb, egyszerűbb a progi. Én láttam olyat, ami egy P100-as procin 2 másodperc alatt kiszámolta 32E számjegyig. És az első 500 számjegy tutira jó volt.)
azutan meg ott van a kerekitesi hibak nemtrivialis problemaja
Ha 60000 számjegyet kezelő programod van, akkor szerintem 30000. számjegynél még pontos kell legyen. :-)
Pille: Grat ! igen errol van szo - azt hiszem psymind is valami ilyesmire gondolt.
psymind: pascalba elg korulmenyesesn lehetne atirni, azt hiszem inkabb mas megkozelitessel ujrairni lenne 1xubb. a pythont sajnos nem ismerem, esetleg valaki aki a prologot es a pytont is ismeri ? hm ?
egyebkent a prolog imho egy nagyxu nyelv, talan erdemes lenne kicsit megnezegetni :)
SusuASarkany: a Pi ilyen pontos szamitasa erdekes, de azt hiszem elegge komplikalt. Eloszor is keves olyan programnyelv van amely tamogatja az 'indefinit precision', azaz tetszoleges pontossagu aritmetikat (pl Lisp). Majd keresni kell egy olyan sort amelyik minnel gyorsabban konvergal - itt a matikusok segithetnek -, azutan meg ott van a kerekitesi hibak nemtrivialis problemaja ...
[megoldas 5]
A metszespontokhoz hozzarendelem az A,B,..,L valtozokat, a haromszog csucsaihoz az X,Y es Z-t.
Nekem ez eppen igy jott ki(jol jonne egy abra..):
KOR1: A+L+D+E+I+C = S (a korok ill haromszog menten levo osszeg)
KOR2: A+G+B+E+J+F = S
KOR3: C+H+B+D+K+F = S
HSZG: G+H+I+J+K+L+X+Y+Z= S
Eloszor a KOR1 valtozoinak adok erteket az {1..15} halmazbol, majd a KOR2 es KOR3, meg erteket nem kapott valtozoinak, a meg fel nem hasznalt szamokbol. Vegul ellenorzom az osszeget a haromszogon.
Ez egy osregi Borland Turbo Prologban igy nez ki (prologosok elonyben :)
(itt a sel(T,A,B,S) predikatum akkor igaz ha A es B a T lista particioja es S a B lista elemeinek osszege).
sel([], [], [], 0).
sel([E|T], [E|A], B, S) :- sel(T, A, B, S).
sel([E|T], A, [E|B], S) :- sel(T, A, B, P), S= E+P.
solve([A,B,C,D,E,F,G,H,I,J,K,L], SUM) :-
T1=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
sel(T1, T2, [A,L,D,E,I,C], SUM), /* T1 szetbomlik T2re es a KOR1 valtozoira */
S1= SUM-(A+E), /* S1 lesz a KOR2 osszege A es E nelkul */
sel(T2, T3, [G,B,J,F], S1), /* T2 szetbomlik T3 ra es aKOR2 valtozoira */
S2= SUM-(C+B+D+F), /* S2 a KOR3 menten fennmarado osszeg */
sel(T3, [X,Y,Z], [H,K], S2), /* T3 bomik a HSZG es a KOR3 valtozoira */
SUM = X+Y+Z+G+H+I+J+K+L. /* ellenorizzuk a HSZG menten az osszeget */
A solve-ot lefuttatva kiderult, hogy a feladat kisse aluldefinialt, ugyanis osszvissz 57 megoldas van.
Harom S ertekre: 56, 57 es 58- ra is van megoldas.
Az egyik pl(S = 57 re): [A,B,C,D,E,F,G,H,I,J,K,L] = [3,9,15,10,12,14,8,2,13,11,7,4]
A fennmarado szamokbol [X,Y,Z] = [1,5,6].
A prologhoz nem ertoktol elnezest; ha erdekel, szivesen elmagyarazom reszletesebben is, hogy mi tortenik a programban.
A fibonacci számhoz még egy tipp:
Hogy számolja ki a 9 éves Pistike táblán 50 fibonacci számát? Elkezdi ugye írogatni. Közben megy utánna Józsika és törli a táblát mögötte fél méterrel. A megoldás mégis megszületik (viszonylag) gyorsan.
[Feladat 6] - Pi számoló algoritmus.
Számoljuk ki a pi-t (3.1415...) mondjuk 30000!!!számjegy pontossággal. :-)
pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + 1/13...
(Bocs, ha matematikailag nem korrekt, de így érthető a középiskolásoknak is.)
A következő egy picit bonyolultabb és nyugodtan le lehet lőni... mert a
megoldásra én is csak "kézzel" jöttem rá és nagyon kíváncsi vagyok, hogy
létezik-e ( valószínűleg létezik ) elegáns algoritmikus megoldása is?
A feladat a következő:
az itt látott ábrán a vonalak metszéspontjaihoz kell számokat írni úgy, hogy
egy-egy körön végighaladva és összeadva az azon lévő számokat, minden körön
ugyanannyit kapjunk. A számok egymást követő egész számok.
( Lényegsen könnyebb lenne, ha mindenhová nullákat lehetne írni... de nem! :-)
Én inkább programozási, mint matematikai megoldásra gondoltam... valami olyasmire,
hogy a már kiszámolt értékeket tárolni kellene, így a nagy számoknál nem
futna végig mindig ugyanaz a "piramis". A matekos megoldása nyilvánvalóan szebb,
de ez gyakrabban előfordulhat olyan feladatoknál is, ahol a matekos változat
nehezen lenne megtalálható.
A fibonacci sorozat es az aranymetszes kozotti kapcsolat nagyon erdekes, de azt hiszem psymind nem arra szamitott, hogy valaki itt szorakozasbol levezeti a Binet formulat :)
A fib definicioja alapjan kezenfekvo a kov. algoritmus:
fib(n): ha n < 2 akkor 1 egyebkent fib(n-1) + fib(n-2). // mindenki irja at kedvenc nyelvere
Ez igy nagyon elegans, de fib(n) kiszamitasahoz eppen fib(n) lepesre van szukseg, emiatt nagy n ertekekre nem praktikus. Van azonban egy egyszeru algoritmus, amely fib(n) erteket n lepesbol szamolja ki. Nem olyan gyors mint egy kepletszamitas, de az elozo algoritmushoz kepest "azonnali" eredmenyt ad. psymind keresere nem lovom le a poent, aki meg nem talalkozott a feladattal annak jo fejtorest. A profiknak meg figyelmukbe ajanlom az elozo feladatokat, ill. irhatnak ujakat.
ap.
A feladat a fibonacci számsorra épül, ennek lényege:
-- veszünk egy nemnegatív egész számot, ezt jelöljük n-nel
-- ha a szám 0 vagy 1, akkor a fibonacci értéke 1
tehát HA n=0 AKKOR fibonacci(n)=1
HA n=1 AKKOR fibonacci(n)=1
-- ha a szám nem 0 vagy 1, akkor az előtte lévő két szám fibonacci
értékének összege adja az adott szám fibonacci értékét
tehát HA n>1 AKKOR fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)
Ha a program egy sima rekurzív algoritmust használ, akkor a 0 és
15 közé eső számokhoz tartozó fibonacci értékeket még "elfogadható"
idő alatt kiszámolja a gép. Ha viszont ennél nagyobb számokkal
szeretnénk dolgozni, a program jelentősen lelassul.
A feladat olyan program írása, amely bármilyen nagy számra
"azonnali" eredményt produkál!
( Ha valaki ismeri a megoldást, akkor nem kell egyből lelőni... :-)
aztán meg csak azt vesszük majd észre, hogy már csak a kopi-pászthoz, meg a pasziánhoz értünk :o) :)))
Sajnos a programozás muvészetbol egyre inkább szalagmunkává válik. Megértem a legtöbb topicban uralkodó hangulatot: 'ebbe-és-ebbe a dologba ütköztem, gyorsan segítsetek'. Nincs már ido felfedezésre.
ebbe a topicba vajon azért nem irtok mert nincs idotök, vagy mert nem tudtok programozni ? ;))
Az általad feldobott példák egy kicsit mind olyan jelszó feltörősdik. Gondolom, nem csak ilyenekre gondoltál ? Bocs, hülye kérdés volt (lásd az 1. feladatot).
Írjunk programot, amely a mastermind játékban kitalálja az elrejtett sorozatot
Az általad feldobott példák egy kicsit mind olyan jelszó feltörősdik. Gondolom, nem csak ilyenekre gondoltál ?
Egyébként nagyon jó ötletnek tartom ezt a topikot. Manapság egyre többen tanulnak programozni, viszont ahogy a többi programozással kapcsolatos topik "laikus" kérdéseit olvasgatom, egyre inkább hiányoltam valami ilyesmit, ahol az algoritmusok és adatstruktúrák kerülnek előtérbe. A rengeteg kész komponens/kódrészlet használata során egyre jobban elkényelmesedünk, aztán meg csak azt vesszük majd észre, hogy már csak a kopi-pászthoz, meg a pasziánhoz értünk :o)
Írhattok feladatokat is. Arra kérlek, kezdjétek az alábbiakhoz hasonlóan, hogy könnyebben lehessen keresni.
Olyan feladatokat írjatok, hogy ha az ötlet már megvan, max. 1 óra alatt be lehessen kódolni.
A megoldásnál az adatstruktúrákat és a rajtuk dolgozó algoritmust írjátok le, röviden. Ne másoljatok ide több oldalnyi forráskódot. Ha valakit majd érdekel, elküldhetitek levélben.
Hogy nagyobb legyen a választék, ime még néhány feladat :
[feladat 2] - kriptaritmusok
Helyettesítsük a betüket számjegyekkel úgy, hogy az alábbi egyenloségek teljesüljenek :
SEND + ME + MORE = MONEY
AKI + SOK + SORT + ISZIK = RÉSZEG
(Az ékezetek nem számítanak, E = É, O = O )
A fentihez hasonló feledatokat brute force módszerrel is meg lehet oldani. Legfeljebb 10 faktoriális módon lehet a betükhöz rendelni a számjegyeket, ezt hamar ledarálja egy mai gép. Van-e más, elegánsabb megoldás ?
- mastermind
Írjunk programot, amely a mastermind játékban kitalálja az elrejtett sorozatot.
5L-esből a 3L-est tele.
3L-esből a 2L-est tele (3l-esben 1L maradt)
2L-est vissza az 5L-esbe (2L-es üres lett)
3L-asből az 1L át a 2L-esbe.
(man-machine)ready
[feladat 1] Adott 3 kancsó: egy 5 literes, egy 3 és egy 2 literes. Az 5 literes kancsó tele van finom ion-borral. Töltögetésekkel érjük el, hogy a 2 literes kancsóba pontosan 1 liter bor kerüljön.
Írjunk programot a fentihez hasonló feladatok megoldásásra.
