Teh­tä­vä:
In­dek­sien kä­sit­te­lyä

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Lau­sek­keis­sa, väit­tä­mis­sä, al­go­rit­meis­sa ja oh­jel­mis­sa esiin­tyy pal­jon ti­lan­tei­ta, jois­sa jo­kin muut­tu­ja käy lä­pi pe­räk­käi­set ar­vot jol­ta­kin ko­ko­nais­lu­ku­vä­lil­tä a, …, y. Toi­si­naan tar­vit­see siir­tää in­dek­sin lä­pi­käy­mää vä­liä yh­del­lä suun­taan tai toi­seen, siis esi­mer­kik­si vä­lik­si a + 1, …, y + 1, si­ten, et­tä lau­sek­keen ar­vo tms. ei muu­tu. Myös mo­ni­mut­kai­sem­pia in­dek­sien muun­nos­tar­pei­ta esiin­tyy esi­mer­kik­si kun sum­ma­mer­kin­tö­jä on si­säk­käin. Täs­sä teh­tä­väs­sä har­joi­tel­laan in­dek­sien muun­ta­mis­ta.

Vä­lin ra­jois­ta

Jat­kos­sa käy­te­tään toi­si­naan ver­tai­lua <, toi­si­naan ≤. Oi­kei­den vas­taus­ten löy­tä­mi­nen hel­pot­tuu, jos muu­tat <:t ≤:ksi. Se on mah­dol­lis­ta, kos­ka in­dek­sit ovat ko­ko­nais­lu­ku­ja. Näin se käy:
i < j < n ⇔ ≤ j ≤
tai

Mit­kä ovat n:n funk­tio­na pie­nin ja suu­rin lu­ku, min­kä ohei­nen oh­jel­ma tu­los­taa?

for( int i=2; i < n; ++i ){ std::cout << i << ' '; }
for( int i=n; i <=4; ++i ){ std::cout << i << ' '; }
std::cout << '\n';
npie­ninsuu­rin
1 tai
2 tai
3 tai
4 tai
5 tai
6 tai
7 tai

Tu­los­te­taan edel­lä ol­leen oh­jel­man kal­tai­ses­ti ko­ko­nais­lu­vut a:sta v − 1:een ja v:stä y:hyn. An­na vält­tä­mä­tön ja riit­tä­vä eh­to sil­le, et­tä jo­kai­nen tu­los­tet­tu lu­ku on vä­hin­tään a ja enin­tään y.
tai

Huo­maam­me, et­tä jos vä­lin vii­mei­nen lu­ku on enin­tään en­sim­mäi­nen lu­ku mii­nus 2, niin pe­räk­käis­ten vä­lien yh­dis­tel­mään tu­lee lu­ku­ja jot­ka ei­vät sin­ne kuu­lui­si. Huo­maam­me myös, et­tä pe­räk­käis­ten vä­lien yh­dis­tä­mi­nen toi­mii hy­vin, jos vä­lin vii­mei­nen lu­ku on ai­na suu­rem­pi, sa­ma tai yh­tä pie­nem­pi kuin vä­lin en­sim­mäi­nen lu­ku. Jat­kos­sa ko­ko tä­män teh­tä­vän ajan voit olet­taa, et­tä muut­tu­jil­la on sel­lai­set ar­vot, et­tä tä­mä eh­to to­teu­tuu. Jos vä­lin vii­mei­nen lu­ku on yh­tä pie­nem­pi kuin vä­lin en­sim­mäi­nen lu­ku, niin vä­lis­sä on nol­la lu­kua.

Kä­sit­tei­tä ja vä­lin ko­ko

In­dek­sin muun­ta­mi­ses­sa en­sim­mäi­nen osat­ta­va asia on tun­nis­taa, mi­kä muut­tu­ja on in­dek­si. Sit­ten on tun­nis­tet­ta­va pie­nin ja suu­rin in­dek­sin ar­vo, joil­la lau­se­ke las­ke­taan tms. Tun­nis­ta ne seu­raa­vis­ta!

∀ i; 1 < i ≤ n: A[i] ≠ A[1]
in­dek­si pie­nin suu­rin
tai

∃ h; a ≤ h < b: A[h] = x
in­dek­si pie­nin suu­rin
tai

`sum_(k=-3)^(i+1) k^2`
in­dek­si pie­nin suu­rin
tai

n := N
while n > 0 do
    A[n] := A[n div 2]; n := n − 1
in­dek­si pie­nin suu­rin
tai

Tar­vit­see osa­ta sel­vit­tää, mon­ta­ko al­kio­ta kä­si­tel­tä­väs­sä vä­lis­sä on. Sii­nä aut­taa, jos muut­tu­jil­le va­li­taan ko­keek­si sel­lai­set ar­vot, et­tä vä­lis­sä on täs­mäl­leen yk­si al­kio. Va­lit­se sel­lai­set ar­vot!

∀ i; 1 < i ≤ n: A[i] ≠ A[1]
n = tai

∃ h; a ≤ h < b: A[h] = x
b = tai

`sum_(k=-3)^(i+1) k^2`
i = tai

n := N
while n > 0 do
    A[n] := A[n div 2]; n := n − 1
N = tai

Nyt si­nun pi­tää ker­toa, mon­ta­ko al­kio­ta kä­si­tel­tä­väs­sä vä­lis­sä on. Sii­hen on pe­riaat­tees­sa help­po ylei­nen lau­se­ke, jon­ka ta­paam­me ihan pian. Käy­tän­nös­sä kui­ten­kin sen kans­sa tu­lee hel­pos­ti vir­hei­tä ja unoh­duk­sia, joi­den vält­tä­mi­ses­sä aut­taa, et­tä on miet­ti­nyt en­sin yk­sit­täis­ta­pauk­sia. Siis­pä nyt pis­tän si­nut miet­ti­mään yk­sit­täis­ta­pauk­sia! Vas­taus­ten saa­mis­ta koh­dal­leen aut­taa tie­to, et­tä vas­taus­te­si tu­lee tuot­taa 1 ti­lan­teis­sa, jot­ka sel­vi­tit edel­lä.

∀ i; 1 < i ≤ n: A[i] ≠ A[1]
tai

∃ h; a ≤ h < b: A[h] = x
tai

`sum_(k=-3)^(i+1) k^2`
tai

n := N
while n > 0 do
    A[n] := A[n div 2]; n := n − 1
tai

Jos pie­nin in­dek­si on p ja suu­rin on s, niin in­dek­si käy lä­pi yh­teen­sä al­kio­ta.
tai

In­dek­si­alueen muun­ta­mi­nen

Min­kä al­kion A[i] va­lit­see, kun i saa pie­nim­män ar­von­sa kaa­vas­sa ∀ i; 1 < i ≤ n: A[i] ≠ A[1]? Se va­lit­see al­kion A[].
tai

Nyt muun­na kaa­va si­ten, et­tä pie­nin i:n ar­vo on 1. Suu­rim­man i:n ar­von saat koh­dal­leen esi­mer­kik­si huo­leh­ti­mal­la, et­tä i käy lä­pi yh­tä mon­ta ar­voa kuin edel­lä huo­ma­sit sen käy­vän lä­pi muun­ta­mat­to­mas­sa kaa­vas­sa. Huo­maa, et­tä si­nun on muu­tet­ta­va myös A[i] jo­ten­kin. Sen saat koh­dal­leen esi­mer­kik­si miet­ti­mäl­lä, min­kä­lai­nen lau­se­ke ha­ka­sul­ku­jen vä­lis­sä pi­tää ol­la, jot­ta se va­lit­si­si i:n ar­vol­la 1 tau­lu­kos­ta sa­man al­kion kuin al­ku­pe­räi­nen lau­se­ke va­lit­si i:n al­ku­pe­räi­sel­lä pie­nim­mäl­lä ar­vol­la.

tai

Teh­dään­pä vie­lä pa­ri mel­kein sa­man­lais­ta niin tu­lee hie­man ru­tii­nia. Täy­tyy siis sa­noa sa­ma väi­te kuin min­kä ∀ i; 1 < i ≤ n: A[i] ≠ A[1] sa­noo, mut­ta i käy lä­pi eri ar­vot.


tai


tai

Sit­ten muun­nam­me ∃ h; a ≤ h < b: A[h] = x. Nyt­kin mer­ki­tyk­sen pi­tää säi­lyä sa­ma­na, vaik­ka in­dek­si käy lä­pi eri ar­vo­ja.
∃ h; 0 < h < : A[] = x
tai

Toi­vot­ta­vas­ti osaat muun­taa tä­män sum­ma­mer­kin­nän, vaik­ka sum­ma­merk­kien pääl­le tu­le­vat teks­tit ei­vät ole ai­van oi­keas­sa koh­das­sa ei­vät­kä ai­van oi­kean nä­köi­set.
   i + 1
`sum_(k=-3) k^2 =``sum_(k=1)`
tai

Sit­ten oli­si vie­lä al­go­rit­min­pät­kä A[n] := A[n div 2]; n := n − 1. Sen mer­ki­tys pi­tää säi­lyt­tää en­nal­laan, vaik­ka si­joi­tus­lau­sei­den jär­jes­tys vaih­de­taan.
n := n − 1; A[] := A[]
tai

Ote­taan lo­puk­si toi­sen­tyyp­pi­nen muun­nos­teh­tä­vä. Jos­kus on tar­peen muun­taa esi­mer­kik­si `sum_(i=1)^n sum_(j=1)^i a_(i,j)` muo­toon `sum_(j=x)^y sum_(i=z)^w a_(i,j)`. Kos­ka yh­teen­las­ku on lii­tän­näi­nen ja vaih­dan­nai­nen, on­gel­ma­na on vain va­li­ta x, y, z ja w si­ten, et­tä jäl­kim­mäi­nen sum­ma­lau­se­ke käy lä­pi sa­mat (i, j)-pa­rit kuin en­sim­mäi­nen. Vas­tauk­sen löy­tä­mis­tä aut­taa, jos piir­rät ruu­du­kon, jon­ka va­sem­mas­sa reu­nas­sa on i:n ar­vo­ja ja ala- tai ylä­reu­nas­sa on j:n ar­vo­ja, ja jo­hon on mer­kit­ty, mit­kä (i, j)-pa­rit sum­ma käy lä­pi.
x = y = z = w =
tai