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.

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            *)
   ...                                                    

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).

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.

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.