Проверяем дз от 27 мая.
Условие первой задачи.
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на одном из языков программирования алгоритм, который находит и выводит сумму наибольшей по длине возрастающей последовательности подряд идущих элементов. Если таких последовательностей несколько, можно вывести любую из них. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Паскаль |
| const N=30; var a: array [1..N] of integer; i, l, lmax, s, smax: integer; begin for i:=1 to N do readln(a[i]); ... end. |
В качестве ответа вам необходимо привести фрагмент программы, который должен находиться на месте многоточия.
Решение.
ВНИМАНИЕ!
Находим не длину, а сумму наибольшей (то есть, самой длинной!) возрастающей последовательности.
Определимся, что будем хранить в данных нам переменных.
i – переменная цикла for;
l – длина возрастающей последовательности;
s – сумма текущей последовательности;
lmax – длина максимальной последовательности;
smax – сумма максимальной последовательности.
Алгоритм решения:
1. Записываем в переменную lmax начальное значение 0, в переменную l – значение 1, а в переменную smax – значение первого элемента массива.
2. В цикле рассматриваем все элементы массива, начиная со 2-ого до
30-ого.
3. Если очередной элемент больше предыдущего, увеличиваем переменную l на 1, а к переменной s добавляем значение этого элемента; иначе записываем 1 в переменную l и значение этого элемента в s.
4. После этого (в теле цикла) сравниваем l и lmax; если l > lmax (нашли новую самую длинную возрастающую цепочку), записываем значение l в lmax, а s в smax.
Решение на паскале
const N=30;
var a: array [1..N] of integer;
i, l, lmax, s, smax: integer;
Begin
for i:=1 to N do readln(a[i]);
lmax:=0; l:=1; s:=a[1];
for i:=2 to N do begin
if a[i] > a[i-1] then begin l:=l+1; s:=s+a[i] end
else begin l:=1; s:=a[i] end;
if l > lmax then begin lmax:=l; smax:=s end
end;
Writeln(smax)
End.
Условие второй задачи.
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать любые целые значения. Опишите на одном из языков программирования алгоритм, который находит и выводит номер элемента массива, наименее отличающегося от среднего арифметического всех его элементов. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Паскаль |
| const N=30; var a: array [1..N] of integer; i, k: integer; s, min: real; begin for i:=1 to N do readln(a[i]); ... end. |
В качестве ответа вам необходимо привести фрагмент программы, который должен находиться на месте многоточия.
Решение.
Сначала находим среднее арифметическое всех элементов массива (считаем в цикле их сумму и делим на N). Затем перебираем во втором цикле все элементы массива и ищем тот, для которого модуль разности этого элемента и среднего арифметического наименьший.
Определимся, что будем хранить в данных нам переменных.
i – переменная цикла for;
s – среднее арифметическое;
k – номер текущего элемента, которое нам нужно вывести;
Алгоритм решения:
1. Записываем в переменную s начальное значение 0.
2. В цикле для всех элементов с 1-го до 30-го добавляем значение текущего элемента к переменной s.
3. После окончания цикла делим значение переменной s на N, таким образом, получаем в переменной s среднее арифметическое всех элементов массива.
4. Записываем в переменную k начальное значение 1.
5. В цикле рассматриваем все элементы со 2-ого до 30-ого.
6. Если модуль разности текущего элемента и переменной s меньше, чем модуль аналогичной разности для k -ого элемента, записываем в переменную k номер текущего элемента.
7. После окончания цикла выводим значение переменной k.
Решение на паскале
const N=30;
var a: array [1..N] of integer;
i, k: integer;
s, min: real;
Begin
for i:=1 to N do readln(a[i]);
s:=0;
for i:=1 to N do s:=s+a[i];
s:=s/N;
k:=1;
for i:=2 to N do
if abs(a[i]-s) < abs(a[k]-s) then k:=i;
Writeln(k)
End.
Условие третьей задачи.
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать произвольные целые значения. Опишите на одном из языков программирования алгоритм, который находит и выводит номера двух элементов массива, сумма которых минимальна. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Паскаль |
| const N=30; var a: array [1..N] of integer; i, k, min, min2: integer; begin for i:=1 to N do readln(a[i]); ... end. |
В качестве ответа вам необходимо привести фрагмент программы, который должен находиться на месте многоточия.
Решение.
ВНИМАНИЕ! Сложность в том, что нужно найти не минимальный элемент, а второй по величине. Можно, конечно, сначала найти минимум, а потом искать следующий за ним, но можно сделать это за один проход по массиву.
Определимся, что будем хранить в данных нам переменных.
i – переменная цикла for;
min – номер первого минимума;
min2 – номер второго минимума;
k – не используется.
Алгоритм решения:
1. Сначала выбираем минимальный из первых двух элементов и записываем его номер в min, а второй по величине записываем в min2:
if a[1] < a[2] then begin
min:=a[1]; min2:=a[2];
End
Else begin
min:=a[2]; min2:=a[1];
end;
2. Затем в цикле перебираем все элементы, начиная с 3-го (первые два уже «задействованы»!) до последнего, 30-ого.
3. Если очередной элемент a[i] меньше, чем min, записываем номер min в min2 (предыдущий минимум становится вторым), а значение a[i] – в min.
4. Иначе, если a[i] меньше, чем min2, записываем номер a[i] в min2. После завершения цикла выводим значение переменной min2.
Решение на паскале
const N=30;
var a: array [1..N] of integer;
i, k, min, min2: integer;
Begin
for i:=1 to N do readln(a[i]);
if a[1] < a[2] then begin min:= 1; min2:= 2 end
else begin min:= 2; min2:= 1 end;
for i:=3 to N do
if a[i] < a[min] then begin min2:= min; min:= i
End
else if a[i] < a[min2] then min2:= i;
Writeln(min, ' ', min2)
End.
Условие четвертой задачи.
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от
–1000 до 1000. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит среднее арифметическое всех элементов массива, оканчивающихся цифрой 5. Гарантируется, что хотя бы один такое элемент в массиве есть.
Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Паскаль |
| const N=30; var a: array [1..N] of integer; i, x, y: integer; s: real; begin for i:=1 to N do readln(a[i]); ... end. |
В качестве ответа вам необходимо привести фрагмент программы, который должен находиться на месте многоточия.
Решение.
ВНИМАНИЕ!
v Если значение в десятичной системе оканчивается на 5, это значит, что остаток от его деления на 10 (основание системы счисления) равен 5.
v При вычислении на компьютере остатка от деления отрицательных чисел (например, с помощью оператора mod в Паскале) этот остаток получается отрицательным [1] , например -25 mod 10 = -5.
v Поскольку сказано, что хотя бы один такой элемент есть, можно не опасаться деления на ноль.
Определимся, что будем хранить в данных нам переменных.
i – переменная цикла for;
x– счетчик найденных элементов;
y – сумма чисел, оканчивающихся на 5;
s– среднее арифметическое.
Алгоритм решения:
1. Обнуляем счетчик найденных элементов и их сумму, т.е. записываем в переменные x и y нулевые значения.
2. В цикле перебираем значения переменной i от 1 до N.
3. Если очередной элемент при делении на 10 дает в остатке 5 или –5, увеличиваем счетчик x на 1 и сумму y – на значение этого элемента.
4. После окончания цикла записываем в переменную s результат деления y на x. Выводим значение переменной s.
ВНИМАНИЕ!
Варианты определения чисел, оканчивающихся на 5, могут быть следующими:
1. При проверке остатка можно использовать сложное условие:
if (a[i] mod 10 = 5) or (a[i] mod 10 = -5) then
begin... end;
2. Перед применением операции mod взять модуль очередного элемента массива:
if abs(a[i]) mod 10 = 5 then begin... end;
3. Еще один вариант условия предложил:
if (a[ i] mod 5 = 0) and (a[ i] mod 2 <> 0) then begin
...
end;
что означает «число делится на 5 и не делится на 2», то есть оканчивается на 5.
Решение на Паскале.
const N=30;
var a: array [1..N] of integer;
i, x, y: integer;
s: real;
Begin
for i:=1 to N do readln(a[i]);
x:=0; y:=0;
for i:=1 to N do
if abs(a[i]) mod 10 = 5 then begin
x:= x + 1;
y:= y + a[i]
end;
s:= y / x;
Writeln(s)
End.