22. lecke
Prímszámkereső rávezetés
lightbulb_outlineMegoldunk 3 feladatot, ami a prímszámkereső megértéséhez segít minket
Ebben a fejezetben egy prímszámkereső programot fogunk írni, gyakorolva ezzel az algoritmizálás művészetét. Mielőtt azonban hozzáfognánk a kódoláshoz nézzünk pár gyakorló példát, ami nagyon jó alapokat ad a prímszámkereső program megírásához a bennük található furfangos programszerkezetek megismerése révén.
Feladat: Háromszög rajz
A feladatunk, hogy bekérjünk a felhasználótól egy N számot és ilyen magas csillagokból álló háromszöget rajzoljunk ki a képernyőre Például:
Hasonló példával már volt dolgunk, akkor egy négyzetet rajzoltunk ki. A rajzolgatás előtt elemeztük az ábrát, megszámoltuk hány darab csillag van, hány darab sor van stb… Algoritmizálható szabályosságokat kerestünk, ezt kell tennünk most is!
- Hány darab sor van?
- A válasz: N
Annyi biztos, hogy szükségünk lesz egy FOR ciklusra, ami kirajzolja ezt az N darab sort. Írjuk meg!
int n; scanf("%d", &n); int i; for(i=1; i<=n; i++){ //... }
Keressünk még szabályosságokat!
- Az 1. sorban hány darab csillag van? A válasz: 1
- Az 2. sorban hány darab csillag van? A válasz: 2
- Az 3. sorban hány darab csillag van? A válasz: 3
- ...
- Az N. sorban hány darab csillag van? A válasz: N
Tehát a most megírt FOR ciklus belsejébe kell írnunk még egy FOR ciklust, ami a megfelelő darabszámú csillagot rajzolja ki. Ehhez a belső FOR ciklushoz természetes létre kell hoznunk egy új cikluváltozót, amit mondjuk nevezzünk ”j”-nek. A nagy kérdés: ”j” mettől meddig fusson?
Induljon 1-től, és fusson egészen a külső FOR ciklus aktuális állapotáig, tehát ”i”-ig!
#include<stdio.h>
int main(){
int n;
scanf("%d", &n);
int i, j;
//külső
for(i=1; i<=n; i++){
//belső
for(j=1; j<=i; j++){
printf("* ");
}
printf("\n");
}
return 0;
}
haromszog.c c 5 * * * * * * * * * * * * * * *
Első ránázásre tök bonyolultnak tűnhet a program a sok változó, pontosvessző és idézőjel miatt, pedig nem az:
- az első sorokban egyszerűen beolvassuk azt az N számot, ahány sort akarunk rajzolni
- a külső FOR ciklus felel a sorokért, ez 1-től N-ig megy
- a beső FOR ciklus felel a sorokon belüli csillagokért, ez 1-től a külső FOR ciklus aktuális állapotáig megy
- ha kell, akkor új sort a printf(”\n”); parancs kezd
Ilyen egyszerű, bármilyen számra kirajzolódik a kért ábra. A prímszámkeresőnél felhasználjuk a most kitalált ötletet miszerint egy belső FOR ciklus akár futhat a külső FOR ciklus aktuális állapotáig is!
Feladat: Hattal osztható
Írjunk egy progamot, ami eldönti egy egész számról, hogy osztható-e 6-tal.
Az első lépéseket már fújjuk is fejből:
- létrehozunk egy változót, beolvassuk az értékét
- ???? :)
Hattal oszthatóságot kétféleképen vizsgálhatunk:
- Egy FOR ciklussal elkezdünk 6-ot kivonogatni a számból egészen addig, amíg el nem érjük a 0-át. Ha egy kivonás eredménye pontosan 0 lesz, akkor megvan a számban egész számszor a 6, tehát a szám osztható 6-tal. Ha a kivonások eredménye soha nem lesz 0, hanem már annyiszor vontunk ki számokat, hogy átcsúsztunk a negatív számokhoz, akkor a szám nem osztható 6-tal:
Ez is egy lehetséges megoldás, de van jobb! A C programnyelv maradékos osztást végző operátora, a %, amit modulo-nak kell kiolvasni! (Nem, ez nem az a % jel, amit a scanf(”%d”…); parancsban látsz, ez egy másik.) Korábbi fejezetben már volt róla szó.
A modulo operátor megadja egy osztás maradékát. Például:
10 % 6 = 4
mert 10-ben a 6 megvan 1x, maradt a 4
100 % 10 = 0
mert 100-ban a 10 megvan 10x, marad a 0
Tehát a feladat megoldása így néz ki: Beolvasunk egy számot, amit ha maradékosan osztunk 6-tal és az eredmény 0, akkor a szám osztható 6-tal.
#include<stdio.h>
int main(){
int szam;
printf("Adj meg egy szamot!");
scanf("%d", &szam);
if( szam % 6 == 0)
{
printf("Osztható hattal.");
}
return 0;
}
hattal.c c 6 Adj meg egy szamot! Osztható hattal.
Próbáld módosítani a programot úgy, hogy ha a egy hattal nem osztható számot adunk neki oda, akkor írja ki, hogy "NEM osztható hattal"!
Prímszámkereső írásához a % modulo operátort is fel fogjuk használni!
Feladat: Szám osztóinak száma
Kérjünk be a felhasználótól egy számot és írjuk ki az osztóinak a darabszámát! Például 12 esetén a kimenet: 6, mert 12-nek az osztói: 1,2,3,4,6,12 ami éppenséggel 6 darab osztó.
A feladatot a maradékos osztás operátorával lehet megoldani. Ha a user beírja az N számot, akkor az összes N-nél kisebb pozitív egész számot tesztelni kell, hogy megvan-e benne, és egy számláló változót növelni, ha igen.
Az ötlet:
- a megadott számnál kisebb számokat egy FOR ciklussal járjuk végig
- a FOR ciklus aktuális állapotával megpróbáljuk elosztani a számot.
- Ha a maradék 0, akkor találtunk egy osztót :) Jee
#include<stdio.h>
int main(){
int szam; //a vizsgált szám
int i; //ciklusváltozó
int darab=0; //osztók száma
printf("Adj meg egy számot és én ");
printf("megmondom hány osztója van!\n");
scanf("%d", &szam);
for(i=1; i<=szam; i++)
{
if(szam % i == 0)
{
darab++;
}
}
printf("%d darab osztója van", darab);
return 0;
}
osztokszama.c c 12 Adj meg egy számot és én megmondom hány osztója van! 6 darab osztója van
Nézzük meg részletesen a program futását. Az első lépések szerintem egyértelműek: Létrehozzuk a szükséges változókat. ”i” a ciklusváltozó, ”darab” az osztók darabszámát számláló változó, ”szam” pedig az a szám, amit bekérünk.
1. ciklus
A FOR ciklus 1-ről kezdődik, tehát az 1. ciklusban az i változó értéke 1. Az IF a számot először 1-el próbálja meg maradékosan osztani. Ez menni fog, minden egész számban maradék nélkül megvan az 1, így a darab változót növeli a program. A növelés a ++ operátorral történik, ami ugye ugyanaz, mintha azt írtam volna: darab = darab +1;
2. ciklus
A FOR ciklus léptet. Az ”i” értéke már 2, ezért az IF a számot most 2-vel próbálja maradékosan osztani. Ha a szám páros szám, akkot ez menni fog és megint növelésre kerül a darab változó – ha páratlan akkor nem.
... és így tovább.
A FOR ciklus mindig nő, az IF pedig mindig megpróbálja elosztani a számot a ciklusváltozóval.
Ha meggonolod, akkor fejben is pontosan ugyanígy csinálod, amikor osztókat keresel. Ez a kis programrészlet a való élet leképzése kódsorokba!
Ezt a most megismert számlálós módszert fehasználjuk a prímszámkereső megírásához a következő fejezetben!
Jelentkezz be a hozzászóláshoz.