i
i
“1358-Juvan-Srecna” — 2010/7/27 — 14:02 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 26 (1998/1999)
Številka 1
Strani 14–17
Martin Juvan:
SREČNA ŠTEVILA Z RAČUNALNIKOM
Ključne besede: računalništvo, programiranje, pascal, Ulamovo re-
šeto.
Elektronska verzija: http://www.presek.si/26/1358-Juvan.pdf
c© 1998 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Računalništvo I
SREČNA ŠTEVILA Z RAČUNALNIKOM
V predzadnji št evilki lanskega let n ika Preseka nas je pr ofesor Grasselli
"poskušal" prepričat i , da je šte vilo 13 srečno (glej prispevek J. Grasselli,
Nesrečno število 13 je srečno , Presek 25 (97/98) , str. 258-260). O te m ,
ali mu je to usp elo ali ne, ne bomo razpravljali, pogled ali pa bomo, kako
lahko s pomočjo računalnika reši mo nalogo, ki jo je zastavil na koncu
pri sp evka . Pred lagal je, da poiščemo vsa srečna števila do 1000.
P redno pa se lot imo naloge, se spomnimo, kako sploh pridem o do
srečnih št evil. Začnemo z zaporedjem vseh nar avn ih št evil
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, . . .
Na prvem koraku iz zaporedja odvržemo vsa soda št evila . Ost ane zapo-
redje
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, . . .
Na drugem kor aku v (že zm anj šanem) zapore dju pogled amo drugo število,
t o je 3, in iz zaporedja odv ržemo vsako tretje število . Ost ane
1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...
Na tretj em kor ak u pogledamo tretji element trenut nega zaporedja, to je
7, in iz za poredja odvržemo vsak sedmi člen . Ostane
1, 3, 7, 9, 13, 15, 21, 25, 27, ...
Gotovo ste uganili nadalj evanj e. Na četrtem koraku pogledamo četrt i
člen , ta je enak 9, in izločimo vsako deveto št evilo. Nato sledi peti korak,
pa šesti it n . Št evila , ki "preživijo" prav vse kor ake, imenujemo srečna.
P ostopek, ki smo ga op isali, imenujem o U1amovo rešeto . Močno spo-
minja na znano Eratostenovo rešeto, s kat erim lahko določimo praštevila
do neke vn aprej izbrane meje. Prepričan sem, da ste pr ogram za iskanje
praštevil z Eratostenovim rešetom že kdaj napisali, saj gre za programer-
ski izziv, s katerim se v mladosti sreča vsak "resen" programer. Ulamovo
rešeto je sicer podobno, a vendarle nekoliko drugačno . P ri Eratost en o-
vem rešetu je odločitev o tem , ali bom o šte vilo izločili ali ne, odvisna od
ostanka pri deljenju, pri Ulamovem rešet u pa je kriter ij mesto št evila v že
zmanjšane m za po redj u. Zato bo progr am za sejanje z Ulamovirn rešetom
malce bo lj zapleten kot program za sejanje z Eratostenovim rešetom.
Računalništvo
Program bomo zapisali v programskem jeziku pascal. Števila , ki so
kandidat i za srečna števila, bomo v programu hranili v tabeli tab. Ker
bomo prvi korak sejanja opravili kar sami, bomo na začetku v tabelo
vp isali liha števila. Pri tem bodo indeksi v tabeli tekli od 1 do 500,
vrednost tab Ci ] pa bo 2 . i - 1. V sprernenljivki n bomo ves čas hranili
podatek, koliko kandidatov za srečna števila je še v tabeli t ab. Na začetku
bo n enako 500 (toliko je lihih števil do 1000). S števcem k bomo šteli
korake. Začetna vrednost bo enaka 2.
Jedro programa bo zanka while. V vsaki ponovitvi zanke bomo
opravili en (k-t i) korak sejanja. Zanko bomo ponavljali toliko časa, dokler
bo k-ti element tabele (tega bomo hranili tudi v sprernenljivki d) manjši
ali enak n. Vemo, da nadaljnji koraki ne morejo več izločiti števil iz
tabele, saj je v tabeli premalo števil. V vsaki ponovitvi zanke bomo iz
tabele odstranili števila, ki so na mestih d, 2 . d, 3 . d , . . . To storimo
tako, da števila, ki so na mestih d + 1, d + 2, .. . , 2· d - 1 pomaknemo
za eno mesto v levo (v tabeli smo pred njimi odstranili eno število, in
sicer tisto na mestu d}, števila na mestih 2 . d + 1, . .. , 3· d - 1 za dve
mesti v levo it n . Premikanje izvedemo v zanki for , pri čemer bomo poleg
števca zanke, tega bomo označili z j , uporabili še pomožni števec i. Ko
j teče od vrednosti d + 1 do n , vsakič pogledamo, ali je de ljiv z d. Če je
deljiv, ne storimo ničesar (pripadajoči eleme nt tabele tako preskočimo in
ga s tem izločimo). Kadar pa j ni deljiv z d, pripadajoči element tabele
tab premaknemo za nekaj mest naprej. Kam ga moramo prestaviti, nam
pove števec i. Vsakič, ko premaknemo kak element, ta števec povečamo
za ena. Kadar pa elementa ne premaknemo, to pa je vsakič, ko je j de ljiv
z d, števec i dodatno zaostane še za eno mesto za števcem j . Začetna
vrednost števca i bo d (na tem mestu v tabeli t ab nastane prva "luknja",
ki jo je treba zapolniti) . Po koncu zanke f or seveda ne smemo pozabiti
na popravek vrednosti spremenljivke n in na pripravo spremenljivk k in d
za novi korak izločanja.
program SrecnaStevila;
{ Poišče srečna števila do konstante meja. }
const
meja = 1000;
vel = (meja + 1) div 2; { 500 }
var
tab: array [1..vel] of integer; {tabela s kandidati}
n: integer; {koliko kandidatov je še v tabeli }
k: integer; {števec korakov }
d, i, j: integer;
{ toliko kandidatov j e "preživelo" k-ti korak}
{ priprava na naslednji korak }
Računalništvo I
begin
{ Zaporedje lihih naravnih šte vil do konstante m eja. }
for i:=l to vel do tabli] := 2 * i - 1;
n .- vel; {Po prvem korak u ostane toliko kandidatov. }
k := 2;
d := t abl k];
while d <= n do begin
i := d; { indeks prvega šte vila, ki ga odvržemo }
for j := d + 1 to n do
if j mod d <> O then begin
tabli] := tab[j];
i := i + 1;
end;
n .- i - 1;
k := k + 1;
d := tablk];
e n d ; {while}
{ Izp is srečnih števil. }
for i:= l to n do wr it e (tab[i]:5);
wr it eln;
e n d .
Pravijo, da je znanje čim več različnih jezikov v življenju zelo po-
membno. No, mo rda pri tem res niso miš ljeni programski jeziki , a vseeno
poskusimo gornjo rešit ev zapisati še v programskem jeziku C.
Čeprav sta t ako pasca l kot C postopkovna progr amska jezika, pa je
med nji ma vseeno kar nekaj raz lik. Omenimo samo nekatere, ki bo do
vp liva le na zapis našega progr ama. V C-ju konstante običajno definiramo
s pomočjo pred procesorjevega ukaza #define. C t udi loči male in velike
črke , v navadi pa je, da s predprocesorjem definirane simbole pišemo z
velikimi črkami. Tako bosta meja in vel p ost ali MEJA in VEL. Zanka for
je v C-ju precej splošnejša kot v pascalu in pravzaprav ustreza pascalski
zanki while (skupaj z inicializacijo spremenlj ivk) . Namesto operatorje v
mod in div iz pascala imamo v C-ju op eratorj a %in / (op erator / pomeni
celoštevilsko deljenj e le tedaj , kadar sta oba op eranda celošt evilska izraza;
če je vsaj ede n od operandov realno število, pot em se t udi deljenje izvede
v real nem). Za prirejanj e namesto := uporabljamo =, v pogojih pa za
primerjanje namesto pasca lskih = in <> uporabljamo == in != . Ena od bolj
zoprnih last nosti C-ja je, da se v t abelah elem enti ved no začno z indeksom
O. To bo vp livalo tudi na zapis našega programa. Pri inicializaciji t abele
tab bo št evec i t ekel od Odo 499, eleme nt tab [iJ pa bo na začetku dobil
I Računalništvo
vrednost 2 . i + 1. Tudi pri izločanju števil bomo mor ali naredit i ust rezni
premik indeksov, saj d-t i element zaporedja ne bo več tab [d] , ampak
t.ab Id - 1] . Tako bomo izločali eleme nte z indeksi d-l,2·d-l , . . . Tudi
števec korakov k bo imel za ena manjšo vrednost . Z up orabo ope ratorja
++ bo mo zapis programa v O-ju še nekoliko "zgostili" . Vrednost izraza
im e++ je (st ar a) vrednost spremenlj ivke im e, "stranski" učinek pa , da se
vr ednost t e sp reme nlj ivke poveča za en a.
#include <stdio .h>
1* PoiSče srečna Stevila do konstante MEJA . *1
#define MEJA 1000
#define VEL ((MEJA + 1) I 2) 1* 500 *1
int main(void)
{
int tab [VEL] ; 1* tabela s kandidat i *1
int n; 1* koliko kandidatov je Se v tabeli *1
int k; 1* Stevec korakov *1
i nt d, i, j ;
1* Zaporedje lihih naravnih Stevil do konstante meja . *1
for (i = O; i < VEL; i++) tab[i] = 2 * i + l j
n = VEL; 1* Po prvem kor aku ostane toliko kandidatov. *1
for (k = 1, d = tab [k] ; d <= n j k++, d = tab[k] ) {
i = d - 1 ; 1* indeks prvega Stevila, ki ga odvržemo *1
for (j = d; j < n; j ++)
if (j % d != d - 1) tab[i++] = tab[j];
n = i ; 1* toliko kandidatov je preživelo k-ti korak *1
}
1* Izpis srečnih Stevil . *1
for (i = Oj i < n; i++) printf(I%5d", tab[i]);
printf("\n" ) ;
return O;
}
Naj tudi sam zaključim z nalogo . Ugotovite, katero je bilo (oziroma bo)
zadnje "srečno" let o v tem tisočletj u in katero bo prvo "srečno" let o v
prihodnjem tisočletju . Z majhno spremembo enega od gornj ih programov
tega ne bo težko storit i.
Mart in Juvan