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

По ка­на­лу связи пе­ре­да­ет­ся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел X_1, X_2, … все числа не пре­вы­ша­ют 1000, их ко­ли­че­ство за­ра­нее не­из­вест­но. Каж­дое число пе­ре­да­ет­ся в виде от­дель­ной стро­ки, со­дер­жа­щей де­ся­тич­ную за­пись числа. При­зна­ком конца пе­ре­да­ва­е­мой по­сле­до­ва­тель­но­сти яв­ля­ет­ся число 0. Уча­сток по­сле­до­ва­тель­но­сти от эле­мен­та XT до эле­мен­та X_T плюс N на­зы­ва­ет­ся подъ­емом, если на этом участ­ке каж­дое сле­ду­ю­щее число боль­ше преды­ду­ще­го. Вы­со­той подъ­ема на­зы­ва­ет­ся раз­ность X_T плюс N минус X_T. На­пи­ши­те эф­фек­тив­ную про­грам­му, ко­то­рая вы­чис­ля­ет наи­боль­шую вы­со­ту среди всех подъ­емов по­сле­до­ва­тель­но­сти. Если в по­сле­до­ва­тель­но­сти нет ни од­но­го подъ­ема, про­грам­ма вы­да­ет 0. Про­грам­ма долж­на на­пе­ча­тать отчет по сле­ду­ю­щей форме:

По­лу­че­но ... чисел Наи­боль­шая вы­со­та подъ­ема: …

 

Вам пред­ла­га­ют­ся два за­да­ния, свя­зан­ные с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния А и Б или одно из них по сво­е­му вы­бо­ру.

Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние со­став­ля­ет 0 бал­лов.

За­да­ние Б яв­ля­ет­ся услож­нен­ным ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме. Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния.

 

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

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А.

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

 

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

При­мер вход­ных дан­ных:

144

17

27

3

7

9

11

10

0

При­мер вы­ход­ных дан­ных для при­ве­ден­но­го выше при­ме­ра вход­ных дан­ных:

По­лу­че­но 8 чисел

Наи­боль­шая вы­со­та подъ­ема: 10

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

Ре­ше­ние.

Про­грам­ма чи­та­ет все вход­ные дан­ные один раз, не за­по­ми­ная все вход­ные дан­ные в мас­си­ве. Во время чте­ния про­грам­ма пом­нит число LMax  — вы­со­ту са­мо­го вы­со­ко­го из уже за­кон­чив­ших­ся подъ­емов, а также не­об­хо­ди­мые све­де­ния о те­ку­щем подъ­еме, на­при­мер, число L  — вы­со­ту те­ку­ще­го подъ­ема (то есть раз­ность между по­след­ним и пер­вым чис­лом участ­ка) и по­след­нее про­чи­тан­ное число T (это число  — наи­боль­шее из чисел те­ку­ще­го подъ­ема). Про­чи­тав оче­ред­ное число R, про­грам­ма срав­ни­ва­ет его с чис­лом T. Если R > T, то зна­че­ние L уве­ли­чи­ва­ет­ся на R-T. В про­тив­ном слу­чае фик­си­ру­ет­ся конец подъ­ема и на­ча­ло но­во­го участ­ка. То есть, во-пер­вых, зна­че­ние L срав­ни­ва­ет­ся с LMax и, при не­об­хо­ди­мо­сти, LMax по­ла­га­ет­ся рав­ным L. Во-вто­рых, по­ла­га­ем L = 0.

 

При­мер пра­виль­ной и эф­фек­тив­ной

про­грам­мы на языке Пас­каль:

При­мер пра­виль­ной и эф­фек­тив­ной

про­грам­мы на языке Бей­сик:

program c4_1;

 

var

R, T, N, L, LMax : Integer;

begin

N:=0;

L:=0;

LMax:=0;

T:=1001;

repeat

ReadLn(R);

if R<>0 then N:=N+1;

if R>T then L:=L+R-T

else begin

if L>LMax then LMax:=L;

L:=0;

end;

T:=R;

until R=0;

WriteLn('По­лу­че­но ', N, ' чисел');

WriteLn('Наи­боль­шая вы­со­та подъ­ема ', LMax);

end.

DIM R, T, N, L, LMax AS INTEGER

N = 0

L = 0

LMax = 0

T = 1001;

DO

INPUT R

IF R <> 0 THEN N = N + 1

IF R > T THEN

L = L + R-T

ELSE

IF L > LMax THEN LMax = L

L = 0

END IF

T = R

LOOP UNTIL R = 0

PRINT "По­лу­че­но "; N; " чисел"

PRINT "Наи­боль­шая вы­со­та подъ­ема "; Lmax

При­мер пра­виль­ной и эф­фек­тив­ной

про­грам­мы на языке Ал­го­рит­ми­че­ском языке:

алг C4_1

нач

цел R, T, N, L, LMax

N:=0

L:=0

LMax:=0

T:=1001;

нц

ввод R

если R<>0 то N:=N+1 все

если R>T то

L:=L+R-T

иначе

если L>LMax то LMax:=L все

L:=0

все T:=R

кц при R=0

вывод "По­лу­че­но ", N, " чисел", нс

вывод "Наи­боль­шая вы­со­та подъ­ема ", LMax, нс

кон

 

 

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

По­яс­не­ния для про­ве­ря­ю­щих.

1. За­да­ние Б яв­ля­ет­ся услож­не­ни­ем за­да­ния А. Если в ка­че­стве ре­ше­ния за­да­ния Б пред­став­ле­но ре­ше­ние за­да­ния А, то со­глас­но при­ведённым ниже кри­те­ри­ям, его оцен­ка будет такой же, как если бы это ре­ше­ние было пред­став­ле­но в ка­че­стве ре­ше­ния за­да­ния А.

2. Два за­да­ния и, со­от­вет­ствен­но, воз­мож­ность для эк­за­ме­ну­е­мо­го пред­ста­вить две про­грам­мы дают уче­ни­ку воз­мож­ность (при его же­ла­нии) сна­ча­ла на­пи­сать менее слож­ное и менее эф­фек­тив­ное ре­ше­ние (за­да­ние А), ко­то­рое даёт ему право по­лу­чить два балла, а затем при­сту­пить к по­ис­ку более эф­фек­тив­но­го ре­ше­ния.

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

 

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

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

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

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

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

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

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

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

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

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

До­пус­ка­ет­ся ошиб­ка при вводе дан­ных, не­вер­ный или не­пол­ный вывод ре­зуль­та­тов или не­вер­ная ра­бо­та про­грам­мы

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

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

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

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

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

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

min := 2001;

for i := 1 to N - 1 do begin

for j := i + 1 to N do begin

if ((a[i]+a[j]) mod 2 = 1) 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
Спрятать решение · КритерииСпрятать критерии · Помощь


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