СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 27 № 13611

Назовём дли­ной числа ко­ли­че­ство цифр в его де­ся­тич­ной за­пи­си. На­при­мер, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых по­ло­жи­тель­ных чисел, каж­дое из ко­то­рых мень­ше 108. Не­об­хо­ди­мо опре­де­лить, числа какой длины чаще всего встре­ча­ют­ся в дан­ном на­бо­ре и сколь­ко в нём чисел этой длины. Если числа раз­ной длины встре­ча­ют­ся оди­на­ко­во часто (и чаще чем числа любой дру­гой длины), нужно вы­брать боль­шую длину. На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

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

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

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

Вы мо­же­те сдать одну или две про­грам­мы ре­ше­ния за­да­чи. Если Вы сда­ди­те две про­грам­мы, каж­дая из них будет оце­ни­вать­ся не­за­ви­си­мо от дру­гой, ито­го­вой ста­нет бо́льшая из двух оце­нок. Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния. Ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию.

Опи­са­ние вход­ных и вы­ход­ных дан­ных

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

5

15

417

125

32

4801

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

3 2

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

Ре­ше­ние.

При за­дан­ных огра­ни­че­ни­ях числа в на­бо­ре могут иметь длину от 1 до 8. Не­об­хо­ди­мо со­здать мас­сив из 8 эле­мен­тов с ин­дек­са­ми от 1 до 8 и ис­поль­зо­вать его для подсчёта ко­ли­че­ства чисел со­от­вет­ству­ю­щей длины. Ис­поль­зо­ва­ние мас­си­ва не де­ла­ет про­грам­му не­эф­фек­тив­ной по па­мя­ти, так как раз­мер мас­си­ва не за­ви­сит от N. Затем нужно найти зна­че­ние мак­си­маль­но­го эле­мен­та этого мас­си­ва и вы­ве­сти мак­си­маль­ный из ин­дек­сов эле­мен­тов, рав­ных этому мак­си­му­му и сам мак­си­мум. Ниже при­ве­де­на ре­а­ли­зу­ю­щая опи­сан­ный выше ал­го­ритм про­грам­ма на языке Пас­каль (ис­поль­зо­ва­на вер­сия PascalABC).

 

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

var

N: integer; {ко­ли­че­ство чисел}

a: longint; {оче­ред­ное число}

d: array[1..8] of integer; {под­счет}

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

imx: integer; {самая частая длина}

i,k: integer;

begin

for i:=1 to 8 do d[i]:=0;

readln(N);

for i:=1 to N do begin

readln(a);

k:=0;

while a>0 do begin

k := k+1;

a := a div 10;

end;

d[k] := d[k]+1;

end;

mx := 0;

for i:=1 to 8 do begin

if d[i] >= mx then begin

mx := d[i];

imx := i;

end;

end;

writeln(imx, ' ', mx)

end.

 

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

var

    N: integer; {ко­ли­че­ство чисел}

    val: integer; {самая частая длина}

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

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

    i, j, k, lenght: integer;

begin

    readln(N);

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

    for i:=1 to N do begin

        k:=0;

        while a[i]>0 do begin

            k:=k+1;

            a[i] := a[i] div 10;

        end;

        a[i]:=k;

    end;

    for i:=1 to N-1 do

        for j:=1 to N-i do

            if a[j] < a[j+1] then begin

                k := a[j];

                a[j] := a[j+1];

                a[j+1] :=             end;

    max_lenght := 0;

    lenght := 1;

    val := a[1];

    for i := 1 to N do

        if a[i]=a[i+1] then

            lenght := lenght + 1

        else if lenght>max_lenght then begin

            max_lenght := lenght;

            val := a[i];

            lenght := 1;

        end;

    writeln(val, ' ', max_lenght);

    end.

 

Вме­сто опре­де­ле­ния ко­ли­че­ства цифр с по­мо­щью по­сле­до­ва­тель­но­го де­ле­ния на 10 можно ис­поль­зо­вать выбор по диа­па­зо­ну до­пу­сти­мых зна­че­ний. На­при­мер, в при­ведённой выше про­грам­ме можно вме­сто при­сва­и­ва­ния k:=0 и сле­ду­ю­ще­го за ним цикла while ис­поль­зо­вать такую по­сле­до­ва­тель­ность дей­ствий:

if a<10 then k:=1

else if a<100 then k:=2

else if a<1000 then k:=3

else if a<10000 then k:=4

else if a<100000 then k:=5

else if a<1000000 then k:=6

else if a<10000000 then k:=7

else k:=8;

Можно также пре­об­ра­зо­вы­вать число в стро­ку или сразу чи­тать его как стро­ку и опре­де­лять длину числа как длину со­от­вет­ству­ю­щей стро­ки. Ниже при­ве­де­на такая про­грам­ма на языке Java (ис­поль­зо­ва­на вер­сия JDK 1.8.0_66)

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

import java.util.Scanner;

public class Problem27a {

public static void main(String args[]){

Scanner scan = new Scanner(System.in);

import java.util.Scanner;

import java.lang.String;

public class problem27a {

public static void main(String args[]){

Scanner scan = new Scanner(System.in);

int N; // ко­ли­че­ство чисел

String a; // оче­ред­ное число КАК СТРО­КА

int d[] = new int[9]; // под­счет чисел дан­ной длины

int mx; // мак­си­маль­ное ко­ли­че­ство в d

int imx=0; // самая частая длина

int i, k;

for (i = 1; i < 9; i++) {d[i] = 0;}

N = scan.nextInt();

for (i = 1; i <= N; i++) {

a = scan.next();

k = a.length();

d[k] = d[k]+1;

}

mx = 0;

for (i=1; i< 9;i++)

if (d[i] >= mx) {

mx = d[i];

imx = i;

}

System.out.println(imx+" "+mx);

}

}

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 12 мая 2017 года Вариант ИН10503