| ZER DAKIDAN: Arrayak ezagutzen ditut. ZER IKASIKO DUDAN: Zenbaki osoen bi dimentsiotako array baten ariketa bat programatuko dut emaniko algoritmoa jarraituz. Ariketa hau hobeto programatzen da laster ikusiko den erregistroen (edo struct datu-mota) array bat erabiliz. |
 |
| Galbahe (edo bahe) baten irudia. Galbaheri esker aleak sailka daitezkeen bezala, zenbaki zerrenda bati galbahe logikoren bat aplikatuz zenbakien segida desberdinak lor daitezke, adibidez: zenbaki lehenak identifikatzeko Eratostenes matematikari greziarrak asmatutakoa |
Ariketa honi bi modutan ekingo diogu:
- Ariketa 63 | Eratostenes-en bahea (I) zenbaki osoen bi dimentsiotako array bat erabiliz
- Ariketa 69 | Eratostenes-en bahea (II) erregistroen dimentsio bakarreko array bat erabiliz
 |
Eratostenes (antzinako grezieraz: Ἐρατοσθένης; K.a. 276 inguru - K.a. 195 inguru) matematikari, geografo, kirolari, poeta eta astronomo greziarra izan zen. Alexandriako Liburutegia famatuaren zuzendari izendatu zuten eta aurkikuntza ugari egin zituen, hala nola, latitude eta longitude sistema. Eratostenes ezaguna da Lurraren zirkunferentzia kalkulatzen lehen greziarra izan zelako, baita Lurraren ardatzak duen makurdura. Bestalde, garaiko ezagutza geografikoaren araberako mundu mapa eratu zuen ere. |
Eratostenes-en bahea zenbaki lehenak aurkitzeko algoritmo bat da, emandako n zenbaki arrunt bat baino txikiagoak direnen artean.
Lehendabizi, taula bat egiten da 2 eta n arteko zenbaki arruntekin, jarraian multiploak markatzen dira hurrengo ordena jarraituz:
- 2tik hasita, haren multiplo guztiak markatzen dira, ostean, hurrengo zenbakiarekin jarraituko da baina bi egoera daude:
- Hurrengo zenbakia markaturik gabe dago, adibidez 3 zenbakia, eta lehen bezala bere multiplo guztiak markatzen dira
- Hurrengo zenbakia markaturik dago, adibidez 4 zenbakia, kasu honetan ez da ezer markatzen eta bere hurrengo zenbakia hartzen da
- 5ekin markatu beharko litzateke (goiko lehen kasua), 6kin ez litzateke ezer markatuko (goiko bigarren kasua), 7ekin markatu beharko litzateke (goiko lehen kasua), 8, 9 eta 10ekin ez litzateke ezer markatuko (goiko bigarren kasuak), e.a.
Prozedura errepikatzen da hau betetzen den bitartean: (MarkatuGabekoZenbakia)2 < n. Beste modu batez esanik, markatu gabeko zenbakiaren karratua n baino handiagoa denean eten prozesu errepikakorra
Eratostenes-en bahearen animazioa 120 baino gutxiagoko zenbaki lehenentzat:
SKopp at German Wikipedia, CC BY-SA 3.0, via Wikimedia Commons
Hona hemen datu-taularen irudia MAX konstanteak 21 balio duenean, non 0 markak zenbaki lehen adierazten duen eta 1 markak zenbaki zatigarri adierazten duen:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | zenbakia |
| 2 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | marka |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
/* Ariketa-63_EratostenesenBahea-1 */
/*
Muga den kopuru arrunta emanez, muga hori baino txikiagoak diren
"Zenbaki Lehenak" lortzeko metodo bat aurkitu zuen Eratostenesek.
Algoritmoa:
----------
2tik iMuga-rako zenbakiak zerrenda batean jartzen dira. Lehenengo, 2ren
multiplo guztiak markatzen dira, eta 2 zenbakia emaitza den lehenen
zerrendari gehituko zaio. Ondoren, 3ren multiplo guztiak markatuko dira,
eta 3 zenbakia gehituko zaio lehenen zerrendari. Gero, 4ari begiratzen
zaio, markatuta dagoela ikusten da, eta horrek esan nahi du 2rekin
zatigarria dela, eta, beraz, ez da lehena. Ondoren, 5era iristen da;
markatuta ez dagoenez, lehena da, bere multiplo guztiak markatzen dira
eta lehenen zerrendara gehituko da.
Prozesu errepikakorra bukatzeko baldintza: Une jakin batean aztertuko den
zenbakiaren karratua iMuga-tik beherakoa bada, jarraitu beharra dago.
Bestela, algoritmoa amaitu egiten da, eta markatu gabe geratu diren
guztiak zenbaki lehenak dira (emaitza-zerrendari gehitu beharrekoak).
Animazio hau ikusi:
https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
Bi programa hauek aztertu:
* Ariketa-63_EratostenesenBahea-1 zenbaki osoen bi dimentsiotako arraya
* Ariketa-69_EratostenesenBahea_2 erregistroen dimentsio bakarreko arraya
*/
#include <stdio.h>
#define MAX 120
typedef int taiDatuak[2][MAX + 1]; // 2 errenkada eta MAX+1 zutabe
typedef int taiLehenak[MAX]; // zenbaki lehenak gordetzeko arraya
void DatuakLortu(taiDatuak aiDatuak, int *iLuzeraDatuak);
void DatuakIkusi(const taiDatuak aiDatuak, int iLuzeraDatuak);
void LehenakLortu(const taiDatuak aiDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak);
void LehenakIkusi(const taiLehenak aiLehenak, int iLuzeraLehenak);
int main()
{
taiDatuak aiDatuak;
int iLuzeraDatuak;
taiLehenak aiLehenak;
int iLuzeraLehenak;
int iIterazioa = 2;
DatuakLortu(aiDatuak, &iLuzeraDatuak);
printf("\nHasierako datuak:\n");
DatuakIkusi(aiDatuak, iLuzeraDatuak);
printf("\n1 zenbakia alde batera utzirik, prozesu errepikakorra 2 zenbakiarekin hasiko da\n\n");
do
{
printf("================================================================================\n");
if (aiDatuak[1][iIterazioa] == 0)
{
printf("%d zenbakia lehena da, ", iIterazioa);
printf("%d zenbakiaren multiploak markatzen...\n", iIterazioa);
for (int k = iIterazioa + 1; k <= MAX; k++)
{
if (aiDatuak[0][k] % iIterazioa == 0)
{
aiDatuak[1][k] = 1; // Es divisible, marca con 1
printf("%4d zenbakia markaturik zatigarria delako\n", aiDatuak[0][k]);
}
}
}
else
{
printf("%d zenbakia zatigarria da\n", iIterazioa);
}
printf("%d arteko datuak:\n", iIterazioa);
DatuakIkusi(aiDatuak, iLuzeraDatuak);
printf("================================================================================\n");
iIterazioa++;
if (iIterazioa * iIterazioa <= MAX)
{
printf(" %d x %d = %d <= %d prozesu errepikakorrarekin jarraitu\n",
iIterazioa, iIterazioa, iIterazioa * iIterazioa, MAX);
}
else
{
printf(" %d x %d = %d > %d prozesu errepikakorra amaitu\n",
iIterazioa, iIterazioa, iIterazioa * iIterazioa, MAX);
}
printf("\n\n");
} while (iIterazioa * iIterazioa <= MAX);
LehenakLortu(aiDatuak, iLuzeraDatuak, aiLehenak, &iLuzeraLehenak);
printf("Lehenen zerrenda:\n");
LehenakIkusi(aiLehenak, iLuzeraLehenak);
printf("\n\nENTER sakatu exekuzioa amaitzeko... ");
getchar(); // itxaron ENTER sakatu arte
return 0;
}
void DatuakLortu(taiDatuak aiDatuak, int *iLuzeraDatuak)
{
*iLuzeraDatuak = MAX;
for (int k = 2; k <= *iLuzeraDatuak; k++)
{
aiDatuak[0][k] = k;
aiDatuak[1][k] = 0; // 0 (FALSE) lehena, 1 (TRUE) zatigarria
}
}
void DatuakIkusi(const taiDatuak aiDatuak, int iLuzeraDatuak)
{
int iKont_0 = 1; // 1 lehena da, ez da prozesatzen
int iKont_1 = 0; // zatigarrien kontagailua
printf("--------------------------------------------------------------------------------\n");
printf(" 1-LEHEN");
for (int k = 2; k <= iLuzeraDatuak; k++)
{
printf("%4d", aiDatuak[0][k]);
if (aiDatuak[1][k] == 0)
{
printf("-LEHEN");
iKont_0++;
} else
{
printf("__ZAT.");
iKont_1++;
}
}
printf("\n--------------------------------------------------------------------------------\n");
printf(" Zenbakien kopurua = %d Lehenen kopurua = %d Zatigarrien kopurua = %d\n",
iLuzeraDatuak, iKont_0, iKont_1);
}
void LehenakLortu(const taiDatuak aiDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak)
{
*iLuzeraLehenak = 1;
aiLehenak[*iLuzeraLehenak] = 1;
for (int k = 2; k <= iLuzeraDatuak; k++)
{
if (aiDatuak[1][k] == 0)
{
(*iLuzeraLehenak)++;
aiLehenak[*iLuzeraLehenak] = aiDatuak[0][k];
}
}
}
void LehenakIkusi(const taiLehenak aiLehenak, int iLuzeraLehenak)
{
printf("********************************************************************************\n");
for (int k = 1; k <= iLuzeraLehenak; k++)
{
printf("%3d, ", aiLehenak[k]);
}
printf("\n********************************************************************************\n");
printf(" iLuzeraLehenak = %d\n", iLuzeraLehenak);
}
iruzkinik ez:
Argitaratu iruzkina