Разбор 27 задания ЕГЭ 2017 года по информатике из демоверсии. Это задание из второй части высокого уровня сложности. Примерное время выполнения задания 55 минут. Максимальный балл за выполнение задания — 4.
Максимальный балл для задания А — 2
Максимальный балл для задания Б — 4
Проверяемые элементы содержания:
— умение создавать собственные программы(30–50 строк) для решения задач средней сложности.
Элементы содержания, проверяемые на ЕГЭ:
— основные этапы разработки программ. Разбиение задачи на подзадачи.
Задание 27
Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.
Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Прямая и обратная пропорциональные зависимости, 6 класс
Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу– 2 балла.
Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Входные данные
Для варианта А на вход программе подаётся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.
Прямо пропорциональная и обратно пропорциональная зависимость. 6 класс.
Пример входных данных для варианта А:
1 3
5 12
6 9
5 4
3 3
1 1
Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ≤ N ≤100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта Б:
6
1 3
5 12
6 9
5 4
3 3
1 1
Пример выходных данных для приведённых выше примеров входных данных: 32
Разбор 27 задания ЕГЭ 2017
Задание Б.
Cначала рассмотрим решение для более общего задания (вариант Б).
Решение 1.
Чтобы получить максимально возможную сумму, будем брать из каждой пары самое большое число. Если полученная при этом сумма будет делиться на 3, её необходимо уменьшить. Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 3, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 3, получить нужную сумму невозможно.
Программа читает все данные один раз. В каждой паре определяется большее число Max и разность между большим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s – сумму всех максимальных элементов прочитанных пар и D_min – наименьшую возможную разность D, не кратную 3. Окончательным ответом будет значение s, если оно не делится на 3, и s–D_min в противном случае. Если s делится на 3, а D_min не определено (разность между числами во всех парах кратна 3), ответ в соответствии с условиями задачи считается равным 0.
Программа 1. Пример правильной и эффективной программы для задания Б на языке Паскаль.
const
aMax = 10000;
var
N: longint;
a, b: longint;
Max: longint;
Min: longint;
s: longint;
D_min: longint;
i: longint;
begin
s := 0;
D_min := aMax + 1;
readln(N);
for i := 1 to N do begin
readln(a, b);
if a>b then begin Max:=a; Min:=b end
else begin Max:=b; Min:=a end;
s := s + Max;
if ((Max — Min) mod 3 > 0) and (Max — Min aMax then s := 0
else s := s – D_min
end;
writeln(s)
end.
Решение 2.
Возможно и решение, основанное на другой идее, а именно будем хранить для каждого прочитанного набора пар три суммы (s0, s1, s2) – максимальные суммы элементов пар, имеющие при делении на 3 соответственно остатки 0, 1 и 2. При обработке очередной пары (a1, a2) эти суммы обновляются. Для этого достаточно рассмотреть суммы s0+a1, s1+a1, s2+a1, s0+a2, s1+a2, s2+a2 и для каждого возможного остатка от деления на 3 выбрать в качестве нового значения s0, s1 или s2 значение наибольшей из указанных сумм, дающей данный остаток. Окончательным ответом будет большая из сумм s1 и s2.
Эта идея приводит к более громоздкой реализации, но все основные требования по эффективности в ней выполнены, поэтому подобное решение при отсутствии ошибок можно оценить максимальным количеством баллов.
Ниже приводится пример основанной на этом принципе программы на языке Паскаль.
Программа 2. Пример правильной и эффективной программы для задания Б на языке Паскаль
var
N: longint;
a: array[1..2] of longint;
s_old, s_new: array[0..2] of longint;
i, j, k, r: longint;
begin
readln(N);
for j := 0 to 2 do
s_old[j] := 0;
for i := 1 to N do begin
readln(a[1], a[2]);
for j := 0 to 2 do
s_new[j] := 0;
for k := 1 to 2 do begin
for j := 0 to 2 do begin
if (s_old[j] > 0) or (i = 1) then begin
r := (s_old[j] + a[k]) mod 3;
if s_new[r] s_new[2] then
writeln(s_new[1])
else
writeln(s_new[2]);
end.
Задание А.
Это задание можно выполнить «в лоб»: сохранить в массиве все исходные данные, перебрать все возможные способы выбора одного элемента из каждой пары и найти максимальную сумму, соответствующую условиям задачи.
Ниже приводится пример такого решения
Пример решения задачи А на языке Паскаль.
var
a: array[1..6, 1..2] of longint;
i1, i2, i3, i4, i5, i6: longint;
s, sMax: longint;
begin
for i1:= 1 to 6 do readln(a[i1,1], a[i1,2]);
sMax := 0;
for i1:=1 to 2 do
for i2:=1 to 2 do
for i3:=1 to 2 do
for i4:=1 to 2 do
for i5:=1 to 2 do
for i6:=1 to 2 do begin
s:=a[1,i1]+a[2,i2]+a[3,i3]+a[4,i4]+a[5,i5]+a[6,i6];
if (s mod 3 <> 0) and (s > sMax) then sMax := s
end;
writeln(sMax)
end.
Источник: infedu.ru
Решение задач на С++
Задача A. Сумма квадратов
По данному натуральному n вычислите сумму 1 2 +2 2 +. +n 2 .
- int n, s = 0;
- cin >> n;
- for ( int i = 1 ; i
- s += i*i;
- cout
Задача C. Факториал
Вычислите N! («эн-факториал») – произведение всех натуральных чисел от 1 до N ( N!=1∙2∙3∙…∙ N ).
N – натуральное, не превосходит 12.
- int n, nf = 1;
- cin >> n;
- for ( int i = 2 ; i
- nf *= i;
- cout
Задача D. Степень
Выведите число 2 N . N не превосходит 30.
- const int count = 2;
- int n, rez = 1;
- cin >> n;
- for ( int i = 1 ; i
- rez *= count;
- cout
- int n;
- cin>>n;
- cout
Задача E. Число сочетаний
По данным натуральным n и k вычислите значение Cn k = n! / (k!(n-k)!) (число сочетаний из n элементов по k).
- long long n,k;
- cin>>n>>k;
- long long res = 1;
- for ( int i=1;i <=k;i++)
- res *= (n-k+i);
- res /= i;
- >
- cout
Задача G. Геометрическая прогрессия
По данному действительному числу a и натуральному n вычислите сумму 1+a+a 2 +. +a n , не используя формулу суммы геометрической прогрессии. Время работы программы должно быть пропорционально n.
- double a;
- int n;
- cin >> a >> n;
- double sum = 1 , an = 1;
- for ( int i = 1 ; i
- an *= a;
- sum += an;
- >
- printf( «%0.8f» ,sum);
Задача H. Сумма – 1
По данному числу n вычислите сумму 1+1/2 2 +1/3 2 +. +1/n 2 . Вводится одно число n, не превосходящее 100000.
- int n;
- cin >> n;
- double sum = 0;
- for ( long long i = 1 ; i
- sum += 1.0/(i*i);
- printf( «%0.8f» ,sum);
Задача I. Сумма – 2
По данному числу n вычислите сумму 4(1-1/3+1/5-1/7+. +(-1) n /(2n+1)). Вводится одно число n, не превосходящее 100000.
- int n;
- cin >> n;
- double sum = 1.0;
- int sign = -1;
- for ( int i = 1 ; i
- sum += sign / ( 2.0 * i + 1 );
- sign = -sign;
- >
- printf( «%0.8f» , 4 * sum);
Задача J. Сумма степеней
Вычислите 1+2+2 2 +2 3 +…+2 N . N – натуральное, не превосходит 30.
- const int osn = 2;
- int n;
- cin >> n;
- int step = 1, sum = 1;
- for ( int i = 1 ; i
- step *= osn;
- sum += step;
- >
- cout
- int n;
- cin >> n;
- int step = 1, sum = 1;
- for ( int i = 1 ; i
- step
- sum += step;
- >
- cout
Задача K. 1/0!+1/1!+1/2!+.
По данному натуральному числу N найдите сумму чисел 1+1/1!+1/2!+1/3!+. +1/N!. Количество действий должно быть пропорционально N.
- int n;
- cin >> n;
- int step = 1, sum = 1;
- for ( int i = 1 ; i
- step
- sum += step;
- >
- cout
1 комментарий:
Источник: cpptasksolver.blogspot.com
прикладная математика
помогите плиз!!
Задание: составить программу для проведения математических вычислений; все исходные данные, необходимые для
вычислений, вводить с клавиатуры.
По координатам трех точек на плоскости вычислить радиус
окружности, проходящей через эти точки.
Программа должна после запуска на исполнение выводить
информацию об авторе, назначении программы (приводится
лабораторное задание полностью), перед запросом ввода данных с
клавиатуры обязательно должно быть сообщение о типе и количестве
вводимых данных.
Программу составить в Free Pascal
uses crt;
function D(x1,y1,x2,y2:real):real;
begin
D:=sqrt(sqr(x1-x2)+sqr(y1-y2));
end;
var x1,y1,x2,y2,x3,y3,d1,d2,d3,s,r:real;
begin
clrscr;
writeln(‘Введите координаты вершин треугольника’);
writeln(‘Вершина 1’);
write(‘x=’);readln(x1);
write(‘y=’);readln(y1);
writeln(‘Вершина 2’);
write(‘x=’);readln(x2);
write(‘y=’);readln(y2);
writeln(‘Вершина 3’);
write(‘x=’);readln(x3);
write(‘y=’);readln(y3);
s:=abs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3))/2;
if s=0 then write(‘Окружность построить нельзя’)
else
begin
d1:=D(x1,y1,x2,y2);
d2:=D(x2,y2,x3,y3);
d3:=D(x3,y3,x1,y1);
r:=d1*d2*d3/4/s;
write(‘Радиус описанной окружности=’,r:0:2);
end;
readln
end.
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
Тема: Циклы while. do и repeat. until.
Задание: Написать две программы, которые выводят на экран заданный
набор символов. Одна программа должна использовать только цикл
while…do, а другая — только цикл repeat…until. Массивы и строки не
применять.
Добавлено (21.11.12, 17:50)
———————————————
Тема: Цикл с параметром, символьный (литерный) тип данных.
Задание: Написать программу при помощи операторов цикла for (без
применения массивов) для распечатки на экране монитора указанного в
варианте набора символов.
F
EF
DEF
CDEF
BCDEF
ABCDEF
Добавлено (21.11.12, 17:57)
———————————————
Тема: ветвление программы (использование условных операторов и оператора
выбора).
Задание: используя оператор условия (if … then), составить программу для
вычисления составной (сложной) функции, имеющей различный вид на
разных участках аргумента. С помощью оператора выбора (case) указать на
каком отрезке находится введенное с клавиатуры значение аргумента, и
вывести значение функции в данной точке.
Функция Участки аргумента
y1= 7sin(x) – 1 y2=(x+1)*(x2+1)-1 – 0.5 y3=1.2sin(2x) 0.5 y4=-(x-0.6)2+1.25 1
P.S: там где у1, 7 в степени sin(x)
Ув. программисты пожалуйста помогите решить 5 задачи. Я дуб дубом в информатике и ничего в ней не понимаю. Заранее благодарна.
1)По данному действительному числу a и натуральному n вычислите сумму 1+a+a2+. +an, не используя формулу суммы геометрической прогрессии. Время работы программы должно быть пропорционально n.
2)По данному числу n вычислите сумму 1+1/22+1/32+. +1/n2.Вводится одно число n, не превосходящее 100000.Необходимо вывести значение суммы.
3)По данному числу n вычислите сумму 4(1-1/3+1/5-1/7+. +(-1)n/(2n+1)).
4)Вычислите 1+2+22+23+…+2 N. N – натуральное, не превосходит 30
5)По данному натуральному числу N найдите сумму чисел 1+1/1!+1/2!+1/3!+. +1/N!. Количество действий должно быть пропорционально N.
Quote ( vil_99 )
Тема: Циклы while. do и repeat. until.
Задание: Написать две программы, которые выводят на экран заданный
набор символов. Одна программа должна использовать только цикл
while…do, а другая — только цикл repeat…until. Массивы и строки не
применять.
pred(); в помощь)
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
Quote ( ksushka2307 )
Тема: ветвление программы (использование условных операторов и оператора
выбора).
Задание: используя оператор условия (if … then), составить программу для
вычисления составной (сложной) функции, имеющей различный вид на
разных участках аргумента. С помощью оператора выбора (case) указать на
каком отрезке находится введенное с клавиатуры значение аргумента, и
вывести значение функции в данной точке.
Функция Участки аргумента
y1= 7sin(x) – 1 y2=(x+1)*(x2+1)-1 – 0.5 y3=1.2sin(2x) 0.5 y4=-(x-0.6)2+1.25 1
P.S: там где у1, 7 в степени sin(x)
«Спасибо» принимается в виде повышения репутации ( Зелёный плюсик:) ).Спасибо
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
Quote ( vil_99 )
1)По данному действительному числу a и натуральному n вычислите сумму 1+a+a2+. +an, не используя формулу суммы геометрической прогрессии. Время работы программы должно быть пропорционально n.
var
sum,a,n,i:integer;
begin
read(a,n);
sum:=1;
for i:=1 to n do
sum:=sum+a*i;
writeln(sum);
end.
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
function factorial(x:integer):integer;
var
i,fact:integer;
begin
fact:=1;
for i:=1 to x do
fact:=fact*i;
factorial:=fact;
end;
var
i,n:integer;
sum:real;
begin
sum:=0;
read(n);
for i:=1 to n do
sum:=sum+1/factorial(i);
writeln(sum);
end.
«Спасибо» принимается в виде повышения репутации ( Зелёный плюсик:) ).Спасибо
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
Тема: Обработка одномерных массивов.
Задание: Заполните один или несколько одномерных массивов. Распечатайте
результат заполнения. Проведите преобразование и упорядочивание
(сортировку) массивов. Распечатайте результирующие массивы. Сортировки
проведите тремя методами. При использовании каждого из методов
желательно использовать свой массив. Если количество массивов меньше
трех, то один из массивов перед сортировкой надо скопировать в
дополнительный массив и провести также и его сортировку.
Дан массив содержащий текст. Среди литер текста особую роль играет
знак # , появление которого означает отмену стоящей перед ним буквы,
несколько знаков # означает отмену аналогичного числа букв. Создать массив
заполненный текстом из первого массива с учетом роли этого знака.
(ХЭ#E##НЕLO#LO = HELLO). Произвести сортировку полученных массивов.
Для контроля результата сделать распечатку массивов, в том числе исходного.
Добавлено (26.11.12, 22:07)
———————————————
Тема: Обработка двумерных массивов.
Вариант задания тот же, что и для предыдущей работы, отличие состоит в
том, что необходимо обработать несколько одномерных массивов
объединенных в двумерный массив.
Источник: primat.org