menu
person

Задача №2909

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

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

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

 

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

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

Ниже при­во­дит­ся при­мер такой про­грам­мы

 

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

 

 

program N_27;

const d = 10;

var

N: integer;

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

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

x: integer;

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

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

m: integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

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*x + mx*mx > m then m := x*x + mx*mx;

        a[i mod d] := x

    end;

    writeln(m)

end.

 

 

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

 

 

const d = 10;

var

N: integer;

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

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

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

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

m:integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

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]*a[i]+mn*mn > m then m := a[i]*a[i]+mn*mn

    end;

    writeln(m)

end.

 

 

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

 

 

Const d = 10;

var

N: integer;

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

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

m: integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

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[i]+a[j]*a[j]>m then

                m := a[i]*a[i]+a[j]*a[j];

        end;

    end;

    writeln(m)

end.

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