Informatika 2023-24: otsaila 2024

2024(e)ko otsailaren 28(a), asteazkena

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:

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

iZenbaki! = iZenbaki * (iZenbaki - 1)!

/* 14-Jarduera_Faktorial-Errekurtsiboa: faktoriala errekurtsiboki */

#include ++stdio.h>

long int faktorialaKalkulatu(int iZbk)
{
    if (iZbk == 1)
    {
        printf("  1! badakit kalkulatzen, itzuli 1 modulu deitzaileari\n");
        return 1;
    }
    else
    {
        printf("%3d! kalkulatzeko...   %d! ezagutu behar dut\n", iZbk, iZbk - 1);
        long int emaitza = iZbk * faktorialaKalkulatu(iZbk - 1);
        printf("%3d! kalkulatu dut...  %d! * %d eginez\n", iZbk, iZbk - 1, iZbk);
        return emaitza;
    }
}

int main()
{
    int iDatua;
    long int liEmaitza;

    do
    {
        printf("Eman zenbaki osoa bere faktoriala kalkulatzeko (adibidez 6): ");
        scanf("%d", &iDatua);
    } while (iDatua ++= 0);

    liEmaitza = faktorialaKalkulatu(iDatua);
    printf("%d! = %ld\n", iDatua, liEmaitza);

    return 0;
}

FaktorialErrekurtsiboa.pas programa hartu eta zuk zeuk exekutatu.

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

Hasierako programa

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.  

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?

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?

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?

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?

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?

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?

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?

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?

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?

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.

Ordenadoreak letra bat aukeratuko du, A eta Z bitartean dagoen letra bat aukeratuko du. Horretarako, random() funtzio estandarra erabiliko du (randomize prozedurarekin batera). programak aukeratzen duen letra cAsmatzeko aldagaian gordeko da
Ezezaguna den letraren heina [A, Z] da hasieran, behemuga A eta goimuga Z. Beraz, cProposatutakoTxikiena:='A' eta cProposatutakoHandiena:='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: M lehen saiakeran, G edo T bigarren saiakeran...
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 cProposatutakoHandiena aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)
Proposatu diogun letra programarena baino txikiagoa bada (tartearen cProposatutakoTxikiena aldatu eta 3. urratsaren hasierara itzuli saiakera berri bat egiteko)

Emaitza erakutsi, begiztatik irteteko aukerak:

Letra asmatu diogu programari, zorionak eta iSaiakera erakutsi
Saiakerak 5 baino gehiago izan dira, cAsmatzeko aldagaiaren edukia erakutsi

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 eskatzen den LetraAsmatu.pas iturburu-programa bat. Zein da zurea?

Hona hemen programaren kodifikazioa non, mesedez, pantaila-irteeran agertzen diren koloreei jaramonik ez diezuen egin behar. Aldiz, oso interesgarria da boAsmatua aldagai boolear laguntzilearen erabilera. Ikusi ere random(), chr(), ord(), pred() eta succ() funtzioek programari egiten dioten ekarpena:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

{  
   'A' eta 'Z' arteko letra bat programak aukeratuko du,
   letra hori guk asmatuko dugu erantzun hauek emanez: 
 
   00000000011111111112222222
   12345678901234567890123456
   ABCDEFGHIJKLMNOPQRSTUVWXYZ
               M                1. saikera
         G            T         2. saikera
      D     J     P      W      3. saikera
    B   F           R      Y    4. saikera
                                5. saikera
                                 
   ---------------------------------------
     
   Zergatik 5 saiakera?
 
   log2(26)=4.7
   logaritmo 2 oinarrian 26 zenbakiarena 4.7 da
   A eta Z artean 26 karaktere
}
 
program LetraAsmatu;
uses
   crt;
const
   iSAIAKERAKOPURUMAXIMOA = 5;
var
   cLetra, cAsmatzeko, cProposatutakoTxikiena, cProposatutakoHandiena, cItxaron: char;
   iEsparrua, iAleatorioa, iSaiakera: integer;
   boAsmatua: boolean;
    
begin
   clrscr;
   writeln;
   writeln('''A'' eta ''Z'' arteko letra bat aukeratuko du konputagailuak eta');
   writeln('ea letra hori asmatzeko gai zaren. Zure proposamenak egitean');
   writeln('"Bilaketa Bitarra" deitzen den estrategia erabil ezazu');
   writeln;
   writeln;
   writeln('Aurrera egiteko tekla bat sakatu!');
   writeln;
   writeln;
   cItxaron := readkey;
   writeln(cItxaron);
    
   clrscr; 
   writeln('//////////////////////////////////////');
   writeln;
    
   randomize;
 
   iEsparrua := ord('Z') - ord('A') + 1;
    
   iAleatorioa := random(iEsparrua);
   (* *) writeln('iAleatorioa=', iAleatorioa);
   cAsmatzeko := chr(iAleatorioa + ord('A'));   (* 0-A, 1-B, 2-C, ... 24-Y, 25-Z *)
   (* *) writeln('cAsmatzeko=', cAsmatzeko);
   writeln;
 
   boAsmatua := FALSE;
   iSaiakera := 1;
   cProposatutakoTxikiena := 'A';
   cProposatutakoHandiena := 'Z';
   repeat
      repeat
         writeln('Saiakera=', iSaiakera, '     Zein da ezkutatu dugun letra maiuskula? ');
         // kolorerik gabe
         write('               ', cProposatutakoTxikiena, '..', cProposatutakoHandiena,' alfabetoko letra bat eman, eta ea asmatzen duzun: ');
          
         // koloreekin
         {
         write('               ');
         textcolor(Cyan);
         write(cProposatutakoTxikiena);
         textcolor(LightGray);
         write('..');
         textcolor(Cyan);
         write(cProposatutakoHandiena);
         textcolor(LightGray);
         write(' alfabetoko letra bat eman, eta ea asmatzen duzun: ');
         }
         readln(cLetra);
         cLetra := upcase(cLetra);
         if (cLetra < cProposatutakoTxikiena) or (cLetra > cProposatutakoHandiena) then
         begin
            // kolorerik gabe
            writeln('Datua ''', cProposatutakoTxikiena, ''' eta ''', cProposatutakoHandiena, ''' artekoa, mesedez!');
             
            // koloreekin
            {
            write('Datua ');
            textcolor(Red);
            write('''', cProposatutakoTxikiena, '''');
            textcolor(LightGray);
            write(' eta ');
            textcolor(Red);
            write('''', cProposatutakoHandiena, '''');
            textcolor(LightGray);
            writeln(' artekoa, mesedez!');
            }
         end;
      until (cLetra >= cProposatutakoTxikiena) and (cLetra <= cProposatutakoHandiena);
       
      if cLetra=cAsmatzeko then
      begin
         boAsmatua := TRUE;
         writeln;
         // kolorerik gabe
         writeln('OSO ONDO!');
          
         // koloreekin
         {
         textcolor(Green);
         writeln('OSO ONDO!');
         textcolor(LightGray);
         }
      end
      else
      begin
         iSaiakera := iSaiakera + 1;
         // kolorerik gabe
         write('EZ, EZ DUZU ASMATU!   ');
          
         // koloreekin
         {
         textcolor(Red);
         write('EZ, EZ DUZU ASMATU!   ');
         textcolor(LightGray);
         }
         if cAsmatzeko < cLetra then
         begin
            cProposatutakoTxikiena := cProposatutakoTxikiena;   {esleipen hau soberan egon daiteke}
            cProposatutakoHandiena := pred(cLetra);
 
            // kolorerik gabe
            writeln('Saiatu bilatzen ''', cProposatutakoTxikiena, ''' eta ''', cProposatutakoHandiena, ''' bitartean');
             
            // koloreekin
            {
            write('Saiatu bilatzen ');
            textcolor(Cyan);
            write('''', cProposatutakoTxikiena, '''');
            textcolor(LightGray);
            write(' eta ');
            textcolor(Cyan);
            write('''', cProposatutakoHandiena, '''');
            textcolor(LightGray);
            writeln(' bitartean');
            }
         end;
         if cAsmatzeko > cLetra then
         begin
            cProposatutakoHandiena := cProposatutakoHandiena;   {esleipen hau soberan egon daiteke}
            cProposatutakoTxikiena := succ(cLetra);
             
            // kolorerik gabe
            writeln('Saiatu bilatzen ''', cProposatutakoTxikiena, ''' eta ''', cProposatutakoHandiena, ''' bitartean');
             
            // koloreekin
            {
            write('Saiatu bilatzen ');
            textcolor(Cyan);
            write('''', cProposatutakoTxikiena, '''');
            textcolor(LightGray);
            write(' eta ');
            textcolor(Cyan);
            write('''', cProposatutakoHandiena, '''');
            textcolor(LightGray);
            writeln(' bitartean');
            }
         end; 
         writeln;
      end;
   until (iSaiakera > iSAIAKERAKOPURUMAXIMOA) or boAsmatua;
    
   if boAsmatua then
   begin
      writeln(iSaiakera, ' saiakera egin ondoren asmatu duzu');
   end
   else
   begin
      writeln('Saiakerak agortu dituzu eta ez duzu asmatu');
      write('Asmatu beharreko letra hau izan da: ');
      // kolorerik gabe
      writeln(cAsmatzeko);
       
      // koloreekin
      {
      textcolor(Red);
      writeln(cAsmatzeko);
      textcolor(LightGray);
      }
   end;
    
   writeln;
   writeln('//////////////////////////////////////');
   readln;
end.
 
 
00000000011111111112222222
12345678901234567890123456
ABCDEFGHIJKLMNOPQRSTUVWXYZ
            M                 1. saikera
      G            T          2. saikera
   D     J     P      W       3. saikera
 B   F           R      Y     4. saikera
                              5. saikera

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. Saiakera bakoitzeko, ordenagailuari informazioa emango diogu esanez zenbaki ezezaguna zein tartetan dagoen.

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... ...iturburu-programa, eta... ...beste iturburu-programa bat da. Ikusten denez, soluzio bakarra ez dago, zein da zurea?

Antzeko algoritmoa aplikatzen da 6. astea | letra bat asmatzen ariketan, non makinak letra bat aukeratzen duen eta guk asmatu behar dugun, LetraAsmatu.pas programaren kodea ikusteko klik egin hemen.

2024(e)ko otsailaren 24(a), larunbata

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, 610, 987, 1597, 2584, 4181, 6765, 10946, ...

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 azpiprograma bakoitzaren kodea falta da. Ikaslearen lana da azpiprogramen kodeak bukatzea eta programaren emaitzak ulertzea.

Hau garrantzitsua da

Ez ahaztu, edozein ariketa programatzerakoan beti Programa Nagusitik hasiko garela, eta Programa Nagusia bukatzean jarraituko dugula azpiprograma guztien kodea idazten. Horregatik, bi adibide hauetan Programa Nagusiak ematen dira eta eskatzen da garatzea bakoitzari dagokion azpiprograma.

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, prozeduraren izena FibonaccirenSekuentziaPantailaratu izan daiteke.

Hona hemen kodifikazioa non programa nagusia ematen den eta prozedura falta den:

{ iKopurua (3 eta 24 artekoa) teklatuz irakurri eta Fibonacci zenbakien }
{ sekuentziaren horrenbeste elementu pantailaratuko dira 0-tik hasita   }
program FibonacciSekuentzia_prozedura ;
 
const                           (* integer-ekin muga 23 da *)
   ZENBAKIKOPURUMAX = 23 ;      (* longint-ekin muga 47 da *)
 
 
{ prozeduraren kodea hemen hasten da }
procedure FibonaccirenSekuentziaPantailaratu...
 
{ prozeduraren kodea hemen amaitzen da } 
 
 
{ ---------------------------------PROGRAMA NAGUSIA--------------------------------- }  
var
   iKopurua : integer ;
begin
   writeln ;
   writeln ;
    
   repeat
      writeln('Fibonacci zenbakien kopurua eman (3 eta ', ZENBAKIKOPURUMAX,' artekoa)') ;
      write('eta 0-tik hasita Fibonacciren segida erakutsiko da: ') ;
      readln(iKopurua) ;
   until (iKopurua >= 3) and (iKopurua <= ZENBAKIKOPURUMAX) ;
    
   FibonaccirenSekuentziaPantailaratu(iKopurua) ;
    
   writeln ;
   write('Programa bukatu da, irteteko RETURN sakatu') ;
   readln ;
end.

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 edo REPEAT-UNTIL egitura bat erabiliko da fniFibonacciZenbakienKopuruaKalkulatu izeneko funtzioan.

Hona hemen kodifikazioa non programa nagusia ematen den eta funtzioa falta den:

{ iMuga teklatuz irakurri eta Fibonacci zenbakien kopurua kalkulatu     }
program FibonacciKopurua_funtzioa ;
 
const
   AZKENMUGA = 28000 ;
 
 
{ funtzioaren kodea hemen hasten da }
function fniFibonacciZenbakienKopuruaKalkulatu...
 
{ funtzioaren kodea hemen amaitzen da }
 
 
{ ---------------------------------PROGRAMA NAGUSIA--------------------------------- }  
var
   iMuga, iKopurua : integer ;
   cErantzuna : char ;
begin
   writeln ;
   writeln ;
     
   repeat
      repeat
         write('Eman azken muga (0 eta ', AZKENMUGA,' artekoa): ') ;
         readln(iMuga) ;
      until (iMuga >= 0) and (iMuga <= AZKENMUGA) ;
 
      iKopurua := fniFibonacciZenbakienKopuruaKalkulatu(iMuga) ;
 
      writeln('Emaitza, Fibonacci zenbakien kopurua ------> ', iKopurua) ;
 
      write('Amaitu nahi duzu? (B/E): ') ;
      repeat
         readln(cErantzuna) ;
         cErantzuna := upcase(cErantzuna) ;
      until (cErantzuna = 'B') or (cErantzuna = 'E') ;
      writeln ;
   until cErantzuna = 'B' ;
    
   write('Programa bukatu da, irteteko RETURN sakatu') ;
   readln ;
end.

Programaren bigarren zatiko irteera bat hau izan daiteke:

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

Goiko bi programa horiek bukatu ondoren, saiatu zaitez bi ariketak programa bakar batean biltzen, hots, funtzionalitate guztiak betetzen dituen Programa Nagusi berria idatzi eta bi azpiprogramen kodea inportatu.

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.