10. astea | Errusiar Biderketaren Metodoa programatzen

Errusiar Biderketaren Metodoa izenburuko artikulua gogoratuz, ariketa honetan bi zenbakiren arteko biderkadura kalkulatzen duen programa egingo dugu, baina biderketa burutzeko taulak arrayetan gordez.

---

TAULAREN NEURRIA ETA DATU-MOTA

Jakinik biderkagai biak integer datu-motakoak direla (biak 0 eta MAXINT artekoak), biderkadura longint datu-motakoa izango da. Gogora ekar dezagun 4. astea | Errusiar Biderketaren Metodoa programatzen artikulua eta bertan ematen den ErrusiarBiderketarenMetodoaProgramatzen.pas 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 = MAXINT = 32767 mailak 14 izango lirateke:

2^rMailak = iBiderkagai1 = 32767


log₂(2^rMailak) = log₂(32767)

rMailak·log₂(2) = log₂(32767)

rMailak = log₂(32767)/log₂(2)

rMailak = ln(32767)/ln(2) = 14.99995

iMailak = 14

Mailak 14 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:

program ErrusiarBiderketarenMetodoa_ARRAY ;

const
   iLUZERA = 14 ;
                                            
type 
   taliTaula = array[0..iLUZERA, 1..2] of longint ;   (* errenkaden kopuru maximoa: iLUZERA *)
                                                      (* biderkagai biak 0. errenkadan      *)
                                                      (* zutaben kopurua beti: 2            *)
   ...                                                    

---

TAULAREN JAKIN BATEN NEURRI EFEKTIBOA

Jakinik biderkagai biak integer datu-motakoak direla (biak 0 eta MAXINT 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).

---

ADIBIDE BAT

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 14-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

Errusiar Biderketaren Metodoa 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.

---

PROGRAMAREN ITURBURU-KODEA

Arrayak darabilen Errusiar Biderketaren Metodoaren programa bat jarraian erakusten da:

{ "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  } 
{ MAXINT izango dela. Horregatik:     2^rLUZERA = MAXINT                         }
{                                     rLUZERA·ln(2) = ln(MAXINT)  >>>  rLUZERA   }
{                                     rLUZERA = ln(MAXINT) / ln(2) = 14.99995    }
{                                     iLUZERA = trunc(ln(MAXINT) / ln(2) = 14    }

program ErrusiarBiderketarenMetodoa_ARRAY ;

const
   iLUZERA = 14 ;
   HANDIENA = MAXINT ;     (* MAXINT bada daturik garaiena iLUZERA 14 izan beharko da *)
                                            
type 
   taliTaula = array[0..iLUZERA, 1..2] of longint ;   (* errenkaden kopuru maximoa: iLUZERA *)
                                                      (* biderkagai biak 0. errenkadan      *)
                                                      (* zutaben kopurua beti: 2            *)
   

function ifnZenbakiarenMailakKalkulatu(iZenbakia: integer): integer ;   
var 
   rMailak: real ;
   iMailak: integer ;
begin
   //writeln('Adibidea -->  2^X=63 ekuazioaren ebazpena 5,98 da eta mailak 5 dira.') ;
   //writeln('Adibidea -->  2^X=64 ekuazioaren ebazpena 6,00 da eta mailak 6 dira.') ;
   //writeln('Adibidea -->  2^X=65 ekuazioaren ebazpena 6,02 da eta mailak 6 dira.') ;     
                                           (* 2^x = 65         *)
   rMailak := ln(iZenbakia) / ln(2) ;      (* x·ln(2) = ln(65) *)
   iMailak := trunc(rMailak) ;

   //writeln(iOINARRIA:15, '^X=', iZenbakia, ' ekuazioaren ebazpena ', rMailak:0:2, ' da. Mailak ', iMailak, ' dira.') ;
   
   ifnZenbakiarenMailakKalkulatu := iMailak ; 
end ;   
   

procedure TaulaBete(var aliTaula: taliTaula;
                     iLuzeraEfek: integer;
                      iZenbaki_1: integer;
                      iZenbaki_2: integer) ;   
var
   iErrenkada: integer ; 
   liErdia, liDoblea: LongInt ;   
begin    
   aliTaula[0, 1] := iZenbaki_1 ;
   aliTaula[0, 2] := iZenbaki_2 ;
      
   liErdia := iZenbaki_1 ;
   liDoblea := iZenbaki_2 ;
   for iErrenkada:=1 to iLuzeraEfek do
   begin
      liErdia := liErdia div 2 ;
      liDoblea := liDoblea * 2 ;
      aliTaula[iErrenkada, 1] := liErdia ;
      aliTaula[iErrenkada, 2] := liDoblea ;
   end ;     
end ; 

   
procedure TaulaIkusi(const aliTaula: taliTaula;
                        iLuzeraEfek: integer) ;   
var
   iErrenkada: integer ; 
begin  
   writeln('Erdiak':32, 'Dobleak':15) ;
   writeln('------':32, '-------':15) ;
   for iErrenkada:=0 to iLuzeraEfek do
   begin
      write(iErrenkada:10, '. maila') ;
      write(aliTaula[iErrenkada, 1]:15) ;
      writeln(aliTaula[iErrenkada, 2]:15) ;
   end ;
end ;     


procedure ErrenkadaBikoitiakKendu(     const aliTaula: taliTaula;
                                          iLuzeraEfek: integer; 
                                  var aliTaulaLaburra: taliTaula;
                                   var iLuzeraLaburra: integer) ; 
var
   iErrenkada: integer ;
begin
   iLuzeraLaburra := -1 ;     (* taularen lehen errenkada 0 delako *)
   for iErrenkada:=0 to iLuzeraEfek do
   begin
      if aliTaula[iErrenkada, 1] mod 2 = 1 then
      begin
         iLuzeraLaburra := iLuzeraLaburra + 1 ;
         aliTaulaLaburra[iLuzeraLaburra, 1] := aliTaula[iErrenkada, 1] ;
         aliTaulaLaburra[iLuzeraLaburra, 2] := aliTaula[iErrenkada, 2] ;
      end ;
   end ;
end ;                                    
                                      
 
function fnliBatuketakEgin(const aliTaulaLaburra: taliTaula;
                                  iLuzeraLaburra: integer): longint ;
var
   iErrenkada: integer ;
   liBatura: longint ;
begin
   liBatura := 0 ; 
   for iErrenkada:=0 to iLuzeraLaburra do
   begin
      liBatura := liBatura + aliTaulaLaburra[iErrenkada, 2] ;
      //writeln(iErrenkada, '. batura = ', liBatura:0:2) ;
   end ;
   
   fnliBatuketakEgin := liBatura ;
end ;   

{ ----------------------------------------------------------------------------- } 
    
var
   iZenbaki_1, iZenbaki_2, iMailak, iLuzeraEfek, iLuzeraLaburra: integer ; 
   aliTaula, aliTaulaLaburra: taliTaula ;  
   liBiderkadura: longint ;  
begin
   writeln ;
   writeln('MAXINT ----> ', MAXINT) ;
   writeln('iLUZERA = trunc(ln(MAXINT) / ln(2)) ----> ', trunc(ln(MAXINT) / ln(2))) ;
   writeln ;
   writeln ;
   
   writeln(' -------------------------------') ;
   writeln('| Errusiar Biderketaren Metodoa =============') ;
   writeln('| -----------------------------              |') ;
   writeln('|                                            |') ;
   writeln('| Kopuru positiboekin lan eginez, bi zenbaki |') ;
   writeln('| irakurri eta haien biderkadura kalkulatu.  |') ;
   writeln(' ============================================') ;
   writeln ;
   
   repeat
      write('   Lehen biderkagaia eman (1 eta ', HANDIENA, ' artekoa), 39 adibidez: ') ;
      readln(iZenbaki_1) ;
   until (iZenbaki_1 > 0) and (iZenbaki_1 <= HANDIENA) ;
   
   repeat
      write('Bigarren biderkagaia eman (0 eta ', HANDIENA, ' artekoa),  7 adibidez: ') ;
      readln(iZenbaki_2) ;
   until (iZenbaki_2 >= 0) and (iZenbaki_2 <= HANDIENA) ;      
   
   iMailak := ifnZenbakiarenMailakKalkulatu(iZenbaki_1) ;
   
   writeln ;
   writeln(iZenbaki_1, ' biderkagaiari dagokion maila kopurua ', iMailak, ' da:') ;
   
   iLuzeraEfek := iMailak ;
   
   TaulaBete(aliTaula, iLuzeraEfek, iZenbaki_1, iZenbaki_2) ;   (* taularen bigarren dimentsioa ez da behar beti 2 delako *)   
   
   writeln ;
   TaulaIkusi(aliTaula, iLuzeraEfek) ;   (* taularen bigarren dimentsioa ez da behar beti 2 delako *)
   writeln ;

   ErrenkadaBikoitiakKendu(aliTaula, iLuzeraEfek, aliTaulaLaburra, iLuzeraLaburra) ;
   
   TaulaIkusi(aliTaulaLaburra, iLuzeraLaburra) ;   (* taularen bigarren dimentsioa ez da behar beti 2 delako *)
   writeln ; 
   
   liBiderkadura := fnliBatuketakEgin(aliTaulaLaburra, iLuzeraLaburra) ;  
 
   writeln('"Errusiar Biderketaren Metodoa" aplikatuz:    ', iZenbaki_1, ' x ', iZenbaki_2, ' = ', liBiderkadura) ;  
   writeln('Biderkadura ohiko * operadorearen bitartez:   ', iZenbaki_1, ' * ', iZenbaki_2, ' = ', iZenbaki_1 * iZenbaki_2) ;      

   writeln ; 
   writeln('====================================================') ;
   writeln('             RETURN sakatu amaitzeko') ;
   writeln('====================================================') ;
   readln ;
end.