Mobili versija | Apie | Visos naujienos | RSS | Kontaktai
 
Vartotojo vardas:
Slaptažodis:
Atsiminti
Login with a social network:

Jūsų požiūris

Aktyvios diskusijos

Ieškoti forume


Išsami paieška

 [ 14 pranešimai(ų) ] 
 
Naujos temos kūrimas Atsakyti į temą Pagrindinis diskusijų puslapis » Žmonių pasaulis » Požiūris - komentarai ir nuomonės
Žinutė Autorius
  Standartinė   Parašytas: 2016-01-11, 13:43 
     
Teisingai, čia prireiks didelių kompiuterio pajėgumų.
Kadangi dabar per programavimo pamokas naudojam C++, ja ir aprašysiu sprendimą.

Sprendimas
Kodas:
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

//funkcija skirta patikrinti ar skaicius pirminis
bool ArPirminis(unsigned int skaicius) {
    if(skaicius >= 11) {
        unsigned int saknis = sqrt(skaicius);
        // didziausias sudėtinio skaiciaus daliklis yra jo saknis, todėl apsiribosime sukdami cikla nuo 2 iki suapvalintos saknies.
        for(unsigned int i = 2; i <= saknis; i++) {
            if(skaicius % i == 0) return false;
        }
    } else {
        if(skaicius == 2 || skaicius == 3 || skaicius == 5 || skaicius == 7) return true;
        else return false;
    }
    return true;
}
int main() {
    unsigned int Pirminiu = 0, n = 0;

    do {
        n++; // pirmas aibės narys 0 + 1, ir t.t.
        if(ArPirminis(n) == true) Pirminiu++; // jeigu yra pirminis, padidinti

    } while(Pirminiu < 1000001); // vykdyti tol kol pirminiu bus 1 000 001

    float dalis = (float)(Pirminiu)/(float)(n)*100; // procentai
    cout << Pirminiu << " / "<< n << " * 100 = " << fixed << setprecision(2) << dalis << "%";
    return 0;
}

Sprendimas suprantamesne kalba:
Sukuriama funkcija, tikrinanti ar skaičius pirminis:
* jei mažesnis už 11, tikrinti ar jis lygus 2,3,5,7. Jei nesidalija, grąžina true, jei dalijasi, grąžina false;
* jei didesnis ar lygus 11, iš skaičiaus traukti šaknį, suapvalinti į mažesnę pusę
cikle nuo 2 iki supavalintos šaknies(i) tikrinti ar skaičius n dalijasi iš i. Kodėl traukiu šaknį? Nes sudėtinių skaičių daliklis būtinai bus nuo 2 iki jo paties natūralios šaknies (sakykim skaičiaus 25 mažiausias daliklis yra 5, o tai yra šaknis)

Pagrindinėje programos funkcijoje yra du kintamieji - Pirminiu skaičius, ir n skaičius. Kol kas jų reikšmės 0.
Aprašau ciklą, kurį reikia vykdyti tol kol Pirminiu bus 1000001. Baigus ciklą skaičių dalijam iš n reikšmės (kuri cikle buvo visada padidinama vienetu) ir dauginame iš 100. Gauname procentus. Aprašome išvestį, išreikšti procentus 2 skaičių tikslumu po kablelio.

Sukompiliiuojam. Matom tokią išvestį:
Cituoti:
1000001 / 15485867 * 100 = 6.46%
Process returned 0(0x0) execution time : 17.346 s

Kompiuteriui susidoroti su šia užduotimi prireikė visų 17 sekundžių (!).


Atsakymas: pirminiai skaičiai sudaro 6.46% nuo visų šioje aibėje esančių skaičių.

  • +1




Užsiregistravo: 2016-01-11, 12:40
Pranešimai: 63
Reputacija: +35
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-11, 19:13 
     
Sveikinu, Vytį M. gražiai išspręsta, 17s, tikras programuotojas. Galima naudotis interneto resursais: einame į puslapį https://primes.utm.edu/nthprime/index.php#piofx į pirmą langelį įrašome 1000001 ir spaudžiame "submit query" ir po kokių 2s sužinome, kad 1000001-asis
pirminis skaičius yra 15485867, tada 100000100/15485867=6,45750735.
Atsakymas: 6,46 %

Matematika - mokslų karalienė, skaičių teorija - matematikos karalienė. Pirminiai skaičiai
turi dar daug neatskleistų paslapčių: http://www.vartiklis.lt/science/math/prime-numbers.htm
  • 0




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-11, 20:03 
     
Ar tai reikėtų suprasti kaip pašaipą ? :)
17 sekundžių - čia ant mano naujo nešiojamo kompiuterio.
O laiką galima sutrumpinti ir iki 7.328 s, nes pamiršau įtraukti tai, jog užtenka tikrinti nelyginius skaičius.
Kodas:
bool ArPirminis(unsigned int skaicius) {
   if(skaicius >= 11) {
        if(skaicius % 2 == 0) return false;
        unsigned int saknis = sqrt(skaicius);
        // didziausias sudėtinio skaiciaus daliklis yra jo saknis, todėl apsiribosime sukdami cikla nuo 2 iki suapvalintos saknies.
        for(unsigned int i = 3; i <= saknis; i+= 2) {
            if(skaicius % i == 0) return false;
        }
    } else {
        if(skaicius == 2 || skaicius == 3 || skaicius == 5 || skaicius == 7) return true;
        else return false;
    }
    return true;
}

Dabar jau pakenčiamos 7 sekundės ant mano nešiojamo kompiuterio mažiausiai reikalaujant kompiuterio resursų.
O kad 2 sekundės truko toje svetainėje, tikėtina, kad jų serveriai kur kas galingesni.

Aišku Jūs galite naudotis interneto resursais, bet tai tebus atsakymas be sprendimo, ir jis Jums neatskrietų iš oro jei dingtų internetas (tarkim esate egzaminuojamas) :)
  • +1




Užsiregistravo: 2016-01-11, 12:40
Pranešimai: 63
Reputacija: +35
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-11, 21:04 
     
Vyčiui M.
Ne, aš niekada iš kolegų nesišaipau.
Priimu pastabą dėl interneto resursų.
Pagalvosiu, ar galima apsieiti be interneto.
Šiaip vis tiek mums reikia 1000001 -to pirminio skaičiaus,
kurį galime arba apskaičiuoti, arba gauti iš interneto arba
iš lentelių. Šiaip aš įsitikinęs, kad tavo programą būtų galima
dar žymiai paspartinti pasisėmus idėjų pvz iš čia: http://web.vu.lt/mif/v.stakenas/a+o/199 ... -19-46.pdf .
  • +1




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-11, 23:27 
     
Jeigu užtektu tikslumo, tai užtektu popieriaus ir pieštuko: https://en.wikipedia.org/wiki/Prime_num ... ime_number.
  • 0




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-12, 00:05 
     
Padarysiu Code Review Vyčio kodui. :)

1. Ar būtinas toks komentaras?
Kodas:
//funkcija skirta patikrinti ar skaicius pirminis
bool ArPirminis(unsigned int skaicius) {

Manau, bool ArPirminis visiškai atsako į klausimą, kam skirta ši funkcija. Kitaip sakant, kodo perkomentuoti nereikėtų.

2. Toliau keistai atrodo, kad dedi tokius if'us kaip:
if(skaicius == 2 || skaicius == 3 || skaicius == 5 || skaicius == 7) return true;
Ar tikrai to reikia? Nes jeigu paimsi skaičiaus N šaknies sveikąją dalį, tai tos paminėtos sąlygos nebūtinos. Štai, tarkime, iš skaičiaus 2 sveikoji dalis yra 1. O jeigu pradėsi ciklą sukti nuo 2, tai ciklo nesuks ir automatiškai grąžinsi true. Su trimis tas pats. Su keturiais jau suksi vieną atvejį, t.y. dviejų, ir gausi false. Su penkiais gausi tą patį, kad penki yra pirminis. Su šešiais užteks dvejeto. Su septyniais irgi panašiai. Su 8 dvejeto pakaks. Su devyniais gausi tris kaip sveikąją dalį ir to pakaks nustatyti, ar skaičius pirminis, ar ne. Kitaip sakant, reikia vengti visokių base case'ų. Kartais jie neišvengiami (taikant rekursiją - netgi būtini, nes kitaip tavo funkcija/metoda išvis nebaigs darbo), bet šis atvejis nėra tas kartas, kai negali algoritmo realizuoti tiesiog homogeniškai.

3. O čia jau main programos defektas bus:
Cituoti:
} while(Pirminiu < 1000001);

Ar tikrai kažkur vidury failo reikia įkalti tokią konstantą kaip 1000001? Gal geriau ją įvardinti pradžioje, pavyzdžiui, "Riba", ir tą vėliau kažkur pritaikyti? Tiesiog programuotojams niekada nepatinka, kai jie turi naršyti kodą ir galvoti, stebėdamiesi, ką tas reiškia, ką anas reiškia. Jiems patinka išsiaiškinti visus dalykus iškart. Tai yra, tavo kodas turi būti skaitomas, įskaitomas, prasmingai įvardytais kintamaisiais ar konstantomis. Na nebent jau dirbtum prie kokio greitintuvo, kur kodo eilutės vieta turi didelę svarbą. Tačiau abejoju, ar net ir ten tas turėtų tokią didelę reikšmę, ypač žinant, kad kompiliatoriai kodą šiais laikais taip apdirba, optimizuoja, kad net ir retas senior'as apie tai mažai ką žino.

4. Patartina visur be išimties naudoti skliaustus, t.y. "{"/"}". Aišku, geri programuotojai tą supranta, bet kode homogeniškumas yra irgi svarbus dalykas. O pagrinde tas būtų dėl tavęs, nes nėra garantijos, kad visada 100% žinosi, ar reikia dėti skliaustus, ar ne. O jeigu padėsi, tokio klausimo net ir nekils. O jeigu kils toks klausimas, tai ne iškart, o tik po ilgo prasikeikimo, kad kažkas lūžta ir veikia ne taip kaip turi veikti. Būtent į šį dalyką atkreipiau dėmesį:
Cituoti:
if(skaicius % i == 0) return false;


5. Pradėk domėtis apie TDD/BDD ir tą taikyti praktiškai, t.y. rašyti modulių testus pirma, o tada realizuoti kodą. Dengti funkcionalumą modulių testais yra tobula praktika, ir jos įvaldymas užtikrina galimybę pradžioje parašyti ne tokį kokybišką kodą, tačiau pilnai atitinkantį visus reikalavimus bei kartu saugią galimybę vykdyti kodo pertvarkas (angl. refactoring). Vėliau, žinoma, kai įgysi patirties, tu modulių testus sugebėtum jau realizuoti kokybiškomis abstrakcijomis iškart. Tačiau yra daug blogiau bandyti sukurti kažkokias "kokybiškas abstrakcijas", nesant jokiems testams. Čia jau ne žmogui spręsti, kas yra teisinga, o kas ne, nes žmogaus protas ribotas, todėl į tai reikia atsižvelgti net ir programuotojams, rašantiems savo kodą.

O bendrai kodas greičiausiai veikia kaip turėtų, tad viskas kaip ir gerai. Ir turbūt tokioje situacijoje tokie dalykai, kuriuos paminėjau, mažai reikšmės teturi, tačiau, esant tokioms užduotėlėms, kaip tik geriau pradėti taikyti visus geriausius principus, kokie tik yra, iš anksto, nes vėliau, kai jau bus dideli projektai, be didelio žinių bagažo tą daryti gali būti keblu.

Ir galiausiai pasiūlymas, kaip pagerinti algoritmą, kuris tikrina, ar skaičius yra pirminis, dar labiau. Nebūtina atmesti viską kas du elementus. Gali ir kas tris, ir kas penkis, ir kas septynis vienu metu, t.y. gali taikyti Eratosteno Rėtį. Kaip tą apsirašysi dinamiškai, kad panaudotum minimalų kiekį atminties, čia jau bus tam tikras challeng'as. O dar geriau būtų, kad, vykdydamas tokią užduotį, pritaikytum ir asimptotinę algoritmo analizę. Pavyzdžiui, asimptotiškai išsinagrinėk savo algoritmo vykdymo laiko augimo santykį, didėjant ribai (angl. growth ratio) šiuo metu ir siek tą pagerinti pagerintame algoritme.

buntu1117 rašė:
<...>
dar žymiai paspartinti pasisėmus idėjų pvz iš čia: http://web.vu.lt/mif/v.stakenas/a+o/199 ... -19-46.pdf .

Nagi nagi, kam gi žmogui mesti tokį griozdą iškart? Suprantu, 28 puslapiai nedaug, bet keli žodžiai, galintys nukreipti link neblogo sprendimo, yra dar trumpiau.
  • 0



Vartotojo avataras

Užsiregistravo: 2014-10-05, 12:06
Pranešimai: 65
Reputacija: +59
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-12, 06:43 
     
Artojui
Darosi įdomu, prisijungia vis daugiau žmonių. Soriukas gal tikrai nereikėjo 28 puslapių, bet ten gražus straipsnis, maniau, kad nepakenks. Be to galima pasidomėti,
kokį algoritmą tie "interneto resursai" naudoja https://primes.utm.edu/nthprime/algorithm.php .
  • 0




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-12, 11:43 
     
Aha... kokios aistros verda.
Žinot, aš kodo nerašiau, kad pasigirti jo gražumu, nors taip, reikėtų gerinti praktiką. Aš greitai pasirašiau juodraštį, patikrinau, rezultatas yra, kaip ir sprendimas automatiškai :)
  • +1




Užsiregistravo: 2016-01-11, 12:40
Pranešimai: 63
Reputacija: +35
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-12, 13:33 
     
Paprasciausias budas ir yra naudotis resursais kurie tau prieinami. Gali mastyti apie uzduoti kaip apie egzamina ir nesinaudot niekuo, bet egzaminas yra tavo ziniu patikrinimas, o realiuose uzdaviniuose, kuriuos meginama isspresti galima naudotis visa prieinama informacija ir metodais. Tiesa, kartais info, kuria pasiimame is kitu saltiniu, nebutinai yra teisinga ar tiksli, tai ta taip pat reik ivertinti.

buntu1117: Interneto resursai naudoja greiciausiai jau suskaiciuotus duomenis, kuriuos saugo duomenu bazese, todel jiems kiekviena kart skaiciuot nereik.

Ne visi moka programuot, del to be isoriniu resursu uzdavinys butu tokiems zmonems neissprendziamas.

As pats ta uzdavini issprendziau su PHP kodo versija:
----------------------------------------------------
function is_prime($number) {
$last = ceil(sqrt($number));
for ($i = 2; $i <= $last; $i++)
if ($number%$i == 0)
return false;
return true;
}

$prime = 0;
$currentNumber = 0;
while ($prime <= 1000000)
if (is_prime(++$currentNumber))
$prime += 1;

$answer = $prime * 100 / $currentNumber;
print round($answer, 2);
----------------------------------------------------
  • 0




Užsiregistravo: 2013-05-31, 15:51
Pranešimai: 17
Reputacija: +1
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-12, 14:57 
     
Mes kiekvienas naudojamės "interneto resursais" kuris jums matau labai užstrigo, bet pasiskaitykite konkurso sąlygas - neužtenka vien atsakymo, ištraukiamo iš oro, reikia ir sprendimo. Kaip jį gaust - jūsų reikalas, jums nenurodinėja.

"Interneto resursų" svetainėje naują skaičių apskaičiuoja (apie 2 sekundes ir pan), o seną, jau naudotą, traukia iš duomenų bazės akimirksniu.

@Baltas, perdėm trumpas ir sumakliavotas kodelis, išknistas ko gero iš interneto ir nepatikrintas.
Aš pabandžiau išgauti laiką per kiek laiko jį įvykdys.. ir ką manai?

Aš tavo kodo gabaliuką įsirašiau į failą milijonas ir viena naktis.php su menkais pakeitimais kad rodytų laiką.

Cituoti:
Fatal error: Maximum execution time of 30 seconds exceeded in /var/www/main/html/milijonas ir viena naktis.php on line 5

line 5:
Kodas:
for ($i = 2; $i <= $last; $i++)

:P
  • +1




Užsiregistravo: 2016-01-11, 12:40
Pranešimai: 63
Reputacija: +35
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-13, 11:56 
     
@Vytis M. aisku galima optimalesniu algoritmu rasti.
Galima tiesiog tiktinti ar skaicius nesidalina is nei vieno pirminio skaiciaus pries tai kitus praleidziant,
tai gali praleisti ne tik kas antra bet ir kas trecia, kas penkta, kas septinta, kas 11 ir t.t.
  • 0




Užsiregistravo: 2013-05-31, 15:51
Pranešimai: 17
Reputacija: +1
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-13, 17:19 
     
O kaip jums šitas algoritmas? http://www.paul-scott.com/nth-prime.php
  • 0




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
  Standartinė   Parašytas: 2016-01-13, 18:13 
     
Jau rašiau, kad "jeigu užtektu tikslumo, tai užtektu popieriaus ir pieštuko: https://en.wikipedia.org/wiki/Prime_num ... ime_number ". Tai dabar nepatingėjau, ir
įstačiau n=1000001 į [27] formulę kuri yra skyriuje "Approximations for the nth prime number" . Gavosi P(1000001)/1000001=15.4838.
Tada 1000001/P(1000001)*100=6.458 arba 6.46% (čia P(1000001) yra 1000001 -as
pirminis skaičius. Tai užteko kalkuliatoriaus su natūriniu logaritmu. Štai jums ir šiuolaikiniai kompiliatoriai :)
  • 0




Užsiregistravo: 2015-12-10, 17:21
Pranešimai: 32
Reputacija: +3
   
 
Į viršų
Rodyti paskutinius pranešimus:
Rūšiuoti pagal
 


Naujos temos kūrimas Atsakyti į temą  [ 14 pranešimai(ų) ] 

Visos datos yra UTC + 2 valandos [ DST ]


Dabar prisijungę

Vartotojai naršantys šį forumą: Registruotų vartotojų nėra ir 4 svečių


Jūs negalite kurti naujų temų šiame forume
Jūs negalite atsakinėti į temas šiame forume
Jūs negalite redaguoti savo pranešimų šiame forume
Jūs negalite trinti savo pranešimų šiame forume
 

Ieškoti:
Pereiti į:
 
 

Reputation System ©'