i
i
“1268-Juvan-iskanje” — 2010/7/22 — 14:12 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 23 (1995/1996)
Številka 5
Strani 282–285
Martin Juvan:
ISKANJE ŠIROKIH ŠTEVIL
Ključne besede: računalništvo, računalniško programiranje, naravna
števila.
Elektronska verzija: http://www.presek.si/23/1268-Juvan.pdf
c© 1996 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
ISKANJE ŠIROKIH ŠTEVIL
Pred časom sem obljubil , da bom napi sal nekaj o štetj u širokih števil.
Predno pa se poglobimo v programiranj e, se spomnimo, da je št evilo
široko, če j e vsota njegovih števk enaka njihovemu produktu .
Ugotoviti sem želel, koliko je širokih št evil, ki so manjša od mil i-
jarde. Ker ugotavljanje, ali j e število široko, ni zapleteno, današnji osebni
računalniki pa so že zelo hitri , sem se prob lema lot il z metodo grobe sile.
Sestavil sem spodnji prog ram , ki za vsako število od 1 do izbrane zgornje
meje po definiciji preveri , ali j e široko.
{ vn os}
{ Ali j e š te vilo široko? }
{ Določi vsoto in produkt š te vk . }
{ Iščemo široka števila do ur, }
{ nlO = io: }
{ največja možna vsota števk }
{ vsota in produkt št evk }
{ š te vec najdenih ši ro kih št evil }
program SirokaStev ilal;
{ Poišče vsa široka števila do lOn z zaporednim preverjanjem p o definiciji. }
c o n st
m axN=9;
var
n : int eger ;
nlO : longint ;
m axVsota: int eger ;
vs ota,produkt: integer;
S: lon gin t ;
i,j : lon gin t ;
ost : in t eger ;
begin
wri t eln (,Iskanje sirokih stevil d o l O'[rr.'} ;
write(' Vpisi n (n <',maxN+l ,') : '); readln(n) ;
nlO := 1; fo r i:= l t o n do nlO := 10*n lO; { Izračunamo l On o }
maxVsota := 9* n; { največja možna vso ta števk}
S := O;
for i := 1 t o nlO do b e gi n
j := i; vsota := O; produkt := 1;
w h ile j >O do begin
ost := j mod 10 ; j := j div 10;
vs ota := vsota-l-ost ; produkt:= produkt-sost;
if produkt >maxVsota t h e n break;
e n d; { while }
if vsota=produkt t hen S := S+l;
e n d; { for }
wr it e ( 'S irokih stevil do ' ,n l O,' j e ' ,S,'.' ) ; readln ;
e n d.
V zanko while , ki preverja , ali j e šte vilo široko , sem dodal pogojni st avek
it , ki z ukaz om break prekine zanko, če produkt števk prekorači največjo
mo žno vsoto št evk. Žal tudi ta majhna izbolj šava ni pomagala . Že ko
sem gornj i program preizku sil pri vrednosti n = 6, sem na odgovor čakal
dobrih dvaj set sekund . Hitro sem ocenil, da bi pri n = 9 na rezul tat čakal
vsaj šest ur , odločno preveč za tako preprosto nal ogo .
Računalništvo
Nekoliko razočaran zara di neuspeha sem tako ugotovil , da reševanj e
naloge zah teva koren ite spremembe v pristopu. Za nekaj nasvetov sem
poprosil še kolego Mark a Petkovška , ki im a vedno na zalogi kakšno up o-
rabno idejo. Tako sem se odločil za reševanj e s sestopanj em , ki pa sem ga
dopolnil z učinkovitim testom, ki pove, kdaj je nadaljevanj e poskušanja
še smi selno. Zaradi lažjega programiranj a sem up orabil rekurzivni zapis
glav nega pod programa. Nastal je naslednji program.
IOn S ses topanjem . }
p r ogram SirokaStevila2;
{ Poišče vsa široka št evila do
co ns t
m axN=64;
var
11: integer;
stevke: array[O..maxN] of
S: lon gint ;
m : inte ger;
1.. 9;
{ Iščemo široka šte vila do IOn . }
{ O. m esto j e p om ožn o. }
{ števec najdenih širok ih š te vil }
procedure Razsiri(i ,m : integer; vsot a,produkt: integer);
{ Določamo i-to šte vko, sk upaj z nj o jih m oramo določiti še m ;
vsota j e vsota, p ro d ukt pa produkt prvih i- 1 števk. }
var
j ,k: integer;
p: lon gin t ;
b egin
if m > O then
for j: = stevke[i-1] d ownto 1 do b egin
ste vke [i] := i :
if produkt -ej < =vsota+ m*j then Razsirifi-} 1,m - 1,vsota-l-j .p rod ukt sj };
e n d
e lse if vsota=produkt then b e gin { Izračuna, koliko števil smo na šli . }
p := 1; k := 1;
for j :=2 to i-1 do b egin
p := p *j;
if stevke[j] < > stevke[j-1] then
k := 1
e lse { Štel-ka se ponovi. }
b e gin k .- k-l-L ; p := p div k; e n d ;
e n d; { for }
S := S+p; { Zgrajeno širo ko š tevilo preds tavlja p širok ih števil . }
e n d; { else if }
e n d; { R azsiri }
b e gin
writeln(, Iska nje siro kih stevil do l O'[n. ']:
wr ite(' Vpisi n (n<',m axN + l,' ) : '); readln(n) ;
S := O; st evk e[O]:= 9;
for m :=l t o n do Razsiri( l,m, O,l); .
write(,Siro kih stevil do lOt' ,n,' j e ',S,' . '); re ad ln;
e n d.
{ vn os }
{ začetni vre dnosti }
Računalništvo I
Spodprogramom Razsiri postopno, števko po števko, v globalni
sprem enljivki stevke gradimo kandidate za široka št evila . Podprogram
ima štiri parametre: prvi nam pove, na katero mesto moramo postaviti
nas lednjo števko , drugi šteje, koliko števk moramo še izbrati , in nam služi
v pogoju , s katerim končamo rekurzijo, tr etji in četrti pa st a vsota in
pro du kt že izbran ih št evk . Široka števila, ki so manjša od IOn , imajo
lahko od 1 do n šte vk. Zato v glavn em prog ramu podprogram Razs iri
kličemo n-k rat . Vrednosti parametrov pr i teh klicih so 1, m, O in 1, kjer
mzavzame vrednosti med 1 in n. Tako začetno števko postavimo na prvo
mesto v tabeli s tevke , iščemo široka št evila z m št evkami , začetna vsota
št evk je enaka O, začetni produkt št evk pa je enak 1.
Nobeno široko šte vilo ne vsebuje števke O, zato pri gradnji kandi-
datov za široka št evila uporabljamo le števke od 1 do 9. Da zmanjšamo
potrebno delo in omogočimo učinkovito preverjanje, ali j e nadaljevanje po-
skušanja smiselno , gradimo le števi la , katerih števke tvo rijo nenaraščajoče
zaporedje. Tako nasl ednja št evka ne sme biti večja od prejšnj e. Če nam
manj ka še m šte vk, vemo pa, da nob ena ne bo večja od i , se vsota števk
lahko poveča kvečjemu za mj. Hkr ati vemo, da se produkt št evk pri do-
dajanju neničelnih števk ne more zmanjšati. Tako dobimo pogoj , ki ga
preverimo , preden naredimo rekurzivn i klic.
Ker gradimo le števila z nenaraščajočim zaporedjem št evk , nam vsako
široko število, ki ga najdemo , če ima vsaj dve različni števki, pravza-
pr av predstavlja več širokih števil. Tako moram o, na primer , ko najdemo
št evi lo 4211, šteti še št evila 4121 , 4112 , 1421, 1412 in 1142 ter še šest
števil, ki jih dobimo iz naštetih, če zame njamo števki 2 in 4. Recim o, da
ima dobljeno široko število n števk. Vseh različnih permutacij teh števk je
n( n -1) ' . .. ·1. To število označimo z n! in ga imenujemo fakult eta števila
n . Vendar pa nekatere perm utacije dajo enako število, saj medsebojne za-
me njave enakih št evk števi la ne spremenijo . Da dobimo dejansko število
različnih št evil , moramo n ! deliti še s fakultetami št evil t ist ih števk, ki v
dobljenem širokem številu nast opijo večkrat. V zgornje m primeru imamo
št irimestno širo ko št evilo 4211. Ker v njem le števka 1 nastopa večkrat, in
sicer dvakrat , nam to šte vilo predstavlja ~ = 12 razl ičnih širokih števi l.
Ta smo že opisali.
Ko sem preizkusil gornj i program , sem bil prijetn o presenečen . Na-
slednjo tabelo je iz računal že v nekaj sekundah.
Ovira, ki prepreihje nsdfinje gtetje h k i h  iitevil r gorqiim programom, 
ni veE Eae raEunaaja, eunpiik obseg v turbo padAcal vgrajerrqa tipa 10- 
gint. &akih litevil se nabere pred,  da bi njihovo & d o  lahko 
&ran% Y spmenxjivko kg8 tipa, tsko da pride do prekm&itve 0-a. 
V tabelo wan vkljud b dodatni stolpec, ki pove, k o b  je "blatw110" 
rwlibih i3bkih ?&evil, torsj t*, ki jih mtav2jsija rmiike h p h e  letevk 
wimms q j h v e  iitevke tvorijo nwarWj& (ali pa nepadajd, obojih 
je ensrko) zqmreaje. Tit& ts stolpx sem haihnal I m s j b  apremembo 
(prawaprav poenwtatavitvijo) gorejega pmgrgma Pwe nam, da so ~ku- 
pine Iltevk, lri dolohjo &roh &v&, &elo redke, Tako je do vmbem &a 
gtevk natauEno 441111 1111 edino d&m&no b k a  &do. Mbqpde, 
r a i h d d k  je  tudi odkril, da &hiindvajmtm&no &holm Stevilo ne obstaja.