Задания
Версия для печати и копирования в MS Word
Тип Д27 C4 № 8003
i

По ка­на­лу связи пе­ре­да­ют­ся по­ло­жи­тель­ные целые числа, не пре­вы­ша­ю­щие 1000,  — ре­зуль­та­ты из­ме­ре­ний, по­лу­чен­ных в ходе экс­пе­ри­мен­та (ко­ли­че­ство из­ме­ре­ний N из­вест­но за­ра­нее, га­ран­ти­ру­ет­ся, что N > 2). После окон­ча­ния экс­пе­ри­мен­та пе­ре­даётся кон­троль­ное зна­че­ние  — наи­мень­шее число R, удо­вле­тво­ря­ю­щее сле­ду­ю­щим усло­ви­ям:

1)  R  — сумма двух раз­лич­ных пе­ре­дан­ных эле­мен­тов по­сле­до­ва­тель­но­сти («раз­лич­ные» озна­ча­ет, что нель­зя про­сто удва­и­вать пе­ре­дан­ные числа, суммы раз­лич­ных, но рав­ных по ве­ли­чи­не эле­мен­тов до­пус­ка­ют­ся);

2)  R  — чётное число.

В ре­зуль­та­те помех при пе­ре­да­че как сами числа, так и кон­троль­ное зна­че­ние могут быть ис­ка­же­ны.

На­пи­ши­те про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер Free Pascal 2.6.4), ко­то­рая будет про­ве­рять пра­виль­ность кон­троль­но­го зна­че­ния. Про­грам­ма долж­на на­пе­ча­тать отчёт по сле­ду­ю­щей форме:

Вы­чис­лен­ное кон­троль­ное зна­че­ние:

…

Кон­троль прой­ден (или Кон­троль не прой­ден)

По­ста­рай­тесь, чтобы про­грам­ма была эф­фек­тив­ной. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, то есть при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

Перед тек­стом про­грам­мы крат­ко опи­ши­те ис­поль­зу­е­мый Вами ал­го­ритм ре­ше­ния.

На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство чисел N (N > 2). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 1000. В по­след­ней стро­ке за­пи­са­но кон­троль­ное зна­че­ние. При­мер вход­ных дан­ных:

6

100

8

35

145

59

84

92

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: Вы­чис­лен­ное кон­троль­ное зна­че­ние: 92.

Спрятать решение

Ре­ше­ние.

Сумма двух чисел чётна, если они имеют оди­на­ко­вую чётность (оба чётные или оба нечётные).

Про­грам­ма, вы­чис­ля­ю­щая кон­троль­ное зна­че­ние, чи­та­ет все вход­ные дан­ные один раз, не за­по­ми­ная их в мас­си­ве. Для про­чи­тан­но­го фраг­мен­та вход­ной по­сле­до­ва­тель­но­сти про­грам­ма хра­нит зна­че­ния двух самых ма­лень­ких чётных и двух самых ма­лень­ких нечётных чисел:

М01  — самое ма­лень­кое чётное число;

М02  — вто­рое по ве­ли­чи­не ма­лень­кое чётное число;

M11  — самое ма­лень­кое нечётное число.

М12  — вто­рое по ве­ли­чи­не ма­лень­кое нечётное число;

После того как все дан­ные про­чи­та­ны, ис­ко­мое кон­троль­ное зна­че­ние вы­чис­ля­ет­ся как мень­шая из сумм M01 + M02 и M11 + M12. По­сколь­ку N > 2, обя­за­тель­но найдётся хотя бы одна пара чисел оди­на­ко­вой чётно­сти и кон­троль­ное зна­че­ние все­гда будет вы­чис­ле­но, но надо от­дель­но об­ра­бо­тать слу­чаи, когда среди дан­ных нет пары чётных или пары нечётных эле­мен­тов. Эту про­вер­ку сле­ду­ет де­лать очень ак­ку­рат­но. На­при­мер, сле­ду­ю­щий очень по­хо­жий на пра­виль­ный фраг­мент на самом деле оши­бо­чен:

if (M12 > 1000) or (M01+M02 < M11+M12) then res:=M01+M02

else res := M11+M12

Этот фраг­мент даст не­вер­ный ре­зуль­тат, на­при­мер, при M01=10, M02=1001, M11=901, M12=915.

Ниже при­ве­де­ны пра­виль­но ре­а­ли­зу­ю­щие опи­сан­ный ал­го­ритм про­грам­мы на языке Пас­каль, а также на ал­го­рит­ми­че­ском языке. До­пус­ка­ют­ся ре­ше­ния, за­пи­сан­ные на дру­гих язы­ках про­грам­ми­ро­ва­ния

 

При­мер пра­виль­ной и эф­фек­тив­ной про­грам­мы на языке Пас­каль

var M01,M02,M11,M12,res,i,N,x, R: longint;

begin

M01 := 1001; M02:= 1001;

M11 := 1001; M12:= 1001;

readln(N);

for i := 1 to N do

begin

readln(x);

if x mod 2 = 0 then begin

if x < M01 then begin

M02:=M01; M01:=x

end

else if x < M02 then M02:=x;

end

else begin

if x < M11 then begin

M12:=M11; M11:=x

end

else if x < M12 then M12:=x;

end

end;

if M02 > 1000 then res:=M11+M12

else if M12 > 1000 then res:=M01+M02

else if M01+M02 < M11+M12 then res := M01+M02

else res := M11+M12

writeln('Вы­чис­лен­ное кон­троль­ное зна­че­ние: ',res);

readln(R);

if R = res

then writeln('Кон­троль прой­ден')

else writeln('Кон­троль не прой­ден');

end.

 

При­мер пра­виль­ной и эф­фек­тив­ной про­грам­мы на ал­го­рит­ми­че­ском языке

алг

нач

цел N | ко­ли­че­ство чисел на входе

цел x | ис­ход­ные дан­ные

цел m01=1001

цел m02=1001

цел m11=1001

цел m12=1001

цел R | вве­ден­ное кон­троль­ное зна­че­ние

цел res | вы­чис­лен­ное кон­троль­ное зна­че­ние

ввод N

нц N раз

ввод x

если mod(x,2) = 0 то

выбор

при x < m01:

m02:=m01; m01:=x

при xm02:=x

все

иначе

выбор

при x < m11:

m12:=m11; m11:=x

при x < m12:

m12:=x

все

кц

выбор

при m02 > 1000: res:=m11+m12

при m12 > 1000: res:=m01+m02

при m01+m02 < m11+m12: res:=m01+m02

иначе res:=m11+m12

все

вывод нс, 'Вы­чис­лен­ное кон­троль­ное зна­че­ние: ',res

ввод R

если R=res

то вывод нс, "Кон­троль прой­ден"

иначе вывод нс, "Кон­троль не прой­ден"

все

кон

Спрятать критерии
Критерии проверки:

Го­во­ря не­фор­маль­но, 4 балла ста­вит­ся за эф­фек­тив­ную и пра­виль­но ра­бо­та­ю­щую про­грам­му, ко­то­рая, воз­мож­но, со­дер­жит до трех син­так­си­че­ских оши­бок (опи­сок). 3 балла ста­вит­ся в слу­чае, когда фак­ти­че­ски за­да­ча ре­ше­на, но

ко­ли­че­ство опи­сок более трех (но не более пяти) и до­пу­ще­но не более одной со­дер­жа­тель­ной ошиб­ки, не поз­во­ля­ю­щей усо­мнить­ся в том, что эк­за­ме­ну­е­мый пра­виль­но при­ду­мал ал­го­ритм (спи­сок до­пу­сти­мых оши­бок при­ве­ден ниже). 2 балла ста­вит­ся, если в до­пол­не­ние к не­точ­но­стям, ко­то­рые пе­ре­чис­ле­ны выше, про­грам­ма ра­бо­та­ет не­эф­фек­тив­но по вре­ме­ни и/или до­пу­ще­но до трех упо­мя­ну­тых выше со­дер­жа­тель­ных оши­бок. Ко­ли­че­ство до­пу­сти­мых опи­сок — до семи. 1 балл ста­вит­ся, если про­грам­ма на­пи­са­на не­вер­но, но из опи­са­ния ал­го­рит­ма и общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи. Далее ска­зан­ное уточ­не­но.

 

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Про­грам­ма пра­виль­но ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Ис­поль­зу­е­мая па­мять не за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел, а время ра­бо­ты про­пор­ци­о­наль­но этому ко­ли­че­ству.

До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы до трех син­так­си­че­ских оши­бок од­но­го из сле­ду­ю­щих видов:

1) про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции;

2) не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния;

3) не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная;

4) при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных.

Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, это счи­та­ет­ся за одну ошиб­ку.

4
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 4 балла. Про­грам­ма в целом ра­бо­та­ет пра­виль­но для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Время ра­бо­ты про­пор­ци­о­наль­но ко­ли­че­ству введённых чисел, пра­виль­но ука­за­но, какие ве­ли­чи­ны долж­ны вы­чис­лять­ся по ходу чте­ния эле­мен­тов по­сле­до­ва­тель­но­сти чисел.

Ко­ли­че­ство син­так­си­че­ских оши­бок (опи­сок) ука­зан­ных выше видов — не более пяти.

Ис­поль­зу­е­мая па­мять, воз­мож­но, за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел (на­при­мер, вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве, кон­тей­не­ре STL в C++ или дру­гой ана­ло­гич­ной струк­ту­ре дан­ных).

До­пус­ка­ет­ся ошиб­ка при вводе дан­ных, не­вер­ный или не­пол­ный вывод ре­зуль­та­тов или не­вер­ная ра­бо­та про­грам­мы в «эк­зо­ти­че­ских» си­ту­а­ци­ях. Кроме того, до­пус­ка­ет­ся на­ли­чие одной ошиб­ки, при­над­ле­жа­щей к од­но­му из сле­ду­ю­щих видов оши­бок:

1) ошиб­ка при ини­ци­а­ли­за­ции мак­си­му­мов;

2) не­вер­но об­ра­ба­ты­ва­ет­ся си­ту­а­ция, когда один или не­сколь­ко мак­си­му­мов не опре­де­ле­ны (все или все, кроме од­но­го, эле­мен­ты ис­ход­ных дан­ных имеют оди­на­ко­вую чётность);

3) до­пу­щен выход за гра­ни­цу мас­си­ва;

4) ис­поль­зу­ет­ся знак < вме­сто <=, or вме­сто and и т. п.

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла. Про­грам­ма ра­бо­та­ет в целом верно, эф­фек­тив­но или нет, но в ре­а­ли­за­ции ал­го­рит­ма есть до трёх со­дер­жа­тель­ных оши­бок, до­пу­сти­мые виды оши­бок пе­ре­чис­ле­ны в кри­те­ри­ях на 3 балла. Ко­ли­че­ство син­так­си­че­ских «опи­сок» не долж­но быть более де­вя­ти.

Про­грам­ма может быть не­эф­фек­тив­на по вре­ме­ни. На­при­мер, все числа за­по­ми­на­ют­ся в мас­си­ве, и пе­ре­би­ра­ют­ся все воз­мож­ные пары эле­мен­тов по­сле­до­ва­тель­но­сти:

min := 1001;

for i := 1 to N - 1 do begin

for j := i + 1 to N do begin

if ((a[i]+a[j]) mod 2 = 0) and

(a[i]+a[j] < min) then min := a[i]+a[j];

end

end;

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Из опи­са­ния ал­го­рит­ма или общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи не­за­ви­си­мо от эф­фек­тив­но­сти. При этом про­грам­ма может от­сут­ство­вать или быть пред­став­лен­ной от­дель­ны­ми фраг­мен­та­ми, без огра­ни­че­ний на ко­ли­че­ство оши­бок.1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл4

Аналоги к заданию № 7684: 7711 7938 8003 Все

Спрятать решение · Прототип задания · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026