Sm. takzhe:
|
Zadachi komandnoj olimpiady shkol'nikov SPb 1994 goda
Chtoby avtomatizirovat' proverku kachestva programmnogo produkta, byli vyrabotany kriterii, po kotorym opredeljajutsja plohie i horoshie cherty programmy. Nekotorye kriterii kasalis' obschego stilja programmirovanija. V dannoj zadache trebuetsja najti znachenija dlja prostejshih iz jetih kriteriev. Napishite programmu, kotoraja vvodit iz fajla ishodnyh tekst programmy na jazyke Pascal i opredeljaet:
Sledujuschaja informacija pomozhet vam vspomnit' strukturu programmy na jazyke Pascal. Tekst programmy zapisyvaetsja v svobodnom formate. Stroki mogut byt' proizvol'noj dliny. Tekst kommentarija nachinaetsja s simvola { i zakanchivaetsja simvolom }. Strokovaja konstanta nachinaetsja i zakanchivaetsja simvolom apostrofa '. Strokovaja konstanta ne mozhet raspolagat'sja na neskol'kih strokah. Dva apostrofa podrjad '' vnutri strokovoj konstanty oboznachajut odin simvol apostrofa i ne javljajutsja koncom ili nachalom strokovoj konstanty. Odnako pri podschete '' schitajutsja kak dva simvola. Figurnye skobki { i } vnutri strokovoj konstanty ne javljajutsja ogranichiteljami kommentarija, tak zhe, kak i apostrofy vnutri kommentarija ne javljajutsja ogranichiteljami strokovoj konstanty. Fajl ishodnyh dannyh soderzhit pravil'nuju (ne soderzhaschuju sintaksicheskih oshibok) programmu na jazyke Pascal. Fajl ne soderzhit simvolov tabuljacii. Stroki mogut byt' skol' ugodno dlinnymi. Simvoly perevoda stroki pri podschete ne uchityvajutsja. Dlina fajla ishodnyh dannyh ne prevoshodit 64-h Kbajt. Primer fajla ishodnyh dannyh: program TEST; { razdel opisanija peremennyh: } var i: integer; s: string; begin s := 'Pechataem chislo '; {jeto kommentarij} for i := 1 to 5 do writeln (s, i); s := '{jeta stroka ne javljaetsja kommentariem}'; end. {konec programmy TEST} Primer vyvoda programmy Kolichestvo strok v programme = 11 Obschee chislo simvolov v programme = 247 Kolichestvo pustyh strok v programme = 0 Kolichestvo kommentariev v programme = 3 Obschee chislo simvolov v kommentarijah = 73 Kolichestvo operatorov GOTO = 0
Dlja zadannogo N (1<=N<=1994) vychislit' znachenie vyrazhenija
Fajl ishodnyh dannyh soderzhit odno ili neskol'ko chisel, razdelennyh probelami i (ili) simvolami perevoda stroki. Dlja kazhdogo takogo chisla vyvesti v vyhodnoj fajl s novoj stroki znachenie ukazannogo vyrazhenija. Primer fajla ishodnyh dannyh 2 10 Primer vyvoda programmy 3976036 993691419595690831723569386546176
Dlja opredelenija togo, mogut li iteracii cikla vypolnjat'sja parallel'no (na vektornom komp'jutere) ispol'zuetsja analiz zavisimosti dannyh. Vasha zadacha provesti analiz zavisimosti dannyh dlja operatora cikla s operatorom prisvaivanija odnomernomu massivu. Vo vhodnom fajle soderzhitsja nabor ciklov. Kazhdyj cikl soderzhit odin operator prisvaivanija, kotoryj vkljuchaet jelementy odnomernogo massiva A c linejnymi indeksami i schetchik cikla I. Dlja kazhdogo cikla trebuetsja opredelit' kakomu iz sledujuschih uslovij on udovletvorjaet:
Operator prisvaivanija zapisyvaetsja v vide
A [expr] := expr2 gde v kachestve indeksov massiva A mogut byt' sledujuschie vyrazhenija:
n I I-m I+m n*I n*I+m n*I-m Zdes' m i n - celye chisla v diapazone -32768..+32767. Vyrazhenie v pravoj chasti prisvaivanija javljaetsja arifmeticheskim vyrazheniem, zapisannym po pravilam jazyka Pascal. Vyrazhenie ne soderzhit strokovyh konstant i kommentariev. Vse vyrezki iz massiva A udovletvorjajut opisannym vyshe trebovanijam. Operator cikla zadaetsja v vide LOOP mm,nn,pp. Cikl zadaet vypolnenie
operatora prisvaivanija dlja kazhdogo I ot mm do nn s shagom pp. Esli pp ne
zadano, to shag schitaetsja ravnym 1. Granicy i shag cikla javljajutsja celymi
chislami v diapazone Operator mozhet byt' vypolnen parallel'no, esli posle prisvaivanija jelementu massiva A (levaja chast' prisvaivanija), ego znachenie ne ispol'zuetsja v pravoj chasti operatora. Analiz zavisimosti ne vypolnjaetsja, esli cikl rabotaet odin ili dva raza. Ishodnye dannye Fajl ishodnyh dannyh soderzhit odnu ili bolee strok, kazhdaja iz kotoryh soderzhit cikl s operatorom prisvaivanija v vide: LOOP mm,nn,pp: A [expr] := expr2 Dlina stroki fajla ishodnyh dannyh ne prevoshodit 80 simvolov. Vyvod programmy Dlja kazhdogo ishodnogo operatora cikla vyvesti v vyhodnoj fajl 2 stroki: sam operator i rezul'tat analiza zavisimosti dannyh: Ne vypolnitsja ni razu Vypolnitsja odin raz Vypolnitsja dva raza Parallel'noe ispolnenie Trebuet posledovatel'nogo ispolnenija Primer vyhodnogo fajla LOOP 1,32767: A [I] := A [I]+1 Parallel'noe ispolnenie LOOP 1,7: A [-2*I+50] := A [I-1]+A [I+40] Trebuet posledovatel'nogo ispolnenija LOOP 2,800,2: A [I] := -2.03E-17*A [2*I-1]+A [I] Parallel'noe ispolnenie LOOP 7,1,-1: A [I] := A [I+6]*3 Trebuet posledovatel'nogo ispolnenija LOOP 2,-90,30: A [I] := 2 Ne vypolnitsja ni razu LOOP 2,3: A [I] := A [I]*4.0 Vypolnitsja dva raza
Lentochnyj kletochnyj avtomat - jeto abstraktnaja vychislitel'naja mashina, na vhod kotoroj podaetsja skleennaja v kol'co lenta s simvolami. Jeta lenta javljaetsja takzhe edinstvennym zapominajuschim ustrojstvom avtomata. Avtomat rabotaet poshagovo soglasno tablice perehodov. Tablica perehodov opredeljaet mgnovennoe izmenenie soderzhimogo lenty za odin shag avtomata. Jelement tablicy perehodov zadaet novoe znachenie jachejki v zavisimosti ot ee soderzhimogo i soderzhimogo dvuh sosednih jacheek.
Zadano nachal'noe sostojanie lenty, kolichestvo shagov avtomata i tablica perehodov. Trebuetsja promodelirovat' rabotu zadannogo avtomata i opredelit' soderzhimoe lenty cherez zadannoe chislo shagov.
Fajl ishodnyh dannyh soderzhit odin ili neskol'ko naborov ishodnyh dannyh, razdelennyh pustoj strokoj.
V pervoj stroke nabora ishodnyh dannyh soderzhitsja nachal'noe sostojanie lenty (ishodnye dannye avtomata). Dopustimymi simvolami na lente javljajutsja bol'shie i malye latinskie bukvy, cifry i simvol podcherkivanija. Dlina lenty ne prevoshodit 20-ti simvolov i ne men'she 3-h simvolov. Vo vtoroj stroke nabora ishodnyh dannyh soderzhitsja chislo shagov avtomata N. N - celoe chislo ot 0 do 100. V sledujuschih strokah nabora ishodnyh dannyh soderzhitsja opisanie tablicy perehodov. Opisanie sostoit iz pravil, kotorye zapisyvajutsja na otdel'nyh strokah v vide:
Takoe pravilo opredeljaet, chto esli jachejka soderzhit simvol A, sosednjaja jachejka sleva soderzhit simvol i, sosednjaja jachejka sprava soderzhit simvol j, to na sledujuschem shage znacheniem jachejki budet simvol B. U pervoj jachejki sosedom sleva javljaetsja poslednjaja jachejka, a u poslednej jachejki sosedom sprava javljaetsja pervaja. Esli dlja jachejki i ee sosedej net podhodjaschego pravila, to ee soderzhimoe na dannom shage ne izmenjaetsja.
Dlja kazhdogo nabora ishodnyh dannyh vyvesti v vyhodnoj fajl s novoj stroki soderzhimoe lenty avtomata cherez zadannoe chislo shagov.
Primer fajla ishodnyh dannyh 100010011 2 101 -> 1 001 -> 1 010 -> 0 110 ->> 0 ABC 6 ADC -> Q Primer vyvoda programmy 001001110 ABC Primechanie Vse ishodnye dannye korrektny i ih proverka ne trebuetsja. Dlina fajla ishodnyh dannyh ne prevoshodit 64-h Kbajt.
Zadano celoe chislo N (1<=N<=1000000). Trebuetsja najti naimen'shee natural'noe chislo s proizvedeniem cifr N. Ishodnyj fajl soderzhit odno ili neskol'ko chisel, razdelennyh probelami i (ili) simvolami perevoda stroki. Dlja kazhdogo takogo chisla vyvesti v vyhodnoj fajl s novoj stroki iskomoe minimal'noe chislo. Esli takogo chisla ne suschestvuet, vyvesti 0. Primer fajla ishodnyh dannyh 10 13 Primer vyvoda programmy 25 0 |