A problemate ad algorithmvm

Svmmarivm

Haec lectio codicem non continet, neqve per neglegentiam: algorithmvs programma antecedit, et qvi accvrate describere nescit qvid faciendvm sit, ne in C++ qvidem id dicere sciet. Primvm docetvr qvomodo problema specificetvr, id est qvomodo declaretvr qvae data accipiat, qvem eventvm reddere debeat et qva relatione ea conivngantvr, et ostenditvr vnam eandemqve envntiationem varias specificationes admittere. Deinde algorithmvs definitvr vt processvs finitvs, praecisvs et generalis, et gradibvs nvmeratis scribitvr algorithmvs divisionis per svbtractiones svccessivas. Docetvr qvomodo algorithmvs tabvla vestigii manv perseqvendvs sit, qvae per totvm cvrsvm primvm instrvmentvm erit ad intellegendvm et ad emendandvm. Exponvntvr tres modi gradvs conivngendi (seqventia, decisio et repetitio), qvibvs omnis algorithmvs scribitvr, et discitvr ostendere repetitionem desinere ope qvantitatis qvae in qvoqve gyro decrescit neqve sine fine descendere potest.

Proposita discendi

Problema simplex specificare, introitvs eivs, exitvs et condiciones qvas implere debent indicando.
Algorithmvm gradibvs nvmeratis describere, sine ambigvitate, decisionibvs et repetitionibvs expressis.
Algorithmvm tabvla vestigii manv perseqvi eivsqve eventvm pro introitv dato determinare.
In processv dato seqventiam, decisionem et repetitionem distingvere, et ostendere repetitionem desinere.

Qvid sit problema compvtationale

Problema compvtationale est relatio inter dvas species datorvm: ea qvae accipivntvr, qvae introitvs appellantvr, et ea qvae reddenda svnt, qvae exitvs appellantvr. Id solvere non est responsvm pro vno casv obtinere, sed methodvm habere qvae, pro qvolibet introitv admissibili, exitvm prodvcat qvi relationem impleat. «Qvantvm est 17 per 5 divisvm?» qvaestio est; «datis dvobvs integris, eorvm qvotientem et residvvm invenire» problema est, qvia de omnibvs integrorvm paribvs simvl loqvitvr.

Iam vero sermo cotidianvs imprecisvs est, et eadem envntiatio plvribvs modis intellegi potest. Qvam ob rem, anteqvam solvitvr, specificatvr: scribitvr qvid intret, qvid exeat et qvas condiciones qvaeqve res implere debeat. Specificatio tria membra habet. Introitvs data cvm sva specie envmerat (integros, decimales, verba) et condiciones qvae ab eis exigvntvr, qvae praecondicio appellantvr: qvi solvtione vtitvr se eas servatvrvm spondet. Exitvs eventvs envmerat. Relatio, sive postcondicio, dicit qvid exitvs respectv introitvs implere debeat: qvi solvtionem scribit se eam praestatvrvm spondet, dvmmodo praecondicio servata sit. Inde seqvitvr specificationem esse pactvm inter evm qvi problema proponit et evm qvi solvit, et extra praecondicionem solvtionem nihil promittere.

ExemplvmMaximvm trivm nvmerorvm

Envntiatio cotidiana: «maximvm trivm nvmerorvm invenire». Specificatio:

Introitvs: tres nvmeri $x$ , $y$ , $z$ (integri vel decimales, sine alia condicione).
Exitvs: nvmervs $m$ .
Relatio: $m$ vnvm ex tribvs datis est, nec vllvm eorvm maivs est qvam $m$ ; id est $m \geq x$ , $m \geq y$ et $m \geq z$ .

Relatio non dicit «maximvs trivm», qvod ipsvm est qvod definiri volebatvr, sed dvas condiciones qvae examinari possvnt. Prima exigit vt $m$ vnvm ex datis sit (sine ea, nvmervs 1000 secvndam pro paene qvolibet introitv impleret); secvnda, vt nvllvm id svperet. Et specificatio obiter dvbivm solvit qvod envntiatio apertvm relinqvebat: si dvo data in maximo aeqvantvr, vt in $(4, 9, 9)$ , exitvs est $9$ , nec vllvs in eo error est.

Eadem envntiatio varias specificationes admittit, et inter eas eligere decisio est, non neglegentia. Casvs maxime instrvctivvs est divisio integrorvm. Pro integris $a \geq 0$ et $b > 0$ omnes consentivnt: qvotiens $q$ et residvvm $r$ soli integri svnt qvi implent

a = b \cdot q + r, \quad 0 \leq r < b

Ita pro $a = 17$ et $b = 5$ svnt $q = 3$ et $r = 2$ , qvia $17 = 5 \cdot 3 + 2$ . Sed envntiatio «dvos integros dividere» non dicit qvid faciendvm sit si $a$ negativvs est, nec qvaestio otiosa est: pro $a = -7$ et $b = 2$ dvo responsa rationabilia svnt.

ExemplvmDvae specificationes divisionis cvm dividendo negativo

Prima specificatio: residvvm nvmqvam negativvm est, $0 \leq r < b$ . Tvm $-7 = 2 \cdot (-4) + 1$ , et exitvs est $q = -4$ , $r = 1$ . Haec est qvae in mathematica traditvr, in lectione «Divisibilitas et divisio cvm residvo» cvrsvs Algebra et Geometria I.

Secvnda specificatio: qvotiens est eventvs divisionis cvm decimalibvs, decimalibvs abiectis, id est ad nihilvm versvs rotvndatvs; residvvm est qvod deest, et signvm dividendi habet. Tvm $-7 / 2 = -3{,}5$ ad $-3$ trvncatvr, et $-7 = 2 \cdot (-3) + (-1)$ : exitvs est $q = -3$ , $r = -1$ .

Ambae $a = b \cdot q + r$ implent; differvnt condicione qvae residvo imponitvr. Nevtra error est, sed programma qvod alteram adhibet credens se alteram adhibere cvm negativis falsos eventvs dabit. Rem in antecessvm dicamvs: C++ secvndam adoptat, vt in lectione Arithmetica videbitvr; qvi primam exspectat mirabitvr.

Est tertia optio, qvae in vsv freqventissima est: casvm per praecondicionem exclvdere. Si specificatio $a \geq 0$ exigit, problema negativorvm evanescit, non qvia solvtvm sit, sed qvia qvi solvtione vtitvr se id non propositvrvm spopondit. Qvod fieri non potest est qvaestionem indecisam relinqvere. Et eadem de cavsa specificatio $b > 0$ exigit: cvm $b = 0$ non exsistvnt $q$ et $r$ qvi relationem impleant, et pactvm id dicere debet.

Error freqvens est per exemplvm specificare: «exitvs ex 17 et 5 est 3 et 2». Exemplvm illvstrat, sed non specificat, qvia non dicit qvid ceteris introitibvs accidat; infinitae relationes diversae in vno casv congrvvnt. Specificatio vt condicio generalis scribitvr, et exempla postea ad eam examinandam servivnt.

Algorithmi

Problemate specificato, qvaeritvr methodvs qva solvatvr. Algorithmvs est series instrvctionvm qvae, cvilibet introitvi praecondicionem implenti applicata, nvmero finito gradvvm exitvm prodvcit qvi postcondicionem implet. Definitio tres postvlationes continet.

Finitas. Algorithmvs nvmero finito instrvctionvm scribitvr et, pro qvolibet introitv admissibili, desinit postqvam nvmervm finitvm earvm peregit. Processvs qvi pro aliqvo introitv in perpetvvm pergit pro illo introitv algorithmvs non est.
Praecisio. Qvaeqve instrvctio vnam tantvm significationem habet, et qvi eam exseqvitvr omni momento scit qvid faciendvm sit et qvae instrvctio seqvatvr. Nvlla decisio arbitrio exseqventis relinqvitvr.
Generalitas. Algorithmvs problema pro omnibvs introitibvs admissibilibvs solvit, non pro vno tantvm casv.

Aliqva cvm libertate, algorithmvs etiam appellatvr processvs praecisvs et qvi desinit, sed qvi pro aliqvo introitv admissibili postcondicionem non implet: stricte loqvendo est algorithmvs pro alio problemate, et dicetvr non rectvs pro problemate specificato. Sic loqventvr problemata hvivs lectionis, qvae algorithmos non rectos exemplo contrario refellvnt.

Praescriptvm cvlinarivm algorithmo simile est, et ideo comparatio vsitata est; sed paene nvllvm algorithmvs est. «Pvgillvm salis addere» praecisvm non est, qvia pvgillvs qvantitas non est; «in fvrno coqvere donec avratvm sit» ex ivdicio pendet qvod dvae personae diverse facerent; «saepivs agitare» non dicit qvot vicibvs. Coqvvs has lacvnas sva experientia explet; compvtatrvm nvllam habet. Inde seqvitvr postvlatio qvae totvm cvrsvm regit: algorithmvm seqvi posse debet etiam qvi problema non intellegit, nihil divinando. Si, vt gradvm exseqvaris, scire oportet ad qvid serviat, gradvs male scriptvs est.

Algorithmi hvivs cvrsvs primvm gradibvs nvmeratis scribvntvr, Latine, cvm qvibvsdam conventionibvs. Data qvae dvrante algorithmo mvtantvr litteris vel verbis nominantvr, vt $q$ vel $r$ , et variabiles appellantvr. Scribitvr « $r$ valorem $r - b$ accipit» vt dicatvr $r - b$ compvtari cvm valore praesenti ipsivs $r$ et eventvm fieri novvm valorem ipsivs $r$ ; valor prior amittitvr. In forma contracta, qvae in notis capiendis adhibetvr, eadem instrvctio sagitta sinistrorsvm versa scribitvr, qvae in claviatvra est r <- r - b. Instrvctiones ordine nvmerorvm svorvm peragvntvr, nisi vna earvm alivd dicat.

ExemplvmDivisio per svbtractiones svccessivas

Problema est id qvod svpra specificatvm est: introitvs, dvo integri $a \geq 0$ et $b > 0$ ; exitvs, dvo integri $q$ et $r$ cvm $a = b \cdot q + r$ et $0 \leq r < b$ . Idea est distribvendi: ex $a$ avfervntvr acervi magnitvdinis $b$ dvm fieri potest, acervi ablati nvmerantvr, et qvod svperest residvvm est.

$q$ valorem $0$ accipit, et $r$ valorem $a$ accipit.
Dvm $r \geq b$ valet, gradvs 3 et 4 repete; cvm valere desinit, ad gradvm 5 perge.
$r$ valorem $r - b$ accipit.
$q$ valorem $q + 1$ accipit; ad gradvm 2 redi.
Redde $q$ et $r$ , et desine.

Gradvs 2 qvaestio est qvae qvoqve tempore ponitvr: ante primvm gyrvm et post vnvmqvemqve. Gradvs 3 et 4 corpvs repetitionis efficivnt, id qvod repetitvr. Nihil arbitrio exseqventis relinqvitvr: omni momento vna tantvm instrvctio seqvens est.

Algorithmvs lentvs est (vt decies centena milia per tria dividat, plvs qvam trecenta milia gyrorvm facit), et methodvs scholastica divisionis mvlto celerior est; sed rectvs est, et simplicitas eivs evm aptissimvm reddit vt de algorithmis ratiocinari discatvr. Cvrsvs ad discrimen inter algorithmvm rectvm et efficientem redibit in lectione Svmptvs algorithmi.

Deniqve expedit algorithmvm a scriptvra sva seivngere. Algorithmvs divisionis per svbtractiones idem est sive Latine scribitvr, sive in diagrammate, sive in C++ sive in alia qvavis lingva programmandi: qvod evm definit est series operationvm, non verba. Programma est scriptvra algorithmi in lingva qvam machina exseqvi potest, et lectio Programmata, compilatores et C++ explicabit qvomodo ea exsecvtio fiat. Qvae si ita svnt, programma dvobvs modis valde diversis vitiosvm esse potest: qvia algorithmvs non rectvs est, et tvm nvlla lingva evm servat, avt qvia algorithmvs rectvs est sed male scriptvs. Vtrvmqve casvm distingvere dimidivm est laboris emendandi, et ideo cvrsvs semper primvm algorithmvm scribit.

Algorithmvm manv perseqvi

Algorithmvm legere non svfficit vt sciatvr qvid faciat; exseqvendvs est. Evm manv perseqvi, vt machina faceret, nec gradvs omittendo nec eventvs divinando, facvltas est programmatoris vtilissima: ea algorithmvs examinatvr anteqvam scribatvr, exitvs programmatis praedicitvr anteqvam exseqvatvr, et error invenitvr in eo qvod deficit.

Instrvmentvm est tabvla vestigii: colvmna pro nvmero gradvs qvi peragitvr, vna colvmna pro qvaqve variabili et, si expedit, vna pro condicionibvs qvae aestimantvr; et vnvs ordo pro qvoqve gradv peracto. In qvoqve ordine notatvr novvs valor variabilis qvae eo gradv mvtata est, et vacvvm relinqvitvr qvod non mvtatvm est, ita vt valor praesens variabilis sit vltimvs in eivs colvmna scriptvs. Condiciones cvm svo eventv notantvr.

ExemplvmVestigivm divisionis 17 per 5

Divisionem per svbtractiones svccessivas perseqvimvr cvm $a = 17$ et $b = 5$ . Sagitta figvrae gradvm modo peractvm indicat; linea pvnctata admonet gradvm 4 ad gradvm 2 redire.

Demonstratio

$(q, r) = (0, 17)$
Gradvs 1: valores initiales dantvr. Introitvs praecondicionem implet, qvia $17 \geq 0$ et $5 > 0$ .
$(q, r) = (1, 12)$
Primvs gyrvs. In gradv 2 confirmatvr $17 \geq 5$ , itaqve corpvs peragitvr: gradvs 3 acervvm qvinqve avfert et gradvs 4 evm nvmerat.
$(q, r) = (2, 7)$
Secvndvs gyrvs: $12 \geq 5$ , et corpvs itervm peragitvr.
$(q, r) = (3, 2)$
Tertivs gyrvs: $7 \geq 5$ , et corpvs itervm peragitvr.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
In gradv 2 condicio deficit, qvia $2 < 5$ : algorithmvs ad gradvm 5 pergit et reddit $q = 3$ et $r = 2$ . Exitvs postcondicionem implet.

Tabvla integra dvodecim ordines habet: gradvm 1, tres gyros ternorvm ordinvm (gradvs 2, 3 et 4), examinationem qvae deficit et redditionem.

Dvae observationes de tabvla. Prima: nvmervs gyrorvm qvotienti aeqvalis est, $3$ , et gradvs 2 semel saepivs qvam corpvs peractvs est, $4$ vicibvs; qvod semper fit in repetitione hvivs formae, qvia vltima examinatio ea est qvae deficit. Secvnda: vestigivm aliqvid docet qvod textvs algorithmi primo aspectv non dicit; si $a < b$ , exempli gratia $a = 3$ et $b = 5$ , condicio prima vice deficit, corpvs nvlla vice peragitvr, et exitvs est $q = 0$ , $r = 3$ , qvi rectvs est, qvia $3 = 5 \cdot 0 + 3$ . Casvm oblivisci qvo repetitio non peragitvr vnvs ex erroribvs freqventissimis est in algorithmis designandis, et vestigivm cvm introitibvs parvis evm detegit.

Vestigivm vnivs casvs non demonstrat algorithmvm rectvm esse: vnvm casvm examinat. Sed vestigivm bene electvm (casvs commvnis, casvs marginalis, casvs qvo repetitio non peragitvr) plerosqve errores detegit, et qvod deficit ostendit vbi sint. Lectio Circvitvs rectos designare docebit qvomodo a casibvs ad demonstrationem transeatvr.

Seqventia, decisio et repetitio

Prope inspecti, algorithmi pavcissimis elementis constrvvntvr. Svnt instrvctiones elementares (variabili valorem dare, eventvm reddere) et tres modi eas conivngendi.

Seqventia: instrvctio post instrvctionem, ordine. Gradvs 3 et 4 divisionis seqventia svnt: primvm svbtrahitvr, deinde nvmeratvr.
Decisio: provt condicio impletvr necne, membrvm vnvm vel altervm peragitvr (vel membrvm vel nihil). «Si $y > m$ , $m$ valorem $y$ accipit» decisio est.
Repetitio: dvm condicio impletvr, membrvm itervm atqve itervm peragitvr. Gradvs 2 divisionis, cvm svo corpore, repetitio est.

Qvaeqve forma vnvm aditvm et vnvm egressvm habet, et interivs eivs rvrsvs qvaelibet ex tribvs esse potest: corpvs repetitionis decisiones continere potest, ramvs decisionis repetitionem continere potest, et sic deinceps. Qvae si ita svnt, tribvs formis algorithmi cvivsvis complexitatis constrvvntvr, sicvt pavcis elementis inter se congrventibvs qvodvis aedificivm constrvitvr. Eas svfficere ad omnem algorithmvm exprimendvm notvm est theoriae programmandi effatvm (id demonstravervnt Corrado Böhm et Givseppe Iacopini anno 1966); hic non demonstratvr, sed totvs cvrsvs id confirmat: programmata qvae in eo scribentvr, qvamvis longa, nihil alivd adhibebvnt qvam has tres formas, in C++ scriptas vt if pro decisione et while vel for pro repetitione, in lectionibvs Decisiones et Circvitvs.

Notatio vtilis ad formam algorithmi videndam est diagramma flvxvs: qvaeqve instrvctio est rectangvlvm, qvaeqve condicio rhombvs cvm dvobvs egressibvs (impleta, qvam figvra signo $1$ notat, et non impleta, $0$ ), et sagittae dicvnt qvis gradvs seqvatvr. Notatio est, non finis: servit ad parvvm algorithmvm vno obtvtv inspiciendvm, sed ad magnitvdinem non accommodatvr, et nemo programma magnvm pingendo scribit.

ExemplvmTres formae earvmqve compositio

Figvra tres formas pingit cvm instrvctionibvs genericis $A$ et $B$ et condicione $c$ , deinde eas componit in diagrammate divisionis per svbtractiones svccessivas.

Demonstratio

$A ; B$
Seqventia: peragitvr $A$ et deinde $B$ ; vnvs aditvs est et vnvs egressvs.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Decisio: si $c$ impletvr, peragitvr $A$ ; sin minvs, $B$ . Ambo rami in vnvm egressvm convenivnt.
$c, A, c, A, \ldots, c$
Repetitio: aestimatvr $c$ ; si impletvr, peragitvr $A$ et itervm aestimatvr $c$ ; sin minvs, exitvr. Condicio semel saepivs qvam corpvs aestimatvr.
$a = b \cdot q + r, \quad 0 \leq r < b$
Compositio: divisio per svbtractiones svccessivas est seqventia (valores initiales, repetitio, redditio) cvivs repetitio pro corpore aliam seqventiam habet (svbtrahere, nvmerare).

Tres formas in processv sermone cotidiano scripto distingvere primvs gradvs est ad evm convertendvm. Signvm decisionis est «si», «si forte» vel «provt»; repetitionis, «dvm», «donec», «pro qvoqve» vel «tot vicibvs qvot». Processvs sine vllo horvm verborvm seqventia est, et si introitvs magnitvdinis variabilis tractare debet (indicem nvmerorvm, textvm), ei deest repetitio.

Desinitne?

Finitas ad definitionem algorithmi pertinet, et repetitio solvs locvs est in qvo amitti potest: seqventia qvinqve gradvvm qvinqve gradvs peragit, et decisio vnvm ex ramis svis peragit; sed repetitio corpvs svvm tot vicibvs peragit qvot condicio impletvr, nec qvicqvam in antecessvm praestat eam impleri desitvram esse.

Vt ostendatvr repetitionem desinere, qvaeritvr qvantitas, ex variabilibvs compvtata, qvae dvas condiciones impleat: nvmervs natvralis est (integer nec negativvs) dvm repetitio pergit, et in qvoqve gyro stricte decrescit. Qvae si ita svnt, repetitio desinit: series natvralivm stricte decrescens infinita esse non potest, qvia qvisqve gyrvs eam saltem vno minvit et a natvrali $n$ non plvres qvam $n$ descensvs ad nihilvm svnt. Haec qvantitas varians vel fvnctio marginis appellatvr, et lectio Circvitvs rectos designare ea ratione certa et constanti vtetvr.

ExemplvmVarians divisionis per svbtractiones

In divisione per svbtractiones svccessivas varians est $r$ . Dvm repetitio pergit, $r \geq b > 0$ , itaqve $r$ natvralis est. In qvoqve gyro $r$ valorem $r - b$ accipit, et qvia $b > 0$ (praecondicio), novvs valor stricte minor est. Ergo repetitio desinit, et id facit svmmvm post $a$ gyros (immo prorsvs post $q$ gyros, qvotientem).

Animadvertatvr vbi praecondicio $b > 0$ adhibita sit. Si algorithmvs cvm $b = 0$ peragitvr, gradvs 3 relinqvit $r$ immvtatvm, condicio $r \geq 0$ semper impletvr et repetitio nvmqvam desinit: algorithmvs non est vitiosvs, sed ei datvs est introitvs qvem pactvm exclvdebat. Et si $b$ negativvs esset, $r$ in qvoqve gyro cresceret. Praecondicio non est ornamentvm: est prorsvs id qvod reqviritvr vt ratiocinatio procedat.

Ambae condiciones variantis necessariae svnt, et facile est in vtralibet errare. Consideretvr hic processvs, qvi decernere vvlt vtrvm natvralis $n$ par sit: «dvm $n \neq 0$ , $n$ valorem $n - 2$ accipit; si ad nihilvm pervenitvr, $n$ par erat». Qvantitas $n$ in qvoqve gyro decrescit, et tamen processvs non desinit si $n$ impar est: cvm $n = 5$ per $3$ , $1$ , $-1$ , $-3$ transit, et condicio $n \neq 0$ nvmqvam deficit. Qvod non impletvr est altera condicio: $n$ natvralis esse desinit, qvia condicio repetitionis non impedit qvominvs infra nihilvm descendat. Correctio est repetere dvm $n \geq 2$ et in fine decernere secvndvm valorem qvi manet, $0$ vel $1$ ; nvnc $n$ in qvoqve gyro natvralis est, qvia tantvm svbtrahitvr cvm $n \geq 2$ , et decrescit: processvs desinit.

Decernere vtrvm repetitio desinat non semper facile est. Exemplvm celebre: a natvrali $n \geq 1$ incipiendo, dvm $n \neq 1$ , si $n$ par est per dvo dividitvr, et si impar est per $3n + 1$ svbstitvitvr. Cvm $n = 6$ series est $6, 3, 10, 5, 16, 8, 4, 2, 1$ , et desinit. Nemo invenit $n$ pro qvo non desinat, et compvtatris pro ingenti copia valorvm confirmatvm est; sed nemo demonstrare potvit eam semper desinere: est coniectvra Collatz, problema apertvm mathematicae. Nvlla qvantitas nota in qvoqve gyro decrescit. Doctrina pro eo qvi programmat modesta et firma est: algorithmvs cvivs finem qvis ostendere nescit absolvtvs non est.

Errores freqventes

Gradvs ambigvi. «Saepivs repetere», «donec bene sit», «nvmervm idonevm svmere». Qvisqve gradvs peragi posse debet sine problemate intellecto; sin minvs, male scriptvs est.
Casvm oblivisci qvo repetitio non peragitvr. Omnis repetitio cvm condicione in initio corpvs svvm nvlla vice peragere potest. Semper qvaerendvm est qvid algorithmvs eo casv reddat, et vestigivm cvm introitv minimo respondet.
Per exemplvm specificare. «Pro 17 et 5 dat 3 et 2» specificatio non est; relatio vt condicio generalis scribitvr, et exemplvm eam illvstrat.
Algorithmvm cvm programmate svo confvndere. Programma qvod deficit vitivm habere potest in algorithmo avt in eivs scriptvra. Qvi algorithmvm antea non scripsit nescit vtrvm qvaerat.
Finem pro certo habere. Qvantitatem decrescere non svfficit: praeterea natvralis esse debet dvm repetitvr.

Problemata solvta

Problema solvtvm 1Maximvs trivm nvmerorvm, cvm aeqvalitatibvs

Algorithmvm scribere qvi specificationem maximi trivm nvmerorvm initio lectionis positam impleat, evmqve manv perseqvi pro introitibvs $(7, 2, 5)$ et $(4, 9, 9)$ .

Solvtio

$m = x$
Idea: introitvs percvrritvr et maximvs adhvc visvs in variabili $m$ servatvr. Primvs gradvs: $m$ valorem $x$ accipit. Post evm $m$ maximvm est datorvm visorvm, qvae svnt tantvm $x$ .
$m = \max(x, y, z)$
Secvndvs gradvs: si $y > m$ , $m$ valorem $y$ accipit. Tertivs gradvs: si $z > m$ , $m$ valorem $z$ accipit. Qvartvs gradvs: redde $m$ . Tres svnt instrvctiones in seqventia, qvarvm dvae decisiones svnt sine ramo alternativo.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Vestigivm pro $(7, 2, 5)$ : post primvm gradvm $m = 7$ ; in secvndo, $2 > 7$ falsvm est et $m$ non mvtatvr; in tertio, $5 > 7$ falsvm est et $m$ non mvtatvr. Redditvr $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Vestigivm pro $(4, 9, 9)$ : post primvm gradvm $m = 4$ ; in secvndo, $9 > 4$ et $m$ valorem $9$ accipit; in tertio, $9 > 9$ falsvm est et $m$ non mvtatvr. Redditvr $9$ , qvod rectvm est: aeqvalitas tractationem propriam non exigit.
$m \geq x, \quad m \geq y, \quad m \geq z$
Ratio: post qvemqve gradvm $m$ vnvm ex datis visis est nec vllvm eorvm id svperat. Vervm est post primvm, et qvaeqve decisio id conservat: si datvm novvm maivs est, fit $m$ ; sin minvs, $m$ non svperat. In fine tria visa svnt, et $m$ postcondicionem implet.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Si $y \geq m$ pro $y > m$ scriptvm esset, eventvs idem esset, qvia in aeqvalitate valor aeqvalis assignatvr. Electio inter $>$ et $\geq$ momentvm haberet si etiam positio maximi peteretvr: cvm $>$ prima positionvm aeqvalivm redditvr, cvm $\geq$ vltima; formvla positionem appellat $p$ .

Problema solvtvm 2Annvs bissextilis, exemplo contrario correctvs

In calendario Gregoriano annvs bissextilis est si per $4$ divisibilis est, exceptis iis qvi per $100$ divisibiles svnt, qvi tantvm bissextiles svnt si praeterea per $400$ divisibiles svnt. Discipvlvs algorithmvm proponit: «si annvs per $4$ divisibilis est, redde ita; sin minvs, redde non». Annvm invenire qvo deficit et algorithmvm rectvm scribere, cvm sva specificatione.

Solvtio

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Specificatio. Introitvs: integer $n \geq 1583$ (calendarivm Gregorianvm ab Octobri mense anni 1582 viget). Exitvs: ita vel non. Relatio: exitvs est ita prorsvs cvm $n$ per $4$ divisibilis est nec per $100$ , vel per $400$ divisibilis est.
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
Algorithmvs propositvs in plerisqve annis recte respondet, et ideo rectvs videtvr. Ad evm refellendvm svfficit annvs per $100$ nec per $400$ divisibilis: $1900$ per $4$ divisibilis est, et algorithmvs dicit ita; sed annvs $1900$ bissextilis non fvit.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Algorithmvs correctvs, tribvs decisionibvs concatenatis. Gradvs 1: si $n$ per $400$ divisibilis est, redde ita et desine. Gradvs 2: si $n$ per $100$ divisibilis est, redde non et desine. Gradvs 3: si $n$ per $4$ divisibilis est, redde ita; sin minvs, redde non.
$2000, \quad 1900, \quad 2024, \quad 2023$
Ordo qvaestionvm essentialis est: a regvla maxime particvlari ad maxime generalem procedvnt. Si primvm de divisore $4$ qvaereretvr, annvs $1900$ ita acciperet anteqvam ad exceptionem perveniretvr. Vestigivm pro qvattvor annis, vno pro qvoqve casv: $2000$ (gradvs 1: ita), $1900$ (gradvs 2: non), $2024$ (gradvs 3: ita), $2023$ (gradvs 3: non).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
Docvmentvm non tantvm ad calendaria pertinet: algorithmvs vno exemplo contrario refellitvr, et exempla contraria in marginibvs regvlarvm qvaervntvr, non in casibvs commvnibvs. Annos $2024$ , $2020$ et $2016$ temptare nihil detexisset.

Problema solvtvm 3Qvot gyros divisio per svbtractiones faciat

Divisionem per svbtractiones svccessivas manv perseqvi cvm $a = 20$ et $b = 5$ , et cvm $a = 0$ et $b = 7$ . Deinde ostendere pro omni introitv admissibili algorithmvm post prorsvs $q$ gyros desinere eivsqve exitvm postcondicionem implere.

Solvtio

$20 = 5 \cdot 4 + 0$
Vestigivm cvm $a = 20$ , $b = 5$ : $r$ per $20$ , $15$ , $10$ , $5$ , $0$ transit, et $q$ per $0$ , $1$ , $2$ , $3$ , $4$ . Qvinta examinatio, $0 \geq 5$ , deficit. Exitvs: $q = 4$ , $r = 0$ . Hic casvs marginalis est divisio exacta: qvartvs gyrvs fit qvia $5 \geq 5$ , et ideo condicio esse debet $\geq$ et non $>$ .
$0 = 7 \cdot 0 + 0$
Vestigivm cvm $a = 0$ , $b = 7$ : prima examinatio, $0 \geq 7$ , deficit; corpvs nvlla vice peragitvr. Exitvs: $q = 0$ , $r = 0$ , qvi rectvs est.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Relatio qvae conservatvr. Ante primvm gyrvm, $b \cdot q + r = b \cdot 0 + a = a$ . In qvoqve gyro $r$ deminvitvr valore $b$ et $q$ avgetvr valore $1$ , ita vt $b \cdot q + r$ non mvtetvr. Ergo aeqvalitas post qvemqve gyrvm valet.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Finis. Dvm repetitvr, $r \geq b > 0$ , et $r$ natvralis est; in qvoqve gyro deminvitvr valore $b \geq 1$ . Series natvralivm stricte decrescens finita est: repetitio desinit.
$a = b \cdot q + r, \quad 0 \leq r < b$
Cvm desinit, condicio defecit: $r < b$ . Praeterea $r \geq 0$ , qvia $b$ tantvm svbtrahitvr cvm $r \geq b$ . Vna cvm relatione qvae conservatvr, exitvs postcondicionem implet; et qvia $q$ gyros nvmerat, nvmervs gyrorvm qvotiens est.

Exercitationes in linea

Exercitatio 1Gyros nvmerare

Algorithmvm seqventem manv perseqvi et in capsa valorem qvem reddit scribere, solvm nvmervm.

$n$ valorem $29$ accipit, et $k$ valorem $0$ accipit.
Dvm $n > 1$ valet, gradvs 3 et 4 repete; cvm valere desinit, ad gradvm 5 perge.
Si $n$ par est, $n$ valorem $n / 2$ accipit; si impar est, $n$ valorem $n + 1$ accipit.
$k$ valorem $k + 1$ accipit; ad gradvm 2 redi.
Redde $k$ .

Navigatrvm responsvm tvvm statim inspicit, neqve aestimat.

Hic responsvm tvvm scribe

Indicivm

Tabvlam fac: $n$ in primo gyro a $29$ ad $30$ transit. Vnvm gyrvm nvmera pro qvaqve mvtatione ipsivs $n$ , donec $n$ valorem $1$ habeat.

Exercitatio 2Condicio qvae deest

Algorithmvs seqvens, forma contracta scriptvs, qvotientem et residvvm divisionis per svbtractiones svccessivas compvtare debet, sed ei deest condicio repetitionis. Seriem lineolarvm infimarvm condicione recta svbstitvere, nihil alivd mvtando.

Navigatrvm responsvm tvvm statim inspicit, neqve aestimat.

Hic responsvm tvvm scribe

Indicivm

Algorithmvm manv perseqvere cvm $a = 10$ et $b = 5$ : secvndvs gyrvs fieri debet qvamvis residvvm prorsvs $5$ valeat.

Problemata proposita

Cviqve problemati indicivm est, qvod non nisi post conatvm aperire expedit, et responsvm, qvod indicio aperto apparet.

Problema propositvm 1Ordinem trivm nvmerorvm specificare

Specificationem problematis «tres nvmeros ordinare» scribere (introitvm, exitvm et relationem) et indicare qvas decisiones capere cogat qvas envntiatio non capiebat. Deinde confirmare specificationem pro introitv $(5, 2, 5)$ hos dvos exitvs reicere, $(2, 5, 6)$ et $(2, 5, 5, 5)$ , et admittere $(2, 5, 5)$ .

Indicivm

Exitvs «ordinatvs» nihil cvm introitv commvne habere potest. Qvae condicio nvmeros exitvs cvm nvmeris introitvs conivngit, repetitis inclvsis? Crescens an decrescens? Strictvs an non?

Responsvm

Introitvs: tres nvmeri $x$ , $y$ , $z$ . Exitvs: tres nvmeri $u$ , $v$ , $w$ . Relatio: $u \leq v \leq w$ , et $(u, v, w)$ est permvtatio ipsivs $(x, y, z)$ , id est eosdem valores cvm eisdem repetitionibvs continet. Decisiones qvas envntiatio non capiebat: directio (hic a minimo ad maximvm); ordinem non esse strictvm ( $\leq$ et non $<$ , qvia cvm valoribvs repetitis ordo strictvs fieri non potest); et exitvm permvtationem esse debere. $(2, 5, 6)$ ordinatvs est sed $6$ continet qvi non aderat; $(2, 5, 5, 5)$ qvattvor valores habet; $(2, 5, 5)$ vtramqve condicionem implet. Sine condicione permvtationis, $(0, 0, 0)$ exitvs rectvs pro qvolibet introitv esset.

Problema propositvm 2Cifrae nvmeri, a dextra ad sinistram

Algorithmvm gradibvs nvmeratis scribere qvi natvralem $n$ accipiat et cifras eivs ab vltima ad primam reddat (pro $4072$ reddit $2$ , $7$ , $0$ , $4$ ), solvm qvotiente et residvo divisionis per $10$ vtendo. Evm manv perseqvi pro $4072$ et pro $0$ , et ostendere evm pro omni $n$ desinere.

Indicivm

Residvvm divisionis per $10$ vltima cifra est, et qvotiens est nvmervs sine ea. Decerne vtrvm condicio ante an post cifram redditam qvaeratvr, et vide qvid fiat cvm $n = 0$ , qvi vnam cifram habet.

Responsvm

Algorithmvs rectvs: (1) redde residvvm divisionis ipsivs $n$ per $10$ ; (2) $n$ valorem qvotientis divisionis ipsivs $n$ per $10$ accipit; (3) si $n > 0$ , ad gradvm 1 redi; sin minvs, desine. Qvaestio post corpvs ponitvr, ita vt corpvs saltem semel peragatvr: pro $n = 0$ reddit $0$ , qvae vnica eivs cifra est. Si in initio qvaereretvr («dvm $n > 0$ »), pro $n = 0$ nihil redderetvr; is est error casvm obliviscendi qvo repetitio non peragitvr. Vestigivm pro $4072$ : reddvntvr $2$ , $7$ , $0$ , $4$ , et $n$ per $407$ , $40$ , $4$ , $0$ transit. Finis: varians est $n$ , natvralis; si ad gradvm 1 reditvr, id fit qvia $n > 0$ , et pro $n \geq 1$ qvotiens per $10$ stricte minor est qvam $n$ , ita vt $n$ in qvoqve gyro stricte decrescat.

Problema propositvm 3Nvmmi pro pecvnia reddenda

Praesto svnt nvmmi $50$ , $10$ et $1$ vnitatvm, copia illimitata. Specificatio: introitvs, natvralis $m$ ; exitvs, tres natvrales $c_{50}$ , $c_{10}$ , $c_1$ cvm $50 c_{50} + 10 c_{10} + c_1 = m$ et minimo nvmero nvmmorvm, $c_{50} + c_{10} + c_1$ . Qvaedam persona algorithmvm seqventem proponit. Introitvm invenire qvo deficit, qvodqve vitivm explicare et corrigere.

$c_{50}$ , $c_{10}$ et $c_1$ valorem $0$ accipivnt.
Si $m \geq 50$ , $c_{50}$ valorem $c_{50} + 1$ accipit et $m$ valorem $m - 50$ accipit.
Dvm $m > 10$ : $c_{10}$ valorem $c_{10} + 1$ accipit et $m$ valorem $m - 10$ accipit.
Dvm $m > 0$ : $c_1$ valorem $c_1 + 1$ accipit et $m$ valorem $m - 1$ accipit.
Redde $c_{50}$ , $c_{10}$ et $c_1$ .

Indicivm

Svmma nvmmorvm semper est $m$ ; qvod deficere potest est eorvm nvmervs. Tempta mvltiplvm exactvm ipsivs $10$ et svmmam maiorem qvam $100$ , et te ipsvm interroga qvo modo gradvs conivngendi gradvs 2 vtatvr et qvo vti debeat.

Responsvm

Dvo vitia svnt. Primvm, gradvs 3 adhibet $m > 10$ : cvm $m = 10$ nvllvm nvmmvm $10$ reddit et decem nvmmos $1$ reddit, pro vno. Secvndvm, gradvs 2 decisio est vbi repetitio reqviritvr: cvm $m = 120$ algorithmvs, vt scriptvs est, vnvm nvmmvm $50$ , sex $10$ et decem $1$ reddit (septendecim nvmmos), et etiam gradv 3 iam correcto vnvm $50$ et septem $10$ redderet (octo), pro dvobvs $50$ et dvobvs $10$ (qvattvor). Introitvs $m = 100$ ambo vitia ostendit: algorithmvs vnvm $50$ , qvattvor $10$ et decem $1$ reddit, qvindecim nvmmos, pro dvobvs. Correctio: gradvs 2, «dvm $m \geq 50$ , …»; gradvs 3, «dvm $m \geq 10$ , …». Sic correctvs algorithmvs semper maximvm nvmmvm qvi capitvr svmit, et cvm his tribvs nvmmis id minimvm nvmervm dat: cifra vnitatvm ipsivs $m$ nvmmis $1$ tantvm solvi potest, et ex eo qvod restat expedit qvam plvrimvm nvmmis $50$ solvere, qvia qvinqve $10$ tantvm valent qvantvm vnvs $50$ . Cvm aliis nvmmis, exempli gratia $1$ , $3$ et $4$ pro $m = 6$ , semper maximvm svmere minimvm iam non dat ( $4 + 1 + 1$ contra $3 + 3$ ).