menu
shopping_cart
0
KOSÁR

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

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

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!