Autors: Nezināms
Mans zinātniski pētnieciskais darbs satur deviņus
informātikas uzdevumus un to atrisinājumus. Uzdevumi ir ņemti no sacensībām
“Mīļās Mājas 2000” (“MMMM”). Es izvēlējos uzdevumus un uzrakstīju tiem
atrisinājumus Pascal valodā. Šeit ir iekļauti tikai tie uzdevumi, kuri ieguva
maksimālo punktu skaitu (tātad ir pilnīgi pareizi). Šiem uzdevumiem es
uzrakstīju īsu algoritma aprakstu un nosūtīju vērtēšanai sacensību rīkotājam.
Arī šo uzdevuma algoritmu vērtējumi, kas ietver savī realizācijas iespējas uz
datora un veiktspējas analīzi, ir saņēmuši maksimālo punktu skaitu. Zinātniski
pēnieciskajā darbā atrisinājumos ir iekļauts programmas teksts Pascal valodā
(pielikumā), galvenās idejas, domāšanas virzieni, programmas algoritma būtības
apraksts, tā aptuvens pamatojums, veiktspējas analīze un līdzīgu uzdevumu
varianti.
Apskatīti
dažādu grūtības līmeņu uzdevumi. Tie prasa dažādus programmēšanas paņēmienus
(pilno caurskati, rekursiju, dinamisko programmēšanu utt.). Tos var izmantot
apgūstot informātikas uzdevumu risināšanu vai/un Pascal valodu.
Šādu
tematu izvēlējos, jo varēju to apvienot ar piedalīšanos sacensībās. Daži no
šiem uzdevumiem ir līdzīgi iepriekšējo gadu dažādu starptautisko informātikas
sacensību uzdevumiem. Tādejādi, pētot šos uzdevumus, lasītājs (un arī es), var
sagatavoties citām sacensībām.
Darba
apakšdaļas ir atsevišķi uzdevumi. Skaitlis iekavās aiz tiem rāda to numuru
sacensībās “MMMM”. Programmu teksti ir pielikumā (disketē).
1. Uzdevumi un to
atrisinājumi
1.1. Piramīda.
(14.)
Vienāda izmēra, bet dažāda salduma āboli noliktavā
novietoti trīsstūra piramīdas veidā. Jebkurā piramīdas līmenī, izņemot augšējo,
katrs ābols saskaras ar trīs citiem zemāka līmeņa āboliem. Augšējā līmenī -
virsotnē - ir viens ābols, zem tā ir 3 āboli, nākošajā līmenī zemāk - 6 āboli,
tālāk - 10 āboli, u.t.t.
Tārpiņš Šugers nolēmis veikt ceļojumu ābolu piramīdā,
katrā līmenī izēdoties cauri vienam ābolam. Tas sāk savu ceļu piramīdas
virsotnē un veic savu ceļu tā, ka savāc maksimālo salduma punktu skaitu. No
jebkura ābola Šugers var nokļūt uz vienu no trim zemāka līmeņa āboliem, uz
kuriem balstās šis ābols. Katram ābolam sākumā ir zināms šī ābola salduma
punktu skaits.
Uzrakstiet programmu, kas nosaka Šugera savākto salduma
punktu skaitu dotajā ābolu piramīdā.
Ievaddati
Pirmajā rindā - piramīdas līmeņu skaits n,
2<=n<=20.
Faila turpinājums satur katra ābola salduma punktu
skaitu, kas katram ābolam nepārsniedz 20. Starp skaitļiem ir vai nu
tukšumsimbols vai rindas beigu simbols. Skaitļi doti, sākot ar virsotnē esošā
ābola salduma punktiem. Līmeņa skaitļu secība ir sekojoša:
1
2 3
4 5 6
7 8 9 10
. . . .
Nākošā līmeņa āboli balstās attiecīgi: 1. uz 1,2,3; 2. uz
2,4,5; 3. uz 3,5,6; 4. uz 4,7,8; 5. uz 5,8,9; u.t.t.
Izvaddati
Viens skaitlis - Šugera savāktā salduma punktu summa.
Piemērs
Ievads
3
1
2 3 4
10 9 8
7 6 5
Izvads
13
Atrisinājums.
K-tajā
līmenī ir n ābolu vairāk kā k-1-ajā līmenī, tā kā pirmajā līmenī ir 1 ābols,
tad k-tajā līmenī ir k * (k + 1) / 2 āboli. 20-tajā līmenī būs 210 āboli, 20
līmeņu piramīdā būs 20 * 1 + 19 * 2 + .. + 1 * 20 = 1540 āboli. Katram piramīdas
līmenim q (1 līdz n), āboli ir sakārtoti q rindās. Katrai tādai rindai e (1
līdz q) ir e āboli. Katrs tāds ābols w (1 līdz e), balstās uz lielākais trijiem
augstāka (q - 1) līmeņa āboliem.
Sākumā
var rasties doma šo uzdevumu risināt ar rekursiju. To būtu diezgan vienkārši
uzrakstīt. Procedūra vai funkcija tiktu izsaukta aptuveni 3n - 1 reizes, kas pie lielākiem n, piemēram 20,
novestu pie 319 = ap miljardu izsaukumu. Protams tāds algoritms
daudziem testiem neiekļausies laikā. Šīs programmas ātrumu varētu uzlabot,
ieviešot masīvu, kurā katram ābolam būtu parādīts lielākais salduma punktu
skaits zem tā, ja tas jau ir aprēķināts; tad nebūtu lieki funkcijas izsaukumi.
Programma tad strādātu ātrāk. Bet abos šajos algoritmos nepieciešams ielasīt
visu piramīdu. To var izdarīt, piemēram, trīsdimensiju masīvā (20*20*20), kurā
gan būtu daudz neizmantotas vietas.
Šajā
uzdevumā būtu lietderīgi izmantot dinamisko programmēšanu. Katrā brīdī atceras
saldumu punktu maksimālās summas tikai iepriekšējā (q - 1) līmeņa āboliem.
Ielasot no faila kāda ābola salduma punktus, lai iegūtu šim ābolam maksimālo
salduma punktu summu, tiem pieskaita lielāko no salduma punktu summu no
āboliem, uz kuru šis balstās. Tā izdarot ar visiem (q-tā) līmeņa āboliem pāriet
uz nākošo līmeni (q + 1-to), bet q-to līmeni jau uzskata par iepriekšējo. Tā
dara viesiem n piramīdas līmeņiem. Beigās maksimālo salduma punktu summu visai
piramīdai atrod no lielākās apakšējā līmeņa ābolu maksimālās salduma punktu
summas. Šeit atkrīt arī nepieciešamība atmiņā saglabāt visu piramīdu. Jāsaglabā
ir tikai divi līmeņi; to var izdarīt lineārā masīvā. Algoritma sarežģītība
atkarībā no līmeņu skaita n ir O(n2), jo ābolu skaits k-tajā līmenī
ir k * (k + 1) / 2. Sliktākajā gadījumā tiek 1540 reizes meklēts lielākais no 3
skaitļiem.
Šī
uzdevuma versijas varētu būt sameklēt vienu vai visus Šugera ceļus, lai savāktu
maksimālo salduma punktu summu.
1.2. Bāzes (07.)
Doti divu skaitļu pieraksti. Jums jānoskaidro, vai
iespējama šo skaitļu vienādība, ja šo skaitļu pieraksti ir dažādās skaitīšanas
sistēmās, kuru bāze var būt no 2 līdz 36. Skaitļu pierakstam tiek lietoti
simboli 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, ..., Z. Skaitļu vērtība nevienā
skaitīšanas sistēmā nepārsniedz 200000000010.
Ievaddati
Katrā rindā ir divu skaitļu x un y pieraksti.
Izvaddati
Jāizvada rezultāts vienā no formām:
x(a)=y(b), ja skaitļa x pieraksts skaitīšanas sistēmā ar
bāzi a apzīmē skaitli, kas sakrīt ar skaitli y, kura pieraksts ir skaitīšanas
sistēmā ar bāzi b. a un b jābūt minimāli iespējamiem;
x<>y, ja skaitļu vienādība nav iespējama nevienā
skaitīšanas sistēmā no 2 līdz 36.
Piemērs
Ievads Izvads
12 5 12(3)=5(6)
10 A 10(10)=A(11)
123 456 123<>456
10 2 10(2)=2(3)
Atrisinājums.
Skaidrs,
ka katram skaitļu pārim atrisinājumu meklē atsevišķi. Katram konkrētam skaitlim
lielākā bāze var būt līdz 36, bet mazāko atrod pēc lielākā skaitļa cipara.
Piemēram, skaitlim 1001 lielākais cipars ir 1 un mazākā iespējamā bāze ir 2,
bet skaitlim 29B5 lielākais cipars ir B un mazākā bāze ir 13. Algoritma pamatideja
ir pārbaudīt abu skaitļu pierakstu visās tiem iespējamās skaitīšanas sistēmās.
Ielasot ievaddatu failu, noskaidro x un y mazāko iespējamo bāzi. Ja zināma
skaitļa bāze un tā pieraksts, tad var uzzināt pašu skaitli pēc šāda algoritma:
(pēdējais cipars)+(pirmspēdējais cipars)*bāze+(pirmspirmspēdējais cipars)*bāze2+..+(pirmais
cipars)*bāze(ciparu skaits -1). Lai atvieglotu šo rēķināšanu,
skaitli programmā neielasa kā simbolu virkni, bet katru ciparu kā skaitli
(piem. “3” = 3, “A” = 10, “Z” = 35). Katrai iespējamai x bāzei (lai iegūtu
minimālus a un b, pārbaudi sāk no mazākās x bāzes), pārbauda visas iespējamās y
bāzes, salīdzinot skaitļus. Ja tie sakrīt, tad iegūta vienādība pie mazākām
iespējamām bāzēm un to izvada un turpina ar nākošo skaitļu pāri. Ja pēc visu
iespējamo bāžu pārbaudes vienādība nav atrasta, tad izvada x<>y.
Sliktākajā
gadījumā būs (36-1)*(36-1) = 1225 pārbaudes, kas ir ļoti ātri. Algoritma
sarežģītība atkarībā no skaitļu pāru skaita n ir O(n), jo katru pāri atrisina,
var uzskatīt, konstantā laikā.
Šis ir
uzdevums ar pilnu iespējamo atrisinājumu pārbaudi un viegli saprotamu
algoritmu. Grūtākais ir to tehniski realizēt. Uzdevums kļūtu vēl sarežģītāks,
ja nebūtu nosacījums, ka skaitļu vērtība nevienā skaitīšanas sistēmā
nepārsniedz 200000000010,
jo tad skaitli nevarētu ielikt Paskāla LongInt tipā.
1.3. Eiklīda algoritms (08.)
Lai atrastu divu skaitļu lielāko kopīgo dalītāju (LKD),
tiek izmantots Eiklīda algoritms, kura mūsdienu versija ir: kamēr a un b
dalījuma atlikums nav nulle, atrast šo atlikumu, a aizstāt ar b un b ar atrasto
atlikumu, jeb
while
(a mod b<>0) {c:=a mod b; a:=b; b:=c;}
Ja kārtējo a un b dalījuma atlikums ir nulle, b ir LKD
sākumā dotajiem a un b.
Papildināsim algoritmu ar skaitītāju, kas skaita, cik
dalījumu cikli veikti:
sk:=0;
while
(a mod b<>0) {c:=a mod b; a:=b; b:=c; sk:=sk+1;}
Kad atrasts LKD, skaitītājs ir kādā noteiktā gala
stāvoklī sk_max.
Dotajam sk_max atrast mazāko iespējamo skaitļu pāri a un
b.
Ievaddati
Viens skaitlis - sk_max, 0<=sk_max<=50.
Izvaddati
Divi skaitļi a un b, kur a
Piemērs
Ievads
2
Izvads
3 5
Atrisinājums.
Šis ir
interesants uzdevums, jo tam īss un ātrs atrisinājums, bet to nav tik viegli
pamanīt. Varētu meklēt a un b pēc kārtas, bet tā būtu ļoti lēni. Algoritma pamatideja
ir darīt pretējas darbības Eiklīda algoritmam sk_max reizes. Problēmas ir tas,
ka nav zināmi beigu a un b un, ka īsti nav pretēja darbība funkcijai mod. Taču
šīs problēmas var atrisināt, ja vajag mazākos sākuma a un b. Ja sk_max = 0, tad
var izdomāt, ka a = 1 un b = 1. Ja sk_max lielāks par 0, tad beigu mazākie
a = 2 un b = 1 (nākošais mazākais
skaitļu pāris pēc (1,1) ir (2,1)). Sk_max reizes dara:
a pieskaita b,
b piešķir a mīnus vecais b.
Tā tiek panākti, ka a un b ir
mazākie iespējamie.
Algoritma
sarežģītība ir O(sk_max). Sk_max<=50 tas ir ļoti ātrs.
1.4. Formula-9 (20.)
Formula-9 sacensības paredz R
sacīkstes sezonā (1<=R<=5). Visi D piloti piedalās katrā sacīkstē
(2<=D<=8). Vienā sacīkstē punktus gūst tikai piloti, kas ieņēmuši pirmās
T vietas (1<=T<=min(4,D)). Pārējie saņem nulles. Pilots, kas savācis
maksimālo punktu skaitu, iegūst sezonas Grand Prix. Jūsu uzdevums ir, zinot
visu pilotu iegūto punktu summu tabulu, noskaidrot visus iespējamos veidus, kā
šādu galarezultātu var sasniegt. Jebkuru tādu veidu var atspoguļot tabulā, kur
rindas atbilst sacīkstēm, bet ailes pilotiem. Tabulas r-tās rindas d-tais
elements rāda, cik punktus pilots ar numuru d guvis sacensībā ar numuru r. Ailes summa sakrīt ar pilota
iegūto punktu summu sezonā.
Ievaddati
Dotas trīs rindas. Pirmajā ir
trīs veseli skaitļi sekojošā kārtībā: pilotu skaits D, sacīkšu skaits R, pirmajās vietās finišējušo skaits T. Otrajā
rindā ir T pozitīvu veselu skaitļu, kas neviens nepārsniedz 15, virkne. Tie ir
punkti, kas tiek piešķirti pilotiem, kas ieņēmuši no pirmās līdz T-ai vietai.
Trešajā rindā dotas sezonā savākto punktu summas katram no D pilotiem.
Izvaddati
Viens skaitlis, kas rāda, cik
veidos iespējams sasniegt šādu sezonas iznākumu.
Piemērs
Ievads
4 3 3
7 4 1
9 9 14 4
Izvads
6
Lūk, visas iespējamās sezonas
tabulas (kas izvaddatos nav jāparāda):
1 7 0 4 4 1 7 0 4 1 7 0 7 1 0 4 1
4 7 0 1 4 7 0
4 1 7 0 1 7 0 4 4 1 7 0 1 4 7 0 7
1 0 4 1 4 7 0
4 1 7 0 4 1 7 0 1 7 0 4 1 4 7 0 1
4 7 0 7 1 0 4
Atrisinājums.
Summa
no sezonā savāktajām punktu summām katram pilotam būtu jāsakrīt ar R * (pirmo T
vietu ieguvēju punktu summa). Ja tā nav, tad šādu sezonas iznākumu nav
iespējams sasniegt.
Šis
ir klasisks rekursijas uzdevums. Katra sacīkste atšķiras no citām ar pirmo T
vietu ieguvējiem un nākošajām sacīkstēm. Apskata visus iespējamos gadījumus.
Procedūra Modele(viet) izvēlas pakāpeniski katrai sacīkstei viet-ās vietas
ieguvējus. Viens pilots vienā sacīkstē nevar iegūt vairākas vietas, tāpēc
jāsaglabā katrai sacīkstei pirmo T vietu ieguvēji. Pilots var būt viet-ajā
vietā arī tikai tad, ja viņa līdzšinējā savākto punktu summa + viet-ās vietas
ieguvēja punkti nepārsniedz doto sezonas punktu summu. Kad atrasts kārtējais
viet-ās vietas ieguvējs, tad izsauc procedūru Modele(viet + 1). Ja viet kļūst
lielāks par T, tad sāk nākošo sacīksti. Ja arī visas sacīkstes bijušas, tad
iegūts vēl viens variants.
Sliktākajā
gadījumā tiek apskatīti ap MaxR * (MaxD * (MaxD - 1) * .. * (MaxD - MaxT +
1))=5 * (8 * 7 * 6 * 5) = 8400 gadījumi, kas iekļaujas laikā.
Līdzīgā
uzdevumā varētu būt jāatrod un jāizvada visas iespējamās sezonas tabulas.
1.5. Sarkanais un melnais (12.)
Spēles laukuma izmērs ir 100x100
lauciņi. Uz katra lauciņa novietots viens spēles kauliņš, kura viena puse ir
sarkana, otra - melna. Sākumā visi kauliņi ir novietoti ar melno pusi uz augšu.
Viens gājiens šādā spēlē ir visu kauliņu vienā rindā vai ailē apgriešana
otrādi.
Uzrakstiet programmu, kas
noskaidro, ar kādu minimālo gājienu skaitu uz spēles laukuma iespējams iegūt
noteiktu skaitu kauliņu, kuriem uz augšu ir sarkanā puse.
Ievaddati
Katrā rindā ir viens skaitlis,
kas rāda, cik kauliņus ar sarkano pusi uz augšu spēlē ir jāiegūst.
Izvaddati
Katrā rindā ir viens skaitlis,
kas rāda mazāko gājienu skaitu, kas nepieciešams, lai iegūtu attiecīgo kauliņu
skaitu ar sarkano pusi uz augšu. Ja attiecīgo kauliņu skaitu nav iespējams
iegūt, jāizvada vārds 'Nevar'.
Piemērs
Ievads
1990
1970
Izvads
22
Nevar
Atrisinājums.
Nav
grūti izdomāt vienkāršu, rekursīvu algoritmu, kas griež pakāpeniski rindu un
aiļu kauliņus. Tāpat viegli saprast, ka šis algoritms ir ļoti lēns. Nedaudz
padomājot var saprast, ka nav vērts griezt vairāk kā 100 rindas un 100 ailes.
Tas algoritmu paātrina, bet vienalga tas ir ļoti lēns. Tālāk var izdomāt, ka
sarkano kauliņu skaits nav atkarīgs no tieši kura rinda vai aile ir apgriezta,
bet tikai no skaita. Tas atkal paātrina algoritmu, bet nepietiekami. Galvenais
ir saprast, ka laukuma kopējais sarkano kauliņu skaits nav atkarīgs no secības
kādā apgriež kāda rindas vai ailes kauliņus. Tad jau var uzrakstīt ātru
programmu. Apzīmēsim apgriezto aiļu skaitu
ar ver, bet rindu ar hor, tad sarkano kauliņu skaits (s), ko iegūstam
izdarot šīs apgriešanas ir 100 * ver + hor * (100 - ver) - hor * ver.
Vienādojums
ir:
s
= 100 * ver + hor * (100 - 2 * ver); 0<=ver,hor<=100; 0<=s<=10000;
Uzdevuma atrisinājums ir lineāra
vienādojuma ar diviem veseliem nezināmajiem atrisinājums ar vismazākiem
nenegatīviem atrisinājumiem, jo mazākais gājienu skaits ir ver + hor. Tā kā ver
un hor ir ļoti mazs intervāls, vienādojumu var atrisināt dažādi. Es piedāvāju
vienkāršu variantu:
Pakāpeniski ielasa vajadzīgo
skaitu (s) un ar katru s dara:
Ja
s ir nepāra, tad atrisinājuma nav (tas redzams pēc vienādojuma). Visvienkāršāk
tālāk ir pārbaudīt visas iespējamās ver (no 0 līdz 100) un hor (no 0 līdz ver
(nav vērts apskatīt gadījumus, kad hor>ver, jo laukums ir simetrisks))
vērtības, ievietojot tos vienādojumā. Maksimāli būs ap 1 + 2 + 3 + .. + 101 =
5151 pārbaudes, kas iekļaujas laikā. Var izmantot arī efektīvāku un daudz
sarežģītāku vienādojuma atrisināšanas algoritmu, bet tik maziem skaitļiem tas
daudz neatmaksājas.
Uzdevuma
varianti varētu būt ar lielāku laukumu, piemēram 10000*10000. Laukums varētu
arī nebūt kvadrāts, piemēram 1000*100. Tas varētu būt arī kubs, kurā rindām un
ailēm pievienotos kolonas.
1.6. Atkal nulles (06.)
Dotajam naturālajam skaitlim n
rindā viens pēc otra tiek izrakstīti visi naturālie skaitļi no 1 līdz n.
Skaitļa n ciparu skaits nepārsniedz 1000. Cik nulles tiek izmantotas šo n
ciparu pierakstīšanai?
Ievaddati
Skaitlis n.
Izvaddati
Nuļļu skaits.
Piemērs
Ievads
123456
Izvads
58985
Ievads
222222222
Izvads
175308642
Atrisinājums.
Acīmredzams
risinājums ir izveidot katru skaitli no 1 līdz n un meklēt tajos nulles. Tā kā
n var būt ļoti liels, tad tas ir ļoti lēni. Jāpadomā kādas sakarības par,
piemēram, skaitļu intervālu no 1 līdz 10, 10 līdz 100 vai 100 līdz 1000.
Problēmas rada tas, ka n nav tikai 10 pakāpe. Tā kā n var būt liels, tad nuļļu
skaits neiekļaujas Pascal skaitļa tipos un jāveido garo skaitļu aritmētika.
Skaitli var saglabāt, piemēram, masīvā, katru tā ciparu kā masīva elementu.
Kopējo nuļļu skaitu varam atrast, ja saskaitām nuļļu skaitu, kas ir pēdējā
ciparā (visiem skaitļiem), priekšpēdējā utt. līdz pirmajam (pieņemam, ka visi
skaitļi pierakstīti ar tikpat cipariem, cik n, un skaitlis nesākas ar 0). K-tā
cipara nuļļu skaits ir skaitlis, ko veido skaitļa n cipari no pirmā līdz k
(neieskaitot) + (ja skaitļa n k-tais cipars nav 0; skaitlis, ko veido skaitļa n
cipari no k + 1-tā līdz pēdējam - skaitlis, ko veido (n ciparu skaits - k)
‘9’-nieki).
Algoritma
sarežģītība atkarībā no n ciparu skaita ir kvadrātiska, garo skaitļu dēļ.
1.7. Pirmais cipars (03.)
Dotajam pozitīvajam skaitlim n,
0<=n<=65535, atrast skaitļa n!=1*2*3*...*n pirmo ciparu.
Ievaddati
Viens skaitlis n.
Izvaddati
Viens cipars.
Piemērs
Ievads
4
Izvads
2
Atrisinājums.
n!
nav iespējams vajadzīgajā laikā aprēķināt, jo tas ir ļoti liels skaitlis.
Aptuvenā novērtējumā skaitlim 65535! varētu būt ap miljons ciparu (jebkurā
gadījumā to nebūtu iespējams saglabāt normāla datora dosatmiņā). Pēc šāda
algoritma atrisinājumu varētu atrast tikai nelieliem n. Bet vajadzīgs ir tikai
faktoriāla pirmais cipars. Pieņemsim, ka zinam 8!=40320. Ja vajadzīgs 9!
pirmais cipars, to var atrast pēc 40320*9=362880 pirmā cipara. bet redzams, ka
nevajag visu skaitli 40320, varam ņemt, piemēram, tikai 403 (403*9=3627), no tā
pirmais cipars nemainās. Var pat ņemt tikai 4 (4*9=36). Vispārīgā gadījumā,
reizinot divus lielus skaitļus, to reizinājuma pirmie cipari galvenokārt ir
atkarīgi no reizinātāju pirmajiem cipariem. Tāpēc skaitlim n! pietiek uzglabāt
tikai pirmos ciparus.
To
ērti izdarīt reāla skaitļa tipā, piemēram paskālā tāds ir extended. Reizina
skaitļus no 1 līdz n, bet pēc katras reizināšanas reizinājumam pārceļ komatu
tūlīt aiz pirmā cipara. Tas nodrošina to, ka reizinājums nepārsniegs savu
maksimālo vērtību (kamēr n
Algoritma
sarežģītība ir tieši proporcionāla n, tas ir lineārs algoritms.
Tā
kā šāds algoritms ir ļoti ātrs, tad, iespējams, maksimālo n, pie kura šis algoritms
dod pareizu rezultātu, nosaka nevis programmas izpildes laiks, bet precizitāte
(pie n>>65535 kaut kad vajadzētu rasties kļūdai pirmajā ciparā). Varētu
padomāt, kad tas notiks.
1.8. Paralēlā mašīna (15.)
Paralēlā mašīna (PM) ir
skaitļotājs, kas satur vairākus procesorus. Katrs procesors var veikt darbu,
kas nav atkarīgs no citiem procesoriem.
Pieņemsim, ka ir N darbi D1, D2,
..., Dn, kas jāveic PM ar P procesoriem. Katrs darbs var tikt veikts ar jebkuru
procesoru. Visu procesoru veiktspēja ir vienāda. Ja visi procesori ir aizņemti,
darbs gaida rindā, līdz kamēr kāds procesors atbrīvojas.
Jums jāizveido programma, kas
palīdz samazināt gaidīšanas laiku. Gaidīšanas laiks kādam darbam ir laiks, kas
jāgaida šim darbam, līdz kamēr atbrīvojas kāds procesors, kurš sāk veikt šo
darbu. Vidējais gaidīšanas laiks ir visu darbu gaidīšanas laiku summa, kas
izdalīta ar darbu skaitu.
Visi darbi tiek nodoti uz
izpildīšanu vienlaicīgi.
Ievaddati
Faila pirmajā rindā ir divi
veseli skaitļi: procesoru skaits P(1<=P<=500) un darbu skaits N
(1<=N<=1000). Nākošajās N rindās doti skaitļi, kas rāda katra darba
izpildei nepieciešamo laiku.
Izvaddati
Jāizvada mazākais iespējamais
vidējais gaidīšanas laiks, noapaļojot līdz 3 zīmēm aiz komata.
Piemērs
Ievads
2 6
4
1
1
2
2
3
Izvads
1.333
Atrisinājums.
Algoritms,
kurā katru darbu mēģina darīt katrs brīvais procesors, ir, protams, par lēnu.
Lai iegūtu mazāko gaidīšanas laiku, sākumā vajag izdarīt darbus ar īsākajiem
izpildīšanas laikiem. Tāpēc darbus vajag sakārtot izpildes laika pieaugšanas
secībā. To var izdarīt ar, piemēram, burbuļa algoritmu (sarežģītība O(N2),
kas pie N<=1000 ir pietiekami ātrs. Kamēr nav izdarīti visi darbi, brīvajiem
procesoriem iedala vēl nepadarītos darbus. Tālāk var laiku palielināt par 1 un
skatīties, kas ir noticis (ja kāds procesors ir savu darbu izdarījis, tam
piešķir jaunu darbu, ja tāds ir). Katru brīdi arī skatās, kuri darbi vēl gaida.
Šī algoritma ātrums pat nav nosakām, jo nav zināmas robežas darbu izpildes
laikam. Ja kādu (vai vairākus) darbu(s) ir jādara ilgi, tas ļoti ietekmē
algoritma ātrumu. Tāpēc vajag izdomāt algoritmu, kura ātrums nav atkarīgs no
darbu izpildes laika. Tāds ir šis:
Kamēr
nav izdarīti visi darbi, gaidīšanas laikam pieskaita (darbu skaits, ko nedara *
pašlaik veicamā īsākā darba laiks) un visiem darbiem, kas tika darīti, atņem
īsākā darba laiku, bet tos pašus (īsākos darbus) uzskata par padarītiem un, ja
vajag, atbrīvojušiem procesoriem liek darīt nākošos darbus. Lai iegūtu vidējo
gaidīšanas laiku, iegūto gaidīšanas laiku dala ar darbu skaitu.
Algoritma
ātrums ir atkarīgs tikai no N.
Principā
līdzīgs uzdevums ir bijis Vispasaules 8. informātikas olimpiādē (Veszprem,
Ungārija, 1996.). Pēc analoģijas ar to, šajā uzdevumā varētu būt divas PM,
kuras darītu katru darbu (vispirms viena, tad otra), un būtu jāatrod mazākais
gaidīšanas laiks.
1.9. Nulles (05.)
Cik nulles noslēdz skaitļa
p!=1*2*3*...*p pierakstu, kur p=(5^n-1) div 4.
Izvaddati
Katrā rindā viens skaitlis, kas
rāda skaitļa pierakstu noslēdzošo nuļļu skaitu katram n: 1<=n<=14.
Atrisinājums.
Līdzīgi
kā uzdevumā 03, arī šeit nav vērts rēķināt p!. 5^14=6103515625, p! būtu kas
neaptverams. Ir jāpadomā, kas nosaka skaitļa noslēdzošo nuļļu skaitu. Tik, cik
skaitlim ir beigās nulles, tieši tik reizes tajā ir reizinātājs “10”. Bet
sadalot “10” pirmreizinātājos, tas ir 2*5. Faktoriālu sadalot pirmreizinātājos,
ord2 (2-nieka pakāpe) būs protams lielāka (pietiek jau ar to, ka nav
mazāka) par ord5. Tāpēc reizinātāja “10” skaitu (līdz ar to arī
beigu nuļļu skaitu) noteiks ord5. Šeit viegli izmantot dinamisko
programmēšanu, skatoties kā mainās noslēdzošo nuļļu skaits palielinot n ar 1
(tas tāpēc, ka jau funkcijā ir ietverta 5-nieka pakāpe ). Pie n=0 nuļļu skaits
(apzīmēsim ar t) it 0 (((5^0-1)div 4)!=1). Mainīgajā p glabāsim 5^n. Sākumā p=1
(5^0=1). Pie katras vajadzīgās n vērtības p pareizina ar 5 un palielina t par
(p-1)div 20. To izvada.
Algoritma
sarežģītība ir O(n).
Izmantoto uzziņas avotu saraksts
Latvijas
informātikas olimpiādes - "http://vip.latnet.lv/lio/".
Starptautisko
informātikas olimpiāžu mājas lapa - "http://olympiads.win.tue.nl/ioi/index.html".
Andžāns A., Auziņš
A., Ikaunieks Ē., Kalējs A., Opmane I., Opmanis M. Latvijas informātikas
olimpiāžu uzdevumi un to atrisinājumi. -Rīga: LU Skaitļošanas centrs, 1989.
Andžāns A., Kalējs
A., Opmanis M. Latvijas informātikas olimpiāžu uzdevumi. -Rīga, 1996.
Annotation
My
research work contains of nine problems in informatics and their solutions.
Problems are taken from competition "Mīļās Mājas 2000"
("MMMM"). I chose some problems and wrote them solution in Pascal.
These are solutions with utmost results in tests. There are text of program (in
addenda (floppy disc)), main ideas, ways of thinking, substantiation of the
algorithm, analyses of speed and some similar problems in solution in the
research work.
There
are tasks in the different levels of difficulty. They require different access
to solve them (for example, dynamic programming, recursion, breadh-first search
etc.). Solutions can by used to learn programming of tasks or/and Pascal. You
can used these examples to prepare for other competitions.
Nav komentāru:
Ierakstīt komentāru