Tehtävä:
Indeksien käsittelyä

Lyhyt MathCheck-ohje (uuteen välilehteen)

Lausekkeissa, väittämissä, algoritmeissa ja ohjelmissa esiintyy paljon tilanteita, joissa jokin muuttuja käy läpi peräkkäiset arvot joltakin kokonais­luku­väliltä `a, ..., y`. Toisinaan tarvitsee siirtää indeksin läpi­käymää väliä yhdellä suuntaan tai toiseen, siis esimerkiksi väliksi `a+1, ..., y+1`, siten, että lausekkeen arvo tms. ei muutu. Myös moni­mutkaisempia indeksien muunnos­tarpeita esiintyy esimerkiksi kun summamer­kintöjä on sisäkkäin. Tässä tehtävässä harjoitellaan indeksien muuntamista.

Koko tämän tehtävän ajan voit olettaa, että muuttujilla on sellaiset arvot, että lauseke lasketaan, silmukan vartalo suoritetaan tms. ainakin kerran.

Jatkossa käytetään välillä vertailua `<`, välillä `<=`. Oikeiden vastausten löytäminen helpottuu, jos muutat `<`:t `<=`:ksi. Se on mahdollista, koska indeksit ovat kokonais­lukuja. Näin se käy:
`i < j < n hArr``<= j <=`
tai

Indeksin muuntamisessa ensimmäinen osattava asia on tunnistaa, mikä muuttuja on indeksi. Siitä ei ole erillistä kysymystä. Sitten on tunnistettava pienin ja suurin indeksin arvo, jolla lauseke lasketaan tms.
lausekepieninsuurin
`AA i; 1 < i <= n: A[i] ne A[1]`
`EE h; a <= h < b: A[h] = x`
`sum_(k=-3)^(i+1) k^2`
while `n > 0` do
    `A[n]` := `A[|__n/2__|]`; `n` := `n-1`
tai

Tarvitsee osata selvittää, montako alkiota käsitel­tävässä välissä on. Siinä auttaa, jos muuttujille valitaan kokeeksi sellaiset arvot, että välissä on täsmälleen yksi alkio.
lausekevastaus
`AA i; 1 < i <= n: A[i] ne A[1]` `n=`
`EE h; a <= h < b: A[h] = x` `b=`
`sum_(k=-3)^(i+1) k^2` `i=`
while `n > 0` do
    `A[n]` := `A[|__n/2__|]`; `n` := `n-1`
`n=`
tai

Nyt sinun pitää kertoa, montako alkiota käsitel­tävässä välissä on. Siihen on periaatteessa helppo yleinen lauseke, jonka tapaamme ihan pian. Käytännössä kuitenkin sen kanssa tulee helposti virheitä ja unohduksia, joiden välttämisessä auttaa, että on miettinyt ensin yksittäis­tapauksia. Siispä nyt pistän sinut miettimään yksittäis­tapauksia! Vastausten saamista kohdalleen auttaa tieto, että vastaustesi tulee tuottaa 1 tilanteissa, jotka selvitit edellä.
lausekealkioita
`AA i; 1 < i <= n: A[i] ne A[1]`
`EE h; a <= h < b: A[h] = x`
`sum_(k=-3)^(i+1) k^2`
while `n > 0` do
    `A[n]` := `A[|__n/2__|]`; `n` := `n-1`
tai

Jos pienin indeksi on `p` ja suurin on `s`, niin indeksi käy läpi yhteensä alkiota.
tai

Minkä alkion `A[i]` valitsee, kun `i` saa pienimmän arvonsa kaavassa `AA i; 1 < i <= n: A[i] ne A[1]`? Se valitsee alkion `A[``]`. Nyt muunna kaava siten, että pienin `i`:n arvo on 1. Suurimman `i`:n arvon saat kohdalleen esimerkiksi huolehtimalla, että `i` käy läpi yhtä monta arvoa kuin edellä huomasit sen käyvän läpi muuntamat­tomassa kaavassa. Huomaa, että sinun on muutettava myös `A[i]` jotenkin. Sen saat kohdalleen esimerkiksi miettimällä, minkälainen lauseke hakasulkujen välissä pitää olla, jotta se valitsisi `i`:n arvolla 1 taulukosta saman alkion kuin alkuperäinen lauseke valitsi `i`:n alku­peräisellä pienim­mällä arvolla.
tai

Tehdäänpä vielä pari melkein samanlaista niin tulee hieman rutiinia. Täytyy siis sanoa sama väite kuin minkä `AA i; 1 < i <= n: A[i] ne A[1]` sanoo, mutta `i` käy läpi eri arvot.


tai

Sitten muunnamme `EE h; a <= h < b: A[h] = x`. Nytkin merkityksen pitää säilyä samana, vaikka indeksi käy läpi eri arvoja.
`EE h; 0 < h <``: A[``] = x`
tai

Toivottavasti osaat muuntaa tämän summa­merkinnän, vaikka summa­merkkien päälle tulevat tekstit eivät ole aivan oikeassa kohdassa eivätkä aivan oikean näköiset.
   `i`+`1`
`sum_(k=-3) k^2 =``sum_(k=1)`
tai

Sitten olisi vielä algoritmin­pätkä `A[n]` := `A[|__n/2__|]`; `n` := `n-1`. Sen merkitys pitää säilyttää ennallaan, vaikka sijoitus­lauseiden järjestys vaihdetaan.
`n` := `n-1`; `A[``]` := `A[``]`
tai

Saatko sievennettyä edellisen kohdan viimeisen vastauksen yksin­kertaisemmaksi?
tai

Otetaan lopuksi toisen­tyyppinen muunnos­tehtävä. Joskus on tarpeen muuntaa esimerkiksi `sum_(i=1)^n sum_(j=1)^i a_(i,j)` muotoon `sum_(j=x)^y sum_(i=z)^w a_(i,j)`. Koska yhteen­lasku on liitännäinen ja vaihdannainen, ongelmana on vain valita `x`, `y`, `z` ja `w` siten, että jälkimmäinen summa­lauseke käy läpi samat `(i,j)`-parit kuin ensimmäinen. Vastauksen löytämistä auttaa, jos piirrät ruudukon, jonka vasemmassa reunassa on `i`:n arvoja ja ala- tai ylä­reunassa on `j`:n arvoja, ja johon on merkitty, mitkä `(i,j)`-parit summa käy läpi.
`x=` `y=` `z=` `w=`
tai