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:

2^fMailak = iBiderkagai1 = 46000
log₂(2^fMailak) = log₂(46000)
fMailak·log₂(2) = log₂(46000)
fMailak = log₂(46000)/log₂(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