| ZER DAKIDAN: Ariketa 63 | Eratostenes-en bahea (I) adibidean bi dimentsiotako array bat erabili nuen programa kodetzeko. ZER IKASIKO DUDAN: Funtzionalitate bera duen programa idatziko dut baina erregistroen 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) erregistroen dimentsio bakarreko array bat erabiliz
- Ariketa 69 | Eratostenes-en bahea (II) zenbaki osoen bi dimentsiotako 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:
| 0 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | zenbakia |
| 1 | 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 |
Programa honetan taularen 0 posizioa eta 1 posizioa ez dira erabiltzen datuak gordetzeko. Horregatik, goiko eskeman bi posizio horiek ez dira erakustsi.
/* Ariketa-69_EratostenesenBahea-2 */
/*
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>
#include <stdbool.h> // bool datu-motarako
#define MAX 120
typedef struct
{
int iKopurua;
bool boMarkatua;
} trdDatua;
typedef trdDatua tardZenbakiak[MAX];
typedef int taiLehenak[MAX];
// Datuak hasieratzen ditu
void DatuakLortu(tardZenbakiak ardDatuak, int *iLuzeraDatuak);
// Zenbakiak ikusten ditu eta markatu gabeko lehenen kopurua kalkulatzen du
void ZenbakiakIkusi(const tardZenbakiak ardDatuak, int iLuzeraDatuak);
// Lehen zenbakiak lortzen ditu
void LehenakLortu(const tardZenbakiak ardDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak);
// Lehen zenbakien zerrenda erakusten du
void LehenakIkusi(const taiLehenak aiLehenak, int iLuzeraLehenak);
// Programa nagusia
int main()
{
tardZenbakiak ardDatuak;
int iLuzeraDatuak;
taiLehenak aiLehenak;
int iLuzeraLehenak;
int iIterazioa = 2;
DatuakLortu(ardDatuak, &iLuzeraDatuak);
printf("Hasierako datuak:\n");
ZenbakiakIkusi(ardDatuak, iLuzeraDatuak);
printf("\n");
printf("1 zenbakia alde batera utzirik, prozesu errepikakorra 2 zenbakiarekin hasiko da\n\n");
while (iIterazioa * iIterazioa <= MAX)
{
printf("================================================================================\n");
if (!ardDatuak[iIterazioa].boMarkatua)
{
printf("%d zenbakia lehena da, %d zenbakiren multiploak markatzen...\n", iIterazioa, iIterazioa);
for (int k = iIterazioa + 1; k < MAX; k++)
{
if (ardDatuak[k].iKopurua % iIterazioa == 0)
{
ardDatuak[k].boMarkatua = true;
printf("%4d zenbakia markaturik zatigarria delako\n", ardDatuak[k].iKopurua);
}
}
}
else
{
printf("%d zenbakia zatigarria da\n", iIterazioa);
}
printf("%d arteko datuak:\n", iIterazioa);
ZenbakiakIkusi(ardDatuak, 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");
}
LehenakLortu(ardDatuak, iLuzeraDatuak, aiLehenak, &iLuzeraLehenak);
printf("Lehenen zerrenda:\n");
LehenakIkusi(aiLehenak, iLuzeraLehenak);
printf("\n\nENTER sakatu exekuzioa amaitzeko... ");
getchar();
return 0;
}
// Datuak hasieratzen ditu
void DatuakLortu(tardZenbakiak ardDatuak, int *iLuzeraDatuak)
{
*iLuzeraDatuak = MAX;
for (int k = 2; k < *iLuzeraDatuak; k++) {
ardDatuak[k].iKopurua = k;
ardDatuak[k].boMarkatua = false;
}
}
// Zenbakiak ikusten ditu eta markatu gabeko lehenen kopurua kalkulatzen du
void ZenbakiakIkusi(const tardZenbakiak ardDatuak, int iLuzeraDatuak)
{
int iKont_TRUE = 0;
int iKont_FALSE = 1; // 1 zenbakia lehen gisa hartuta
printf("--------------------------------------------------------------------------------\n");
printf(" 1-FALSE");
for (int k = 2; k < iLuzeraDatuak; k++)
{
printf("%4d", ardDatuak[k].iKopurua);
if (ardDatuak[k].boMarkatua)
{
printf("--TRUE");
iKont_TRUE++;
}
else
{
printf("-FALSE");
iKont_FALSE++;
}
//printf("%d", ardDatuak[k].boMarkatua);
}
printf("\n--------------------------------------------------------------------------------\n");
printf(" Zenbakien kopurua = %d Lehenen kopurua = %d Zatigarrien kopurua = %d\n", iLuzeraDatuak, iKont_FALSE, iKont_TRUE);
}
// Lehen zenbakiak lortzen ditu
void LehenakLortu(const tardZenbakiak ardDatuak, int iLuzeraDatuak, taiLehenak aiLehenak, int *iLuzeraLehenak)
{
*iLuzeraLehenak = 1;
aiLehenak[*iLuzeraLehenak - 1] = 1;
for (int k = 2; k < iLuzeraDatuak; k++)
{
if (!ardDatuak[k].boMarkatua)
{
aiLehenak[(*iLuzeraLehenak)++] = ardDatuak[k].iKopurua;
}
}
}
// Lehen zenbakien zerrenda erakusten du
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