Learn2Code team - 2020.05.30 - Oktatás
Az előző blogban prímszámokkal foglalkoztunk. Mutattunk egy olyan programmintát, amely felismerte, hogy a beírt szám prímszám-e vagy sem. Ma egy konkrét példa segítségével szeretném megmutatni, hogyan oldja meg ennek a blognak az alcíme, és így megtudhatja a prímszámokat a természetes számok meghatározott intervallumán, miközben az intervallum felső határát a felhasználó. Az intervallum alsó határa 0 lesz, ami természetesen nem prímszám, mert a prímszám osztható az 1 számmal és önmagával. Ebből következik, hogy a 0, bár osztható 1-vel, nem osztható 0-val, mert a 0/0 kifejezés nincs meghatározva. Bár azt gondolnánk, hogy az eredmény megegyezhet az 1-es számmal, ez nem így van. A nulla egyszerűen nem oszthat meg egyetlen kifejezést sem.
Menjünk most egy kicsit tovább. Az utolsó blogban arra a következtetésre jutottam, hogy még az 1 sem prímszám, mert osztható 1-gyel és önmagával, ami megint az 1. szám. És 1 és 1, nincs két különböző tényező.
A feltétel, amely kizárja a 0 és 1 nem prímszámokat, természetesen a programomban szerepel. De mi van a többi számmal, amely azon az intervallumon található, amelynek felső határát a felhasználó adta meg. Az Eratosthene szita nevű egyszerű algoritmus közvetlen választ ad erre a kérdésre.
A cyrene-i Eratosthenes többek között görög matematikus volt, aki az ókori Alexandriában dolgozott mintegy 280 évig. Krisztus előtt. A föld kerületének kiszámítása mellett meghatározott egy algoritmust is, amelyet a C felsőbb programozási nyelvben implementáltam az Ön számára.++.
Mielőtt részletesen elemeznénk egy C ++ nyelven írt programot, megmutatjuk az algoritmust a következő természetes számokon: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Tehát van egy olyan szekvenciánk, amelyet az elején a 0 szám, a végén pedig a 20 szám határoz meg, amely már kívül esik a szekvenciaintervallumon. És pontosan ez a fent említett felső határ.
Ezt a sorrendet egy egysoros táblázatba helyezzük, amelyet programomban egész számok vektorával (int vektor) fogunk ábrázolni.
Megjegyzésként az STL könyvtár osztályt fogjuk használni, amely egy vektor. A vektor olyan entitás, amelyet jobban lehet kezelni, mint egy tömböt. Éppen ezért ez a cikk azoknak az olvasóknak szól, akik legalább némileg ismerik a vektorok kérdését. Azok számára, akik nem ismerik a vektorproblémákat, javasoljuk, hogy először tanulmányozzák a size_t típust, a vektorosztályt és a vektor push_back () osztály tagmódszerét. Ezután buzgón ezek az olvasók belekezdhetnek ebbe a blogba.
De térjünk vissza a meghatározott problémánkra. Tehát legyen az említett sorrend:
Ebben a táblázatban kék színnel jelezzük azt a tényt, hogy a 0 és az 1 nem prímszám:
Ezért nem térünk vissza azokhoz az indexekhez, amelyeken a 0 és 1 szám található. Nézzük a 2. számot. Tudjuk, hogy ez a szám a legkisebb prímszám ebben az intervallumban, ami az elsődleges feltétel ahhoz, hogy megoldjuk a blog alcímét. Eratosten szitával teszteljük a szekvencia többi elemét (számát) - vagyis eltávolítjuk a 2 szám többszörösét. Mivel a 3 szám nem a 2-es szám többszöröse, áthalad az Eratosten szitán . Tehát írjuk a táblázatban a 2-es szám többszöröseit pirossal.
Látjuk, hogy egy lépésben az algoritmus (Eratosten szita) eltávolította a 4, 6, 8, 10, 12, 14, 16 és 18 számokat. Ugyanakkor semmiképpen sem térünk vissza a 2-es szám indexéhez. Az előző táblázatból az is nyilvánvaló, hogy a 3-as szám prímszám. Most távolítsuk el a többszöröseit az asztalról, és jelöljük zölddel ezt a tényt.
A következő lépésben az algoritmus eltávolította a 6, 9, 12, 15, 18 számokat, amelyek nem prímszámok. Igen, zöld színnel is megjelöltünk néhány olyan számot, amelyeket az előző lépésben a 2-es többszörösével eltávolítottunk. Ez azonban nem változtat azon a tényen, hogy ez a lépés más számokat is eltávolított a sorozatból, amelyek számok: 9 és 15. az említett lépést végrehajtva azt látjuk, hogy az 5-ös szám sárga színnel maradt. Az 5-ös szám tehát prímszám, mert átjutott egy Eratosten szitán. Ha a következő lépésben eltávolítjuk az 5 szám többszöröseit, azt találjuk, hogy a 10 és 15 számokat már eltávolította egy másik szám többszöröse. Tehát mikor lesz vége az algoritmusnak? Ez addig lesz így, amíg ténylegesen el nem érjük a 19-es számot. A 19-es számnak már nem feladata többszörös eltávolítása, mert a táblánkban nincs mögöttük semmi. Az index elérése egy bizonyos interakciós változóval az algoritmus végének feltétele, bár a prímszámok vagy az eltávolított számok állapotában semmi sem változik.
Válasszuk ki most az összes sárga színnel jelölt számot a táblázatunkból:
Maradnak számok, amelyek minden bizonnyal prímszámok. Tehát elértük algoritmusunk eredményét, amely a 2, 3, 5, 7, 11, 13, 17 és 19 szám. Ennek ellenőrzéséhez összehasonlíthatja ezeket a számokat a más forrásokban megadott prímszámokkal, de mindenképpen ugyanazt az eredményt kapja.
Most térjünk ki részletesen a következő C ++ nyelven írt forráskódra, amely az algoritmus fent említett szóbeli magyarázatának megvalósítása. A C ++ nyelv más lehetőségeket kínál számunkra a számítás hatékonyabbá tételéhez. Ők pl. ugrik a programba, amelyet a break és folytatás kulcsszavakkal végre tudunk hajtani. De erről később. Tegyük rendbe az első sort.
Az 1. sorban megvan az iostream.h fejlécfájl, amelyet az előprocesszor irányelv ad hozzá. Ez azt jelenti, hogy az iostream.h fájl tartalma beillesztésre kerül erre a sorra. Hasonlóképpen, a 2. és a 3. sorra ugyanezzel az irányelvvel illesszük be a vector.h és string.h fejlécfájlokat. A 4. sor kijelenti, hogy az egy állományt alkotó teljes forráskódban az std névteret fogjuk használni, ezért nem kell ezt kifejezetten a fő függvényben hívnunk, ha osztályra vagy objektumra van szükségünk belőle. Ilyen lehet például egy cin vagy cout objektum. A 6. vonalon meghatározzuk a main függvényt, majd a 7. vonalon kezdődik a teste. A 8. sorban deklarálunk egy integrált típusú változót, konkrétan char-t a c_end változó azonosítójával. Ez a változó egy olyan karaktert képvisel, amely eldönti, hogy megszakítja-e a külső hurkot, vagy sem Eratosten saját algoritmusának végrehajtása után. Ezért a 89-es vonalon a felhasználót arra kérik, hogy nyomja meg az a vagy n gombot. Ha elnyomja az n értéket, a program folytatja a while ciklus következő ciklusát. Ha megnyom egy másik gombot, a program befejeződik.
A 9. sor az osztályazonosító karakterlánc új példányát definiálja sz azonosítóval, amelyet inicializálunk egy üres értékre.
Ezen inicializálás után a 10. sor további inicializálás nélkül mutatja az iSZ változó deklarációját az int típushoz.
A 11. sorban deklarálunk egy bool típusú változót, amely információt tárol a programban, függetlenül attól, hogy a felhasználó egy érvényes érték (azaz egész érték) megadásával válaszolt-e a program promptjára, amelyet az iSZ változó tárol. Ha a felhasználó érvényes bemeneti információkat ad meg a konzolalkalmazás ablakából, akkor az is_size_t változó értéke true, máskülönben (hacsak a felhasználó nem ad meg érvényes értéket az egész tartományból) az is_size_t változó értéke false. Az is_size_t változó kezdetben hamisra inicializálódik a sorban. Ez azt az állapotot jelenti, hogy az iSZ változót még nem inicializálták, és ez valójában igaz. A 13. sorban a kulcsszó látható. Ez azt jelenti, hogy a hurok törzse egy idővel kezdődik, amelyben a feltétel összehasonlítja a c_end változó tartalmát az n karakterrel (lásd a 95. sort).
Amikor a program folytatódik, a 14. sorhoz jut, amely egy időre kinyitja az említett hurok testét, majd egy rövid hurok következik a 15. vonalon, ami egy ciklust jelent, amelynek feltételei vannak az egyes ciklusok elején. Itt kérdezi (összehasonlítja) a program, hogy a hamis érték tárolva van-e a változóban. Ha igen, akkor a program pozitív ággal folytatódik, és a 17. vonalon kéri a felhasználót, hogy adja meg az Eratosten szita felső határát. Ezt az értéket nem vesszük figyelembe egy prímszám tesztelésekor. A 18. sorban a felhasználó által beírt bemenet betölti az sz változóba (objektum), amely a karakterlánc osztály új példánya. A betöltés a getline () módszerrel történik, amelynek két paramétere van, nevezetesen a cin objektum és az sz objektum.
A 20. sort egy try and catch kódblog követi, amely felismeri a felhasználó által az sz objektumba beírt érték érvényességét. A try ágban a program megpróbálja az sz objektumban szereplő értéket egy egész szám értékévé konvertálni, amely annak az intervallumnak a hosszát képviseli, amelyen az összes prímszámot az Eratosten szitán keressük. A konverzióhoz a stoi függvényt használják, ami röviden stringet egész számra (szlovákul string egészre) jelent. Az átalakítás után a 24. sorban tesztelik, hogy a felhasználó nem írta-e be a 0. számot a bemenetbe. Ha igen, akkor a program az is_size_t változót hamisra állítja, és a következő while ciklus átértékelt feltételeire ugrik a folytassa a nyilatkozatot. Mivel az is_size_t változó ismét hamis, a program a while ciklusban folytatódik, amikor a 17. vonalon a felhasználót ismét arra kérik, hogy adja meg az Eratosten szita intervallumának felső határát. Ily módon a program addig ciklizálható, amíg a felhasználó érvényes értéket nem ír be a konzolalkalmazás bemenetén.
Nézzük meg most, amikor a felhasználó nem ad meg értéket az integrált típustartományból (pl. Érvénytelen "hsfu" érték). Valószínűleg már tudja, hogy ez nem egy integrált típusú érték, hanem értelmetlen karakterek, amelyeket a felhasználó megadhat, mivel ezek az értékek hozzárendelhetők a karakterlánc típusához, de ez az érték nem konvertálható egész értékre. Ezért van programunkban egy fogási blokk a 34. vonalon, amely megfogja ezt a kivételt. És mi fog történni ezután? De ugyanúgy, mint a 0 beírása esetén, ez azt jelenti, hogy a hamis érték az is_size_t változóra van állítva, és a program a folytatás utasítással a while ciklus elejére ugrik, ahol a feltétel ismételten kiértékelődik a folytatáshoz a Eratosten szitája, és mivel az is_size_t változóban az érték negációja igaz, a program úgyis megteszi. Így a program arra kéri a felhasználót, hogy adjon meg egy érvényes értéket.
Ha a felhasználó érvényes értéket ad meg, akkor a program a try ágra ugrik, ahol az if utasítás negatív ágára ugrik (else záradék a 29. soron), ahol az is_size_t értéke már igazra van állítva. Így ebben a ciklusban a program kiugrik a while ciklusból, mert már nem felel meg a ciklus következő végrehajtásának feltételének.
Amikor a felhasználó megadta az Eratosten szita érvényes felső határát, ez az információ felhasználható egy iSZ hosszúságú vektor kiosztására (vektorelosztás vNumberVector azonosítóval), amely a 41-es vonalon valósul meg. (vektor a vPrimeVektor azonosítóval). Ebben a vektorban tárolni fogjuk az Eratosten rostán áthaladó prímszámokat. A vektor hossza 0, mert csak akkor lehet hozzáadni egy prímszámot, ha az algoritmus egy része eldönti, hogy a vNumberVector vektorból kiválasztott szám prímszám-e vagy sem.
A 44. vonalon kezdődik a for ciklus, amelyet az egyes ciklusaiban egy iteratív i változó vezérel, amelyet minden ciklusban növekszünk, amíg el nem éri az iSZ értéket. Ez a testben lévő hurok számára kitölti a vNumberVector vektort 0 és 19 közötti számokkal (mert a példában definiált felső határ 20).
Ha az osztás után fennmaradó rész nulla, akkor a tesztelt szám nem prímszám, ami azt jelenti, hogy a flag változót hamisra állítjuk, a break kulcsszóval (j iterációs változó) a u ciklus végére ugrunk. Ebben az esetben semmi nincs tárolva a vPrimeVector vektorban, mert az értékváltozó a flag változóban van tárolva. a hurok külső része akkor fejeződik be, amikor a vNumberVector vektorban tárolt összes számot teszteljük. Az utolsó tesztelt szám tehát a 19-es.
Az összes szám tesztelése után a prímszámokat beírjuk a konzolalkalmazás ablakába (lásd a 78–83. Sort), amelyhez a cout objektumot és a for ciklust használjuk. Természetesen a bejegyzés magában foglalja a kurzor áthelyezését egy új vonalra a 85-ös vonalon.
Ezután a konzolalkalmazás ablakba beírnak egy kérdést, amely megkérdezi a felhasználót, hogy ki akar-e lépni a programból vagy sem. Ha a felhasználó megnyomja az n gombot, a program folytatódik, és a felhasználót arra kéri, hogy írja be újra az Eratosten szita felső határát, az is_s érték ismét hamis értékként tárolva.
Ha a felhasználó elnyom egy másik kulcsot (ami a program befejezését jelenti), akkor a program a külső while hurok után ugrik a 97-es vonalra, a fő függvény 0-t ad vissza az operációs rendszernek, és az egész program befejeződik. Hadd emlékeztessem önöket arra, hogy a 98-as vonalon van egy megfelelő program zárójel, amely bezárja a fő funkció törzsét.
Programlista main.cpp
Konzolalkalmazás-ablak az Eratosten szita 20 felső határán
Az ábrán látható, hogy a kapott prímszámok megegyeznek az általunk analitikusan kiszámított prímszámokkal (lásd a szöveg utolsó táblázatát).
Remélem, hogy érdekli a példa és a program az Eratosten szitával, csak annyit kell tennie, hogy megvalósítja a számítógépén.
Ezt a blogot Marek ŠURKA, a C ++ tanfolyamok oktatója írta. Ha kérdése van, írja meg őket a megjegyzésekbe.
Megtanítjuk az embereket tervezésre, weboldalak létrehozására és programozásra. Teljes munkaidős tanfolyamainkat Szlovákia több városában találja meg, és online tanfolyamok segítségével otthonából kényelmesen tanulhat.