Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Умови прийому: наявність диплому бакалавра, спеціаліста або магістра за будь-якою спеціальністю. Зарахування до інституту відбувається за результатам...полностью>>
'Документ'
Курс «Політична географія» є спеціальним у підготовці фахівців з географії на освітньо-кваліфікаційному рівні спеціаліст та магістр, викладається сту...полностью>>
'Документ'
Конечно же, сама исходная книга не лишена определенных перегибов. Скажем, некоторое умиление вызывают польские карты Северного и Южного полюсов (стр.3...полностью>>
'Документ'
1. Утвердить санитарные правила и нормативы СП 2.6.1.2612-10 «Основные санитарные правила обеспечения радиационной безопасности (ОСПОРБ 99/2010)» (пр...полностью>>

Отчетная работа тема: Решение задач по программированию на егэ

Главная > Публичный отчет
Сохрани ссылку в одной из сетей:

МБОУ АСОШ №1 Артинского ГО

Отчетная работа

тема:

Решение задач по программированию на ЕГЭ

Спиридович А.С.

Учитель информатики

Арти 2011 г.

Решение задач по программированию в вариантах ЕГЭ или вступительных экзаменах в вузы требует от учащихся умения писать программы. Подразумевается, что программа использует минимально необходимую память, и алгоритм ее решения имеет минимальную сложность. Кроме того, необходимо, чтобы ученики были знакомы с базовыми алгоритмами обработки данных (в том числе массивов).

Во время решения задач учащихся желательно знакомить с разными способами решения одной и той же задачи, они должны в принципе научиться решать задачи.

Для этого:

1. Решаем базовые задачи, которые позволяют освоить технику работы с массивами.

2. Решаем задачи, алгоритмы которых являются составляющими многих задач на обработку массивов данных.

3. Учимся “читать” чужие программы.

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

· решение задачи “в лоб”;

· метод введения дополнительных данных;

· метод преобразования входных данных;

и решаем задачи по каждому методу.

Например:

1. Значения двумерного массива размера 7 * 7 задаются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования).

Бейсик

FOR n = 1 TO 7

FOR k = 1 TO 7

B(n, k) = k – n

NEXT k

NEXT n

 Паскаль

for n := 1 to 7 do

for k := 1 to 7 do

B[n, k] := k – n;

Алгоритмический язык рассматривать не будем.

 

Сколько элементов массива будут иметь положительные значения?

1) 49

2) 28

3) 21

4) 7

Правильный ответ: 21.

Решение

Школьники, как правило, решают эту задачу “в лоб”, они рисуют таблицу (двумерный массив) и вписывают в нужные клетки получаемые значения. Такой способ при решении задач с небольшой размерностью допустим.

Другой способ основывается на анализе выполнения вложенного цикла. При p-м выполнении внутреннего цикла выражение k – n будет положительным при k > n. Так как k и n изменяются от 1 до 7, искомое значение будет равно

6 + 5 + 4 + 3 + 2 + 1 = 21.

2. Все элементы двумерного массива A размером 10 * 10 элементов первоначально были равны 0. Затем значения элементов меняются с помощью вложенного оператора цикла в представленном фрагменте программы (ниже представлена одна и та же программа, записанная на разных языках программирования).

Бейсик

FOR n = 1 TO 4

FOR k = n TO 4

A(n,k) = A(n,k) + 1

A(k,n) = A(k,n) + 1

NEXT k

NEXT n

Паскаль 

for n := 1 to 4 do

for k := n to 4 do

begin

A[n, k] := A[n, k] + 1;

A[k, n] := A[k, n] + 1;

end

 

Сколько элементов массива в результате будут равны 1?

1) 0

2) 16

3) 12

4) 4

Правильный ответ: 12.

2. Базовые технические задачи

К базовым техническим задачам на обработку массивов мы относим следующие задачи:

1. Заполнить массив по возрастанию, по убыванию, случайным образом.

2. Не используя вспомогательных массивов, переставить элементы массива в обратном порядке.

3. Сдвинуть элементы массива влево, вправо на k позиций (это две разные задачи).

4. Циклический сдвиг элементов массива на k позиций влево, вправо.

5. Эффективный алгоритм циклического сдвига элементов массива на k позиций влево, вправо.

6. “Сжатие” массива.

7. Заполнение двумерного массива (по возрастанию, выше главной диагонали, только главную диагональ и т.п.).

8. Вывод двумерного массива на экран в виде таблицы.

3. Сформировать массив, элементами которого будут квадраты соответствующих индексов.

Замечание. Это один из способов формирования упорядоченного по возрастанию массива.

4. Требуется создать массив из N случайных целых чисел.

Решение. При отработке технических навыков программирования важно научить школьников не использовать в тексте программы числовые константы в явном виде. Всем таким константам должны быть даны имена в блоке const.

const N = 10;

{количество элементов массива}

MAX_V = 15;

{диапазон случайных чисел}

var m: array[1..N] of integer;

i: integer;

begin

randomize;

for i := 1 to N do

{создание и вывод элементов массива}

begin

m[i] := random(MAX_V);

writeln('m[i]=',m[i])

end

end.

5. Из элементов массива А сформировать элементы массива B по правилу:

b[i] := а[1] + а[2] + ... + а[i].

Замечание. Для решения этой задачи не надо использовать вложенные циклы. Ниже приведен фрагмент программы.

b[1] := а[1];

for i := 2 to n do b[i] := b[i - 1] + а[i];

6. Ввести с клавиатуры n чисел и распечатать их в обратном порядке.

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

for i := n downto 1 do write(a[i]:4).

7. Не используя других массивов, переставить элементы целочисленного массива в обратном порядке.

Решение. Для всех индексов 1 i (n div 2) необходимо каждый i-й элемент поменять местами с (n – i + 1)-м элементом. При решении этой задачи учащиеся отрабатывают операцию обмена значений элементов массива. Важно обратить внимание учащихся, что для обмена местами левой и правой половин массива цикл должен отработать только (n div 2) раз при любом n (как четном, так и нечетном). Ниже приведен фрагмент программы.

for i := 1 to n div 2 do

begin

k := x[i]; x[i] := x[n + 1 - i];

x[n + 1 - i] := k

end;

8. Значения массива сдвинуть циклически вправо на одну позицию так, чтобы последний элемент стал первым.

Решение

const n = 10;

var x: array [1..n] of integer;

t, i: integer;

begin

t := x[n];

for i := n downto 2 do

x[i] := x[i - 1];

x[1] := t

end.

В данной задаче принципиальным является порядок выполнения сдвигов. Так, если цикл downto заменить на for i := 2 to n do, то все элементы получат значение x[1].

9. Значения массива сдвинуть циклически вправо на k позиций.

Решение. Эту задачу можно решить следующим способом: выполнить в цикле k раз тело предыдущей программы. Подсчитаем сложность предложенного алгоритма. Основной операцией при выполнении этой программы является оператор присваивания. Он будет выполнен (n + 1)k раз. При k, близком к n, мы получим квадратичную сложность.

10. Написать эффективную программу циклического сдвига значений массива вправо на k позиций, где k < n.

Решение. Для решения этой задачи можно предложить алгоритм линейной сложности без использования дополнительных массивов. Идея алгоритма состоит в следующем. Запишем в обратном порядке первые n – k элементов. Затем запишем в обратном порядке последние k элементов. А затем перепишем в обратном порядке весь измененный массив.

const n = 10;

var a:array [1..n] of integer;

k,p,t:integer;

begin

{заполнение массива}

for p := 1 to (n - k) div 2 do

begin

t := a[p];

a[p] := a[(n - k) – p + 1];

a[(n - k) – p + 1] := t

end;

for p := 1 to k div 2 do

begin

t := a[n – k + p];

a[n – k + p] := a[n – p + 1];

a[n – p + 1] := t

end;

for p := 1 to n div 2 do

begin

t := a[p];

a[p] := a[n – p + 1];

a[n – p + 1] := t

end

end.

Сложность этого алгоритма, вычисленная в операторах присваивания, равна 3n и не зависит от k.

11. Дан целочисленный массив размерности n. “Сожмите” массив, выбросив из него каждый второй элемент. “Освободившиеся” места в правой части массива заполните нулями. Дополнительный массив не использовать.

Решение

const n = 10;

a: array [1..n] of byte = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

var i, j, k: integer;

begin

k := 0;

i := 1;

while i <= n do

begin

a[i – i div 2] := a[i];

{перемещаем элемент с четным индексом на "свое" место}

i := i + 2

end;

a[i] := 0;

{последние (n – n div 2 + 1) элементы обнуляем }

for i := 1 to n do write(a[i]: 3);

readln

end.

12. Дан массив, содержащий нулевые элементы. “Сожмите” его, передвинув нулевые элементы в конец массива. Дополнительный массив не использовать.

Решение

const n = 10;

a: array [1..n] of byte = (1, 0, 0, 2,

0, 3, 4, 7, 0, 1);

var i, k: integer;

begin

k := 0;

i := 1;

for i := 1 to n do

begin

if a[i] = 0 then inc(k)

{подсчитываем количество нулей в части

массива от 1 до i}

else a[i - k] := a[i];

{перемещаем ненулевой элемент на

первое свободное место}

end;

for i := n – k + 1 to n do a[i] := 0;

{освободившиеся места заполняем

нулями}

for i := 1 to n do write(a[i]: 2);

readln

end.

13. С помощью датчика случайных чисел заполнить двумерный массив A размера n x n числами 1, 4, 7, 10. Подсчитать в нем количество таких четверок

A[i, j], A[i + 1, j], A[i, j + 1], A[i + 1, j + 1],

в которых все элементы различны.

Решение. Искомая четверка элементов должна удовлетворять условию

A[i, j] * A[i + 1, j] * A[i, j + 1] * A[i + 1, j + 1] = 280.

const n = 10;

v = 4;

var m: array[1..N, 1..N] of integer;

i, j, k: integer;

begin

randomize;

k := 0;

for i := 1 to n do

{создание и вывод элементов массива}

begin

for j := 1 to n do

begin

m[i,j] := random(v) * 3 + 1;

{массив заполняется числами

1, 4, 7, 10}

write(m[i,j]:3)

end;

writeln

end;

for i := 1 to n — 1 do

for j := 1 to n – 1 do

if A[i,j] * A[i + 1,j] *

A[i,j + 1] * A[i + 1,j + 1] = 280

then k := k + 1;

writeln(k)

end.

14. Двумерный массив размера n x n содержит только положительные значения. Замените на ноль значения всех элементов, расположенных на главной и на побочной диагоналях. Главная диагональ идет из верхнего левого угла в правый нижний угол, побочная диагональ идет из верхнего правого в левый нижний угол.

Решение. Ниже приведен фрагмент программы.

for i := 1 to n do

begin

m[i,i] := 0; m[i, n – i + 1] := 0

end

15. Двумерный массив размера n x n содержит не равные нулю значения. Замените на ноль значения всех элементов, расположенные выше побочной диагонали.

Решение. Ниже приведен фрагмент программы.

for i := 1 to n do

for j := 1 to n — i do

m[i,j] := 0;

3. Базовые алгоритмы

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

1. Поиск максимального (минимального) значения в массиве.

2. Поиск двух максимальных (минимальных) значений массива.

3. Подсчет суммы значений элементов.

4. Проверить, что все элементы в массиве одинаковы.

5. Проверить, что все элементы массива различны.

6. В двумерном массиве подсчитать суммы по столбцам (строкам).

7. В двумерном массиве найти элемент максимальный по строке и минимальный по столбцу.

3.1. Поиск максимального (минимального) значения в массиве

Рассмотрим две задачи.

Синоптики фиксировали дневные температуры в течение всего года. Найти максимальную (минимальную) годовую температуру.

Синоптики фиксировали дневные температуры в течение всего года. Распечатать все дни, когда температура достигала максимального (минимального) значения.

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

Вот пример программы для решения подобной задачи.

const n = 365;

var i, a, max: integer;

begin

read(a);

max := a;

for i := 1 to n do

begin

read(a); {считываем данные}

if max < a then max := a;

{при поиске минимального значения

достаточно заменить условный оператор

на следующий: if min > a then min := a}

end;

writeln(max)

end.

Вторую задачу решить без использования массивов не представляется возможным. Рассматриваемая задача делится на две подзадачи:

1) поиск максимального значения среди всех годовых температур;

2) определение дней со значением температуры, равной максимальной.

Для выполнения этих подзадач необходимо обработать каждое значение два раза, что требует их хранения в памяти компьютера.

const n = 365;

var mas: array [1..n] of integer;

i, max: integer;

begin

randomize;

for i := 1 to n do

mas[i] := random(40) -20;

max := mas[1];

for i := 2 to n do

if max < mas[i] then max := mas[i];

for i := 1 to n do

if mas[i] = max then write(i: 4);

end.

Обратим внимание, что инициализирование переменной max первым обрабатываемым значением — прием, позволяющий избежать многих ошибок.

Замечание. В задачах часто требуется определить не само максимальное значение, а индекс этого элемента в массиве. Это, например, требуется при реализации сортировки выбором. Этому навыку также необходимо учить школьников.

3.2. Поиск максимального (минимального) и следующего за ним по величине значений массива

Синоптики фиксировали дневные температуры в течение всего года. Найти максимальную годовую температуру и следующую за ней по величине температуру.

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

В переменных max1 и max2 будем хранить соответственно максимальный и следующий за максимальным элемент в уже просмотренной части массива.

const n = 365;

var mas: array [1..n] of integer;

i, max1, max2: integer;

begin

randomize;

for i := 1 to n do

mas[i] := -20 + random(40);

if mas [1] < mas[2] then

begin max1 := mas[2]; max2 := mas[1]

end

else

begin max1 := mas[1]; max2 := mas[2]

end

for i := 3 to n do

if max1 < mas[i] then

begin max2 := max1: max1 := mas[i] end

else if max2 < mas[i] then

maх2 := mas[i];

writeln(max1: 3, max2: 3)

end.

Синоптики фиксировали дневные температуры в течение всего года. Определить месяц, в котором максимальное число раз дневная температура равнялась первому или второму максимуму.

3.3. Подсчет суммы значений элементов массива и среднего значения для элементов массива

Дан целочисленный массив. Подсчитать число элементов, больших среднего значения всех элементов массива.

Решение. Задача делится на две подзадачи: сначала надо найти среднее значение элементов массива (за один проход по массиву), а затем подсчитать количество элементов со значением, превышающим найденное среднее (второй проход по массиву).

Магазин обслужил за день 200 покупателей, каждый из которых потратил на покупки не более 1000 рублей. Посчитать дневную прибыль магазина и сумму среднего потребительского чека.

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

const n = 200;

m = 1000;

var mas: array [1..n] of integer;

i, sum: integer;

begin

randomize;

for i := 1 to n do

mas[i] := 1 + random(m);

sum := 0;

for i := 1 to n do sum := sum + mas[i];

writeln('Прибыль магазина:', sum: 8);

writeln('Средний чек:', sum/n: 8: 2)

end.

3.4. Проверить, все ли элементы в массиве одинаковы

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

Решение

const n = 60;

var i: integer;

mas: array [1..n] of integer;

flag: boolean;

{флаг, который отвечает за равенство элементов}

begin

randomize;

for i := 1 to n do mas[i] := random(2);

flag := true;

i := 2;

while (i <= n) and flag do

begin

flag := mas[i – 1] = mas[i];

{проверка элементов на равенство

предыдущему}

inc(i)

end;

if flag then writeln('система работает нормально')

else writeln('надо проверить систему');

readln

end.

3.5. Проверить, все ли элементы массива различны

В базе данных хранятся номера сотрудников, которым была выписана премия за месяц. Проверить, не попал ли кто-либо из сотрудников в эту базу дважды.

Решение

const n = 10;

a: array [1..n] of byte = (1,2,3,4,5,6,7,8,9,10);

var i, j: integer;

b: boolean;

begin

i := 1;

b := true;

while (i <= n – 1) and b do

begin

j := i + 1;

while (j <= n) and b do begin

b := b and (a[i] <> a[j]);

inc(j)

end;

inc(i)

end;

writeln(b);

readln

end.

С помощью внутреннего цикла мы проверяем, не встречается ли обрабатываемый элемент a[i] в подмассиве от (i + 1) до n.

В худшем случае, если все элементы в массиве различны, операция сравнения выполнится n(n – 1)/2 раз.

3.6. Подсчет количества различных значений в массиве

Диспетчер заносила в базу номера товаров, которые поступали на склад в течение дня. Посчитать, сколько различных видов товаров было привезено на склад за этот день.

Решение. Счетчик различных номеров будем увеличивать тогда, когда элемент a[i] встретился в массиве последний раз. Для этого будем перебирать элементы массива; если элементa[i] совпал с каким-то элементом a[j], где j > i, то мы прекращаем сравнения a[i] с a[j] и переходим к элементу a[i + 1].

Пример 1. Для массива {1 2 2 2 1 1 3 4 5 6} увеличение счетчика для a[i] = 1 произойдет при обработке 6-го элемента, для a[i] = 2 увеличение счетчика произойдет при обработке 4-го элемента, для a[i] = 3 увеличение счетчика произойдет при обработке 7-го элемента и т.д.

Пример 2. Для массива {3 3 3 3 3 3 3 3 3 3} увеличение счетчика произойдет при обработке последнего элемента.

const n = 10;

a: array [1..n] of byte = (1,1,1,1,1,1,7,7,7,1);

var i, j, k: integer;

begin

k := 1;

for i := 1 to n — 1 do

begin

j := i + 1;

while (j <= n) and (a[i] <> a[j]) do

inc(j);

if j = n + 1 then inc(k)

{учитываем элемент, когда встретили

его последний раз}

end;

writeln(k);

readln

end.

3.7. Подсчет суммы по строкам (столбцам) в двумерном массиве

На предварительных экзаменах ученики сдавали 5 экзаменов, каждый из которых оценивался по 10-балльной системе. Определить сумму баллов, набранную каждым учеником.

Решение

const n = 5; {количество предметов}

m = 30; {количество учеников}

var mas: array [1..m, 1..n] of integer;

i, j, sumstr: integer;

begin

randomize;

for i := 1 to m do

for j := 1 to n do

mas[i,j] := random(11);

{инициализация двумерного массива}

for i := 1 to m do

begin

sumstr := 0;

{обнуляем значение переменной — сумма

по текущей строке}

for j := 1 to n do

sumstr := sumstr + mas[i, j];

writeln('Сумма баллов ученика ', i, ' равна ',

sumstr);

end

end.

3.8. В двумерном массиве найти элемент максимальный по строке и минимальный по столбцу

Дана таблица a, состоящая из n строк и n столбцов. Требуется определить, есть ли в таблице такой элемент a[i, j], который был бы максимален в i-й строке и минимален в j-м столбце. Если такой элемент есть в таблице, то вывести его координаты. Если таких элементов несколько, то вывести координаты одного из них.

Решение

const n = 4;

a: array [1..n, 1..n] of

integer = ((10,9,80,7),(11,8,20,11), (9,7,40,1),(13,3,20,6));

var i, j, k, st, min : integer;

flag: boolean;

begin

i := 1;

flag := false;

while (i <= n) and not flag do

begin

st := 1;

for j := 2 to n do

if a[i, j] > a[i, st] then st := j;

{нашли максимум по i-й строке, запомним

его в переменной min}

min := a[i,st];

flag := true;

k := 0;

repeat

inc(k);

flag := flag and (a[k, st] >= min);

{flag будет равен true, если найденный

максимальный элемент является минимальным в

столбце st}

until (k >= n) or not flag;

inc(i)

end;

if flag then writeln(i-1:3, st:3)

else writeln('no');

readln

end.

При решении задачи стоит обратить внимание на следующие моменты:

1) задача распадается на следующие подзадачи. Для каждой строки надо найти максимальный элемент, затем проверить, является ли он минимальным в своем столбце. Эту операцию при необходимости надо проделать со всеми строками;

2) когда мы ищем максимальный элемент в строке, мы должны обязательно запоминать координаты этого элемента, чтобы знать, для какого столбца проверять, является ли найденный элемент минимальным;

3) для поиска максимального элемента в строке целесообразно использовать цикл for, так как мы должны перебрать все элементы строки;

Массив размерности n заполнен словами, состоящими только из строчных латинских букв. Слова между собой разделятся ровно одним пробелом. Вывести на экран длину самого длинного слова.

Решение. Воспользуемся описанным выше приемом, т.е. увеличим размерность массива. Теперь каждое слово в массиве оканчивается хотя бы одним пробелом. Двигаясь по слову, будем подсчитывать его длину. Затем сравним полученное значение с максимальной длиной слова из уже обработанных.

const n = 10;

var a:array [1..n] of char;

k, len, maxlen:word;

begin

maxlen := 0;

k := 1;

len := 0;

while (a[k]<> ' ') and (k <= n) do

begin

inc(k);

inc(len)

end;

if len > maxlen then

begin

maxlen := len;

ken := 0

end;

while (a[k] = ' ') and (k <= n) do

inc(k)

end;

writeln(maxlen)

end.

5. Приемы решения задач из ЕГЭ по информатике

Опишите на русском языке или на одном из языков программирования алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элемента в числовом массиве из 30 различных элементов.

Решение этой задачи полностью основано на знании базового алгоритма поиска двух максимальных (минимальных) значений в массиве.

Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл — 9), информатика (максимальный балл — 9), литература (максимальный балл — 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй — количество мест K (K < N), на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: <Фамилия> <оценка1> <оценка2> <оценка3>, где <Фамилия> — строка, состоящая не более, чем из 20 символов, оценки — числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными.) Пример входных строк:

Иванов 8 9 3

Петров 2 0 0

Требуется написать программу на языке Паскаль или Бейсик, которая определяла бы по имеющимся данным количество абитуриентов, набравших полупроходной балл в данный вуз, или сообщала, что такой балл отсутствует. (Полупроходным называется такой балл, что лишь часть абитуриентов, набравших такой балл и не получивших ни одной неудовлетворительной оценки, попадает в K лучших, которые должны быть зачислены на 1-й курс.) Считается, что абитуриенты, получившие только удовлетворительные оценки, обязательно присутствуют.

Решение. Алгоритм решения этой задачи основан на использовании метода подсчета. Введем массив m:array[0..23] of integer, в p-м элементе которого будем подсчитывать количество абитуриентов, набравших p баллов. Если абитуриент получил хотя бы одну двойку, то удобно считать, что его общий балл равен 0.

Заполнять массив m будем в процессе считывания данных, сами данные хранить не будем. Заметим, что сумма всех элементов массива m равна n — числу абитуриентов. Взять на первый курс могут только k человек. Здесь возможна ситуация, что есть группа абитуриентов, набравших одинаковое количество баллов p, но если их всех зачислить на первый курс вместе с абитуриентами, набравшими больше чем p баллов, то мест не хватит (это и есть полупроходной балл).

Для определения полупроходного балла будем подсчитывать сумму элементов этого массива (т.е. число абитуриентов), начиная с 23-го, до тех пор, пока она не превосходит K (алгоритм подсчета суммы элементов массива также относится к базовым). Индекс первого элемента массива, который не войдет в эту сумму и будет искомым полупроходным баллом. Если проходной балл набрали ровно K абитуриентов, то программа сообщает, что полупроходной балл отсутствует.

Для правильного решения задачи надо грамотно организовать считывание данных.

var m:array[0..23] of integer;

c:char;

i, K, N, S, m1, m2, m3:integer;

begin

readln(N); readln(K);

for i := 0 to 23 do m[i] := 0;

for i := 1 to N do

begin

repeat

read(c)

until c=' '; {считана фамилия абитуриента}

readln(m1, m2, m3);

if (m1 < 3)or(m2 < 3)or(m3 < 3) then

s := 0

else s := m1 + m2 + m3;

m[s] := m[s] + 1

{учитываем абитуриента в элементе

массива, соответствующем его баллам}

end;

s := m[23]; i := 23;

while s + m[i - 1] <= K and (i > 9)

{9 — минимально возможный балл} do

begin

i := i - 1;

s := s + m[i]

end;

if (s < K)and(i > 9) then

writeln('полупроходной балл набрали', m[i - 1],

' человек')

else writeln('полупроходной балл

отсутствует');

readln

end.

Опишите на русском языке или одном из языков программирования алгоритм подсчета числа элементов, равных максимальному в числовом массиве из 30 элементов.

Решение. Алгоритм решения задачи основан на применении базового алгоритма нахождения максимального элемента в массиве. Смотри задачи 16 и 17. Заметим, что задачу можно решить за 1 проход по массиву.

Опишите на русском языке или одном из языков программирования алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна (если таких пар несколько, то можно выбрать любую из них).

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

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

const N = 30;

var a:array[1..N] of integer;

MaxSum, MaxNum, i: integer;

begin

MaxNum := 1;

MaxSum := a[1] + a[2];

for i := 2 to N – 1 do

begin

if a[i] + a[i + 1] > MaxSum then

begin

MaxNum := i;

MaxSum := a[i] + a[i + 1]

end

end;

writeln(MaxNum)

end.

На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <оценки>, где <Фамилия> — строка, состоящая не более чем из 20 символов, <Имя> — строка, состоящая не более чем из 15 символов, <оценки> — через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:

Иванов Петр 4 5 4

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

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

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

Отметим, что для более “красивого” решения в программе целесообразно использовать массив типа record:

a:array[1..100] of record

name:string;

sum:integer;

end;



Скачать документ

Похожие документы:

  1. Учебно-методический комплекс курса по выбору "задачи егэ по информатике" (физико-математический факультет) для специальности

    Учебно-методический комплекс
    Целевая установка и организационно-методические указания. Данный курс предполагает изучение следующих тем: «ЕГЭ по информатике: история, структура экзаменационной работы, особенности проведения экзамена и подготовки к нему», «Математическая
  2. Отчет о результатах самообследования математического факультета по состоянию на 01. 06. 2008 года

    Публичный отчет
    5.5 Результаты опросов общественного мнения студентов, преподавателей, потенциальных работодателей о качестве предоставляемых образовательных услуг, организации учебного процесса,
  3. План проспект курсовых мероприятий Чувашского республиканского института образования на 2009 2010 учебный год

    Документ
    Комплектование учебных групп осуществляется традиционно по заявкам органов управления образованием, образовательных учреждений, а также по индивидуальным заявкам.
  4. Отчет о результатах самообследования физико-технического факультета по состоянию на 01. 06. 2008 года

    Публичный отчет
    5.5 Результаты опросов общественного мнения студентов, преподавателей, потенциальных работодателей о качестве предоставляемых образовательных услуг, организации учебного процесса,
  5. Конкурсная документация по конкурсу на размещение муниципального заказа на поставку товарно-материальных ценностей для нужд Управления образования администрации мо шурышкарский район

    Конкурс
    Настоящая конкурсная документация разработана в соответствии с Федеральным законом от 21.07.2005г. № 94-ФЗ «О размещении заказов на поставки товаров, выполнение работ, оказание услуг для государственных и муниципальных нужд».

Другие похожие документы..