Programozás

[Dew]

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

újra előszedtem, és kicsit elszoktam tőle... (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... )

[BimmBimm]

Originally Posted by Dew

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

újra előszedtem, és kicsit elszoktam tőle... (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... )

Hát én csak konzolos dolgokat csináltam C++-ban, ott meg elég a cout << valtozo;
Egyébként egy stringből így lehet char*-ot csinálni:
string a = "asdasdasd";
char* b = a.c_str();
asszem...

[Dew]

Originally Posted by BimmBimm

Hát én csak konzolos dolgokat csináltam C++-ban, ott meg elég a cout << valtozo;
Egyébként egy stringből így lehet char*-ot csinálni:
string a = "asdasdasd";
char* b = a.c_str();
asszem...

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

[Redback]

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.

[Redback]

Originally Posted by Redback

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?!

[tulip]

Originally Posted by Redback

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?!

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.

[Redback]

Originally Posted by tulip

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.

[tulip]

Originally Posted by Redback

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.

[Redback]

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

[tulip]

Originally Posted by Redback

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.