menu
person

Задача №2911

Для за­дан­ной по­сле­до­ва­тель­но­сти не­от­ри­ца­тель­ных целых чис

Поиск задачи:

Для за­дан­ной по­сле­до­ва­тель­но­сти не­от­ри­ца­тель­ных целых чисел не­об­хо­ди­мо найти мак­си­маль­ное про­из­ве­де­ние двух её эле­мен­тов, но­ме­ра ко­то­рых раз­ли­ча­ют­ся не менее чем на 8. Зна­че­ние каж­до­го эле­мен­та по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 1000. Ко­ли­че­ство эле­мен­тов по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 10000.

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

 

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

 

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

 

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

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

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти — 4 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, — 3 балла.

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

 

Вход­ные дан­ные пред­став­ле­ны сле­ду­ю­щим об­ра­зом. В пер­вой стро­ке задаётся число N — общее ко­ли­че­ство эле­мен­тов по­сле­до­ва­тель­но­сти. Га­ран­ти­ру­ет­ся, что N > 8. В каж­дой из сле­ду­ю­щих N строк задаётся одно не­от­ри­ца­тель­ное целое число – оче­ред­ной эле­мент по­сле­до­ва­тель­но­сти.

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

10

100

45

55

245

35

25

10

10

10

26

Про­грам­ма долж­на вы­ве­сти одно число — опи­сан­ное в усло­вии про­из­ве­де­ние. При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных: 2600.

 

По­яс­не­ние.

За­да­ние Б (ре­ше­ние для за­да­ния А при­ве­де­но ниже, см. про­грам­му 3). Для каж­до­го эле­мен­та с но­ме­ром k (ну­ме­ра­цию на­чи­на­ем с 1), на­чи­ная с k = 9, рас­смот­рим все до­пу­сти­мые по усло­ви­ям за­да­чи пары, в ко­то­рых дан­ный эле­мент яв­ля­ет­ся вто­рым.

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

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

 

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

program N_27;

const d = 8;

var

N: integer;

a: array[0..d-1] of integer; {буфер}

{k-е вве­ден­ное число за­пи­сы­ва­ем в ячей­ку a[k mod d]}

x: integer;

mx: integer; {мак­си­маль­ное вве­ден­ное число}

{(не счи­тая 8 по­след­них)}

m: longinteger; { мак­си­маль­ное зна­че­ние про­из­ве­де­ния}

i: integer;

begin

readln(N);

{Ввод пер­вых d чисел}

for i:=1 to d do

begin

readln(x);

a[i mod d] := x

end;

{ Ввод осталь­ных эле­мен­тов, поиск мак­си­маль­но­го

про­из­ве­де­ния}

mx := 0; m := 0;

for i := d + 1 to N do

begin

readln(x);

if a[i mod d] > mx then mx := a[i mod d];

if x * mx > m then m := x * mx;

a[i mod d] := x

end;

writeln(m)

end.

 

 

Ра­бо­та с бу­фер­ным мас­си­вом может быть ор­га­ни­зо­ва­на и без ис­поль­зо­ва­ния опе­ра­ции mod, на­при­мер, цик­ли­че­ским пе­ре­за­пи­сы­ва­ни­ем эле­мен­тов со сдви­гом. Этот спо­соб также яв­ля­ет­ся эф­фек­тив­ным. Если вме­сто не­боль­шо­го мас­си­ва фик­си­ро­ван­но­го раз­ме­ра (цик­ли­че­ско­го или со сдви­га­ми) хра­нят­ся все ис­ход­ные дан­ные (или все те­ку­щие мак­си­му­мы), про­грам­ма со­хра­ня­ет эф­фек­тив­ность по вре­ме­ни, но ста­но­вит­ся не­эф­фек­тив­ной по па­мя­ти, так как тре­бу­е­мая па­мять растёт про­пор­ци­о­наль­но N. Ниже при­во­дит­ся при­мер такой про­грам­мы на языке Пас­каль. По­доб­ная (и ана­ло­гич­ные по сути) про­грам­мы оце­ни­ва­ют­ся не выше 3 бал­лов.

 

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

const d = 8;

var

N: integer;

a: array[1..10000] of integer; {хра­не­ние всех

эле­мен­тов по­сле­до­ва­тель­но­сти}

mn:integer; {мак­си­маль­ное вве­ден­ное число}

{не счи­тая d по­след­них}

m:longinteger; {мак­си­маль­ное зна­че­ние про­из­ве­де­ния}

i: integer;

begin

readln(N);{Ввод всех эле­мен­тов по­сле­до­ва­тель­но­сти}

for i:=1 to N do readln(a[i]);

mn := 0;

m := 0;

for i := d + 1 to N do

begin

if a[i-d] > mn then mn := a[i-d];

if a[i] * mn > m then m := a[i] * mn

end;

writeln(m)

end.

 

 

Воз­мож­но также пе­ре­бор­ное ре­ше­ние, в ко­то­ром на­хо­дят­ся про­из­ве­де­ния всех до­пу­сти­мых пар и из них вы­би­ра­ет­ся мак­си­маль­ное. Ниже при­ведён при­мер по­доб­но­го ре­ше­ния. Это (и ана­ло­гич­ные ему) ре­ше­ние не эф­фек­тив­но ни по вре­ме­ни, ни по па­мя­ти. Оно яв­ля­ет­ся ре­ше­ни­ем за­да­чи А, но не яв­ля­ет­ся ре­ше­ни­ем за­да­ния Б. Оцен­ка за такое ре­ше­ние – 2 балла. Про­грам­ма 3. При­мер пра­виль­ной про­грам­мы на языке Пас­каль, не эф­фек­тив­ной ни по вре­ме­ни, ни по па­мя­ти:

 

Const d = 8;

var

N: integer;

a: array[1..10000] of integer;

{хра­не­ние всех эле­мен­тов}

m: longinteger; {мак­си­маль­ное зна­че­ние про­из­ве­де­ния}

i, j: integer;

begin

readln(N);

{Ввод зна­че­ний эле­мен­тов}

for i:=1 to N do readln(a[i]);

m := 0;

for i := 1 to N-d do begin

for j := i+d to N do begin

if a[i] * a[j] > m then m := a[i] * a[j];

end;

end;

writeln(m)

end.

Категория: по информатике | Добавил: Просмотров: 1 | Теги: Об­ра­бот­ка символьных строк | Рейтинг: 0.0/0
Всего комментариев: 0