2025(e)ko martxoaren 28(a), ostirala

Ariketa 64 | Bi array paralelo

ZER DAKIDAN:
Arrayak ezagutzen ditut.



ZER IKASIKO DUDAN:
Kateen array baten eta zenbaki errealen array baten ariketa bat programatuko dut. Ariketa hau hobeto programatzen da laster ikusiko den erregistroen (edo struct datu-mota) array bat erabiliz.


Array batean ikasleen izenak ditugu eta beste array batean ikasleen notak gorderik daude. asIzenak arraya karaktere-kateak biltegitzen ditu, eta arNotak arrayak zenbaki errealak jasoko ditu. 

Array biren arteko lotura posizioetan datza, hau da, array baten lehen posizioko informazioa elkarturik dago beste arrrayaren lehen posizioko informazioarekin, eta horrela posizio guztiekin. Noski, luzera efektiboa bera delako, array bientzat lan egiten duen iLuzera aldagai bakarra erabiliko dugu. 

Adibidez:
     asIzenak 
0   'Klara' 
1    'Pedro'  
2    'Igone'  
3  
4
 
...
 
39  
                iLuzera=3


     arNotak 
0   6.77 
1     4.35  
2    9.25  
3  
4
 
...
 
39  


/* Ariketa-64_BiArrayParalelo: bi array sortuko dira, bat izenekin teklatua erabiliz
                               eta bestea auzaz lortiriko zenbaki errealez osaturik. */

// Suspendituen notak inkrementatu, ikasle baten izena bilatu eta nota berri bat gorde.
// Ariketa hau erregistroen array baten kasuaren sarrera-adibidea izan daiteke.

#include <stdio.h>
#include <string.h>   // strcmp() funtziorako
#include <stdlib.h>   // srand() eta rand() funtzioetarako
#include <time.h>     // time() funtziorako

#define BEHEMUGA 0
#define GOIMUGA 39
#define MAXIMOA 30+1  // 30 karaktere gehi null mugatzailea

typedef char tsKatea[MAXIMOA];
typedef float tafNotak[GOIMUGA];
typedef tsKatea tasIzenak[GOIMUGA];


void IzenakLortu(tasIzenak asIzenak, int *iLuzera);
void NotakLortu(tafNotak afNotak, int iLuzera);
void IzenakIkusi(const tasIzenak asIzenak, int iLuzera);
void NotakIkusi(const tafNotak afNotak, int iLuzera);
void NotakInkrementatu(tafNotak afNotak, int iLuzera);
int fniIkasleaBilatu(const tasIzenak asIzenak, int iLuzera, const char *sGakoa);


int main()
{
    tafNotak afNotak;
    tasIzenak asIzenak;
    int iLuzera;
    char sGakoa[MAXIMOA];
    int iPosizioa;

    IzenakLortu(asIzenak, &iLuzera);
    IzenakIkusi(asIzenak, iLuzera);

    NotakLortu(afNotak, iLuzera);
    NotakIkusi(afNotak, iLuzera);

    printf("Suspendituak inkrementatzen...\n");
    NotakInkrementatu(afNotak, iLuzera);
    NotakIkusi(afNotak, iLuzera);

    printf("Ikasle baten nota aldatu\n");
    printf("Ikaslearen izena eman: ");
    scanf("%s", sGakoa);

    iPosizioa = fniIkasleaBilatu(asIzenak, iLuzera, sGakoa);

    if (iPosizioa == -1)
        printf("'%s' izena duen ikaslerik ez dago\n", sGakoa);
    else
    {
        printf("Nota berria eman: ");
        scanf("%f", &afNotak[iPosizioa]);
        printf("\n'%s' ikaslearen nota aldatu ondoren\n", sGakoa);
        NotakIkusi(afNotak, iLuzera);
    }

    return 0;
}


void IzenakLortu(tasIzenak asIzenak, int *iLuzera)
{
    int iKont;

    do
    {
        printf("Zenbat ikasle dira? ");
        scanf("%d", iLuzera);
    } while (*iLuzera <= BEHEMUGA || *iLuzera > GOIMUGA);

    printf("\nIzenen arrayan %d datu gordetzen\n", *iLuzera);
    for (iKont = BEHEMUGA; iKont < *iLuzera; iKont++)
    {
        printf("Eman %d. izena: ", iKont);
        scanf("%s", asIzenak[iKont]);
    }
}


void NotakLortu(tafNotak afNotak, int iLuzera)
{
    int iKont;

    printf("Noten arrayan %d datu gordetzen\n", iLuzera);
    srand(time(NULL));  // ausazko zenbakiak sortzeko
    for (iKont = BEHEMUGA; iKont <= iLuzera; iKont++)
        afNotak[iKont] = (rand() / (float)RAND_MAX) * 10;  // 0.0 eta 9.999 arteko balioak
}


void IzenakIkusi(const tasIzenak asIzenak, int iLuzera)
{
    int iKont;

    printf("\nIzenen arrayaren edukia:\n");
    for (iKont = BEHEMUGA; iKont < iLuzera; iKont++)
        printf("%2d. ikaslea = %s\n", iKont, asIzenak[iKont]);
    printf("\n");
}


void NotakIkusi(const tafNotak afNotak, int iLuzera)
{
    int iKont;

    printf("Noten arrayaren edukia:\n");
    for (iKont = BEHEMUGA; iKont < iLuzera; iKont++)
        printf("%2d. nota = %.3f\n", iKont, afNotak[iKont]);
    printf("\n");
}


void NotakInkrementatu(tafNotak afNotak, int iLuzera)
{
    int iKont;

    for (iKont = BEHEMUGA; iKont < iLuzera; iKont++)
        if (afNotak[iKont] < 5.0)
            afNotak[iKont] += 1.0;
    printf("\n");
}


int fniIkasleaBilatu(const tasIzenak asIzenak, int iLuzera, const char *sGakoa)
{
    int iKont;

    for (iKont = BEHEMUGA; iKont < iLuzera; iKont++)
        if (strcmp(asIzenak[iKont], sGakoa) == 0)
            return iKont;

    return -1;  // Ikaslerik ez bada aurkitzen
}






  • Ariketa-64_BiArrayParalelo.cbp | main.c  


 

Ariketa 63 | Eratostenes-en bahea (I)

ZER DAKIDAN:
Arrayak ezagutzen ditut.



ZER IKASIKO DUDAN:
Zenbaki osoen bi dimentsiotako array baten ariketa bat programatuko dut emaniko algoritmoa jarraituz. Ariketa hau hobeto programatzen da laster ikusiko den erregistroen (edo struct datu-mota) array bat erabiliz.

Galbahe (edo bahe) baten irudia. Galbaheri esker aleak sailka daitezkeen bezala, zenbaki zerrenda bati galbahe logikoren bat aplikatuz zenbakien segida desberdinak lor daitezke, adibidez: zenbaki lehenak identifikatzeko Eratostenes matematikari greziarrak asmatutakoa

Ariketa honi bi modutan ekingo diogu:





Eratostenes (antzinako grezieraz: Ἐρατοσθένης; K.a. 276 inguru - K.a. 195 inguru) matematikari, geografo, kirolari, poeta eta astronomo greziarra izan zen. Alexandriako Liburutegia famatuaren zuzendari izendatu zuten eta aurkikuntza ugari egin zituen, hala nola, latitude eta longitude sistema. Eratostenes ezaguna da Lurraren zirkunferentzia kalkulatzen lehen greziarra izan zelako, baita Lurraren ardatzak duen makurdura. Bestalde, garaiko ezagutza geografikoaren araberako mundu mapa eratu zuen ere. 

                   
 

Eratostenes-en bahea zenbaki lehenak aurkitzeko algoritmo bat da, emandako n zenbaki arrunt bat baino txikiagoak direnen artean.

Lehendabizi, taula bat egiten da 2 eta n arteko zenbaki arruntekin, jarraian multiploak markatzen dira hurrengo ordena jarraituz:

  • 2tik hasita, haren multiplo guztiak markatzen dira, ostean, hurrengo zenbakiarekin jarraituko da baina bi egoera daude:
    • Hurrengo zenbakia markaturik gabe dago, adibidez 3 zenbakia, eta lehen bezala bere multiplo guztiak markatzen dira
    • Hurrengo zenbakia markaturik dago, adibidez 4 zenbakia, kasu honetan ez da ezer markatzen eta bere hurrengo zenbakia hartzen da
  • 5ekin markatu beharko litzateke (goiko lehen kasua), 6kin ez litzateke ezer markatuko (goiko bigarren kasua), 7ekin markatu beharko litzateke (goiko lehen kasua), 8, 9 eta 10ekin ez litzateke ezer markatuko (goiko bigarren kasuak), e.a.
    Prozedura errepikatzen da hau betetzen den bitartean: (MarkatuGabekoZenbakia)2 < n. Beste modu batez esanik, markatu gabeko zenbakiaren karratua n baino handiagoa denean eten prozesu errepikakorra

Eratostenes-en bahearen animazioa 120 baino gutxiagoko zenbaki lehenentzat:

Sieve of Eratosthenes animation
SKopp at German Wikipedia, CC BY-SA 3.0, via Wikimedia Commons

Hona hemen datu-taularen irudia MAX konstanteak 21 balio duenean, non 0 markak zenbaki lehen adierazten duen eta 1 markak zenbaki zatigarri adierazten duen:

  1    2   3    4   5    6   7    8    9   10 11  12 13  14  15  16 17  18 19  20  21   zenbakia  
  2    0  0  1  0  1  0  1  1  1  0  1  0  1  1  1  0  1  0  1  1 marka

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21


/* Ariketa-63_EratostenesenBahea-1 */

/*
   Muga den kopuru arrunta emanez, muga hori baino txikiagoak diren
   "Zenbaki Lehenak" lortzeko metodo bat aurkitu zuen Eratostenesek.

   Algoritmoa:
   ----------
   2tik iMuga-rako zenbakiak zerrenda batean jartzen dira. Lehenengo, 2ren
   multiplo guztiak markatzen dira, eta 2 zenbakia emaitza den lehenen
   zerrendari gehituko zaio. Ondoren, 3ren multiplo guztiak markatuko dira,
   eta 3 zenbakia gehituko zaio lehenen zerrendari. Gero, 4ari begiratzen
   zaio, markatuta dagoela ikusten da, eta horrek esan nahi du 2rekin
   zatigarria dela, eta, beraz, ez da lehena. Ondoren, 5era iristen da;
   markatuta ez dagoenez, lehena da, bere multiplo guztiak markatzen dira
   eta lehenen zerrendara gehituko da.
   Prozesu errepikakorra bukatzeko baldintza: Une jakin batean aztertuko den
   zenbakiaren karratua iMuga-tik beherakoa bada, jarraitu beharra dago.
   Bestela, algoritmoa amaitu egiten da, eta markatu gabe geratu diren
   guztiak zenbaki lehenak dira (emaitza-zerrendari gehitu beharrekoak).

   Animazio hau ikusi:
   https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif

   Bi programa hauek aztertu:
      * Ariketa-63_EratostenesenBahea-1 zenbaki osoen bi dimentsiotako arraya
      * Ariketa-69_EratostenesenBahea_2 erregistroen dimentsio bakarreko arraya
*/

#include <stdio.h>

#define MAX 120

typedef int taiDatuak[2][MAX + 1];   // 2 errenkada eta MAX+1 zutabe
typedef int taiLehenak[MAX];         // zenbaki lehenak gordetzeko arraya

void DatuakLortu(taiDatuak aiDatuak, int *iLuzeraDatuak);
void DatuakIkusi(const taiDatuak aiDatuak, int iLuzeraDatuak);
void LehenakLortu(const taiDatuak aiDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak);
void LehenakIkusi(const taiLehenak aiLehenak, int iLuzeraLehenak);


int main()
{
    taiDatuak aiDatuak;
    int iLuzeraDatuak;
    taiLehenak aiLehenak;
    int iLuzeraLehenak;
    int iIterazioa = 2;

    DatuakLortu(aiDatuak, &iLuzeraDatuak);
    printf("\nHasierako datuak:\n");
    DatuakIkusi(aiDatuak, iLuzeraDatuak);
    printf("\n1 zenbakia alde batera utzirik, prozesu errepikakorra 2 zenbakiarekin hasiko da\n\n");

    do
    {
        printf("================================================================================\n");
        if (aiDatuak[1][iIterazioa] == 0)
        {
            printf("%d zenbakia lehena da, ", iIterazioa);
            printf("%d zenbakiaren multiploak markatzen...\n", iIterazioa);
            for (int k = iIterazioa + 1; k <= MAX; k++)
            {
                if (aiDatuak[0][k] % iIterazioa == 0)
                {
                    aiDatuak[1][k] = 1;  // Es divisible, marca con 1
                    printf("%4d zenbakia markaturik zatigarria delako\n", aiDatuak[0][k]);
                }
            }
        }
        else
        {
            printf("%d zenbakia zatigarria da\n", iIterazioa);
        }

        printf("%d arteko datuak:\n", iIterazioa);
        DatuakIkusi(aiDatuak, iLuzeraDatuak);
        printf("================================================================================\n");

        iIterazioa++;
        if (iIterazioa * iIterazioa <= MAX)
        {
            printf(" %d x %d = %d <= %d   prozesu errepikakorrarekin jarraitu\n",
                   iIterazioa, iIterazioa, iIterazioa * iIterazioa, MAX);
        }
        else
        {
            printf(" %d x %d = %d > %d   prozesu errepikakorra amaitu\n",
                   iIterazioa, iIterazioa, iIterazioa * iIterazioa, MAX);
        }
        printf("\n\n");
    } while (iIterazioa * iIterazioa <= MAX);

    LehenakLortu(aiDatuak, iLuzeraDatuak, aiLehenak, &iLuzeraLehenak);
    printf("Lehenen zerrenda:\n");
    LehenakIkusi(aiLehenak, iLuzeraLehenak);

    printf("\n\nENTER sakatu exekuzioa amaitzeko... ");
    getchar(); // itxaron ENTER sakatu arte
    return 0;
}


void DatuakLortu(taiDatuak aiDatuak, int *iLuzeraDatuak)
{
    *iLuzeraDatuak = MAX;
    for (int k = 2; k <= *iLuzeraDatuak; k++)
    {
        aiDatuak[0][k] = k;
        aiDatuak[1][k] = 0;  // 0 (FALSE) lehena, 1 (TRUE) zatigarria
    }
}

void DatuakIkusi(const taiDatuak aiDatuak, int iLuzeraDatuak)
{
    int iKont_0 = 1;  // 1 lehena da, ez da prozesatzen
    int iKont_1 = 0;  // zatigarrien kontagailua

    printf("--------------------------------------------------------------------------------\n");
    printf("   1-LEHEN");
    for (int k = 2; k <= iLuzeraDatuak; k++)
    {
        printf("%4d", aiDatuak[0][k]);
        if (aiDatuak[1][k] == 0)
        {
            printf("-LEHEN");
            iKont_0++;
        } else
        {
            printf("__ZAT.");
            iKont_1++;
        }
    }
    printf("\n--------------------------------------------------------------------------------\n");
    printf(" Zenbakien kopurua = %d     Lehenen kopurua = %d     Zatigarrien kopurua = %d\n",
           iLuzeraDatuak, iKont_0, iKont_1);
}


void LehenakLortu(const taiDatuak aiDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak)
{
    *iLuzeraLehenak = 1;
    aiLehenak[*iLuzeraLehenak] = 1;

    for (int k = 2; k <= iLuzeraDatuak; k++)
    {
        if (aiDatuak[1][k] == 0)
        {
            (*iLuzeraLehenak)++;
            aiLehenak[*iLuzeraLehenak] = aiDatuak[0][k];
        }
    }
}


void LehenakIkusi(const taiLehenak aiLehenak, int iLuzeraLehenak)
{
    printf("********************************************************************************\n");
    for (int k = 1; k <= iLuzeraLehenak; k++)
    {
        printf("%3d, ", aiLehenak[k]);
    }
    printf("\n********************************************************************************\n");
    printf("  iLuzeraLehenak = %d\n", iLuzeraLehenak);
}






  • Ariketa-63_EratostenesenBahea-1.cbp | main.c  


 

Ariketa 62 | Zortearen Zenbakien Segida

ZER DAKIDAN:
Arrayak ezagutzen ditut.



ZER IKASIKO DUDAN:
Zenbaki osoen array baten ariketa bat programatuko dut emaniko algoritmoa jarraituz.

Galbahe (edo bahe) baten irudia. Galbaheri esker aleak sailka daitezkeen bezala, zenbaki zerrenda bati galbahe logikoren bat aplikatuz zenbakien segida desberdinak lor daitezke, adibidez: "Zortearen Zenbakien Segida" delakoa

Galbahe (edo bahe) baten aplikatzearen aditza bahetu da. Artikulu honetan Zortearen Zenbakien Segida lortuko dugu baina ikusi ere 10. astea | Eratostenesen bahea (I) eta 11. astea | Eratostenesen bahea (II) artikuluak non zenbaki lehenak lantzen diren.

Zortearen Zenbakien Segida eskuratzeko zenbaki arruntei galbahe jakin bat aplikatuko zaie. Zenbaki arrunten zerrenda batean Zortearen Zenbakiak identifikatzeko, zenbakien posizioak aintzat hartuko dira bahetze prozesuan. Cuaderno de Cultura Científica web guneneko artikulu hau ikusi: Los números de la suerte.

Demagun 1etik hasita eta 99 arteko Zortearen Zenbakiak lortu nahi ditugula. Programaren irteerak aztertuz algoritmoa asma dezagun.

Hasierako datuek jarraian erakusten den zerrenda osatzen dute, hots, 1 eta 99 arteko zenbaki arruntek (biak barne) osatzen duten zerrenda:

1 eta 99 arteko zenbaki arruntak behin baino gehiagotan bahetuz Zortearen Zenbakiak lortuko ditugu. Zerrenda hau gordetzeko aiDatuak arraya erabil daiteke

Zerrenda horretako Zortearen Zenbakiak lor ditzagun urratsez-urrats...

Prozesu arrepikakor guztiek bezala, hasieraketa bat egin beharko da. Kasu honetan, repeat-until (edo while-do) agindura sartu aurretik zenbaki bikoitiak kenduko dira hasierako zerrendatik. Lehen bahetze jardun horren arabera emaitza-zerrenda hau osatuko da:

aiDatuak hasierako arraytik abiatuta aiEmaitza array hau lortzen da repeat-until (edo while-do) agindutik kanpo

Algoritmoaren oinarria

Bi array izango ditugu aiDatuak arraya eta aiEmaitza arraya, une jakin bateko aiDatuak arrayari bahetze prozesua aplikatuz lortuko da une horri dagokion aiEmaitza arraya. Baina baheketa desberdinak behar direnez, baheketak errepikatu beharko dira (repeat-until edo while-do aginduaren bat beharko da).

Prozesu errepikorraren aginduaren hasieran aiDatuak arraya aldatuko dugu eta bere balio berriak aurreko aiEmaitza arrayarenak izango dira, begiztaren barnean aiEmaitza arraya berkalkulatuko dugu. Iterazio batetik bestera, joku hau egingo dugu: n iterazio jakin batean lortu dugun aiEmaitza emaitza, n+1 iterazioan aiDatuak datua izango da eta honi esker aiEmaitza emaitza berria kalkulatuko dugu.



Prozesu errepikakorraren barnean, iIterazioa aldagaiak 2 balio du eta horren arabera, uneko aiDatuak arrayaren bigarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 3 da) eta 3., 6., 9. e.a. posizioko elementuak bahetuz aiEmaitza array berria lortuko da:

2. iterazioaren balioa 3 da, horregatik 3 posizioko jauziak egingo dira. Horrela: 3. posizioko 5 balioa kendu,
6. posizioko 11 balioa kendu, 9. posizioko 17 balioa kendu, 12. posizioko 23 balioa kendu, eta abar

2. iterazioa amaitzean uneko zerrendak 34 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 19 21 25 27 31 33 37 39 43 45 49 51 55 57 61 63 67 69 ... 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... 34


iIterazioa aldagaiak 3 balio du eta horren arabera, uneko aiDatuak arrayaren hirugarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 7 da) eta zazpiko jauziak egingo dira 7., 14., 21. eta 28. posizioko elementuak bahetuz aiEmaitza array berria lortzeko:

3. iterazioaren balioa 7 da, horregatik 7 posizioko jauziak egingo dira. Horrela: 7. posizioko 19 balioa kendu,
14. posizioko 39 balioa kendu, 21. posizioko 61 balioa kendu eta 28. posizioko 81 balioa kendu

3. iterazioa amaitzean uneko zerrendak 30 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 21 25 27 31 33 37 43 45 49 51 55 57 63 67 69 73 75 79 ... 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... 30


iIterazioa aldagaiak 4 balio du eta horren arabera, uneko aiDatuak arrayaren laugarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 9 da) eta bederatziko jauziak egingo dira 9., 18. eta 27. posizioko elementuak bahetuz aiEmaitza array berria lortzeko:

4. iterazioaren balioa 9 da, horregatik 9 posizioko jauziak egingo dira. Horrela: 9. posizioko 27 balioa kendu,
18. posizioko 57 balioa kendu eta 27. posizioko 91 balioa kendu

4. iterazioa amaitzean uneko zerrendak 27 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 21 25 31 33 37 43 45 49 51 55 63 67 69 73 75 79 85 87 ... 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ... 27


iIterazioa aldagaiak 5 balio du eta horren arabera, uneko aiDatuak arrayaren bosgarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 13 da) eta hamahiruko jauziak egingo dira 13. eta 26. posizioko elementuak bahetuz aiEmaitza array berria lortzeko:

5. iterazioaren balioa 13 da, horregatik 13 posizioko bi jauzi egingo dira.
Horrela: 13. posizioko 45 balioa kendu eta 26. posizioko 97 balioa kendu

5. iterazioa amaitzean uneko zerrendak 25 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 21 25 31 33 37 43 49 51 55 63 67 69 73 75 79 85 87 93 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25


iIterazioa aldagaiak 6 balio du eta horren arabera, uneko aiDatuak arrayaren seigarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 15 da) eta hamabosteko jauziak egingo dira 15. posizioko elementu bakarra bahetuz aiEmaitza array berria lortzeko:

6. iterazioaren balioa 15 da, horregatik 15 posizioko jauziak egingo dira.
Baina, 15. posizioko 55 balioa kendu ostean gehiagorik ezingo da kendu

6. iterazioa amaitzean uneko zerrendak 24 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 85 87 93 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24


iIterazioa aldagaiak 7 balio du eta horren arabera, uneko aiDatuak arrayaren zazpigarren posizioko elementuaren balioa hartu behar da (ikusten denez, balio hori 21 da) eta hogeita bateko jauziak egingo dira 21. posizioko elementu bakarra bahetuz aiEmaitza array berria lortzeko:

7. iterazioaren balioa 21 da, horregatik 21 posizioko jauziak egingo dira.
Baina, 21. posizioko 85 balioa kendu ostean gehiagorik ezingo da kendu

7. iterazioa amaitzean uneko zerrendak 23 elementu izango ditu. Arraya hau izango litzateke non arrayaren 0 posizioa ez den erabiltzen:

 ?  1  3  7  9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Ikusten den bezala, azken zerrendako 1. elementua 1 da, 2. elementua 3 da eta 23. elementua 99 da. Hurrengo iterazioan jauzien neurria 25ekoa da baina zerrendak 23 elementu dituenez ez da 8. iteraziorik izango:

8. iteraziorik ez da izango bere balioa 25 delako eta zerrendaren elementu kopurua 23 delako


Ariketaren balizko kode osoa ikusi:

/* Ariketa-62_ZortearenZenbakienSegida: zenbaki arruntak bahetzen */

//  "Zortearen Zenbakiak" ala "Josephus Flaviusen Baheketa"

//  Zortearen Zenbakien Segida lortzeko zenbaki arruntei galbahe jakin
//  bat aplikatuko zaie. Zortearen Zenbakiak zerrendan identifikatzeko
//  bahetze prozesuan zenbaki arrunten posizioak aintzat hartuko dira.
//  Web gune hau ikusi:

//  https://culturacientifica.com/2024/01/10/los-numeros-de-la-suerte/

#include <stdio.h>

#define MAX 100

void DatuakLortu(int aiDatuak[], int *iLuzeraDatuak);
void ZenbakiakIkusi(int aiZenbakiak[], int iLuzera);


int main()
{
    int aiDatuak[MAX];    // une jakin bateko datuak
    int aiEmaitza[MAX];   // une jakin bateko emaitza
    int iLuzeraDatuak;
    int iLuzeraEmaitza;
    int iIterazioa;
    int k;

    printf("\n\n");

    DatuakLortu(aiDatuak, &iLuzeraDatuak);
    printf("\nHasierako datuak:\n");
    ZenbakiakIkusi(aiDatuak, iLuzeraDatuak);
    printf("iLuzeraDatuak=%d\n\n", iLuzeraDatuak);

    iIterazioa = 2; // lehen baheketan bikoitiak kenduko dira
    printf("1. iterazioa kanpoan, jauzien neurria: %d = aiDatuak[%d]\n", aiDatuak[iIterazioa], iIterazioa);
    iLuzeraEmaitza = 0;

    for (k = 1; k <= iLuzeraDatuak; k++)
    {
        if (k % aiDatuak[iIterazioa] != 0)
        {
            iLuzeraEmaitza++;
            aiEmaitza[iLuzeraEmaitza] = aiDatuak[k];
        }
    }
    ZenbakiakIkusi(aiEmaitza, iLuzeraEmaitza);
    printf("iLuzeraEmaitza=%d\n\n", iLuzeraEmaitza);

    iIterazioa = 2; // bigarren iterazioan 2. posiziokoa eta hurrengoak kentzeko
    do
    {
        for (k = 1; k <= iLuzeraEmaitza; k++)
        {
            aiDatuak[k] = aiEmaitza[k];
        }
        iLuzeraDatuak = iLuzeraEmaitza;

        printf("%d. iterazioan jauzien neurria: %d = aiDatuak[%d]\n", iIterazioa, aiDatuak[iIterazioa], iIterazioa);
        iLuzeraEmaitza = 0;

        for (k = 1; k <= iLuzeraDatuak; k++)
        {
            if (k % aiDatuak[iIterazioa] != 0)
            {
                iLuzeraEmaitza++;
                aiEmaitza[iLuzeraEmaitza] = aiDatuak[k];
            }
            else
            {
                printf("%4d kenduta\n", aiDatuak[k]);
            }
        }

        ZenbakiakIkusi(aiEmaitza, iLuzeraEmaitza);
        printf("iLuzeraEmaitza=%d\n", iLuzeraEmaitza);
        if (iLuzeraEmaitza > 0)
        {
            printf("Hurrengo iterazioaren jauzien neurria: %d\n", aiEmaitza[iIterazioa + 1]);
        }

        printf("\n");
        iIterazioa++;
    } while (iLuzeraDatuak >= aiEmaitza[iIterazioa]);

    printf("\nENTER sakatu exekuzioa amaitzeko... ");
    getchar();

    printf("\n\n");
    return 0;
}


// programazioa errazteko arrayaren 0 posizioa ez da erabiliko
void DatuakLortu(int aiDatuak[], int *iLuzeraDatuak)
{
    *iLuzeraDatuak = MAX;
    for (int k = 1; k <= *iLuzeraDatuak; k++)
    {
        aiDatuak[k] = k;
    }
}


void ZenbakiakIkusi(int aiZenbakiak[], int iLuzera)
{
    printf("--------------------------------------------------------------------------------\n");
    for (int k = 1; k <= iLuzera; k++)
    {
        printf("%4d", aiZenbakiak[k]);
    }
    printf("\n--------------------------------------------------------------------------------\n");
}






  • Ariketa-62_ZortearenZenbakienSegida.cbp | main.c  


 

Ariketa 61 | Errusiar Biderketaren Metodoa arrayekin

ZER DAKIDAN:
3. jarduera (I) | Errusiar Biderketaren Metodoa zertan den artikuluan ikasi nuen Errusiar Biderketa zertan den eta programatu nuen ere.



ZER IKASIKO DUDAN:
3. jarduera (III) | Errusiar Biderketaren Metodoa programatzen artikuluan idatzitako kodea arrayak erabiliz programatuko dut.

3. jarduera (I) | Errusiar Biderketaren Metodoa zertan den izenburuko artikulua gogoratuz, ariketa honetan bi zenbakiren arteko biderkadura kalkulatzen duen programa egingo dugu, baina biderketa burutzeko taulak arrayetan gordez.

Jakinik biderkagai biak int datu-motakoak direla (biak 0 eta 46000 artekoak), biderkadura long datu-motakoa izango da. Gogora ekar dezagun 3. jarduera (III) | Errusiar Biderketaren Metodoa programatzen artikulua eta bertan ematen den kodea, programa hori exekutatzean biderkagai handienak sartuko bagenitu ondoko emaitza eskuratuko genuke:


Horregatik, taularen datu-mota holako zerbait izango da, non zutabeak bi diren eta errenkaden kopurua iLUZERA oraindik ez dugun zehaztu:

type 
   taliTaula = array[0..iLUZERA, 1..2] of longint ; 

Errenkaden behemuga 0 izatea komeniko zaigu eta errenkaden goimuga den iLUZERA zehazteko jakin behar dugu "erdiak ematen dituen sekuentzia" segida logaritmiko bat dela, lehen biderkagaiaren baliorik handiena aukeratuko bagenu iBiderkagai1 =46000 mailak 14 izango lirateke:

2fMailak = iBiderkagai1 = 46000
log2(2fMailak) = log2(46000)
fMailak·log2(2) = log2(46000)
fMailak = log2(46000)/log2(2)
fMailak = ln(46000)/ln(2) = 10.736397/0.693147 = 15,48935
iMailak = 15

Mailak 15 izango dira gehienez, baina biderkagai biak taulak bildu nahi ditugunez, errenkaden behemuga 0 izan dadila eta errenkada horretan datuak diren biderkagai biak kokatuko ditugu. Ondorioz, taularen datu-mota hau izango da:

#define iHANDIENA 46000
#define iLUZERA 15                         
                                           // errenkaden kopuru maximoa: iLUZERA
typedef long taliTaula[iLUZERA + 1][2];    // biderkagai biak 0. errenkadan
                                           // zutaben kopurua beti: 2


Jakinik biderkagai biak integer datu-motakoak direla (biak 0 eta 46000 artekoak), biderkadura longint datu-motakoa izango da eta, gehienez, taularen neurria 15x2 izango da (0 errenkada barne). Baina, exekuzio jakin batean ez da zertan taula osoa bete behar; adibidez, biderkagaiak 34 eta 7 badira taularen neurri efektiboa honako ha izango da:

                                  Erdiak   Dobleak
                                  ------   -------
                        0. maila      34         7
                        1. maila      17        14
                        2. maila       8        28
                        3. maila       4        56
                        4. maila       2       112
                        5. maila       1       224
Argi dago zutabeak beti 2 izango direla eta taularen neurri efektikoa errenkada baliagarriak kopuruak finkatuko duela (goiko adibidean 5).


Laburbilduz: Aurreko azpiataleko goiko taula hori memorian gordetzeko, bi dimentsiotako array bat beharko dugu, hots, zenbaki osoen taula bat beharko dugu. Orokorrean, bi dimentsiotako arrayaren indizeak 0-tik 15-ra joango dira errenkadetan eta zutabeak izendatzeko 1 eta 2 indizeak erabiliko ditugu. Baina adibidera etorriz, taularen neurria 5x2 izango da (non 2 beti konstantea den), horregatik iLuzeraEfek aldagaian 5 gordeko da.

iBiderkagai1 aldagaian 34 hartu bada, eta iBiderkagai2 aldagaian 7 hartu bada, aliTaula arrayaren itxura honako hau izango da, non iMailak = iLuzeraEfek = 5 izango den:

aliTaula
       1  
   2   
0     34       7   
1    17  
   14   
2     8       28   
3     4       56   
4     2      112   
5 1 224
6    
7    
...    
13    
14    

3. jarduera (I) | Errusiar Biderketaren Metodoa zertan den aplikatuz, lehen zutabeko bikoitien errenkadak kenduko ditugu eta  aliTaula arraya abiapuntuz harturik aliTaulaLaburra arraya eskuratuko dugu:

aliTaula
       1  
   2   
0    34       7   
1    17  
   14   
2     8       28   
3     4       56   
4     2      112   
5 1 224
6    
7    
...    
13    
14    

aliTaulaLaburra array berriaren itxura honako hau izango da, non adibide honetan errenkadak bi direlako iLuzeraEfek = 1 izango den:

aliTaulaLaburra
       1  
   2   
0    17  
   14   
1     1     224 
2    
3    
...    
13    
14    

Eskumako zutabean geratu diren zenbakien batuketa eginez, lortu den 14+224=238 batura bilatzen dugun emaitza da, hots, lortutako batura helburuko 34x7=238 biderkadura bezalakoa da.


/* Ariketa-61_ErrusiarBiderketa: arrayekin */

// "Errusiar Biderketaren Metodoa" aplikatzen duen programa bat idatzi nahi da.

// DATUAK:
//       Sarrerako datuak bi biderkagaiak izango dira, biak positiboak eta osoak.
// EMAITZA:
//       Irteera biderkadura izango da, bere datu-mota LONGINT izango da.

// Arrayaren neurria zehazteko, suposatuko dugu sarrerako biderkagairik handiena
// iHANDIENA (46000) izango dela. Horregatik:   2^fLUZERA = iHANDIENA
//                                   fLUZERA·ln(2) = ln(iHANDIENA)  >>>  fLUZERA
//                                   fLUZERA = ln(iHANDIENA) / ln(2) = 14.99995
//                                   iLUZERA = trunc(ln(iHANDIENA) / ln(2) = 15

#include <stdio.h>
#include <conio.h>  // getch() funtziorako
#include <math.h>   // trunc() eta log() funtzioetarako

#define iHANDIENA 46000
#define iLUZERA 15

typedef long taliTaula[iLUZERA + 1][2];

int iZenbakiarenMailakKalkulatu(int iZenbakia);
long liBatuketakEgin(const taliTaula aliTaulaLaburra, int iLuzeraLaburra);
void ErrenkadaBikoitiakKendu( const taliTaula aliTaula, int iLuzeraEfek,
                             taliTaula aliTaulaLaburra, int *iLuzeraLaburra);
void TaulaBete(taliTaula aliTaula, int iLuzeraEfek, int iZenbaki_1, int iZenbaki_2);
void TaulaIkusi(const taliTaula aliTaula, int iLuzeraEfek);


int main()
{
    int iZenbaki_1, iZenbaki_2, iMailak, iLuzeraEfek, iLuzeraLaburra;
    taliTaula aliTaula, aliTaulaLaburra;
    long liBiderkadura;

    printf("\niHANDIENA ----> %d\n", iHANDIENA);
    printf("iLUZERA = trunc(ln(iHANDIENA) / ln(2)) ----> %d\n\n", (int)trunc(log(iHANDIENA) / log(2)));

    printf(" -------------------------------\n");
    printf("| Errusiar Biderketaren Metodoa =============\n");
    printf("| -----------------------------              |\n");
    printf("|                                            |\n");
    printf("| Kopuru positiboekin lan eginez, bi zenbaki |\n");
    printf("| irakurri eta haien biderkadura kalkulatu.  |\n");
    printf(" ============================================\n\n");

    do
    {
        printf("   Lehen biderkagaia eman (1 eta %d artekoa), 39 adibidez: ", iHANDIENA);
        scanf("%d", &iZenbaki_1);
    } while (iZenbaki_1 <= 0 || iZenbaki_1 > iHANDIENA);

    do
    {
        printf("Bigarren biderkagaia eman (0 eta %d artekoa),  7 adibidez: ", iHANDIENA);
        scanf("%d", &iZenbaki_2);
    } while (iZenbaki_2 < 0 || iZenbaki_2 > iHANDIENA);

    iMailak = iZenbakiarenMailakKalkulatu(iZenbaki_1);

    printf("\n%d biderkagaiari dagokion maila kopurua %d da:\n", iZenbaki_1, iMailak);

    iLuzeraEfek = iMailak;

    TaulaBete(aliTaula, iLuzeraEfek, iZenbaki_1, iZenbaki_2);

    printf("\n");
    TaulaIkusi(aliTaula, iLuzeraEfek);
    printf("\n");

    ErrenkadaBikoitiakKendu(aliTaula, iLuzeraEfek, aliTaulaLaburra, &iLuzeraLaburra);

    TaulaIkusi(aliTaulaLaburra, iLuzeraLaburra);
    printf("\n");

    liBiderkadura = liBatuketakEgin(aliTaulaLaburra, iLuzeraLaburra);

    printf("\"Errusiar Biderketaren Metodoa\" aplikatuz:    %d x %d = %ld\n", iZenbaki_1, iZenbaki_2, liBiderkadura);
    printf("Biderkadura ohiko * operadorearen bitartez:   %d * %d = %d\n", iZenbaki_1, iZenbaki_2, iZenbaki_1 * iZenbaki_2);

    printf("\n====================================================\n");
    printf("           Edozein tekla sakatu amaitzeko\n");
    printf("====================================================\n");

    getch();  // karaktere bati itxaron
    return 0;
}

int iZenbakiarenMailakKalkulatu(int iZenbakia)
{
    return (int)trunc(log(iZenbakia) / log(2));
}


void TaulaBete(taliTaula aliTaula, int iLuzeraEfek, int iZenbaki_1, int iZenbaki_2)
{
    aliTaula[0][0] = iZenbaki_1;
    aliTaula[0][1] = iZenbaki_2;

    long liErdia = iZenbaki_1;
    long liDoblea = iZenbaki_2;

    for (int iErrenkada = 1; iErrenkada <= iLuzeraEfek; iErrenkada++) {
        liErdia /= 2;
        liDoblea *= 2;
        aliTaula[iErrenkada][0] = liErdia;
        aliTaula[iErrenkada][1] = liDoblea;
    }
}


void TaulaIkusi(const taliTaula aliTaula, int iLuzeraEfek)
{
    printf("%32s %15s\n", "Erdiak", "Dobleak");
    printf("%32s %15s\n", "------", "-------");

    for (int iErrenkada = 0; iErrenkada <= iLuzeraEfek; iErrenkada++)
    {
        printf("%10d. maila%15ld%15ld\n", iErrenkada, aliTaula[iErrenkada][0], aliTaula[iErrenkada][1]);
    }
}


void ErrenkadaBikoitiakKendu( const taliTaula aliTaula, int iLuzeraEfek,
                             taliTaula aliTaulaLaburra, int *iLuzeraLaburra)
{
    *iLuzeraLaburra = -1;  // La primera fila del array es 0
    for (int iErrenkada = 0; iErrenkada <= iLuzeraEfek; iErrenkada++)
    {
        if (aliTaula[iErrenkada][0] % 2 == 1)
        {
            (*iLuzeraLaburra)++;
            aliTaulaLaburra[*iLuzeraLaburra][0] = aliTaula[iErrenkada][0];
            aliTaulaLaburra[*iLuzeraLaburra][1] = aliTaula[iErrenkada][1];
        }
    }
}


long liBatuketakEgin(const taliTaula aliTaulaLaburra, int iLuzeraLaburra)
{
    long liBatura = 0;
    for (int iErrenkada = 0; iErrenkada <= iLuzeraLaburra; iErrenkada++)
    {
        liBatura += aliTaulaLaburra[iErrenkada][1];
    }
    return liBatura;
}






  • Ariketa-61_ErrusiarBiderketa.cbp | main.c