Echipa Learn2Code - 30.05.2020 - Educație

obțineți

În blogul anterior, ne-am ocupat de numere prime. Am arătat un eșantion al unui program care a recunoscut dacă numărul introdus este sau nu un număr prim. Astăzi, aș dori să vă arăt, folosind un exemplu specific, cum îl rezolvă subtitrarea acestui blog și, astfel, să aflați numerele prime pe un interval definit de numere naturale, în timp ce limita superioară a intervalului va fi introdusă de utilizator. Limita inferioară a intervalului va fi 0, care desigur nu este un număr prim, deoarece numărul prim este divizibil cu 1 și el însuși. Rezultă că 0, deși divizibil cu 1, nu este divizibil cu 0 deoarece expresia 0/0 nu este definită. Deși s-ar crede că rezultatul ar putea fi egal cu numărul 1, nu este cazul. Zero pur și simplu nu poate diviza nicio expresie.

Hai să mergem puțin mai departe acum. În ultimul blog am concluzionat că nici 1 nu este un număr prim, deoarece este divizibil cu 1 și de la sine, care este din nou numărul 1. Și 1 și 1, nu există doi factori diferiți.

Condiția care exclude 0 și 1 nu sunt numere prime este, desigur, abordată în programul meu. Dar ce se întâmplă cu alte numere care se află pe intervalul a cărui limită superioară a fost introdusă de utilizator. Un algoritm simplu numit sită Eratostene ne va oferi un răspuns direct la această întrebare.

Eratostene din Cirena a fost, printre altele, un matematician grec care a lucrat în Alexandria antică timp de aproximativ 280 de ani. î.Hr. Pe lângă calculul perimetrului pământului, el a definit și un algoritm pe care l-am implementat pentru dvs. în limbajul de programare de nivel superior C++.

Înainte de a analiza în detaliu un program scris în C ++, prezentăm algoritmul pe următoarele numere naturale: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.

Deci avem o secvență care este definită la început de numărul 0 inclusiv și la sfârșit de numărul 20, care este deja în afara intervalului de secvență. Și aceasta este exact limita superioară menționată mai sus.

Vom plasa această secvență într-un tabel cu un rând, care în programul meu va fi reprezentat de un vector de numere întregi (vector int).

Ca o remarcă, vom folosi clasa bibliotecii STL, care este un vector. Un vector este o entitate care este mai bine manipulată decât o matrice. De aceea, acest articol este destinat acelor cititori care sunt cel puțin oarecum familiarizați cu problema vectorilor. Pentru cei care nu sunt familiarizați cu problemele legate de vector, vă recomand să studiați mai întâi tipul size_t, clasa vectorială și metoda membru a clasei vector push_back (). Apoi, cu zel, acești cititori se pot îmbarca pe acest blog.

Revenim însă la problema noastră definită. Deci, să avem secvența menționată:

În acest tabel, indicăm în albastru faptul că 0 și 1 nu sunt numere prime:

Prin urmare, nu vom reveni la indexurile pe care se află numerele 0 și 1. Să ne uităm la numărul 2. Știm că acest număr este cel mai mic număr prim din acest interval, care este condiția principală pentru a rezolva subtitrarea acestui blog. Vom testa celelalte elemente (numere) ale secvenței cu o sită Eratosten - adică vom elimina acum multiplii numărului 2. Deoarece numărul 3 nu este multiplu al numărului 2, va trece prin sita Eratosten . Deci, să scriem multiplii numărului 2 în roșu în tabel.

Vedem că într-un singur pas algoritmul (sita Eratosten) a eliminat numerele 4, 6, 8, 10, 12, 14, 16 și 18. În același timp, nu vom reveni în niciun fel la indicele numărului 2. Din tabelul anterior este, de asemenea, evident că numărul 3 este un număr prim. Să scoatem acum multiplii din tabel și să marcăm acest fapt în verde.

În pasul următor, algoritmul a eliminat numărul 6, 9, 12, 15, 18, care nu sunt primii. Da, am marcat și cu verde câteva numere care au fost eliminate în pasul anterior cu un multiplu de 2. Cu toate acestea, acest lucru nu schimbă faptul că acest pas a eliminat alte numere din secvență, care sunt numerele: 9 și 15. După efectuare pasul menționat vedem că numărul 5 a rămas marcat cu galben. Prin urmare, numărul 5 este un număr prim, deoarece a trecut printr-o sită Eratosten. Dacă eliminăm multiplii numărului 5 în pasul următor, vom constata că numerele 10 și 15 au fost deja eliminate de un multiplu al unui alt număr. Deci, când se va termina algoritmul? Acesta va fi cazul până când vom ajunge efectiv la numărul 19. Numărul 19 nu mai are sarcina de a elimina niciun multiplu, deoarece nu există nimic în spatele lor în tabelul nostru. Obținerea indicelui său printr-o anumită variabilă de interacțiune este o condiție pentru sfârșitul algoritmului, deși nimic nu se schimbă în starea numerelor prime sau a numerelor eliminate.

Să selectăm acum toate numerele marcate cu galben din tabelul nostru:

Vom rămâne cu numere care sunt cu siguranță numere prime. Așa că am ajuns la rezultatul algoritmului nostru, care sunt numerele 2, 3, 5, 7, 11, 13, 17 și 19. Pentru a verifica, puteți compara aceste numere cu numerele prime date în alte surse, dar veți face obține cu siguranță același rezultat.

Să trecem acum în detaliu la următorul cod sursă scris în C ++, care este o implementare a explicației verbale a algoritmului menționat mai sus. Limbajul C ++ ne oferă alte posibilități de eficientizare a calculului. Sunt de ex. salturi în program pe care le putem efectua folosind cuvintele cheie break și continuare. Dar mai multe despre asta mai târziu. Să punem ordine din prima linie.

Pe linia 1, avem fișierul antet iostream.h adăugat de directiva preprocesorului. Aceasta înseamnă că conținutul fișierului iostream.h este inserat pe această linie. În mod similar, pe liniile 2 și 3, inserăm fișierele antet vector.h și string.h cu aceeași directivă. Linia 4 declară că vom folosi spațiul de nume std în întregul cod sursă care alcătuiește un fișier, deci nu trebuie să-l apelăm în mod explicit în funcția principală atunci când avem nevoie de o clasă sau obiect din acesta. Un exemplu ar putea fi un obiect cin sau cout. Pe linia 6 definim funcția principală și apoi pe linia 7 începe corpul acesteia. Pe linia 8 declarăm o variabilă de tip integral, în special char cu identificatorul variabilei c_end. Această variabilă reprezintă un caracter care decide dacă se termină sau nu bucla externă după executarea algoritmului propriu al lui Eratosten. De aceea, pe linia 89, utilizatorul este solicitat să apese tasta a sau n. Dacă elimină n, programul continuă cu următoarea buclă a buclei while. Dacă este apăsată o altă tastă, programul se termină.

Linia 9 definește o nouă instanță a șirului de clase cu identificatorul sz, care este inițializată la o valoare goală.

După această inițializare, linia 10 arată declarația variabilei iSZ la tipul int fără inițializare ulterioară.

Pe linia 11, declarăm o variabilă de tip bool, care va stoca informații în program, indiferent dacă utilizatorul a răspuns la solicitarea programului introducând o valoare validă (adică valoare întreagă), care va fi stocată în variabila iSZ. Dacă utilizatorul introduce informații de intrare valide din fereastra aplicației consolei, variabila is_size_t este setată la true, în caz contrar (cu excepția cazului în care utilizatorul introduce o valoare validă din intervalul întreg), variabila is_size_t este setată la false. Variabila is_size_t este inițial inițiată la fals pe linie. Aceasta reprezintă o stare în care variabila iSZ nu a fost încă inițializată și acest lucru este de fapt adevărat. Rândul 13 arată cuvântul cheie către. Aceasta înseamnă că corpul buclei începe cu un timp, în care condiția este o comparație a conținutului variabilei c_end cu caracterul n (vezi linia 95).

Când programul continuă, ajunge la linia 14, care deschide corpul buclei menționate într-un timp, urmată de o buclă while pe linia 15, ceea ce înseamnă o buclă cu o condiție la începutul fiecărui ciclu. Aici programul întreabă (compară) dacă valoarea false este stocată în variabilă. Dacă da, programul continuă cu o ramură pozitivă și solicită utilizatorului linia 17 să introducă limita superioară a sitei Eratosten. Această valoare nu va fi luată în considerare la testarea unui număr prim. Pe linia 18, intrarea introdusă de utilizator este încărcată în variabila (obiect) sz, care este o nouă instanță a clasei șir. Încărcarea se efectuează folosind metoda getline (), care are doi parametri, și anume obiectul cin și obiectul sz.

Linia 20 este urmată de un blog de cod de încercare și captură, care este utilizat pentru a recunoaște validitatea valorii introduse de utilizator în obiectul sz. În ramura try, programul încearcă să convertească valoarea obiectului sz la valoarea unui număr întreg, care reprezintă lungimea intervalului pe care căutăm toate numerele prime prin sita Eratosten. Funcția stoi este utilizată pentru această conversie, care pe scurt înseamnă șir la întreg (în limba slovacă șir la întreg). După conversie, se testează pe linia 24 dacă utilizatorul nu a introdus numărul de intrare 0. Dacă da, programul setează variabila is_size_t la fals și sare la condițiile reevaluate ale buclei următoare în timp ce folosește declarație continuă. Deoarece în variabila is_size_t este din nou fals programul continuă în bucla while, când pe linia 17 utilizatorul este solicitat din nou să introducă limita superioară a intervalului sitei Eratosten. În acest fel, programul poate fi buclat până când utilizatorul introduce o valoare validă la intrarea aplicației consolei.

Să vedem acum când utilizatorul nu introduce o valoare din gama de tip integral (de exemplu, o valoare nevalidă "hsfu"). Probabil știți deja că aceasta nu este o valoare de tip integral, ci caractere fără sens pe care utilizatorul le poate introduce, deoarece aceste valori pot fi atribuite tipului de șir, dar această valoare nu poate fi convertită într-o valoare întreagă. De aceea, există un bloc de blocare pe linia 34 în programul nostru, care prinde această excepție. Și ce se va întâmpla de fapt în continuare? Dar la fel ca în cazul introducerii 0, înseamnă că valoarea false este setată la variabila is_size_t și programul sare cu declarația continue la începutul buclei while, unde condiția este evaluată din nou pentru a continua solicitând utilizatorului pentru a introduce o valoare validă la limita superioară. Sita lui Eratosten și întrucât negarea valorii din variabila is_size_t este adevărată, programul o va face oricum. Astfel, programul va cere utilizatorului să introducă o valoare validă.

Dacă utilizatorul introduce o valoare validă, programul sare la ramura try, unde apoi sare la ramura negativă a instrucțiunii if (clauza else de pe linia 29), unde valoarea is_size_t este deja setată la true. Astfel, în această buclă, programul sare din buclele while pentru că nu mai îndeplinește condiția pentru următoarea execuție a buclei.

Când utilizatorul a introdus o limită superioară validă a sitei Eratosten, aceste informații pot fi folosite pentru a aloca un vector de lungime iSZ (alocare vectorială cu identificatorul vNumberVector), care este implementat pe linia 41. Liniei 42 i se alocă un vector de lungime 0 (vector cu identificatorul vPrimeVektor). În acest vector vom stoca numere prime care trec prin sita Eratosten. Vectorul are o lungime de 0, deoarece este posibil să adăugați un număr prim după el până când partea algoritmului decide dacă numărul selectat din vectorul vNumberVector este sau nu un număr prim.

Pe linia 44, începe bucla for, care în ciclurile sale individuale este controlată de o variabilă iterativă i, care este incrementată în fiecare ciclu până când atinge valoarea iSZ. Aceasta pentru bucla din corpul său umple vectorul vNumberVector cu numere de la 0 la 19 (deoarece limita superioară definită în exemplu este 20).

Dacă restul după împărțire este egal cu zero, numărul testat nu este un număr prim, ceea ce înseamnă că setăm variabila steagului la fals, sărim la sfârșitul buclei for folosind cuvântul cheie break (variabila de iterație j). În acest caz, nimic nu este stocat în vectorul vPrimeVector deoarece variabila valoare este stocată în variabila flag. bucla exterioară se termină atunci când sunt testate toate numerele stocate în vectorul vNumberVector. Ultimul număr testat este deci numărul 19.

După testarea tuturor numerelor, numerele prime sunt scrise în fereastra aplicației consolei (vezi liniile 78 până la 83), pentru care folosim obiectul cout și bucla for. Desigur, intrarea include și mutarea cursorului pe o nouă linie pe linia 85.

Apoi, un mesaj este scris în fereastra aplicației consolei pentru a întreba utilizatorul dacă dorește să renunțe la program sau nu. Dacă utilizatorul apasă tasta n, programul continuă și utilizatorul este solicitat să reintroducă limita superioară a sitei Eratosten, cu valoarea is_s din nou stocată false.

Dacă utilizatorul suprimă o altă tastă (ceea ce înseamnă terminarea programului), programul sare după bucla exterioară while la linia 97, funcția principală returnează 0 la sistemul de operare și întregul program se termină. Permiteți-mi să vă reamintesc că pe linia 98 există o paranteză dreaptă de program care închide corpul funcției principale.

Listarea programului main.cpp

Fereastra de aplicare a consolei la limita superioară a sitei Eratosten 20

Se poate vedea în figură că numerele prime rezultate sunt aceleași cu numerele prime pe care le-am calculat analitic (a se vedea ultimul tabel din text).

Sper că vă interesează exemplul și programul cu sită Eratosten, tot ce trebuie să faceți este să îl implementați pe computer.

Acest blog a fost scris de Marek ŠURKA, lector de cursuri C ++. Dacă aveți întrebări, scrieți-le în comentarii.

Învățăm oamenii să proiecteze, să creeze site-uri web și să programeze. Puteți găsi cursurile noastre cu normă întreagă în mai multe orașe din Slovacia și cu ajutorul cursurilor online puteți învăța din confortul casei dvs.