Контрольная работа по программированию 9 класс
1. Ввести с клавиатуры 3 действительных положительных числа. Найти
среднее геометрическое и среднее арифметическое этих чисел и
Вывести их на экран.
2. Ввести число хи вычислить у=
(х2, если х<=o
(3*X, если х> 0
3. С оператора цикла вывести на экран целые числа от 5 до 12.
Подумаем, как можно было бы решать задачу.
- Наивный сохранить все числа в массив и пробежаться по нему в двойном цикле, в псевдокоде это выглядит примерно так:
max = 0
for i = 1 to n do
for j = 1 to n do
if |i - j| >= 8 and max < a[i] * a[j] then
max = a[i] * a[j]
Это нехорошо и по времени (время выполнения порядка n^2), и по памяти (количество памяти растет с ростом n пропорционально n).
- Немного ускоряем: у нас пары i, j и j, i ничем не отличаются, так что будем считать, что j < i. Учитывая условие, что |i - j| >= 8, получаем, что j <= i - 8. Переписываем:
max = 0
for i = 9 to n do
for j = 1 to i - 8 do
if max < a[i] * a[j] then
max = a[i] * a[j]
Это решение работает в 2 раза быстрее, но этого недостаточно. Памяти тоже слишком много.
- Продолжаем ускорять. Пусть i зафиксировано. Мы пытаемся сравнить a[i] * a[j] с max для всех j от 1 до i - 8. Очевидно, произведение будет максимально, если a[j] - максимум среди a[1], a[2], ..., a[i - 8]. Возможное решение: создадим массив из максимумов среди первых k чисел, и будем сравнивать уже с максимумом.
maximums[1..n]
maximums[1] = a[1]
for i = 2 to n do
maximums[i] = max(maximums[i - 1], a[i])
max = 0
for i = 9 to n do
if max < a[i] * maximums[i - 8] then
max = a[i] * maximums[i - 8]
Это решение уже работает быстро, но остались проблемы с большим расходом памяти.
- Последний рывок. Заметим, что для того, чтобы разобраться с числом под номером i, нам совсем не нужен массив a, а из массива maximums достаточно знать только maximums[i - 8], ..., maximums[i - 1] - 8 чисел. Так что большие массивы не нужны, их можно убрать. Тогда программа будет эффективна и по времени, и по памяти.
У меня максимумы хранятся в массиве maxs[0..7], все номера берутся по модулю 8. В вашей программе это может быть реализовано иначе.
Pascal:
var
i, n, t, max: integer;
maxs: array[0..7] of integer;
begin
read(n);
read(t);
max := 0;
maxs[1] := t;
for i := 2 to n do
begin
read(t);
if (i > 8) and (max < t * maxs[i mod 8]) then
max := t * maxs[i mod 8];
if t > maxs[(i + 7) mod 8] then
maxs[i mod 8] := t
else
maxs[i mod 8] := maxs[(i + 7) mod 8];
end;
write(max);
end.
program n_3;var n, i,s, imax: integer;a:array[1..10] of integer;begin//третья прогаwriteln('3 прога');
for i:=1 to 10 do a[i]:=random(50);for i:=1 to 10 do write (a[i],' ');n:=0;for i:=1 to 10 doif a[i]=50 then n:=i;if n=0 then write ('нет') else write (i);writeln();writeln('2 прога');s:=0;//вторая прогаfor i:=1 to 10 do a[i]:=random(50);for i:=1 to 10 do write (a[i],' ');imax:=1;for i:=2 to 10 doif a[i]>imax then imax:=1;writeln();write ('наибольший элемент a[', imax, ']=' ,a[imax]);writeln();writeln('1 прога');begin//1 прогаfor i:=1 to 10 do a[i]:=random(50);for i:=1 to 10 do n:=n+a[i];writeln('Сумма елементов =',n);end;end.