amúgy ért valaki a C++-hoz?

újra előszedtem, és kicsit elszoktam tőle... :p (mostanában leginkább Javában írogattam) Meggyűlt a bajom a változó kiíratásokkal... ha jól emlékszem volt valami olyasmi, hogy valami("A kenyér ára: %dFt", kenyerar);
A ShowMessage nem képes, csak egy valamit kiírni, a MessageBox meg csak const char-okat akar bevenni, még string-et sem. (most beolvasom egy stringbe az összes változót, stb-it és azt iratom ki ShowMessage-dzsel, de nem igazán elegáns... :o)

nahh majd holnap kipróbálom... :p Köszi! :)

Olyan programot kellett volna írni versenyen, hogy bekérsz egy számot, nevezzük N-nek, [2;14] intervallumban, és kiírja egy állományba az összes N számjegyű prímet, melynek számjegyei balról jobbra nem csökkennek. N=10-re kb 10 perc alatt kell lefutnia. Én a közelébe sem értem az 1 percnek. Valaki ha írna egy ilyen programot, Pascalban, C-ben vagy JAVA-ban megköszönném.

Most látom, elírtam. N=10-re kb 1 perc alatt kell lefutni. Sikerült megcsinálni, N=11-re 40 mp alatt fut le. Versenyen miért nem jutott így eszembe?!:mad:

Azt tanultam, hogy Eratoszthenész szitája a leggyorsabb ismert prímszám kereső algoritmus. Ha igazán gyorsat szeretnék írni N=10-re, akkor 10^10-nek a gyökéig előállítanám Eratoszthenész szitájával a prím számokat, majd az így megtalált prím számokkal osztogatnám végig a kérdéses intervallumokat. Ha többmagos a processzor, akkor természetesen több szálra tenném ezt a második lépést. Szerintem ez bőven belefér 1 percbe 10 jegy esetén.

a pascalban csak 2^32-en méretű lehet egy tömb, ez 4,2 milliárd. 14 számjegyű szám gyökéig bőven több, mint 4,2 milliárd prímszám van, szerintem.

Bocs, csak a 10 jegyűeken gondolkodtam, nem a teljes feladatot, mert csak arra mondtál 1 perces korlátot.

Úgy emlékeztem, hogy pascalban nem is lehetett 2^16-nál nagyobb tömböt definiálni. Helyette megoldható mutatókkal. C++-ban és Java-ban viszont 10 jegyűek gyökéig haladva a számokkal szerintem még belefér, mert az csak 100.000.

A 14 jegyű szám esetén nem gondolkodtam. Ahhoz legfeljebb gyök(10^14)=10 millió adatot kellene a memóriában tárolni. Azt hiszem, ennek inkább már C++-ban esnék neki mutatókkal, az még simán lekezel ennyit.

köszi azért :) végül sikerült megcsinálnom :)

Érdekelne, hogy milyen módszerrel oldottad meg, mert én kipróbáltam azt, amit én javasoltam, de úgy már 10 millióig az összes prímszám megkeresése 5 másodpercig tartott, az pedig csak N=7 eset, szóval pillanatnyilag meg sem tudom közelíteni a feladat szerinti N=10 esetet 1 perc alatt. Nem futtattam, de az eredmények alapján kb. 8 óra lenne a futási ideje. :)

Kitaláltam egy másik módszert, de az túl bonyolult ahhoz, hogy csak úgy hirtelen összedobjam, és nem is biztos elég gyors.


Most olvastam a Fermat-prímtesztet. Ha csak néhány estre nézzük a Fermat-prímteszttel a számokat, akkor a nem prímek jó eséllyel megbuknak és csak a maradékra kell nézzük meg, hogy valóban prímek-e. Majd kipróbálom valamikor, hogy ez segít-e rajta.

Azt ugye belekalkuláltad, hogy a számjegyek balról jobbra nem növekedhetnek? Ha igen, akkor elmondom én hogy csináltam:

Egy számgeneráló eljárás és egy eléggé felturbózott (gyökéig osztókat kereső) prímkereső algoritmussal.

Számgeneráló:
primkereső:
Ha nem vagy benne pascalban, akkor leírom majd pszeudo kódban is :)

a fermat prímteszttel az a gondom, hogy 2^(10^14)-en szám pedig horribilis memóriát foglalna, ha egyáltalán bele tudnám tuszkolni valami változóba :D

A szerintem nagyon kevés :)
Van egy ismert képlet a prímszámok darabszámára.
Ha nem tévedek, akkor 10^8-ig kb 5,5 millió prím van. (kb minden 18. szám lesz prím.)
10^8-on meg 10^15 gyöke fölött van.

Szóval a 4,2 milliárdos határt bizony nem éri el.

Kicsit utánaolvasva a dolgonak, a prímszámok darabszáma [0;x] intervallumban: ~(x/ln(x)). Ez a függvény nagyobb x esetén pontosabb értéket ad, és 10 számjegyű számoknál már csak 4,8% az eltérés a prímek valós számától.

10^14-ig ~3.102.103.442.166 prím szám van. Ebből vegyük el, a 10^13-ig lévő prím számok darabszámát, ami kb ~334.072.678.387.
3.102.103.442.166-334.072.678.387=2.768.030.763.779.
Ha nem számoltam el semmit, akkor elvileg több mint 4,2 milliárd 14 számjegyű prímszám van.

Azt írtad, hogy a gyökéig kell nézni. 10^15-en gyöke tudtommal 10^7,5<10^8.

óbasszus, tényleg. Fáradt vagyok, bocsi. Csodálkoztam is, hogy meg tudlak cáfolni :D:D De sajna nem :)

Igazad van. Használhatatlan. Le is mondtam róla.

Futási idő 1 perc és 19 másodperc:
10^8-ig pontosan 5.761.455 db prím szám van. :)

megnézem az én pascalos buher módszerem mennyi ideig keresi :) Biztos több idő lesz, sajnos :( Te miben írtad? C?

Átírtam C-re a Te algoritmusodat lényegi változtatás nélkül és 4 perc 8 másodperc alatt futott le. (Ez 64 bites linux alatt futott, a NetBeans mérte az időt E5200-as procival.) C++-ról viszont az enyémet nem tudom átírni pascalra, mert objektum-orientáltan írtam és nem tudok annyira pascal-ul. :)
Így néz ki a Tied, hogy lásd, nem változtattam semmit:


#include <stdlib.h>
#include <math.h>
#include <stdio.h>

bool prim(long unsigned long szam) {
long unsigned long gyok, i;
gyok = round(sqrt(szam));
i=3;
while (i<=gyok) {
if (szam % i == 0) return false;
i++;
i++;
}
return true;
}



int main(int argc, char** argv) {
unsigned long k = 1;
for (long unsigned long i = 2; i < 50000000 ; i++) {
if (prim(i*2-1)) {
k++;
}
}
printf("%d", k);
printf("\n");
return (EXIT_SUCCESS);
}

Az enyém pascalban még 5 perc alatt sem futott le :D Lehet ideje lenne elkezdenem tanulni a C-t... Azt mondták Pascalban iszonyatrossz az objektumorientáltság, ezért nem is fogtam hozzá :) Amúgy grat a gyors algoritmusodhoz ;)

Szerintem Pascalból C++-ra viszonylag egyszerűen, fájdalommentesen át lehet térni, mert a megszokott függvények egy kis utána olvasás után szinte ugyanúgy megvalósíthatóak. Viszont nekem úgy tűnik, hogy a C++ sokkal nagyobb szabadságot ad a megvalósításban. Ezeknek a lehetőségeknek a megismerése és használata számomra elég bonyolultnak tűnik, de kicsit barátkozva a lehetőségekkel a Pascal-t már nagyon korlátoltnak találtam és le is szoktam róla. A Java-ban viszont azt szeretem, hogy bár a C++-hoz képest nekem kötöttnek tűnik, alapból tele van egy halom hasznos, könnyen kezelhető library-val, így kevés tudással is egyszerű benne olyan függvényeket megvalósítani, amelyekről a Pascal-os korszakomban legfeljebb csak álmodhattam. Emellett a Java programozás rákényszeríti az embert egy, a Pascaltól gyökeresen eltérő szemléletre. A C++ ilyen szempontból számomra egy lépcső volt a Pascal és a Java között. Lehet vele ökörködni pascalos stílusban, és lehet vele tovább lépni a Pascalon. De a Java számomra sokkal egyszerűbb, mint a C++. Szerintem mindenképpen érdemes valamilyen irányban túllépni a Pascalon, és a Delphi rossz irány. Azt is próbáltam. Kecsegtető Pascal után, de a C++ vagy a Java-hoz képest elcseszett dolog.

Javítottam az algoritmuson. 10^8-ig az összes prím szám megszámolása 3 másodpercre csökkent.

10^9-ig az összes prím szám megszámolása 34 másodperc. Pillanatnyilag nincs ötletem, hogyan lehetne ezen még tovább gyorsítani, de gondolkodom rajta.

De akkor ez most azt jelenti, hogy a 10 számjegyű prímeket hamar meg tudod már találni ezzel az algoritmussal, nem?

az megkérdezhetem, hogyan keresed a prímeket?:) mert szerintem a gyökéig osztogatóssal ezt lehetetlen megoldani.még arra gondolok, hogy egy nagyon nagy tömbben mindig kivenni az i. és k*i. elemet, ( k eleme a pozitív egész számoknak ) majd növelni i értékét.

Igen, a 10 számjegyűeket elvileg megtalálom, de az még mindig sok idő. Egyelőre 10^9-ig mértem a sebességét, így csak az összes legfeljebb 9 jegyű prím számot találtam meg 34 másodperc alatt. Természetesen ebben nincs kiíratás, csak megszámoltattam.

Zseni vagy :)
Azt hiszem pár oldallal ezelőtt ajánlotta tulip a prímszitát, ami pont ezt csinálja.
Azóta belefutottam, hogy létezik egy komplementer prímszita eljárás is, esetleg azt kellene kipróbálni.

1, Legenerálom a prím számokat a vizsgálandó legnagyobb szám gyökéig.
2, Megadok egy 50.000 elemes boolean tömböt (50.000 fölött nem gyorsult tovább) és darabonként eratoszthenészi szitával fedem le a teljes tartományt. De mindig csak egyetlen tömb van jelen a memóriában, azaz tologatom a lefedő tömböt.

Tehát először megvan az 1-es pont, ezt egyszer végzem el. Ez után, ha valamelyik számról el akarom dönteni, hogy prím-e, pl. a 120121-ről, akkor a program megvizsgálja, hogy le van-e fedve eratoszthenészi szitával. Ha nincs, akkor 120121-től kezdődően 120121+49999-ig elkészíti az eratoszthenészi szitát, figyelembe véve, hogy a tömb 0-49999-ig van sorszámozva és a 0 itt a 120121-et fogja jelölni. Természetesen itt is csak a gyök(120121+49999)-ig folyik a vizsgálat.

Hogy érthetőbb legyen. Ha úgy választunk meg 2 vizsgálandó számot, hogy a különbség köztük nagyobb, mint az 50.000-es tömb, pl. 2 és 120121-ről szeretnénk eldönteni, hogy prímek-e, akkor megkeresi az algoritmus 2-50001-ig az összes prímet és megkeresi 120121-170120 között az összes prímet, tehát egy halom felesleges számolást végez. Ellenben ha pl. megnézzük a 2, 11201, 503, 57,45511, 27 számokra, akkor csak egyetlen, 2-49999-ig tömböt fog kiszámolni.

Tehát ez az algoritmus akkor igazán gyors, ha sorban növekvő elemeket akarunk vizsgálni.

Átgondoltam. 6-ból 4 oszlopot zár ki és a maradék esetek további vizsgálatot igényelnek. Viszont a 4 kizárt oszlop tartalmazza az összes páros és az összes 3-al osztható számot, amelyet egyébként is az elsők között zárunk ki a prímszám keresések alkalmával, így valójában nem gyorsít semmit, csak egy felesleges kört futunk előtte.

Ebben a témában volt régebben szó web alapú játékfejlesztésről (lásd: 6. és 7. oldal, Csokibácsi pl.). Érdeklődnék, hogy van-e bárki, akinek van ilyen irányú érdekélődése?? Akár grafikus (nem kell világmegváltó grafika), akár programozó (php, flash, java, javascript, jquery/ajax, bármilyen kombinációban, de egy szerveroldali mindenképpen fontos lenne).

A helyzet az, hogy én már vagy egy éve gondolkodom egy valamiféle játékon. Ha hasonlítani akarnám valamihez, akkor a Hódító MUD is ilyesmi, de persze köze nem lenne hozzá, más irányvonal és felépítés van a fejemben, más világgal, stb. :) Alapjaiban más lenne (bár ugyan úgy egy kalandjáték, szerepjáték kategória). A példa csak azt szemlélteti, hogy mégis mi a téma, szóval nincs benne koppintás, meg ilyenek.

Igazából néhány hét kivételével nagyon ráérek egész nyáron, így ha valakiben van valami érdeklődés a téma iránt, akkor az alapokat le lehetne fektetni a következő pár hónapban. Nálam a motiváció megvan, de egyedül nincs energiám semmibe sem belekezdeni.

Tárhely, domain és látogatók (játékosok). Ezekkel is tudok majd szolgálni. Részemről PHP, JQuery meg MySQL tapasztalataim is vannak, és rengeteg időm + elég gyorsan tanulok.

Ha összejön egy néhány fős csapat, akkor azzal már sok mindent lehet kezdeni. Bár picit félek, hogy senki nem fog jelentkezni erre a felhívásra, de hát meg kell próbálni. :p

Egyenlőre azért még csak érdeklődés szintjén megy a dolog. PM-eket várnék ezzel kapcsolatban, aztán majd eldől, hogy lesz-e belőle valami. Nagyon remélem. Szóval bombázzatok a levelekkel. Köszi. :)

Egen, sejthető volt, hogy senki sem fog jelentkezni. :p

Ha lenne időm ... bár, még a saját szarom is ott áll sehogyse állapotban http://www.tms.hu/smiley/monokli.gif

Amiatt is érdeklődtem már...
De gondolom semmiképp sem adnál át félkész munkát másnak.

Gázos, mert nem szoktam kommentelni a kódot.
Múltkor belenéztem ... hát nem volt egyszerű rájönnöm, mit miért csináltam :D
Ha újrakezdeném, biztosan posztapokaliptikus témájú lenne a cucc (de azért nem Fallout másolat).

Azért én lehet, hogy kíváncsi lennék. :p

Én maradok a fantasynál. Olyan világot tudok jót építeni. A Fallout jó játék, de alkotni nem tudnék olyat.

Adott egy 100mx100m-es térkép. Minden egyes ponthoz meg van adva a magassága. Tekintsük úgy, hogy egy négyzet 1mx1m, és egy négyzet minden pontja ugyan olyan tengerszint feletti magasságon van. Írjunk programot, amely megmondja kialakítható-e rajta egy legalább 50M^2-es tó, bal felső és jobb alsó koordinátáját adja meg a tónak. HAsználnátok-e hozzá valamilyen féle mesterséges intelligenciás algoritmust? Ha igen, melyiket? Nekem megvan a program ,viszonylag gyors is, de mesterséges intelligenciát nem hiszem hogy tartalmaz.

Nem hiszem, hogy a jelenlévők közül bárki is tudna olyat írni, ami tényleg MI. Mármint, én nem nevezem mesterséges intelligenciának a tapasztalat alapján tanuló programot, például. Belátásos tanulást meg még nem igazán tud csinálni az emberiség. :)

Szóval mire gondolsz mesterséges intelligencia alatt?? :)

Matektanárom valami méylségi keresést, meg valami backtrack valamit emlegetett. Annyira nem vagyok benne a dologban, igazából én is arra lennék kíváncsi, hogy mit is nevezünk Mesterséges Intelligenciának.

Hát az MI nem igazán találó elnevezés a backtrack-re, de speciel az egyik vizsgatételem az, de ha google-ben rákeresel valag anyagot találsz, én is inkább onnan szedtem össze:D