Teh­tä­vä:
Lu­vun 7.1 oh­jel­mat helppo ja nopea

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

Täs­sä teh­tä­väs­sä tar­kas­tel­laan luen­to­jen lu­vun 7.1 oh­jel­mia helppo ja nopea. Mer­kit­sem­me nii­den muut­tu­jan nn ar­voa sym­bo­lil­la n. Muut­tu­ja n voi saa­da ar­vok­seen nol­lan tai po­si­tii­vi­sen ko­ko­nais­lu­vun.

Kuin­ka mon­ta sel­lais­ta ko­ko­nais­lu­kua i on ole­mas­sa, et­tä 0 ≤ i < n?
ok_text Oi­kein! Täs­tä se al­kaa! f_nodes 1 hide_expr n = tai

Kuin­ka mon­ta pa­ria (i, j), mis­sä 0 ≤ i < n ja 0 ≤ j < n, on kai­ken kaik­kiaan ole­mas­sa? Vih­je Mi­kä on ne­liön ala, jos si­vun pi­tuus on x? En­tä jos si­vun pi­tuus on n?
ok_text Oi­kein! f_nodes 3 hide_expr n^2 = tai

Kuin­ka mo­nes­sa edel­lä mai­ni­tuis­ta pa­reis­ta i = j eli al­ku­koh­ta on sa­ma kuin lop­pu­koh­ta?
ok_text Oi­kein tä­mä­kin! f_nodes 1 hide_expr n = tai

Kuin­ka mo­nes­sa pa­ris­sa al­ku­koh­ta on eri kuin lop­pu­koh­ta? Vih­je Muo­dos­ta vas­taus edel­lis­ten koh­tien vas­taus­ten avul­la.
ok_text Näin on! f_nodes 5 hide_expr n^2 - n = tai

Kuin­ka mo­nes­sa pa­ris­sa al­ku­koh­ta on ai­kai­sem­min kuin lop­pu­koh­ta? Vih­je Sel­lai­sia pa­re­ja on yh­tä pal­jon kuin sel­lai­sia, jois­sa al­ku­koh­ta on myö­hem­min kuin lop­pu­koh­ta. Tie­dät jo, pal­jon­ko näi­tä mo­lem­pia on yh­teen­sä.
ok_text Hy­vin su­juu! f_nodes 13 hide_expr (n^2-n)/2 = tai

Kuin­ka mon­ta pa­ria helppo ko­kei­lee? Vih­je for-sil­mu­kas­sa i ≤ j < n. Sik­si tu­los on sum­ma kah­des­ta ai­kai­sem­min saa­mas­ta­si tu­lok­ses­ta.
ok_text Niin ko­kei­lee! Ei­kös ole ai­ka pal­jon. f_nodes 13 hide_expr (n^2+n)/2 = tai

Luen­to­jen mit­tauk­sis­sa käy­tet­ty tie­to­ko­ne ko­kei­lee noin 215 mil­joo­naa pa­ria se­kun­nis­sa ajaes­saan oh­jel­maa helppo. Mik­si helppo käyt­tää usei­ta se­kun­te­ja, kun n ≥ 30 000? Va­lit­se seu­raa­vis­ta vaih­toeh­dois­ta.

only_no_yes_on hide_expr ok_text Oi­kein ar­va­sit. Tai tie­sit ☺!

	Tie­to­ko­ne hi­das­tuu, kun n on tar­peek­si iso.
	Opet­ta­ja hui­ja­si. Hän ei to­del­li­suu­des­sa teh­nyt mit­tauk­sia vaan kek­si lu­vut omas­ta pääs­tään.
	Sil­loin pa­re­ja on pal­jon enem­män kuin 215 mil­joo­naa.
	Mit­taus­ten ai­ka­na sat­tui säh­kö­kat­ko, jo­ka se­koit­ti tu­lok­set.

tai

Oh­jel­mien helppo ja nopea ajan ku­lu­tus riip­puu muus­ta­kin kuin ko­keil­ta­vien pa­rien mää­räs­tä.

Sil­loin kun ta­voit­tee­na on osoit­taa, et­tä oh­jel­ma on hi­das, ei ole vält­tä­mä­tön­tä tar­kas­tel­la kaik­kea mi­tä se te­kee. Riit­tää, et­tä osoi­te­taan, et­tä oh­jel­ma te­kee ai­na­kin nääääin pal­jon asioi­ta, jo­ten ai­kaa ku­luu ai­na­kin nooooin pal­jon. Sik­si oh­jel­man helppo tar­kas­te­lu edel­lä on pä­te­vä.

Mut­ta kun ta­voit­tee­na on osoit­taa, et­tä oh­jel­ma on no­pea, on tar­kas­tel­ta­va kaik­kea mi­tä se te­kee.

Kat­ta­va tar­kas­te­lu on niin mo­ni­mut­kais­ta, et­tä em­me tee si­tä täl­lä ker­taa. Opet­ta­ja on teh­nyt kat­ta­van tar­kas­te­lun ja lu­paa, et­tä oh­jel­mien helppo ja nopea ta­pauk­ses­sa ko­keil­ta­vien pa­rien mää­rän tar­kas­te­le­mi­nen an­taa oi­kean yleis­kä­si­tyk­sen.

only_no_yes_on hide_expr ok_text Vas­tauk­se­si kel­paa kyl­lä de­mo­ti­lai­suu­des­sa!

	Ym­mär­sin, mi­tä yl­lä sa­not­tiin.
	En ym­mär­tä­nyt mi­tä yl­lä sa­not­tiin.
	Opet­ta­ja hui­jaa taas.

tai

Oh­jel­man nopea en­sim­mäi­nen vai­he et­sii ta­ka­hui­put. Kuin­ka mon­ta pa­ria se ko­kei­lee? Vih­je Se ko­kei­lee i:n ar­vot n − 1, n − 2, …, 1, 0. Jo­kai­sel­la niis­tä se te­kee yh­den kor­keus­ver­tai­lun.
ok_text Ei­kös ole ai­ka vä­hän! f_nodes 1 hide_expr n = tai

ok_text En­sim­mäi­nen oi­kein, tois­ta jän­ni­te­tään … f_nodes 3 hide_expr assume n>0; n-1 = En­sim­mäi­nen vai­he ko­kei­lee yh­den pa­rin tur­haan. Sii­nä i = end_of_answer ok_text Tai­dat ol­la oh­jel­moin­ti­gu­ru! arithmetic f_nodes 3 hide_expr assume n>0; n-1 = ja th = .
tai

Mer­ki­tään ta­ka­huip­pu­jen mää­rää sym­bo­lil­la m. Kuin­ka mon­ta pa­ria nopea:n toi­nen vai­he ko­kei­lee enin­tään, jos m = 1?
ok_text Oli­ko­han tä­mä liian help­po? f_nodes 1 hide_expr n = tai

Kuin­ka mon­ta pa­ria nopea:n toi­nen vai­he ko­kei­lee enin­tään, jos m = 2?
ok_text Muut­tuu hil­jal­leen vai­keam­mak­si … f_nodes 3 hide_expr n+1 = tai

Kuin­ka mon­ta pa­ria nopea:n toi­nen vai­he ko­kei­lee enin­tään, jos m = 5?
ok_text Vie­lä py­syt mu­ka­na! f_nodes 3 hide_expr n+4 = tai

Kuin­ka mon­ta pa­ria nopea:n toi­nen vai­he ko­kei­lee enin­tään? Nyt vas­taus riip­puu se­kä n:stä et­tä m:stä.
ok_text Hy­vin mie­tit­ty! f_nodes 5 hide_expr assume 0 < m <= n; n+m-1 = tai

Ta­ka­huip­pu­jen mää­rää ei vält­tä­mät­tä tie­de­tä etu­kä­teen. Sik­si ha­luam­me ko­keil­ta­vien pa­rien mää­räl­le ylä­li­kiar­von, jo­ka ei rii­pu m:stä. Mil­loin ta­ka­huip­pu­jen mää­rä on suu­rim­mil­laan?

only_no_yes_on hide_expr ok_text Osaa­mi­se­si me­nee­kin ylä­mä­keä!

	Kun reit­ti on ko­ko­nai­suu­des­saan ylä­mä­keä.
	Kun reit­ti on ko­ko­nai­suu­des­saan ala­mä­keä.
	Kun reit­ti on täy­sin ta­sai­nen.
	Kun rei­til­lä jo­ka toi­nen kor­keus­ar­vo on ylem­pä­nä ja jo­ka toi­nen alem­pa­na kuin edel­li­nen.

tai

Kuin­ka mon­ta ta­ka­huip­pua on enin­tään, eli kuin­ka suu­ri m voi enin­tään ol­la? Il­mai­se vas­taus n:n avul­la. Vih­je Kuin­ka mon­ta ta­ka­huip­pua on sil­loin, kun reit­ti on ko­ko­nai­suu­des­saan ala­mä­keä?
ok_text Joo, niin on! f_nodes 1 hide_expr assume 0 < m <= n; n = tai

Kuin­ka mon­ta pa­ria nopea:n toi­nen vai­he ko­kei­lee enin­tään? An­na vas­taus, jo­ka voi riip­pua n:stä mut­ta ei rii­pu m:stä. Vih­je Va­lit­se m:lle se n:n avul­la il­mais­tu ar­vo, jo­ka mak­si­moi ko­keil­ta­vien pa­rien mää­rän. Si­joi­ta se ai­kai­sem­paan lau­sek­kee­seen, jos­sa esiin­ty­vät se­kä n et­tä m.
ok_text Oli­ko vai­keaa? f_nodes 5 hide_expr assume 0 < m <= n; 2n-1 = tai

Kuin­ka mon­ta pa­ria nopea ko­kei­lee enin­tään? An­na vas­taus, jo­ka voi riip­pua n:stä mut­ta ei rii­pu m:stä. Vih­je Tu­los on sum­ma pa­ris­ta ai­kai­sem­mas­ta vas­tauk­ses­ta.
ok_text Olet ihan huip­pu! f_nodes 5 hide_expr assume 0 < m <= n; 3n-1 = tai

Ei ole mi­tat­tu, kuin­ka mon­ta pa­ria nopea ko­kei­lee se­kun­nis­sa. Kos­ka nopea on mo­ni­mut­kai­sem­pi kuin helppo, ole­tam­me täs­sä, et­tä nopea ko­kei­lee vain 100 mil­joo­naa pa­ria se­kun­nis­sa. Mil­lä n:n ar­vol­la nopea käyt­tää ai­kaa ta­san yh­den se­kun­nin? An­na vas­taus li­kiar­vo­na, jos­sa on en­sin kak­si muu­ta nu­me­roa ja sit­ten nol­lia, esim. 99000.
ok_text Hy­vin me­ni li­kiar­vot! f_nodes 1 hide_expr only_no_yes_on 33000000 = tai

Kuin­ka pal­jon helppo käyt­tää ai­kaa, kun kor­keus­ar­vo­ja on edel­li­sen vas­tauk­se­si mu­kai­nen mää­rä? Il­moi­ta vas­taus vuo­ro­kau­si­na pyö­ris­tet­ty­nä kah­teen mer­kit­se­vään nu­me­roon. Vih­je Edel­lä il­moi­tet­tiin, kuin­ka mon­ta pa­ria helppo ko­kei­lee se­kun­nis­sa. Edel­lä olet joh­ta­nut kaa­van, jo­ka ker­too, kuin­ka mon­ta pa­ria tar­vit­see ko­keil­la. Näis­tä saat tar­vit­ta­vien se­kun­tien mää­rän. Vuo­ro­kau­des­sa on 86400 se­kun­tia.
ok_text Lois­ta­vaa! Sait tä­män­kin rat­kais­tua! f_nodes 1 hide_expr only_no_yes_on 29 = tai

Toi­vot­ta­vas­ti mie­lee­si jäi, et­tä ei ole yh­den­te­ke­vää, min­kä­lais­ta al­go­rit­mia oh­jel­ma käyt­tää. Suo­ri­tus­ai­ka voi riip­pua sii­tä val­ta­vas­ti. On pal­jon ki­vem­pi odo­tel­la vas­taus­ta yk­si se­kun­ti kuin mon­ta vuo­ro­kaut­ta.

Toi­vot­ta­vas­ti mie­lee­si jäi myös, mi­ten päät­te­lim­me suo­ri­tu­sa­jas­ta. Päät­te­ly­tai­don har­joit­te­le­mi­sek­si kan­nat­taa näh­dä vai­vaa. Hy­väs­tä päät­te­ly­tai­dos­ta on to­del­la pal­jon hyö­tyä se­kä opin­nois­sa et­tä töis­sä.