Kontajner, ktory.... – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Kontajner, ktory.... – C / C++ – Fórum – Programujte.comKontajner, ktory.... – C / C++ – Fórum – Programujte.com

 

Tom@sQo0
Stálý člen
23. 1. 2008   #1
-
0
-

ahoj,
potreboval by som kontajner, ktory vie najst prvky podla hodnoty(nie indexu), resp. mazat ich podla moznosti v O(1)...

totiz potrebujem zistim prvocisla v nejakom rozsahu(napr. 1 az 10 000 000) a napadlo ma, ze to spravim cez eratostenovo sito(vsetky cisla supnem tu a potom mazem nasobky...) any better ideas? :)

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
tmi0
Věrný člen
23. 1. 2008   #2
-
0
-

nevim ale prijde mi ze na to jdes moc slozite, nebylo by lepsi v cyklu o poctu iteraci odpovidajici rozsahu kontrolovat delitelnost iterovane promenne jiz nalezenymi prvocisly, ktera bys ukladal do nejakeho treba vektoru? (pozn: iterace by ti stacila po dvou)

Nahlásit jako SPAM
IP: 89.185.230.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
Santas0
Věrný člen
23. 1. 2008   #3
-
0
-

v nasich skriptach na c mame hladanie prvocisla podla erastenovho sita... kod ti mozem poskytnut

Nahlásit jako SPAM
IP: 195.91.64.–
http://psandtner.sk/blog
midin0
Věrný člen
23. 1. 2008   #4
-
0
-

Nebo si ho muze snadno najit... uz treba i na ty pitomy wikipedii...

Nahlásit jako SPAM
IP: 89.24.4.–
Zápisky z dění na FB (momentálně ve vývoji): http://fbpd.ic.cz/
tmi0
Věrný člen
24. 1. 2008   #5
-
0
-

a nebo ho hlavne muze sam zkusit napsat bez cumeni na nejakej hotovej zdrojak jen na zaklade ty myslenky. opisovanim cizych zdrojaku se nikdy programovat nenauci

Nahlásit jako SPAM
IP: 89.185.230.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
croniak0
Newbie
24. 1. 2008   #6
-
0
-

Co treba pole o tom rozsahu a jednotlive polozky 0/1 smazano.

Nahlásit jako SPAM
IP: 62.84.145.–
Tom@sQo0
Stálý člen
24. 1. 2008   #7
-
0
-

huha, tych answerov ale je ;)
takze pekne po jednom:
tmi(prvy tvoj post): noo imho tvoje je skor zlozitejsie a hlavne casovo o dost narocnejsie, resp. ked som dobre pochopil, tak si mal na mysli nieco take ako



for(int i=0; i != range_end; i+=2){/*rozhodnem, ci je to prvocislo*/}

lenze ak sa nemylim(pozn: nesom si isty), tak aj tak asymptoticku zlozitost nijak nezmensim(bude to O(0.5*N), pricom konstanty sa neberu do uvahy takze == O(N))

santas: diky velmi pekne za ochotu, ake nepotrebujem to :) mne ide len o myslienku, nie o kod ;)
midin: ou shiiit, uplne som zabudol, ze existuje aj wikipedia :) sry :) uz som to ocheckoval na ceskej.
tmi(2.post): no ide o to, ze kamarat urobil taku minisutaz na http://kruzok.d42.sk/sutaz/ a tam to treba; o to, ze sa takto nenaucim kodit, sa neboj ;) ja kodim o dost viac, nez len tato sutaz, a okrem toho toto je len "prakticky priklad", (vid http://kruzok.d42.sk/sutaz/index.php?act=instructions), takze tu popisovat myslienku netreba, treba len aby to zbehlo :) na popisovanie a dlh(s)e rozmyslanie je tu stale "teoreticky priklad"
croniak: no lenze ja sa skor pytam, JAK chces taketo pole vygenerovat(teraz sa uz nepytam, lebo to uz viem, ale povedzme, ze sa pytam ;-]) a potom este by to nebolo velmi dobre celkovo do prikladu, pretoze ulohou je zistit kolko je prvocisel v zadanom rozsahu a to by sa potom uz nedalo spravit v log N (mam na mysli binarne hladanie) ;)

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
tmi0
Věrný člen
24. 1. 2008   #8
-
0
-

hele myslis si ze to de v lepsim case nez to mam? abych se priznal, moje znalosti vlastnosti prvocisel jsou mizive (vicemene konci u bertrandova postulatu), ale myslim si ze nemuzes (alespon o tom nevim) obecne spocitat pocet prvocisel v nejakem rozsahu lepe nez jejim vyctem.
k cemu chces tady pouzivat binarni hledani? to mi nedochazi... jestlize chces znat pocet prvocisel v urcitem intervalu, pak (pokud uz ta prvocisla dopredu neznas, ale to by pak ten program trochu nemel smysl) tak si je proste do onoho intervalu dogenerujes a spocitas.

btw. sice ti to zkraceni casu na polovinu vynechanim sudych cisel nepomuze, ale dava to najevo ze tusis o co jde.

ohledne te slozitosti: pokud umis rozhodnout v konst. case zdali je cislo prvocislo, pak ma muj alg. slozitost O(N). ja to tedy neumim, takze ta slozitost je "trochu vetsi", konkretne O(N*log(log N)) pri pouziti ersita. o kterem si koneckoncu mluvil i ty, tak nevim proc by mel byt tvuj alg lepsi nez muj.

Nahlásit jako SPAM
IP: 89.185.230.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
Tom@sQo0
Stálý člen
24. 1. 2008   #9
-
0
-

tmi: okay, okay, neratal som zlozitost ersita takze nemozem sa s tebou hadat :) kazdopadne som si nevsimol, ze tiez pouzivas ersito pri tvojom rieseni;)

a k comu pouzivat to binarne hladanie? nechce sa mi kazdy detail zadania opisovat, tak radsej tu supnem cele ;)



Časový limit: 50s
Pamäťový limit: 32MB

Rasťo sa prednedávnom v jednej knižke dočítal, že prvočísel je nekonečne veľa... ale už o dve strany neskôr sa dozvedel aj to, že existujú ľubovoľne dlhé úseky po sebe idúcich prirodzených čísel, medzi ktorými nie je ani jedno prvočíslo. A ked na dôvažok zistil, že Bertrandov postulát hovorí, že pre každé N je medzi N a 2N aspoň jedno prvočíslo, mal v tom už dokonalý zmätok. Pomohol by mu program, ktorý by vedel pre zadané intervaly hovoriť, koľko prvočísel vlastne obsahujú.
Vstup

Na prvom riadku vstupu je jedno celé číslo T (1 ≤ T ≤ 20) – počet intervalov, ktoré budú nasledovať. Nasleduje T riadkov, v i-tom z nich sú 2 celé čísla ai, bi (1 ≤ ai ≤ bi ≤ 1 000 000).
Výstup

Výstup by mal obsahovať T riadkov, na i-tom z nich jedno celé číslo – počet prvočísel, ktoré ležia medzi ai a bi (vrátane).
Poznámky
Prvočíslo je prirodzené číslo, ktoré má práve dvoch deliteľov (jednotku a seba samého). Najmenšie prvočísla sú teda 2, 3, 5, 7, 11, ...
Snaž sa, aby tvoj program bol čo najrýchlejší. Nerátaj zbytočne viackrát to isté. Zbytočne pomalé programy nemusia stihnúť skončiť v časovom limite.
Príklad
Vstup
3
3 5
122 125
340000 350000
Výstup
2
0
795

k tomu ;) vygererujem prvocisla a potom hladaam :)

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
24. 1. 2008   #10
-
0
-

Přez to sito se na to vykašli. Taky jednou mi kamarád řekl ať vypíšu prvočísla v nějakým rozsahu, já jsem neznal algoritmus, ale pak mi poradil a už jsem to napsal:
Dokázal jsme ten kod tak kratce zapsat že ho mám i v javě.

C++



bool JePrvocislo(int cislo)
{
if (cislo == 0) return false; // vyjimka
for (int i = (int)sqrt(cislo); i != 1; --i)
if ((cislo % i) == 0)
return false;
return true;
}

Java


static boolean JePrvocislo(int cislo)
{
if (cislo == 0) return false; // vyjimka
for (int i = (int)Math.sqrt(cislo); i != 1; --i)
if ((cislo % i) == 0)
return false;
return true;
}

Možná to budeš muset u C++ přetypovat na double v tom sqrt já si tedka nejsem jistý.

Nahlásit jako SPAM
IP: 85.160.93.–
Muj starý nick Tomik512
24. 1. 2008   #11
-
0
-

Vysvětlení:
Ještě bych vysvětlil ten algoritmus. Prvočíslo má jenom 2 dělitele jednim je 1 a druhym je číslo samotné. Když vemu číslo 25 tak k tomu abych zjistil zda to je prvočíslo nemusim kontrolovat od jedné do 25 jestli je dělitelné pouze 2x, stačí ho kontrolovat do 5 což je jeho odmocnina. To platí u každého čísla, když je tedy jeho odmoznina dělitelná do jedničky nějakym číslem je není to prvočíslo.
Proto ten algoritmus.
Podrobný rozbor algoritmu:
0 pokud si ze školy pamatuju správně neni prvočíslo ani neprvočíslo, ale patří do specialní skupiny, navíc s ní nelze dělit, tak musí být odchycena před testováním.
Proč ten for takto



for (int i = (int)Math.sqrt(cislo); i != 1; --i)
místo


for (int i = 1 ; i != (int)Math.sqrt(cislo); i++)
To je kuli náročnosti, když spočítám odmocninu z vyššího čísla může to být pro počítač záhul. A když pak program jede a při každym cyklu počítá tu odmocninu, aby zjistil zda má pokračovat je hloupé protože ta odmocnina bude stále stejná.
Pak už jenom kontroluju v každym cyklu zbytek po dělení a když doběhne for kompletně potvrdí funkce prvočíslo.

Kdyby měl někdo rychlejší řešení, chtěl bych o něm slyšet, protože mám pocit, že líp už algoritmus zapsat nejde.

Nahlásit jako SPAM
IP: 85.160.93.–
Muj starý nick Tomik512
Tom@sQo0
Stálý člen
25. 1. 2008   #12
-
0
-

noo je tu taky problemik; vid zadanie, ktore som poslal; totiz vstup bude urcite OBROVSKY(dostanem 1000 intervalov a v kazdom obrovskom rozsahu mam zistit pocet prvocisel, takze nemozem si dovolit to dvakrat pocitat). len tak zo srandy som narychlo nakodil ten priklad pomocou tej funkcie a este som tam pridal pre rychlost konktrolu, ze ak je cislo parne a je vacsie ako 2, tak to nieje prvocislo... noo skoncilo to obrovskym(kamarat nespecifikoval, akym) prekrocenim casoveho limitu

Nahlásit jako SPAM
IP: 213.81.187.–
Tom@sQo
25. 1. 2008   #13
-
0
-

Tom@sQo:
No tak samozřejně algoritmus se dá vylepšovat na úkor přehlednosti. Tak ho vychytáme společně tady na foru. Takže tedka ho máš nějak talke?



bool JePrvocislo(int cislo)
{
if ((cislo != 0) || ((cislo > 2)&&(cislo % 2 != 0)))
for (int i = (int)sqrt((double)cislo); i != 1; --i)
if ((cislo % i) == 0)
return false;
return true;
}

Tak takle vlastně děláme takové menší síto.
Tak hele


#include <iostream>
#include <math.h>
#include <time.h>

using namespace std;

bool JePrvocislo(int cislo)
{
if ((cislo != 0) || ((cislo > 2)&&(cislo % 2 != 0)))
for (int i = (int)sqrt((double)cislo); i != 1; --i)
if ((cislo % i) == 0)
return false;
return true;
}


int main()
{
clock_t start = clock(), end;
for(int i = 1; i != 100000; ++i)
if(JePrvocislo(i))
cout<<i<<endl;
end = clock();
cout<< "Cas : "<< end - start ;

cin.get();
return 0;
}

U mě má tento build cca 2010 (asi to jsou milisekundy)
Bez předešlé podmínky u mě má, ale stejně :smile1:
Můžou tedy zkoušet ostatní, taky by mě zaímalo jak se to dá ještě zrychlit. Prosím uvádějte čas tohoto i vaší modifikace.

Nahlásit jako SPAM
IP: 85.160.83.–
Muj starý nick Tomik512
25. 1. 2008   #14
-
0
-

Upřesnění:
Tu smyčku bzrdí nevíce příkay cout.
Když tedy main upravim takto:



int main()
{
clock_t start = clock();
for(int i = 1; i != 100000; ++i)
JePrvocislo(i);
cout<< "Cas : "<< clock() - start;

cin.get();
return 0;
}

Dostanu číslo 128. Když necháp podmínku jak byla dostanu skoro stené číslo, samozřejně mi běží několik programů na pozadí a číslo se mění, ale průměr mají stený. Takže takle:


bool JePrvocislo(int cislo)
{
if (cislo != 0)
for (int i = (int)sqrt((double)cislo); i != 1; --i)
if ((cislo % i) == 0)
return false;
return true;
}

to asi od mě nejvíc co můžeš dostat. Mohl by jsi si vztvořit vlastní odmocninu aby se tam nemuselo přetypovávat, ale pochbuju že tím něco zrychlíš, jsou to funkce jazyka to jsou vždy nejrychlejší.

Nahlásit jako SPAM
IP: 85.160.83.–
Muj starý nick Tomik512
Tom@sQo0
Stálý člen
26. 1. 2008   #15
-
0
-

ahoj ;)
noo som sa sekol kusa aj ja, aj ty :)
1) tie prvocisla su v rozsahu od 1 do 1000000 vratane (ty si sa sekol), ale aj tak mi to zbehne do 7 sekund ;)
2) ten vstup bude maximalne to, ze: bude 20 hladani a ze casovo najnarocnejsi bude, ze najdi mi pocet prvocisel od 1 do 1000000(ja som sa sekol, bo som neprecital zadanie) a to musi stihnut do 50 sekund... kazdopadne cele to ukladam to vektoru a uz len naimplementujem binarne hladanie(co ***prosim vsetkych***, nepiste ho tu, ja ho chcem napisat sam :-] v utorok je deadline, takze dovtedy ho napisem ja sam ;-])

kazdopadne diky za ten algoritmus ;) vobec som si nemyslel, ze je taky rychly(len 7 sekund) pricom je ovela kratsi ako ersito ;-)

ps: miesto tej fcie clock, ti navrhujem pouzivat radsej moju formulku ;) "g++ -Wall subor.cpp; time ./a.out < in " ktoru velmi casto pouzivam na sutaziach na meranie casu ;-) a nepotrebujem tym spinit kod :)

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
26. 1. 2008   #16
-
0
-

Jj, já to nepsal podle zadání, ale abych ti poradil algoritmus. :smile1: To měření času moc nepoužívám, ale díky za tu ulitu na měření. Ono zase ve většim projektu kde se ti hodí čas jenotlivejch funkcí to už si kod zašpinit musíš s tim že to tam máš jenom když to ladíš a pak to smažeš..

Tak hodně štěstí a vyhraj ! ! ! :smile7: :smile7:

Nahlásit jako SPAM
IP: 85.160.68.–
Muj starý nick Tomik512
mephi0
Expert
26. 1. 2008   #17
-
0
-

ja len pridam taky napad:
netreba deliť všetkymi čislami, stači deliť prvočislami menšimi ako odmocnina z kontrolovaneho čisla ;)

dnes je k dispozícii veľmi veľa pamäte, tak prečo nesptaviť 1MB subor s predvypočítanými číslami ? :)

cout << je pomalší ako printf() , mam to vyskušane.

Nahlásit jako SPAM
IP: 85.248.56.–
Program nemusi fungovat rychle, staci ze funguje dostatecne rychle.
Tom@sQo0
Stálý člen
26. 1. 2008   #18
-
0
-

mephi:
k tomu napadu: Tomas Dejmek to uz tak pouzil v kode ;)

daleeej co sa tyka toho 1MB suboru:
uz som to skusal hned prvy den, lenze mi to neprijalo...kod musi byt do 64 kB ale aj tak...limit je 50 sekund, z toho 7 sekund zaberie to generovanie, takze imho to ani netreba ukladat ;)

co sa tyka cout vs printf, tak je to pravda, ze cout je cca 15 krat pomalsi, lebo tam uz ta trieda je riadne premakana a dost ti dobre "detekuje" typy a (skoro) vsetko vypise spravne narozdiel od printf, kde musis typ explicitne uviest ;)
LENZE na sutaziach z programovania su ulohy naschval tak napisane, aby neslo o tieto blbosti, ale o casovu narocnost algoritmu... aj tu si uvedom, ze tych 20 riadkov vstupu vystupu je skoro uplne jedno, cim sa to vypise ;)

Tomas Dejmek:
diky za povzbudenie ;) podla http://kruzok.d42.sk/sutaz/index.php?act=results som az druhy(Tomas Novella), ale dufam, ze sa tvoje prianie splni ;))

Nahlásit jako SPAM
IP: 88.212.23.–
Tom@sQo
26. 1. 2008   #19
-
0
-

memphi to myslel jinak, odmocnina je horní hranice z které zkoušíš dělit po jedničkách každou možnost (algoritmus odemě), on myslel dělit to pouze prvočísly, a má pravdu, ale nevim jestli to má cenu psát....
Vypadalo by to asi takle:
1) Vypočitání horní hranice testování ze vstupního čísla(ozmocnina).
2) vygenerování prvočísel do horní hranice.
3) testování zbytku po dělení prvočísly.

Bod 2 znamená zpomalujicí smyčku, ale bod 3 se tím zrychlí. Bod 2 by se dal obejít tim, že by jsi měl už čísla vygenerovaný sám (tím myslel to 1MB)
Otázka je jestli se dá mluvit o algoritmu. :smile3: Možná by se to ještě na úkor přehlednosti ale dalo ještě vylepšit, přemýšlej otom kdyžtak.

Soutěž: Věřim ti, 1. nemám moc navrch.
PS: Tomášové jsem asi nejlepší programátoři :smile6: :smile6: :smile6: viz tabulka

Nahlásit jako SPAM
IP: 85.160.68.–
Muj starý nick Tomik512
26. 1. 2008   #20
-
0
-

Jo hele jak sjem ten algoritmus upravil naposled, tak v té verzi JE CHYBA!!! Když to je nula vráti to true což je blbost... já jsem tam měniil tu podmínku a nevšim jsem si toho.

Nahlásit jako SPAM
IP: 85.160.68.–
Muj starý nick Tomik512
tmi0
Věrný člen
26. 1. 2008   #21
-
0
-

jak bych to asi resil ja:
nacitane vstupy bych hazel do intervaloveho stromu, a zaroven bych mezi nimi nasel maximum.
pote bych spustil alogritmus na hledani vsech prvocisel (je jedno jestli se pouzije klasicke ersito s eliminaci nasobku nebo jeho varinata s delenim (to je totiz v podstate taky ersito, jen funguje trochu jinak), zalezi na tom jak rychle pocitac zvlada nasobeni oproti deleni. vzhledem k tomu ze to jsou cela cisla bych se asi vice klonil k druhe variante). pravdepodobne bych je ukladal do nejakyho pole vsechny, dalsi pocitani se tim celkem urychli. pri postupnym pocitani prvocisel bych pouze kontroloval spodni patra toho intervalovyho stromu a pokud by cislo bylo v intervalu tak bych zvysil pocet v ramci intervalu, pripadne bych se posunul o interval vyse.
no a nakonec bych pro jednotlive zadane intervaly spocital ktere casti intervaloveho stromu jim patri.
vyhodu to ma tu ze se vse potrebne pocita skutecne jen jednou. nad slozitosti se mi spekulovat nechce (zalezi na tom jak by se implementoval ten intervalak), ono hledani prvocisel by trvalo onech O(n*log(logN)), kde N je nejvetsi cislo z intervalu. vytvoreni intervalaku by zalezelo na tom jak moc "disjunktivni" ty intervaly jsou, v nejlepsim logT, obecne asi O(log(pocet disjunktivnich podintervalu)), samotne spocitani by se zvladlo O(pocet_disjunktivnich_intervalu + pocet_prvocisel_v_0-N) a vypsani vysledku v O(pocet_disjunktivnich_podintervalu + T*log(pocet_disjunktivnich_podintervalu). Celkem to dava O (T*log(pocet_disjunktivnich_podintervalu) + pocet_disjunktivnich_podintervalu + pocet_prvocisel_v_0-N + N*log(logN)).
pametove je potreba O(pocet_prvocisel_v_0-N + pocet_disjunktnivnich_podintervalu).

tohle reseni by bylo efektivni jen pro hodne pruniku mezi zadanymi intervaly, pokud by tam zadne pruniky nebyly tak je celkem zbytecne ten intervalak stavet, pak by se totiz kazde prvocislo pocitalo jednou tak jako tak.

Nahlásit jako SPAM
IP: 89.185.230.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 25 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý