informatika-2022-23: otsaila 2023

2023(e)ko otsailaren 24(a), ostirala

Errekurtsibitatea zertan den

Ez dugu ariketa errekurtsibo asko aurkituko gure programetan, baina interesgarria da kontzeptu hori lantzea azpiprogramak aktibatzen direnean zer gertatzen den ikasteko.

Egoera errekurtsiboak bizitzan eta naturan ematen dira eta jarraian adibide grafikoak erakusten dira:

Faktoriala funtzio errekurtsibo bezala

iZenbaki zenbaki baten faktoriala kalkulatzen duen funtzio errekurtsiboa erakusten da jarraian. Faktorialaren kalkulu errekurtsiboa algoritmo honetan oinarritzen da:

iZenbaki! = iZenbaki * (iZenbaki - 1)!

program FaktorialErrekurtsiboaAzaltzen ;

function fnliFaktorialaKalkulatu(iZbk: integer) : longint  ;
begin
   if iZbk = 1 then
   begin
      WriteLn('1! badakit kalkulatzen, itzuli 1 modulu deitzaileari') ;
      fnliFaktorialaKalkulatu := 1 ;
   end
   else
   begin
      writeln(iZbk, '! kalkulatzeko ', iZbk-1, '! ezagutu behar dut') ;
      fnliFaktorialaKalkulatu := iZbk * fnliFaktorialaKalkulatu(iZbk - 1) ;
      writeln(iZbk, '! kalkulatu dut ', iZbk-1, '! * ', iZbk, ' eginez') ;
   end ;
end ;


var
  liEmaitza : longint ;
  iDatua : integer ;

begin
   repeat
      write('Eman zenbaki osoa: ') ;
      readln(iDatua) ;
   until iDatua > 0 ;
   liEmaitza := fnliFaktorialaKalkulatu(iDatua) ;
   writeln(iDatua, '! = ', liEmaitza) ;
   readln ;
end.

FaktorialErrekurtsiboa.pas programa hartu eta zuk zeuk exekutatu.

Fibonacciren zenbakiak funtzio errekurtsibo bidez

Fibonacciren segidaren adierazpen orokorra gogoratuz:

$F_{n}={\begin{cases}0&n=0{\mbox{ bada}}\\1&n=1{\mbox{ bada}}\\F_{n-1}+F_{n-2}&n>1{\mbox{ bada}}\\\end{cases}}$

Hauxe da fniFibonacci funtzio errekurtsiboa:

{-------------------------FUNTZIO ERREKURTSIBOA-------------------------}
function fniFibonacci(iZbk: integer): integer ;
begin
   if (iZbk = 0) or (iZbk = 1) then
      fniFibonacci := iZbk
   else
      fniFibonacci := fniFibonacci(iZbk-1) + fniFibonacci(iZbk-2) ;
end ;

Teklatuaren bitartez iZenbat kopuru oso bat irakurri eta Fibonacci-ren lehen iZenbat zenbakiak pantailaratu. Hauxe da programa eta bere exekuzioaren irteera bat:

program FibonacciErrekurtsiboa ;
uses
   crt ;
const
   AZKENMUGA = 24 ;    { integer datu-motak ez du gehiago ematen }


{-------------------------FUNTZIO ERREKURTSIBOA-------------------------}
function fniFibonacci(iZbk: integer): integer ;
begin
   if (iZbk = 0) or (iZbk = 1) then
      fniFibonacci := iZbk
   else
      fniFibonacci := fniFibonacci(iZbk-1) + fniFibonacci(iZbk-2) ;
end ;


{---------------------------PROGRAMA NAGUSIA---------------------------}
var
   iZenbat, iKont: integer ;
   cErantzuna: char ;
begin
   writeln ;
   repeat
      repeat
         write('Eman Fibonacci segidaren zenbaki kopurua (1 eta ', AZKENMUGA,' artekoa): ') ;
         readln(iZenbat) ;
      until (iZenbat >= 1) and (iZenbat <= AZKENMUGA) ;

      writeln ;

      for iKont:=1 to iZenbat do
      begin
         if (iKont = 1) or (iKont = 2) then
            writeln(iKont:20, ' >>>>>> ', fniFibonacci(iKont-1))
         else
            writeln(iKont:20, ' -----> ', fniFibonacci(iKont-1)) ;
      end ;

      writeln ;

      write('Amaitu nahi duzu? (B/E): ') ;
      repeat
         cErantzuna := readkey ;
         writeln(cErantzuna) ;
         cErantzuna := upcase(cErantzuna) ;
      until (cErantzuna = 'B') or (cErantzuna = 'E') ;
      writeln ;
      writeln ;
   until cErantzuna = 'B' ;
   
   write('Programa bukatu da') ;
   
   repeat until keypressed ;
end.

Goiko programa hobeto ulertzeko, aztertu ere FibonacciErrekurtsiboa_formatua.pas bertsioa non pantailan idazketa batzuk egiten diren, eta horiei esker programa exekutatzean ikus daiteke kodearen zein puntutan aurkitzen garen.

Azpiprogramak: Divide et Impera

Azpiprogramak → Divide et Impera

program AzpiprogramenParametroak_01 ;
uses
   crt;

procedure Gehitu5Gehiago (Zenbaki1: integer; Zenbaki2: integer);
begin
   textcolor(Cyan);
   writeln('    Gehitu5Gehiago BARRUAN, batuketa egin baino LEHEN:  ',
                Zenbaki1:4, Zenbaki2:4);
   Zenbaki1 := Zenbaki1 + 5;
   Zenbaki2 := Zenbaki2 + 5;
   writeln('    Gehitu5Gehiago BARRUAN, batuketa egin ONDOREN:      ',
                Zenbaki1:4, Zenbaki2:4);
   textcolor(LightGray);
end;
  
{------------------------ Programa Nagusia ------------------------}
var
   iKopuru1, iKopuru2: integer;
begin
   iKopuru1 := 10;
   iKopuru2 := 20;
   writeln('PROGRAMA NAGUSIAN Gehitu5Gehiago deitu AURRETIK:        ',
            iKopuru1:4, iKopuru2:4);
   writeln;
    
   Gehitu5Gehiago(iKopuru1, iKopuru2);
    
   writeln;
   writeln('PROGRAMA NAGUSIAN Gehitu5Gehiago deitu ONDOREN:         ',
            iKopuru1:4, iKopuru2:4);
   writeln;
   readln;
end.

1 Uneko parametroak eta parametro formalak

Programa bat daukagu Gehitu5Gehiago izeneko prozedurari deia egiten diona, honako hauek ikusi:

Gehitu5Gehiago prozedurak bi parametro ditu, biak integer datu-motatakoak

Gehitu5Gehiago prozeduraren bi parametroak sarrerakoak dira

Gehitu5Gehiago prozedurari deia egiteko sententzia bezala idazten da

Gehitu5Gehiago prozedurari deia egitean uneko parametroak komaz banatzen dira

Gehitu5Gehiago prozeduraren parametro formalak puntu eta komaz banatzen dira

AzpiprogramenParametroak_01.pas programaren bitartez zer ikasi duzu?

2 Sarrerako parametroak

Programa bat daukagu Gehitu5Gehiago prozeduraren parametroak sarrerakoak direla ikusi, honako frogak egin:

AzpiprogramenParametroak_02 programa exekutatu eta emaitza aztertu

AzpiprogramenParametroak_02 programaren emaitza aztertu aldaketa hauek eginez:

iKopuru1 uneko parametroaren balioa 100 izan dadila

iKopuru2 uneko parametroaren balioa 200 izan dadila

Gehitu5Gehiago prozedura barruko parametroen izenak aldatu:

Zenbaki1 parametro formala iKopuru1 izendatu

Zenbaki2 parametro formala iKopuru2 izendatu

Gehitu5Gehiago prozeduraren deian uneko parametroak elkar trukatu:

iKopuru1 uneko parametroaren posizioan iKopuru2 idatzi

iKopuru2 uneko parametroaren posizioan iKopuru1 idatzi

Gehitu5Gehiago prozeduraren deia aldatu adierazpen matematiko hauek jarriz:

Gehitu5Gehiago(iKopuru1 + 10, iKopuru2 + 20) ;

Gehitu5Gehiago prozeduraren deia aldatu konstante hauek jarriz:

Gehitu5Gehiago(11, 22) ;

AzpiprogramenParametroak_02.pas programaren bitartez zer ikasi duzu?

3 Uneko parametro eta parametro formalen arteko bateragarritasuna

Gehitu5Gehiago prozeduraren parametroen datu-motak aldatu, honako frogak egin:

AzpiprogramenParametroak_03 programaren hasieran parametro guztiak integer dira:

iKopuru1 eta iKopuru2 aldagaiak integer bezala erazagutu dira

Zenbaki1 eta Zenbaki2 parametro formalak integer dira ere

Gehitu5Gehiago prozeduraren parametro formal baten datu-mota aldatu:

Zenbaki1 parametro formala integer bezala mantendu

Zenbaki2 parametro formala real datu-motara aldatu

iKopuru1 eta iKopuru2 uneko parametroak integer bezala mantendu

Gehitu5Gehiago prozeduraren deian uneko parametro baten datu-mota aldatu:

Zenbaki1 parametro formala integer bezala mantendu

Zenbaki2 parametro formala integer bezala berriro jarri

iKopuru1 uneko parametroa integer bezala mantendu

iKopuru2 uneko parametroari datu-mota aldatu real jarriz

AzpiprogramenParametroak_03.pas programaren bitartez zer ikasi duzu?

4 Irteerako parametroak

Gehitu5Gehiago prozeduraren parametro bat irteerakoa izanik, honako frogak egin:

Gehitu5Gehiago prozedura hasierakoa da eta lehen bezala:

Zenbaki1 parametro formala integer izanik sarrerakoa da

Zenbaki2 parametro formala integer izanik sarrerakoa da

Programa exekutatu Gehitu5Gehiago prozeduraren deia hasierako hau delarik:

Gehitu5Gehiago(iKopuru1, iKopuru2) ;

Programa exekutatu Gehitu5Gehiago prozeduraren deia aldatu adierazpen matematiko hauek jarriz:

Gehitu5Gehiago(iKopuru1 + 10, iKopuru2 + 20) ;

Aldaketa, Gehitu5Gehiago prozeduraren parametro formal baten datu-mota aldatu:

iKopuru1 eta iKopuru2 uneko parametroak integer dira

Zenbaki1 parametro formala integer bezala mantendu

Zenbaki2 parametro formala real datu-motara aldatu

Gehitu5Gehiago prozedura berriarekin, programa exekutatu deiak hauek direla:

Gehitu5Gehiago(iKopuru1, iKopuru2) ;

Gehitu5Gehiago(iKopuru1 + 10, iKopuru2) ;

Gehitu5Gehiago(iKopuru1, iKopuru2 + 20) ;

Gehitu5Gehiago hasierako egoera berreskuratu (parametro bat sarrerakoa eta bestea irteerakoa) eta prozeduraren deia aldatu konstante hauek jarriz:

Gehitu5Gehiago(11, 22) ;

AzpiprogramenParametroak_04.pas programaren bitartez zer ikasi duzu?

5 Aldagai orokorrak

iKopuru1 eta iKopuru2 aldagaiak non erazagutzen diren garrantzitsua da:

Gehitu5Gehiago prozedura barruko lehen esleipena aldatu hau idatziz:

iKopuru1 := Zenbaki1 + 5 ;

Ikusi iKopuru1 eta iKopuru2 aldagaiak prozedura baino lehenago erazaguturik daudela

Gehitu5Gehiago prozedura barruko esleipen berria mantenduz, iKopuru1 eta iKopuru2 aldagaiak tokiz aldatu:

iKopuru1 := Zenbaki1 + 5 ;

iKopuru1 eta iKopuru2 aldagaiak prozedura eta gero erazagutu

AzpiprogramenParametroak_05.pas programaren bitartez zer ikasi duzu?

6 Bertako aldagaiak

Gehitu5Gehiago prozeduraren barruan aldagai laguntzaileak sortuko ditugu, egiteko daukagun asmoa hauxe da urratsez-urrats:

iLaguntzaile1 izeneko aldagaia sortu integer bezala

iLaguntzaile1 izeneko aldagaiari hasieraketarik ez egin eta...

...iLaguntzaile1 aldagaiaren balioa pantailaratu prozedura barruan

Gehitu5Gehiago prozeduraren bertako aldagaiak iker ditzagun:

Aurrekoa egin bi aldagai laguntzaile sortuz:

var iLaguntzaile1, iLaguntzaile2 : integer ;

iLaguntzaile1 eta iLaguntzaile2 aldagaiei hasieraketarik ez egin eta...

writeln(' iLaguntzaile1 = ', iLaguntzaile1, ' iLaguntzaile2 = ', iLaguntzaile2) ;

Aurrekoa errepikatu bi aldagai laguntzaileen sorreran ordena trukatuz:

var iLaguntzaile2, iLaguntzaile1 : integer ;

iLaguntzaile1 eta iLaguntzaile2 aldagaiei hasieraketarik ez egin eta...

writeln(' iLaguntzaile1 = ', iLaguntzaile1, ' iLaguntzaile2 = ', iLaguntzaile2) ;

Programa nagusian lan eginez iKopuru1 eta iKopuru2 aldagaien balioak pantailaratu

Programa nagusian lan eginez iLaguntzaile1 eta iLaguntzaile2 aldagaien balioak pantailaratu

AzpiprogramenParametroak_06.pas programaren bitartez zer ikasi duzu?

7 Funtzioak

Programa bat daukagu fniBatuBiEtaGehitu5Gehiago izeneko funtzioari deitzen diona, honako hauek ikusi:

fniBatuBiEtaGehitu5Gehiago funtzioak bi parametro ditu, biak integer datu-motatakoak

fniBatuBiEtaGehitu5Gehiago funtzioaren bi parametroak sarrerakoak dira.

fniBatuBiEtaGehitu5Gehiago funtzioak irteera bakarra du eta integer datu-motatakoa da

fniBatuBiEtaGehitu5Gehiago funtzioari deia egitean esleipen bat idatziko da

fniBatuBiEtaGehitu5Gehiago funtzioaren deia adierazpen aritmetiko batean ager daiteke

fniBatuBiEtaGehitu5Gehiago funtzioaren deia beste azpiprograma baten uneko parametroa izan daiteke

fniBatuBiEtaGehitu5Gehiago funtzioak emaitza itzuliko dio programa nagusiari, emaitza den balio hori itzultzeko fniBatuBiEtaGehitu5Gehiago etiketa erabiliko du

AzpiprogramenParametroak_07.pas programaren bitartez zer ikasi duzu?

8 Faktoriala kalkulatzen duen funtzio iteratiboa

iZenbaki zenbaki baten faktoriala kalkulatzen duen funtzioak eragiketa hau egin behar du eta horretarako FOR-DO egitura bat erabil daiteke:

iZenbaki! = 1 * 2 * 3 * ... (iZenbaki - 1) * iZenbaki

program FaktorialaKalkulatzen ;

function fnliFaktoriala(iZbk:integer) : longint ;
var
   k : integer ;
   liMetatua : longint ;
begin
   liMetatua := 1 ;
   for k:=1 to iZbk do
   begin
      liMetatua := liMetatua*k ;
      WriteLn(k, ' ---> ', liMetatua) ;
   end ;
   fnliFaktoriala := liMetatua ;
end ;

var
  liEmaitza : longint ;
  iDatua : integer ;
begin
   repeat
      write('Eman zenbaki osoa: ') ;
      readln(iDatua) ;
   until iDatua > 0 ;
   liEmaitza := fnliFaktoriala(iDatua) ;
   writeln(iDatua, '! = ', liEmaitza) ;
   readln ;
end.

Programa horretan fnliFaktoriala() funtzioari dei bakar bat egiten zaio, programa nagusian liEmaitza aldagaiari balioa ematen zaio baino lehenago iDatua aldagaiaren balioa teklatuaren bitartez irakurri dugu. fnliFaktoriala() funtzioaren kodifikazioan FOR-DO egitura bat behar dugu eta hura kontrolatzeko k aldagaia behar dugu, faktoriala kalkulatzen duen liMetatua aldagaia beharko dugu ere.

fnliFaktoriala() funtzioak programa nagusiari emaitza itzultzeko fnliFaktoriala etiketa erabili behar da derrigorrez, bestela liMetatua aldagaiak faktorialaren balioa gordeko du baina programa nagusiari ez zaio inolaz ere helduko.

AzpiprogramenParametroak_08.pas programaren bitartez zer ikasi duzu?

9 Errekurtsibitatea

Gehitu5Gehiago prozedurari deituko diogu Gehitu5Gehiago prozeduraren barrutik:

Gehitu5Gehiago prozedura barruko esleipenak mantendu baina IF-THEN bat gehitu, honelaxe:

Zenbaki1 := Zenbaki1 + 5 ;

if Zenbaki1 <= 25 then Gehitu5Gehiago(Zenbaki1, Zenbaki2) ;

Zenbaki2 := Zenbaki2 + 5 ;

Aurrekoa errepikatu baina Zenbaki1 parametro formala irteerakoa izanik:

procedure Gehitu5Gehiago (var Zenbaki1: integer; Zenbaki2: integer) ;

Aurrekoa errepikatu IF-THEN egitura kenduz eta dei errekurtsiboa mantenduz:

Zenbaki1 := Zenbaki1 + 5 ;

Gehitu5Gehiago(Zenbaki1, Zenbaki2) ;

Zenbaki2 := Zenbaki2 + 5 ;

AzpiprogramenParametroak_09.pas programaren bitartez zer ikasi duzu?

10 Faktoriala kalkulatzen duen funtzio errekurtsiboa

iZenbaki zenbaki baten faktoriala kalkulatzen duen funtzio errekurtsiboa erakusten da jarraian. Faktorialaren kalkulu errekurtsiboa algoritmo honetan oinarritzen da:

iZenbaki! = iZenbaki * (iZenbaki - 1)!

program FaktorialErrekurtsiboa ;

function fnliFaktoriala(iZbk:integer) : longint  ;
begin
   writeln('Dei errekurtsiboa baino lehen ---> ', iZbk) ;   
   if iZbk = 1 then
      fnliFaktoriala := 1
   else
      fnliFaktoriala := iZbk * fnliFaktoriala(iZbk - 1) ;
   writeln ('Dei errekurtsiboa eta gero ------> ', iZbk) ;   
end ;

var
  liEmaitza : longint ;
  iDatua : integer ;

begin
   repeat
      write('Eman zenbaki osoa: ') ;
      readln(iDatua) ;
   until iDatua > 0 ;
   liEmaitza := fnliFaktoriala(iDatua) ;
   writeln(iDatua, '! = ', liEmaitza) ;
   readln ;
end.

AzpiprogramenParametroak_10.pas programaren bitartez zer ikasi duzu? Azalpenak eta irudiak ikusteko Errekurtsibitatea zertan den izeneko blog-artikulua irakurri.

6. astea | letra bat asmatzen

Ordenadoreak letra bat pentsatuko du eta guk asmatu beharko dugu

A eta Z bitartean dagoen letra bat aukeratuko du ordenadoreak eta ezezaguna den letra hori guk asmatuko dugu. Egiten dugun saiakera bakoitzeko, programak informazioa emango digu esanez letra ezezaguna zein tartetan dagoen. Algoritmoa hauxe da:

Ordenadoreak letra bat aukeratuko du, A eta Z bitartean dagoen letra bat aukeratuko du. Horretarako, random() funtzio estandarra erabiliko du (randomize prozedurarekin batera)

Ezezaguna den letraren heina [A, Z] da hasieran, behemuga A eta goimuga Z. Beraz, cBehemuga:='A' eta cGoimuga:='Z'

Errepikatu letra asmatu arte edo 5 saiakera egin arte:

Teklatuaren bitartez irakurriz, soluzio bat proposatuko diogu programari. Nahi dugun soluzioa proposatuko diogu programari, modurik eraginkorrena da tartearen erdiko letra proposatzea programari, erdikoa honela kalkulatuko genuke: cSoluzioa := chr((ord(cBehemuga) + ord(cGoimuga)) div 2)

Gure proposamenaren arabera programak bi aukera izango ditu eta honela jokatuko du:

Proposatutako letra eta programak asmatutakoa bat datoz, letra asmatu dugunez begiztatik irten

Proposatutako letra eta programak asmatutakoa ez datoz bat, ez dugunez letra asmatu beste saiakera bat emango digu programak (5 saiakeraren muga ez badugu oraindik gainditu). Hurrengo saiakeraran erakutsiko digun tartea egokituko du programak, honelaxe:

Proposatu diogun letra programarena baino handiagoa bada (tartearen cGoimuga aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)

Proposatu diogun letra programarena baino txikiagoa bada (tartearen cBehemuga aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)

Emaitza erakutsi, begiztatik irteteko aukerak:

Letra asmatu diogu programari: cSoluzioa erakutsi

Saiakerak 5 baino gehiago izan dira

Zergatik 5 saiakera?

A-ren eta Z-ren artean 26 karaktere. Urrats bakoitzean,

karaktere guztietatik erdiak baztertzen dira. Beraz:

log₂(26)=4,70044

logaritmo (2 oinarrian) 26 zenbakiarena 4,70044 da

  2^x = 26   >>>   ln(2^x) = ln(26)   >>>
  x·ln(2) = ln(26)   >>>   x = ln(26)/ln(2)
  x = 3.25810/0.69315 = 4.70044   >>>   x=5

Ikusi LetraAsmatu.exe programaren balizko exekuzio bat:

Eskatzen den ariketaren hurbilpen hau... LetraAsmatu_hasiera.pas ...abiapuntutzat har daiteke. Hau da...
LetraAsmatu.pas ...iturburu-programa bat. Zein da zurea?

6. astea | zenbaki bat asmatzen

Guk pentsaturiko zenbakia ordenadoreak asmatuko digu

0 eta 100 bitartean dagoen zenbaki osoa pentsatuko dugu eta ordenagailuak galdera batzuk eginez zenbaki hori asmatuko digu. Algoritmoa hauxe da:

Zenbaki oso bat pentsatu dugu, hots, 0 eta 100 bitartean dagoen zenbaki osoa pentsatu dugu

Ezezaguna den zenbakiaren heina [0, 100] da hasieran, behemuga 0 eta goimuga 100. Beraz, iBehemuga:=0 eta iGoimuga:=100

Errepikatu zenbakia asmatu arte edo 7 saiakera egin arte:

Programak proposatuko digun soluzioa kalkulatuko du, soluzioa: baligarria den heinaren erdia. Beraz, iSoluzioa := (iBehemuga + iGoimuga) div 2

Programak galdetuko digu proposatu duen soluzioa egokia den ala ez, aukerak:

B, bai, proposatu digun zenbakia guk pentsatu duguna izan da (begiztatik irten)

H, ez, proposatu digun zenbakia ez da guk pentsatutakoa, proposatu digun zenbakia gurea baino handiagoa da (heinaren iGoimuga aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)

T, ez, proposatu digun zenbakia ez da guk pentsatutakoa, proposatu digun zenbakia gurea baino txikiagoa da (heinaren iBehemuga aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)

Emaitza erakutsi, begiztatik irteteko aukerak:

Gure erantzuna B izan denez, ordenagailuak gure zenbakia asmatu du: iSoluzioa erakutsi

Saiakerak 7 baino gehiago izan dira, horrek esan nahi du ez dugula zuzen jokatu eta gure erantzunetan gezurra esan diogula programari

Zergatik 7 saiakera?

0-tik 100-ra, biak barne, 101 aukera. Urrats bakoitzean,

aukera guztietatik erdiak baztertzen dira. Beraz:

log₂(101)=6,658

logaritmo (2 oinarrian) 101 zenbakiarena 6,658 da

  2^x = 101   >>>   ln(2^x) = ln(101)   >>>
  x·ln(2) = ln(101)   >>>   x = ln(101)/ln(2)
  x = 4.61512/0.69315 = 6.65821   >>>   x=7

Ikusi ZenbakiaAsmatu.exe programaren balizko exekuzio bat:

Eskatzen den ariketaren hurbilpen hau... ZenbakiaAsmatu_hasiera.pas ...abiapuntutzat har daiteke. Hona hemen... ZenbakiaAsmatu.pas ...iturburu-programa, eta... ZenbakiaAsmatu_azpiprogramak.pas beste iturburu-programa bat da. Ikusten denez, soluzio bakarra ez dago, zein da zurea?

6. astea | Fibonacciren zenbakiak azpiprogramaz

Leonardo Pisano (Pisa, Italia, 1170-1250), Leonardo Bonacci, Leonardo Fibonacci edo Fibonacci moduan ezaguna, Italiar matematikaria izan zen, Erdi Aroko ezagunetarikoa. Ezaguna da batez ere bi aurkikuntzengatik:

Hindu-arabiar zenbaki sistema Europan sartu zuen eta berau erabiltzeko bideak jarri zituen XIII. mendeko "Liber Abaci" liburuaren bitartez

Fibonacciren zenbakiak deskribatu zituen liburu berean, nahiz eta berak ez zituen aurkitu baizik eta adibide moduan jarri

Leonardo Pisano, Fibonacci, ezagutzeko hemen duzu artikulu bat Fibonacci, el matemático que se puso a contar conejos y descubrió la secuencia divina.

Fibonacciren sekuentziako lehen zenbakia 0 da, Fibonacci-ren bigarren zenbakia 1 da, eta hirugarren zenbakia lortzeko aurreko biak batuko dira, horregatik Fibonacciren hirugarren zenbakia 1 da, laugarren zenbakia 2 izango da, bosgarrena 3, ...

Beraz, Fibonacciren sekuentzia honako hau da:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...

Ondorengoa da Fibonacciren segidaren adierazpen orokorra:

$F_{n}={\begin{cases}0&n=0{\mbox{ bada}}\\1&n=1{\mbox{ bada}}\\F_{n-1}+F_{n-2}&n>1{\mbox{ bada}}\\\end{cases}}$

Fibonacciren zenbakiak grafikoki adieraztean honako blokeen sorta eta espirala lortzen dira:

Fibonacciren sekuentziako bi zenbaki hartuz eta zatiketa eginez, urrezko zenbakia edo jainkozko proportzioa edo urrezko proportzioa edo zerutiar zenbakia lortzen da:

Fibonacciren sekuentzia sarritan agertzen da naturan. Izan ere, naturan hazkundea gertatzen denean Fibonacciren sekuentziaren arabera ematen da:

Eskatzen den programa (prozedura bat eta funtzio bat)

Programa bakarra izan arren programak bi zati izango ditu. Lehen zatian prozedura bati dei egingo zaio eta programaren bigarren zatian funtzio bati dei egingo zaio.

Programaren prozedura eta programaren funtzioa jarraian deskribatzen dira eta bakoitzaren kode gehiena ematen da. Ikaslearen lana da kodeak bukatzea eta programaren emaitzak ulertzea.

Lehen zatia. Fibonacciren sekuentzia osatuko duten zenbakien iZenbat kopurua teklatuz irakurri programa nagusian eta prozedura batek ondoko taularen pantailaraketa egin dezala FOR-DO egitura bat erabiliz, FibonaccirenSekuentziaPantailaratu izeneko prozeduraren barruan errepikatzen den prozesua hau delarik:

   procedure FibonaccirenSekuentziaPantailaratu(iZenbat: integer) ;

      ...
   
   begin { prozeduraren kodea hemen hasten da }

      ...
      
      for k:=3 to iZenbat do
      begin
         iFibo3 := iFibo1 + iFibo2 ;
         iIndizea := iIndizea + 1 ;
         writeln(iIndizea:15, iFibo3:15, 1.0*iFibo3/iFibo2:25:7) ;
      
         iFibo1 := iFibo2 ;
         iFibo2 := iFibo3 ;
      end ; 

      ...
      
   end ; { prozeduraren kodea hemen amaitzen da }

Programaren lehen zatiko irteera bat hau izan daiteke:

Bigarren zatia. Prozesu errepikakor bat izango da eta bertatik irteteko b edo B erantzun beharko da, bestela programa nagusian iMuga teklatuz irakurriko da eta funtzio batek kalkulatuko du 0-tik hasita zenbat Fibonacciren zenbaki dauden. Horretarako, WHILE-DO egitura bat erabiliko da, funtzio barruko prozesu errepikakorra hauxe da, non funtzioak itzuli behar duen emaitza iFiboKopuru den eta arrazoi horregatik balio hori kanporatu behar du fniFibonacciZenbakienKopuruaKalkulatu izeneko funtzioak:

   function fniFibonacciZenbakienKopuruaKalkulatu(iMuga: integer): integer ;

      ...
   
   begin { funtzioaren kodea hemen hasten da }

      ...
      
      iFibo1 := 0 ;
      iFibo2 := 1 ;
      iFibo3 := iFibo1 + iFibo2 ;

      while iFibo3 <= iMuga do
      begin
         iFibo1 := iFibo2 ;
         iFibo2 := iFibo3 ;
         iFibo3 := iFibo1 + iFibo2 ;
         iFiboKopuru := iFiboKopuru + 1 ;
      end ;
   
      fniFibonacciZenbakienKopuruaKalkulatu := iFiboKopuru ;
   end ; { funtzioaren kodea hemen amaitzen da }

Programaren bigarren zatiko irteera bat hau izan daiteke:

Balizko emaitzaren iturburu-programa hau izan daiteke... laster argitaratuko da

6. astea | zenbaki konbinatorioa (prozedura)

zenbaki konbinatorioa, kopuru osoa da eta hura lortzeko m eta n zenbaki osoak eta positiboak ezagutu behar dira. Jakinik ere, zenbaki negatiboen faktoriala definiturik ez dagoelako datuek baldintza hau betetzen dutela: m >= n.

Ikusita daukagun ondoko programa honek ZenbakiKonbinatorioaMonolitikoa.pas zenbaki konbinatorioa kalkulatzen du, baina aintzat hartu beharra dago programak inolako barne antolaketarik ez duelako faktorialaren kalkulua hiru aldiz egiten duela:

Aurreko programaren beste bertsio bat ondoko irudian erakusten da, non programa nagusian datuak irakurri eta gero EmaitzaKalkulatu()izeneko prozedurari deia egiten zaion. Prozedura horren barruan hiru faktorialak kalkulatuko dira:

Aurrekoa ikusita, prozeduraren barruan faktorialak kalkulatzen duen programa egizu. Beraz, ZenbakiKonbinatorioaProzeduraz.PAS programa idatz ezazu, hauek izanik hiru azpiprogramen deskribapenak eta definizioak.

1. DatuakHartu()prozedura barruan bi ReadLn() egin ondoren irakurritako bi balioak programa nagusira bidaltzen dira. Hauxe litzateke DatuakHartu()prozeduraren definizioa:

DatuakHartu() prozedura,

sarrera: sarrerarik ez dago

irteera: bi irteera, biak Integer datu-motakoak

2. EmaitzaKalkulatu()prozedura barruan hiru aldiz kalkulatzen da faktoriala, horregatik programa hori beste modu batez plantea daiteke: faktoriala lortzeko gai den funtzio bat erabili eta funtzioari hiru dei egin. Hauxe litzateke EmaitzaKalkulatu()prozeduraren definizioa:

EmaitzaKalkulatu() prozedura,

sarrera: bi sarrera, Integer datu-motako bi sarrera

irteera: irteera bakarra, LongInt datu-motakoa

3. fniFaktoriala()funtzioak zenbaki oso baten faktoriala kalkulatu eta itzultzen du. Hauxe litzateke fniFaktoriala() funtzioaren definizioa:

fniFaktoriala() funtzioa,

sarrera: Integer bat

irteera: LongInt bat

Hona hemen ZenbakiKonbinatorioaAzpiprogramaz.pas programa non datuak prozedura batean irakurtzen diren:

program ZenbakiKonbinatorioa_Azpiprogramaz ;

procedure DatuakHartu(var iZbkM, iZbkN: integer) ;
begin
   repeat
      write('m zenbaki osoa eta positiboa eman: ') ;
      readln(iZbkM) ;
      write('n zenbaki osoa (non n <= m ): ') ;
      readln(iZbkN) ;
   until (iZbkN >= 0) AND (iZbkM >= iZbkN) ;
end ;

function fnliFaktoriala(iZbk: integer): longint ;
var
   iKontagailua: integer ;
   liMetagailua: longint ;
begin
   liMetagailua := 1 ;
   for iKontagailua:=1 to iZbk do
      liMetagailua := liMetagailua * iKontagailua ;

   fnliFaktoriala := liMetagailua ;
end ;


procedure EmaitzaKalkulatu(iZbkM, iZbkN: integer; var iEmaitza: integer) ;
var
   iZbkM_N: integer ;
   liFaktM, liFaktN, liFaktM_N: longint ;
begin
   liFaktM := fnliFaktoriala(iZbkM) ;
   liFaktN := fnliFaktoriala(iZbkN) ;
   iZbkM_N := iZbkM - iZbkN ;
   liFaktM_N := fnliFaktoriala(iZbkM_N) ;

   iEmaitza := liFaktM div (liFaktN * liFaktM_N) ;
end ;

{ ----------PROGRAMA NAGUSIA---------- }
var
   iZbkM, iZbkN, iEmaitza: integer ;
begin
   DatuakHartu(iZbkM, iZbkN) ;
   EmaitzaKalkulatu(iZbkM, iZbkN, iEmaitza) ;
   write('Zenbaki konbinatorioa --->   ', iZbkM, '! div (', iZbkN,'! * ', iZbkM-iZbkN,'!)') ;
   write(' = ', iEmaitza) ;
   readln ;
end.

6. astea | zenbaki konbinatorioa (funtzioa)

zenbaki konbinatorioa, kopuru osoa da eta hura lortzeko m eta n zenbaki osoak eta positiboak ezagutu behar dira. Jakinik ere, zenbaki negatiboen faktoriala definiturik ez dagoelako datuek baldintza hau betetzen dutela: m >= n.

Ondoko programa honek ZenbakiKonbinatorioaMonolitikoa.pas zenbaki konbinatorioa kalkulatzen du, baina aintzat hartu beharra dago programak inolako barne antolaketarik ez duelako faktorialaren kalkulua hiru aldiz egiten duela:

Aurreko programaren beste bertsio bat ondoko irudian erakusten da, ZenbakiKonbinatorioaFuntzioz.pas izeneko bertsio berri horrek programa nagusian datuak irakurri ondoren fnliFaktoriala() izeneko funtzioa hiru aldiz deia egiten dio. Funtzio horrek programa nagusiko datu bat jasotzen du eta dagokion faktoriala kalkulatu eta programa nagusiari itzultzen dio:

program ZenbakiKonbinatorioa_Funtzioz ;

function fnliFaktoriala(iZbk : integer) : longint ;
var
    iKontagailua : integer ;
    liMetagailua : longint ;
begin
    liMetagailua := 1 ;
    for iKontagailua:=1 to iZbk do
       liMetagailua := liMetagailua * iKontagailua ;

    fnliFaktoriala := liMetagailua ;
end ;

{ ----------PROGRAMA NAGUSIA---------- }
var
    iZbkM, iZbkN, iZbkM_N, iEmaitza : integer ;
    liFaktM, liFaktN, liFaktM_N : longint ;

begin
    repeat
        write('m zenbaki osoa eta positiboa eman: ') ;
        readln(iZbkM) ;
        write('n zenbaki osoa (non n <= m ): ') ;
        readln(iZbkN) ;
    until (iZbkN >= 0) AND (iZbkM >= iZbkN) ;

    liFaktM := fnliFaktoriala(iZbkM) ;

    liFaktN := fnliFaktoriala(iZbkN) ;

    iZbkM_N := iZbkM - iZbkN ;
    liFaktM_N := fnliFaktoriala(iZbkM_N) ;

    iEmaitza := liFaktM div (liFaktN * liFaktM_N) ;

    write('Zenbaki konbinatorioa ---> ', iZbkM, '! div (', iZbkN,'! * ', iZbkM-iZbkN,'!)') ;
    write(' = ', iEmaitza) ;

    readln ;
end.