Сложные задачи по программированию егэ - Помощь в подготовке к экзаменам и поступлению

На уроке рассмотрено решение 25 задания ЕГЭ по информатике: дается подробное объяснение и разбор заданий демонстрационных вариантов и досрочных экзаменов

Содержание:

Объяснение задания 25 ЕГЭ по информатике
- Алгоритмизация и программирование
Решение 25 заданий ЕГЭ по информатике
- Делители числа
- Простые числа
Задания прошлых лет для тренировки (до 2021)
- Задачи с поэлементной обработкой массива
- Задачи на обработку элементов массива с последующей заменой
- Задачи на обработку пар элементов массива (два подряд идущих)
- Задачи на обработку трёх подряд идущих элементов массива (тройки элементов массива)
- Задачи на поиск максимума, минимума элементов массива и другие
Решение 25 заданий ЕГЭ по информатике: более сложные задания

25-е задание: «Программная обработка целочисленной информации»

Уровень сложности

— высокий,

Требуется использование специализированного программного обеспечения

— да,

Максимальный балл

— 2,

Примерное время выполнения

— 20 минут.

Проверяемые элементы содержания: Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации

Рекомендации по выполнению:

«В этом задании требуется написать фрагмент программы, реализующий простую обработку целочисленного массива. У экзаменуемых, хорошо освоивших технику программирования, это задание обычно не вызывает серьёзных затруднений, поскольку алгоритм обработки массива не относится к сложным»

Типичные ошибки и рекомендации по их предотвращению:

«в цикле происходит выход за границу массива;

не инициализируется или неверно инициализируется искомое значение;

исходный массив не изменяется;

изменяются не все требуемые элементы (например, только первый или последний из них);

отсутствует вывод ответа, или ответ выводится не полностью (например, только один элемент массива ввиду пропущенного цикла вывода элементов или операторных скобок);

используется переменная, не объявленная в разделе описания переменных;

не указано или неверно указано условие завершения цикла»

«Часто бывает, что увлекшись написанием решения, экзаменуемый совершает ошибки в простых ситуациях: организация ввода-вывода, описание и инициализация переменных, обработка массива (выход за границу) и т.д. Эти ошибки могут стоить Вам нескольких баллов, старайтесь их не допускать»

ФГБНУ «Федеральный институт педагогических измерений»

Алгоритмизация и программирование

Для решения задания требуется вспомнить темы:

Одномерные массивы.
Двумерные массивы.

Решение 25 заданий ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Делители числа

25_7:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [126849; 126871], числа, имеющие ровно 4 различных делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке возрастания.

✍ Решение:

PascalABC.net:

begin
  var divCount := 4;
  for var n := 126849 to 126871 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to n do
      if n mod d = 0 then begin
        divs.Add(d);      
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.

Python:

for n in range(126849,126871+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        print(*divs)

С++:

✎ Решение (оптимизированный вариант):

Будем использовать оптимизированный вариант программы, подходящий для «медленных» компьютеров. Для этого перебор делителей для числа n будем выполнять от 2 до √n, округлив его до ближайшего целого числа (не включая точный квадратный корень, если он существует):

вместо диапазона делителей [1; число]
использовать диапазон [1; округл(√n)]

При переборе делителей будем определять: если делитель – это точный квадратный корень(n), то в список делителей добавлять будем только сам делитель, если нет – то добавляем пару делителей (делитель и n // делитель):

Пример:
число 8 = 2 * 4
Достаточно рассмотреть цикл от 2 до округл(√8) (=2)
если 8 делится на 2 и 8/2 не равно 2, то делители: 2 и 4 (8/2)

PascalABC.net:

begin
  var divCount := 4;
  for var n := 126849 to 126871 do
  begin
    var divs := new List<integer>;
    var d := 1;
    while d * d <= n do  // можно цикл for var d := 1 to round(sqrt(n)) do
    begin
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
      d := d+1;
    end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.

Python:

# import math # для квадратного корня числа (sqrt)
divCount = 4  # нужное количество делителей
for n in range(126849,126871 + 1):
  divs = [] # чистим список делителей
  d = 1
  #  вместо while можно цикл for d in range(1,round(math.sqrt(n))):
  while d*d <= n: # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d: # если делитель - не точный квадратный корень n
        divs.append(n//d)
      if len(divs) > divCount: break
    d+=1
  if len(divs) == divCount:
    divs.sort()
    print(divs)

С++:

✎ Решение: Генерация списка делителей.
Общая идея:

Для каждого числа указанного диапазона генерируем список делителей.
Если длина списка равна четырем, выводим его.

PascalABC.net:	Python: for n in range(126849, 126871+1): divs = [d for d in range(1, n+1) if n % d == 0] if len(divs) == 4: print( *divs )
С++:

Ответ:

1 3 42283 126849
1 47 2699 126853
1 5 25373 126865
1 293 433 126869

25_8:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [164700; 164752], числа, имеющие ровно 6 различных делителей.
Выведите эти делители для каждого найденного числа в порядке возрастания.

✍ Решение:

PascalABC.net:

begin
  var divCount := 6;
  for var n := 164700 to 164752 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to round(sqrt(n)) do
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.

Python:

import math # для квадратного корня sqrt
divCount = 6  # нужное количество делителей
for n in range(164700, 164752 + 1):
  divs = [] # чистим список делителей
  for d in range(1,round(math.sqrt(n))): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d:
        divs.append(n//d)
      if len(divs) > divCount: break
  if len(divs) == divCount:
    divs.sort()
    print(divs)

С++:

✎ Решение: Генерация списка делителей.
Общая идея:

Для каждого числа указанного диапазона генерируем список делителей.
Если длина списка равна четырем, выводим его.

PascalABC.net:	Python: for n in range(164700, 164752+1): divs = [d for d in range(1, n+1) if n % d == 0] if len(divs) == 6: print( *divs )
С++:

Ответ:

1 2 4 41177 82354 164708
1 3 9 18301 54903 164709
1 2 4 41179 82358 164716
1 2 4 41183 82366 164732

25_9:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [190201; 190230], числа, имеющие ровно 4 различных делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке убывания.

✍ Решение:

PascalABC.net:

begin
  var divs := new integer[4];
  for var n := 190201 to 190230 do
  begin
    var i := 0; // для индекса массива
    for var d := 1 to n do
    begin
      if n mod d = 0 then 
      begin
        if i < 4 then
          divs[i] := d;
        inc(i);
      end;
      if i > 4 then 
        break; 
    end;
    if i = 4 then begin
      println(divs.Reverse())
    end;
  end;
end.

Python:

for n in range(190201,190230+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        divs.reverse()
        print(*divs)

С++:

✎ Решение (оптимизированный вариант):

PascalABC.net:

begin
  var divCount := 4;
  for var n := 190201 to 190230 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to round(sqrt(n)) do
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      divs.Reverse();
      Println(divs);
    end;
  end;
end.

Python:

import math # для квадратного корня sqrt
divCount = 4  # нужное количество делителей
for n in range(190201, 190230 + 1):
  divs = [] # чистим список делителей
  for d in range(1,round(math.sqrt(n))): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d:
        divs.append(n//d)
      if len(divs) > divCount: break
  if len(divs) == divCount:
    divs.sort()
    divs.reverse()
    print(divs)

С++:

✎ Решение: Генерация списка делителей.
Общая идея:

Для каждого числа указанного диапазона генерируем список делителей.
Если длина списка равна четырем, выводим его.

PascalABC.net:	Python: for n in range(190201, 190230+1): divs = [d for d in range(1, n+1) if n % d == 0] if len(divs) == 4: divs.reverse() # реверсируем (по убыванию) print( *divs )
С++:

Ответ:

190201 17291 11 1
190202 95101 2 1
190214 95107 2 1
190219 853 223 1
190222 95111 2 1
190223 17293 11 1
190227 63409 3 1
190229 14633 13 1

Видеоразбор задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

25_10:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [190201; 190280], числа, имеющие ровно 4 различных ЧЁТНЫХ делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке убывания.

✍ Решение:

PascalABC.net:

begin
  var divs := new integer[4];
  for var n := 190201 to 190280 do
  begin
    var i := 0; // для индекса массива
    for var d := 1 to n do
    begin
      if (n mod d = 0) and (d mod 2 = 0) then 
      begin
        if i < 4 then
          divs[i] := d;
        inc(i);
      end;
      if i > 4 then 
        break; 
    end;
    if i = 4 then begin
      println(divs.Reverse())
    end;
  end;
end.

Python:

for n in range(190201,190280+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0 and d%2==0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        divs.reverse()
        print(*divs)

С++:

✎ Решение: Генерация списка делителей.

Общая идея:

Для каждого числа указанного диапазона генерируем список делителей.
Если длина списка равна четырем, выводим его.

PascalABC.net:	Python: for n in range(190201, 190280+1): divs = [d for d in range(1, n+1) if n % d == 0 and d % 2 == 0] if len(divs) == 4: divs.reverse() print( *divs )
С++:

Ответ:

190226 838 454 2
190234 17294 22 2
190238 2606 146 2
190252 95126 4 2
190258 758 502 2
190274 27182 14 2
190276 95138 4 2

25_11:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [394441; 394505], числа, имеющие максимальное количество различных делителей. Если таких чисел несколько, то найдите минимальное из них.
Выведите количество делителей найденного числа и два наибольших делителя в порядке убывания.

✍ Решение:

PascalABC.net:

begin
  var max := 0;
  var divsMax := new List<integer>; 
  for var n := 394441 to 394505 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to n do
      if n mod d = 0 then 
        divs.Add(d);      
    if divs.Count > max then 
    begin
      max := divs.Count;
      divsMax := divs;
    end;
  end;
  divsMax.Reverse();
  print(max, divsMax[0], divsMax[1])
end.

Python:

maxim = 0  # нужное количество делителей
divsMax = []
for n in range(394441, 394505 + 1):
  divs = [] # чистим список делителей
  for d in range(1,n+1): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
  if len(divs) > maxim: 
    maxim = len(divs)
    divsMax = divs
divsMax.reverse()
print(maxim,divsMax[0],divsMax[1])

С++:

✎ Решение (Генерация списка делителей):

PascalABC.net:

Python:

maxim=0
divsmax=[]
for n in range(394441, 394505+1):
    divs = [d for d in range(1, n+1) if n % d == 0] 
    if len(divs) > maxim:
        maxim = len(divs)
        divsmax = divs # сохраняем делители для числа с макс кол-вом дел-ей
divsmax.reverse()
print(maxim, divsmax[0], divsmax[1])

С++:

Ответ: 48 394450 197225

Видео

Простые числа

25_12:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [3532000; 3532160], простые числа.
Выведите все найденные простые числа в порядке убывания, слева от каждого числа выведите его номер по порядку.

✍ Решение:

PascalABC.net:

begin
  var count := 0;
  for var n := 3532160 downto 3532000 do // цикл с конца 
  begin
    var flag := true; 
    for var d := 2 to n - 1 do // перебор делителей, начиная с двух до n-1
    begin
      if n mod d = 0 then begin // есть делитель помимо единицы и самого n
        flag := false; // число не простое     
        break;
      end;
    end;
    if flag = true then // если число простое
    begin
      inc(count);
      Println(count, n);
    end;
  end;
end.

Python:

count = 0
for n in range(3532160, 3532000-1, -1): # цикл с конца и с шагом (-1) 
  flag = True
  for d in range(2, n): # перебор делителей, начиная с двух
    if n % d == 0: # есть делитель помимо единицы и самого n
      flag = False # число не простое
      break
  if flag == True: # число простое
    count+=1
    print(count , n)

С++:

✎ Решение (оптимизированный вариант):

PascalABC.net:

begin
  var count := 0;
  for var n := 3532160 downto 3532000 do // цикл с конца 
  begin
    var flag := true; 
    var d := 2;
    while d * d <= n - 1 do // перебор делителей, начиная с двух
    begin
      if n mod d = 0 then begin // есть делитель помимо единицы и самого n
        flag := false;  // число не простое    
        break;
      end;
      d := d + 1;
    end;
    if flag = true then // если число простое
    begin
      inc(count);
      Println(count, n);
    end;
  end;
end.

Python:

count = 0
for n in range(3532160, 3532000-1, -1): # цикл с конца и с шагом (-1) 
      flag = True
      d = 2
      while d*d <= n-1: # перебор делителей, начиная с двух
            if n % d == 0: # есть делитель помимо единицы и самого n
                  flag = False # число не простое
                  break
            d+=1
      if flag == True: # число простое
            count+=1
            print(count , n)

С++:

Ответ:

Задания прошлых лет для тренировки (до 2021)

Задачи с поэлементной обработкой массива

25_1: ЕГЭ по информатике 2017 года (один из вариантов со слов выпускника):

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество элементов массива НЕ кратных 3.

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но использовать все описанные переменные не обязательно.

const N = 20;
var i,j,k:integer;
a:array [1..N] of integer; 
begin
for i:=1 to N do 
  readln(a[i]); 
…
end.

✍ Решение:

Рассмотрим заданный фрагмент решения:

в цикле со счетчиком i запрашиваются значения элементов массива, т.е. формируется массив;
из постановки задания видим, что необходимо найти количество чего-то, это значит, что нужно использовать переменную счетчик;
объявлены три целочисленных переменных: i, j, k; переменная i использована в первом цикле, значит для счетчика можно взять переменную k;
счетчик всегда нужно обнулять, поэтому следующим оператором будет:
определим, количество чего нам необходимо считать: количество элементов массива не кратных 3. Кратность можно определить через остаток от деления: если значение элемента массива при делении на 3 в остатке не возвращает 0, значит элемент не кратен трем;
остаток при делении в паскале — оператор mod. Поскольку необходимо просмотреть каждый элемент массива, то это нужно делать в цикле for;
переменная i уже использована в первом цикле for, значит, для очередного цикла возьмем неиспользованную переменную j:

for j:=1 to N do
  if a[j] mod 3 <> 0 then

если условие истинно (т.е. нашелся элемент массива, не кратный трем), то увеличиваем счетчик:
после цикла остается вывести значение счетчика, т.е. вывести количество элементов массива не кратных 3:

Результат:

k:=0;
for j:=1 to N do
  if a[j] mod 3 <> 0 then
    inc(k);
writeln(k);

Смотрите видео с подробным объяснением и разбором данного 25 задания:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

Задачи на обработку элементов массива с последующей заменой

25_3: Решение 25 задания ЕГЭ по информатике Демоверсия 2018:

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на одном из языков программирования алгоритм, который находит количество элементов массива, больших 100 и при этом кратных 5, а затем заменяет каждый такой элемент на число, равное найденному количеству. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести измененный массив, каждый элемент массива выводится с новой строчки.

Например, для массива из шести элементов: 4 115 7 195 25 106
программа должна вывести числа 4 2 7 2 25 106

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Паскаль:

const
N = 30;
var
a: array [1..N] of longint;
i, j, k: longint;
begin
	for i := 1 to N do
		readln(a[i]);
	...
end.

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.

Похожие задания для тренировки

✍ Решение:

k := 0;
for i := 1 to N do
	if (a[i] > 100) and (a[i] mod 5 = 0) then
		k:=k+1;
for i := 1 to N do begin
	if (a[i] > 100) and (a[i] mod 5 = 0) then
		a[i] := k;
writeln(a[i])
end

25_6:

Дан массив, содержащий неотрицательные целые числа. Необходимо вывести:

максимальный чётный элемент, если количество чётных элементов не меньше, чем нечётных;

максимальный нечётный элемент, если количество нечётных эле-ментов больше, чем чётных.

Например, для массива из шести элементов: 4 6 12 17 3 8
ответом будет 12 — наибольшее чётное число, поскольку чётных чисел в этом массиве больше

Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Python:

# допускается также использовать
# целочисленные переменные j, k, m
a = []
n = 2000 // менять значение n нельзя
for i in range(0, n):
  a.append(int(input()))

✍ Решение:

a = []
n = 2000 // менять значение n нельзя
for i in range(0, n):
    a.append(int(input()))
j = 0 
k = 0 
m = 0 
for i in range(0, n):
	if a[i]%2 == 0:
		j+=1
	else:
		k+=1
if k>j:
	j = 0
	for i in range(0, n):
		if a[i]>j and a[i] % 2 != 0:
			j = a[i]
	print(j)
else:
	for i in range(0, n):
		if a[i]>m and a[i] % 2 == 0:
			m = a[i]
	print(m)

Задачи на обработку пар элементов массива (два подряд идущих)

25_4:

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых одно из чисел двузначное. В данной задаче под парой подразумевается два подряд идущих элемента массива.

Например, для массива из семи элементов: 13; 323; 12; 33; 117 — ответ: 4.

const
  N = 40;
var
  a: array [1..N] of integer;
  i, j, k: integer;
begin
  for i := 1 to N do 
    readln(a[i]);
  ...
end.

✍ Решение:

k := 0;
for i := 1 to N - 1 do
 if ((a[i] < 100) and (a[i] > 9)) or ((a[i + l] < 100) and (a[i + 1] > 9)) then 
      inc(k);
writeln(k);

25_5:

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от -10 000 до 10 000 включительно. Опишите алгоритм, позволяющий найти и вывести количество пар элементов массива, в которых сумма элементов делится на 2, но не делится на 4. В данной задаче под парой подразумевается два подряд идущих элемента массива.

Python:

#  допускается также использовать
#  две целочисленные переменные
#  j и k
a = []
n = 20
for i in range(0, n):
  a.append(int(input()))

✍ Решение:

В первой строчке кода объявляется список а. Дальше, идет объявление переменной n = 20, она отвечает за размер массива.

При решении такого рода задач, необходимо помнить, что массив в Python — это список и это динамический тип данных. Кроме того, нумерация элементов массива начинается с 0.

Ниже мы видим инициализацию списка а. Мы должны дописать код дальнейшей программы, который последует после заполнения списка пользователем.
Итак, по условию мы должны находить пары элементов, сумма которых делится на 2, но не делится на 4, причем парами считаются соседние элементы, например: a[0] и a[1], a[1] и a[2].
Мы можем узнать, делится ли данный элемент на число, если остаток от деления на него равен 0, и не делится — в противном случае. Тогда сумма соседних элементов при делении на 2 должна давать остаток 0, а при делении на 4 наоборот — отличный от 0.
Введем цикл, который будет перебирать все элементы массива, считать сумму соседей и проверять истинность условия.

for i in range(0, n-1):
    j = a[i] + a[i+1]
    if j%2 == 0 and j%4 != 0:

Так как мы рассматриваем элемент a[i + 1], значит, цикл должен работать до n — 1, чтобы не выйти за границы диапазона массива.

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

...
 if j%2 == 0 and j%4 != 0:
        k+=1

Мы добавили допустимую переменную j, чтобы условный оператор выглядел компактнее.
Однако задача еще не решена. Во-первых, мы должны до цикла инициализировать счетчик k = 0. Так как иначе Python выдаст ошибку.

Дело в том, что мы пытаемся присвоить переменной k его же значение, но на 1 больше, но интерпретатор «не встречал» раньше переменной k, из-за чего возникает ошибка.

Кроме того, добавим вывод результата после цикла.
Таким образом, правильный вариант с учетом доработок:

a = []
n = 20
for i in range(0, n):
  a.append(int(input()))
k = 0
for i in range(0, n - 1):
    j = a[i] + a[i + 1]
    if j%2 == 0 and j%4 != 0:
        k += 1
print(k)

Задачи на обработку трёх подряд идущих элементов массива (тройки элементов массива)

25_2:

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество троек элементов массива, состоящих из равных между собой чисел. В данной задаче под тройкой подразумевается три подряд идущих элемента массива.

Например, для массива из семи элементов: 2; 2; 2; 4; 4; 4; 4 — ответ: 3.

const
  N=40;
var
  a: array[1..N] of integer;
  i, j, k:integer;
begin
  for i:=1 to N do
    readln(a[i]);
  ...
end.

✍ Решение:

из постановки задания видим, что необходимо искать количество чего-то, это значит, что нужно использовать переменную счетчик; возьмем для нее объявленную переменную k;
счетчик всегда нужно сначала обнулять, поэтому следующим оператором будет:
определим, количество чего нам необходимо считать: количество троек элементов массива, состоящих из равных между собой чисел. Т.е. необходимо сравнивать между собой каждые три подряд идущих элемента массива, например так:

if (a[i]=a[i+1]) and (a[i]=a[i+2]) then
    inc(k);

inc(k) — оператор, увеличивающий счетчик k на единицу;
условие необходимо выполнять в цикле, так как нужно проверить все элементы массива; цикл со счетчиком необходимо организовать от 1 до N-2, в противном случае индексы элементов a[i+2] выйдут за границы диапазона массива (например, при i = 40, получим … a[40+2], а 42-го элемента массива не существует, поэтому цикл надо делать до i = 38, т.е. N-2).

Результат:

for i:=1 to N-2 do
    if (a[i]=a[i+1]) and (a[i]=a[i+2]) then
      inc(k);
writeln(k);

Более подробное объяснение предлагаем посмотреть на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

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

Источник

Всего: 526 1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 365 S = S + 36 N = N + 7 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 365 do     begin         s := s + 36;         n := n + 7     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 365)     {         s = s + 36;         n = n + 7;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 365     s := s + 36     n := n + 7 кц вывод n кон
Python
n = 0 s = 0 while s <= 365:     s += 36     n += 7 print(n)

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

Бейсик	Python
DIM S, N AS INTEGER S = 80 N = 0 WHILE S + N < 150 S = S − 5 N = N + 15 WEND PRINT N	s = 80 n = 0 while s + n < 150:     s = s − 5     n = n + 15 print(n)
Паскаль	Алгоритмический язык
var s, n: integer; begin     s := 80;     n := 0;     while s + n < 150 do     begin         s := s − 5;         n := n + 15;     end;     writeln(n) end.	алг нач     цел s, n     s := 80     n := 0     нц пока s + n < 150         s := s − 5         n := n + 15     кц     вывод n кон
Си++
#include <iostream> using namespace std; int main() {     int s = 80, n = 0;     while (s + n < 150) {         s = s − 5;         n = n + 15;     }     cout << n;     return 0; }

Источник: ЕГЭ по информатике 28.05.2018. Основная волна, вариант А. Имаева — «Котолис».

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 365 S = S + 33 N = N + 10 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 365 do     begin         s : = s + 33;         n : = n + 10     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 365)     {         s = s + 33;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n : = 0 s : = 0 нц пока s <= 365     s : = s + 33     n : = n + 10 кц вывод n кон
Python
n = 0 s = 0 while s <= 365:     s += 33     n += 10 print(n)

Определите, что будет напечатано в результате выполнения следующей программы (записанной ниже на разных языках программирования):

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 While S <= 365 S = S + 36 N = N + 5 WEND PRINT N	var n, s : integer; begin     n := 0;     s := 0;     while s <= 365 do     begin         s := s + 36;         n := n + 5     end;     write(n); end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main () {     int n, s;     n = 0;     s = 0;     while (s <= 365)     {         s = s + 36;         n = n + 5;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 365     s := s + 36;     n := n + 5; кц вывод n кон
Python
n = 0 s = 0 while s <= 365:     s += 36     n += 5 print(n)

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 While S <= 365 S = S + 36 N = N + 10 WEND PRINT N	var n, s : integer; begin     n := 0;     s := 0;     while s <= 365 do     begin         s := s + 36;     n := n + 10     end;     write(n); end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main () {     int n, s;     n = 0;     s = 0;     while (s <= 365)     {         s = s + 36;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 365     s := s + 36;     n := n + 10; кц вывод n кон
Python
n = 0 s = 0 while s <= 365:     s += 36     n += 10 print(n)

Бейсик	Паскаль
DIM N, S AS INTEGER N = 30 S = 25 WHILE S < 425 S = S + 40 N = N + 10 WEND PRINT N	var n, s: integer; begin     n : = 30;     s : = 25;     while s < 425 do     begin         s : = s + 40;         n : = n + 10     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 30;     s = 25;     while (s < 425)     {         s = s + 40;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n : = 30 s : = 25 нц пока s < 425     s : = s + 40     n : = n + 10 кц вывод n кон
Python
n = 30 s = 25 while s < 425:     s += 40     n += 10 print(n)

Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования):

Бейсик	Паскаль
DIM N, S AS INTEGER N = 60 S = 25 WHILE S < 365 S = S + 20 N = N + 10 WEND PRINT N	var n, s: integer; begin     n : = 60;     s : = 25;     while s < 365 do     begin         s : = s + 20;         n : = n + 10     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 60;     s = 25;     while (s < 365)     {         s = s + 20;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n : = 60 s : = 25 нц пока s < 365     s : = s + 20     n : = n + 10 кц вывод n кон
Python
n = 60 s = 25 while s < 365:     s += 20     n += 10 print(n)

Определите число, которое будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования):

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 257     S = S + 10     N = N + 3 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 257 do     begin         s := s + 10;         n := n + 3     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 257)     {         s = s + 10;         n = n + 3;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 257         s := s + 10         n := n + 3     кц вывод n кон
Python
n = 0 s = 0 while s <= 257:     s += 10     n += 3 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 1.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 257     S = S + 25     N = N + 4 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 257 do     begin         s : = s + 25;         n : = n + 4     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 257)     {         s = s + 25;         n = n + 4;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 257         s : = s + 25         n : = n + 4     кц вывод n кон
Python
n = 0 s = 0 while s <= 257:     s += 25     n += 4 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 2.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 325     S = S + 10     N = N + 3 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 325 do     begin         s : = s + 10;         n : = n + 3     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 325)     {         s = s + 10;         n = n + 3;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 325         s : = s + 10         n : = n + 3     кц вывод n кон
Python
n = 0 s = 0 while s <= 325:     s += 10     n += 3 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 1.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 257     S = S + 10     N = N + 3 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 257 do     begin         s : = s + 10;         n : = n + 3     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 257)     {         s = s + 10;         n = n + 3;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 257         s : = s + 10         n : = n + 3     кц вывод n кон
Python
n = 0 s = 0 while s <= 257:     s += 10     n += 3 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 5.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 249     S = S + 24     N = N + 3 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 249 do     begin         s : = s + 24;         n : = n + 3     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 249)     {         s = s + 24;         n = n + 3;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 249         s : = s + 24         n : = n + 3     кц вывод n кон
Python
n = 0 s = 0 while s <= 249:     s += 24     n += 3 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Сибирь. Вариант 3.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 256     S = S + 25     N = N + 5 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 256 do     begin         s : = s + 25;         n : = n + 5     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 256)     {         s = s + 25;         n = n + 5;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 256         s : = s + 25         n : = n + 5     кц вывод n кон
Python
n = 0 s = 0 while s <= 256:     s += 25     n += 5 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 2.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 512     S = S + 25     N = N + 4 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 0;     while s <= 512 do     begin         s : = s + 25;         n : = n + 4     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 512)     {         s = s + 25;         n = n + 4;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 0     нц пока s <= 512         s : = s + 25         n : = n + 4     кц вывод n кон
Python
n = 0 s = 0 while s <= 512:     s += 25     n += 4 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 3.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 512 WHILE S > 0     S = S — 25     N = N + 4 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 512;     while s > 0 do     begin         s : = s — 25;         n : = n + 4;     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 512;     while (s > 0)     {         s = s — 25;         n = n + 4;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 512     нц пока s > 0         s : = s — 25         n : = n + 4     кц вывод n кон
Python
n = 0 s = 512 while s > 0:     s -= 25     n += 4 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Центр. Вариант 2.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 256 WHILE S > 0     S = S — 25     N = N + 3 WEND PRINT N	var n, s: integer; begin     n : = 0;     s : = 256;     while s > 0 do     begin         s : = s — 25;         n : = n + 3;     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; void main() {     int n, s;     n = 0;     s = 256;     while (s > 0)     {         s = s — 25;         n = n + 3;     }     cout « n « endl; }	алг нач цел n, s     n : = 0     s : = 256     нц пока s > 0         s : = s — 25         n : = n + 3     кц вывод n кон
Python
n = 0 s = 256 while s > 0:     s -= 25     n += 3 print(n)

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Центр. Вариант 3.

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 325 S = S + 10 N = N + 3 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 325 do     begin         s := s + 10;         n := n + 3     end;     write (n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main () {     int n, s;     n = 0;     s = 0;     while (s <= 325)     {         s = s + 10;         n = n + 3;     }     cout « n « endl; }	алг нач целn, s n := 0 s := 0 нц пока s <= 325     s := s + 10     n := n + 3 кц вывод n кон
Python
n = 0 s = 0 while s <= 325:     s += 10     n += 3 print(n)

Источник: Демонстрационная версия ЕГЭ—2014 по информатике.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 365 S = S + 36 N = N + 8 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 365 do     begin         s := s + 36;         n := n + 8     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 365)     {         s = s + 36;         n = n + 8;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 365     s := s + 36     n := n + 8 кц вывод n кон
Python
n = 0 s = 0 while s <= 365:     s += 36     n += 8 print(n)

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

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 267 S = S + 25 N = N + 10 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 267 do     begin         s := s + 25;         n := n + 10     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 267)     {         s = s + 25;         n = n + 10;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 267     s := s + 25     n := n + 10 кц вывод n кон
Python
n = 0 s = 0 while s <= 267:     s += 25     n += 10 print(n)

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 501.

Бейсик	Паскаль
DIM N, S AS INTEGER N = 0 S = 0 WHILE S <= 267 S = S + 25 N = N + 20 WEND PRINT N	var n, s: integer; begin     n := 0;     s := 0;     while s <= 267 do     begin         s := s + 25;         n := n + 20     end;     write(n) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 0;     s = 0;     while (s <= 267)     {         s = s + 25;         n = n + 20;     }     cout « n « endl; }	алг нач цел n, s n := 0 s := 0 нц пока s <= 267     s := s + 25     n := n + 20 кц вывод n кон
Python
n = 0 s = 0 while s <= 267:     s += 25     n += 20 print(n)

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 502.

Всего: 526 1–20 | 21–40 | 41–60 | 61–80 …

Источник

1. Правильный алгоритм
2. Эффективность.
2.1. Эффективность по времени.
2.2. Эффективность по памяти.
3. Культура оформления программного кода.

Автор статьи — репетитор-профессионал Лада Борисовна Есакова.

Поговорим о задаче 27 (С4) на ЕГЭ по информатике. Она оценивается следующим образом:

— 4 балла, если написанная программа работает верно, она эффективна и содержит до трех синтаксических ошибок;
— 3 балла, если написанная программа работает верно, она не эффективна по памяти (но эффективна по времени), содержит не более пяти синтаксических ошибок и не более одной смысловой ошибки;
— 2 балла, если написанная программа работает верно, но она неэффективна, содержит не более семи синтаксических ошибок и не более двух смысловых ошибок;
— 1 балл, если программа не написана или работает неверно, однако алгоритм решения описан правильно.

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

Давайте выделим основные моменты в решении этой самой сложной задачи.

к оглавлению ▴

1. Правильный алгоритм

До того, как начать программировать, мы должны хорошо понять, что собственно мы собираемся запрограммировать. Причем продумать алгоритм нужно до мелочей, учесть все возможные варианты поведения программы. После этого обязательно подробно и понятно записать алгоритм на простом языке, в виде блок-схемы или в виде таблицы. Кому как удобнее. Это описание будет нашей путеводной нитью при разработке программы. А заодно мы заработаем 1 балл.
Я настойчиво рекомендую подробно описывать алгоритм, даже если Вы уверены в абсолютной правильности программы.

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

к оглавлению ▴

2. Эффективность.

В постановке задачи требуется не просто написать программу, а написать эффективную программу. Давайте разберемся, что же такое эффективность.

Эффективность в данном смысле – это умение экономно расходовать основные ресурсы: память компьютера и время.

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

к оглавлению ▴

2.1. Эффективность по времени.

Наиболее ценным ресурсом в этой задаче считается время. Эффективность по времени расценивается «дороже», чем эффективность по памяти. Как же написать эффективную по времени программу?

Обозначим время выполнения программы T. Допустим, нам нужно последовательно просмотреть в цикле N элементов массива. Тогда время выполнения программы будет прямо пропорционально количеству элементов (T~N).

Если же для каждого из N элементов нам нужно заново просмотреть весь массив (цикл в цикле), то время будет пропорционально квадрату количества элементов.

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

Таким образом, нужно стараться избегать вложенных циклов. Это не всегда возможно. Любая сортировка (например, метод пузырька) обязывает нас использовать цикл в цикле.

к оглавлению ▴

2.2. Эффективность по памяти.

Все, что выполняет наша программа, происходит в памяти компьютера.
Объявляя переменные, мы резервируем ячейки памяти (переменная типа Integer занимает в классическом Паскале 2 байта, переменная типа Real – 6 байт).
Записывая введенные данные в массив или переменные, мы используем память.

Поэтому основные приемы экономии памяти:
— Правильно выбирать тип переменной;
— При возможности не сохранять вводимые данные в массив или переменные, а анализировать сразу при вводе;
— Экономно использовать переменные (если возможно, использовать одну переменную для разных целей).
И опять же, позаботьтесь о проверяющем. После написания программы сделайте анализ эффективности. Объясните, почему вы выбрали такие типы переменных. Укажите, где вы экономно использовали одну и ту же переменную в разных целях. Возможно, Вы сознательно уменьшили эффективность по памяти для увеличения эффективности по времени.

к оглавлению ▴

3. Культура оформления программного кода.

Вы не представляете, какой это кошмар – проверять сухой программный код, никак не описанный, нигде не прокомментированный, использующий безликие переменные a1, a2 и тому подобные.

Способы решения задачи могут быть самые разные, и проверяющему предстоит понять, что же именно делает ваша программа.

Настоятельно рекомендую выполнять следующие правила, которые не добавят Вам лишний балл, но позитивно настроят проверяющего и застрахуют от возможной недооценки вашей работы:
— Используйте имена переменных, указывающие на их назначение. Например, для обозначения переменной, хранящей максимальную сумму можно использовать наименование maxsum, для массива с номерами школ – schoolnum. Только не переусердствуйте! Под счетчики достаточно ввести переменные i, j…

— Форматируйте текст отступами, обозначая начало-конец программных блоков. Такое форматирование избавит Вас от потери закрывающих скобок и упростит чтение текста;

— Используйте комментарии, коротко описывающие основной смысл происходящего.

Выполнив эти несложные требования, Вы гарантированно получите высший балл за самую сложную задачу ЕГЭ по информатике!

Благодарим за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №27. Написание сложной программы.» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ.
Чтобы успешно сдать нужные и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из данного раздела.

Публикация обновлена:
08.03.2023

Источник

Инфоурок

›

Информатика

›Другие методич. материалы›Подготовка к ЕГЭ. Решение сложных задач по программированию.

Подготовка к ЕГЭ. Решение сложных задач по программированию.

Скачать материал

Выберите документ из архива для просмотра:

С2.exe

Сейчас обучается 32 человека из 22 регионов

Сейчас обучается 32 человека из 18 регионов

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

6 155 280 материалов в базе

Выберите категорию:
Выберите учебник и тему

Выберите класс:
Тип материала:
- Все материалы
- Статьи
- Научные работы
- Видеоуроки
- Презентации
- Конспекты
- Тесты
- Рабочие программы
- Другие методич. материалы

Найти материалы

Другие материалы

24.12.2017
925
4

24.12.2017
825
1

24.12.2017
6766
60

24.12.2017
320
0

24.12.2017
214
1

24.12.2017
2618
75

24.12.2017
6725
0

Вам будут интересны эти курсы:

Курс повышения квалификации «Информационные технологии в деятельности учителя физики»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Облачные технологии в образовании»
Курс повышения квалификации «Сетевые и дистанционные (электронные) формы обучения в условиях реализации ФГОС по ТОП-50»
Курс повышения квалификации «Развитие информационно-коммуникационных компетенций учителя в процессе внедрения ФГОС: работа в Московской электронной школе»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»
Курс повышения квалификации «Современные языки программирования интегрированной оболочки Microsoft Visual Studio C# NET., C++. NET, VB.NET. с использованием структурного и объектно-ориентированного методов разработки корпоративных систем»

Настоящий материал опубликован пользователем Дудников Юрий Алексеевич. Инфоурок является
информационным посредником и предоставляет пользователям возможность размещать на сайте
методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них
сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с
сайта, Вы можете оставить жалобу на материал.

Удалить материал
- На сайте: 5 лет и 2 месяца
- Подписчики: 2
- Всего просмотров: 22960
- Всего материалов:
  
  16

Файлы

Рабочий лист подходит для учеников 7 класса, работающих по учебнику «Информатика. ФГОС», автор Л….

Источник

МЕТОДИКА РЕШЕНИЯ ЗАДАЧ ЕГЭ ВЫСОКОГО УРОВНЯ 27 (С4)

Автор: учитель информатики Шахова Е.А., г. Севастополь, ГБОУ «Гимназия №1 им. А.С. Пушкина».

Задача №27 в ЕГЭ является задачей высокого уровня, призванная , прежде всего, проверить умения учащихся на практике составлять и реализовывать эффективные и правильные алгоритмы, составлять программы на языках высокого уровня.

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

Характеристика	Значение
Что проверяется	Умение создавать собственные программы (30–50 строк) для решения задач средней сложности
Требования к проверяемым элементам содержания	Основные этапы разработки программ. Разбиение задачи на подзадачи.
Проверяемые требования к уровню подготовки	Создавать программы на языке программирования по их описанию
Уровень сложности	Высокий
Максимальный балл	4
Примерное время выполнения	55 мин

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

Проанализируем результаты решения этой задачи в 2015-2016 учебном году. Процент выполнения этой задачи представлен в следующей таблице:

Полученные баллы	1	2	3-4	0
Процент участников	7%	3,7%	5,7%	16,2%

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

Итак, как же научиться решать эти задания?

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

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

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

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

Перед тем как говорить о решении задач, вспомним необходимые понятия.

Сложность алгоритмов

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

Основные ресурсы:

время (временнáя сложность) и
объем памяти (ёмкостная сложность).

Наиболее важной характеристикой является время.

Сложность задачи может быть разной для разных входных данных (экземпляров задачи).

Различают сложность в худшем случае и сложность в среднем.

В теории сложности чаще оперируют понятием сложности в худшем случае.

Обычно оценивают порядок роста сложности при n®¥: T = O(f(n)).

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

Например, если сравнивать порядок зависимости времени решения задачи, можно привести данные, представленные в таблице:

Выделим основные типы и темы заданий:

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

Рассмотрим каждый тип задачи отдельно.

Возможная формулировка задания (тип I)

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат:

где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и , а также и разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N=1000.

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

Необходимые знания и умения:

Решение задачи разбиения строки на подстроки по пробелам.

Функции и процедуры (Pascal) : pos, copy, delete, length, insert.

Преобразование строки в число, в цифры.

Функции и процедуры (Pascal) : val, StrToInt (Delphi).

Работа с символами. Функции (Pascal): ord, chr.
Работа с записями (структурами).

Type Rec=record

{поля записи}

F:string[20]; {фамилия}

IO: string[4]; {инициалы}

num: integer;{номер школы}

end;

Подробно останавливаться не будем из-за неактуальности.

Возможная формулировка задания (тип II)

По каналу связи передаются положительные целые числа, не превышающие 1000, – результаты измерений, полученных в ходе эксперимента (количество измерений известно заранее). После окончания эксперимента передаётся контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

1) R — сумма двух различных переданных элементов последовательности («различные» означает, что нельзя просто удваивать переданные числа, суммы различных, но равных по величине элементов допускаются);

2) R — нечётное число.

Если чисел, соответствующих приведённым условиям, нет, считается, что R = –1. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, FreePascal 2.6.4), которая будет проверять правильность контрольного значения.

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:

100

145

Пример выходных данных:

145

Рассмотрим неоптимальное решение полным перебором, которое оценивается в 2 балла.

Организация полного перебора

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

Текст программы (авторский).

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-1 do

for j:=i+1 to n do

begin

R:=a[i]+a[j];

{проверка условия контрольного значения}

if (R then Rmin:=R;

end;

if Rmin=2001 then Rmin:=-1;

writeln(Rmin);

End.

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

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

Как видно, для данного типа задач можно подготовить шаблонное неоптимальное решение на 2 балла.

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

Оптимальное решение.

Если не хранить все числа, то тогда во время ввода данных какие именно хранить?

ИДЕЯ: Хранить в памяти не все введенные ранее числа, а только те, которые «лучше» остальных.

Чтобы сумма была меньше, нужно брать меньшие числа, достаточно хранить только минимальные, удовлетворяющие условию.

Сколько таких чисел хранить и какие должны быть условия?

По условию сумма должна быть наименьшей и кратной трем. Хранить только наименьшее нет смысла, потому как с другим наименьшим оно может не дать нужного остатка при делении на 3.

Вывод: следует хранить все минимальные числа, имеющие разные остатки при делении на 3.

Попытаемся словесно сформулировать алгоритм решения. Назовем парным остатком такой остаток, который в сумме с текущим будет делиться на 3.

Алгоритм оптимального решения

Считываем количество чисел n.

Инициализируем переменные.

Цикл из n итераций

Чтение очередного числа a.

Вычисление его остатка от деления на 3.

Выбираем число, остаток от деления на 3 от которого в сумме с остатком деления a на 3 кратен 3 (парный).

Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.

Если число a меньше минимального, имеющего тот же остаток от деления на 3, запоминаем его.

Если контрольное число не изменилось, запоминаем в него 1.

Вывод контрольного значения.

Программа для оптимального решения

Var R, Rmin: integer;

n, a, I,m1,m2:integer;

b : array[0..2] of integer; {массив, хранящий минимальные значения с разными остатками при делении на 3.}

Begin

Rmin:=2001;

for i:=0 to 2 do b[i]:=1001; // заполняем массив «невозможными» числами

readln(n);

for i:=1 to n do

begin

readln(a);

m1:=(a mod 3); //смотрим остаток от деления на 3

m2:=( 3-m1)mod 3;//смотрим парный остаток от деления на 3

if b[m2]1001 then

begin R:=a+b[m3]; {читаем сумму текущего элемента с минимальным, имеющим парный остаток}

if R

Rmin:=R;

end;

{проверяем, не является ли текущий элемент лучше предыдущего, имеющего такой же остаток }

if a

b[m1]:=a;

end;

if Rmin=2001 then Rmin:=-1; //если сумма не нашлась такая

writeln(Rmin);

End.

Как мы видим, что алгоритм сложнее, но, тем не менее, тоже может быть формализован.

Возможная формулировка задания (тип III)

Для заданной последовательности неотрицательных целых чисел необходимо найти минимальную сумму двух её элементов, номера которых различаются не менее чем на 4. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Задача А (2 балла). Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.

Задача Б (4 балла). Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

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

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности. Гарантируется, что N 4. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередной элемент последовательности. Программа должна вывести одно число – описанную в условии сумму.

Пример входных данных:

7

10

45

55

245

35

25

10

Пример выходных данных :

20

Решение задачи А (не оптимальное)

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

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R : integer;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=2001;

for i:=1 to n-4 do

for j:=i+4 to n do

begin

R:=a[i]+a[j];

if (R) then {проверка условия контрольного значения}

Rmin:=R;

end;

writeln(Rmin);

End.

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

Оптимальное решение

Намного интереснее найти оптимальное решение. Как всегда нужно сформулировать идею.

Рассмотрим следующую последовательность:

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

Если нельзя хранить все введенные ранее числа, то сколько чисел хранить в памяти и какие?

Во-первых, необходимо хранить числа — «кандидаты» в лучшие для составления с новым полученным числом контрольного значения. Эти числа были получены как минимум за 4 (согласно условию задачи) числа до текущего. В текущем примере это только число 4, которое минимально из всех предыдущих чисел.

Во-вторых, необходимо хранить предпоследние 3 числа, которые пока не могут быть использованы для формирования контрольного значения, но могут пригодиться для последующих чисел. В данном случае мы видим, что в красной зоне есть числа 3 и 1, которые меньше 4, и для будущих чисел могут составить лучше пару, но пока еще использоваться не могут.

Внимание: если условие для контрольного значения сложное, «кандидатов» может быть несколько, как в предыдущей задаче.

Сформулируем алгоритм решения.

Алгоритм решения задачи Б

Считываем количество чисел n.

Инициализация переменных, считываем первое число, сохраняем как лучшее.

Считываем 3 числа, запоминаем в массив.

Цикл из n-4 итераций

Чтение очередного числа a.

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

Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее.

Сдвигаем влево на 1 элементы массива.

Запоминаем a в последний элемент массива.

Вывод контрольного значения.

Программа для решения задачи Б

Const delta=4; {минимальный интервал}

Var R :integer; {минимальная сумма}

n, a, m:integer; {количество чисел, очередное значение, лучшее}

b :array[1..delta-1] of integer; {массив промежуточных значений}

Begin

R:=2001;

readln(n);

readln(m); {читаем первое, считаем его «лучшим»}

{ Считываем 3 числа, запоминаем в массив }

for i:=1 to delta-1 do readln(b[i]);

for i:= delta+1 to n do

begin { Чтение очередного числа a}

readln(a);

{Складываем с лучшим. Если их сумма меньше контрольного значения, запоминаем ее как контрольное значение.}

If (m+a)

{Сравниваем первый элемент массива и лучшее, запоминаем из них лучшее}

if b[1]

{Сдвигаем влево на 1 элементы массива}

for j:=1 to delta-2 do b[j]:=b[j+1];

{Запоминаем a в последний элемент массива}

b[delta-1]:=a;

end;

writeln(R);

End.

Модификация задачи (тип III)

Для заданной последовательности положительных целых чисел необходимо найти минимальное, кратное пяти произведение двух её элементов, номера которых различаются не менее чем на 6. Если таких чисел нет, вывести 0.

Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000.

Можно заметить, что задача очень похожа на предыдущую, но появляется дополнительное условие, а именно необходимость кратности пяти произведения. Получается некий симбиоз задачи типа II и типа III. Объединим идеи.

Решение задачи А (не оптимальное)

Var a:array [1..10000] of integer;

n, i, j: integer;

Rmin, R :longint;

Begin

readln(n);

for i:=1 to n do

readln(a[i]);

Rmin:=1000001;

for i:=1 to n-6 do

for j:=i+6 to n do

begin

R:=a[i]+a[j];

if (Rthen

Rmin:=R;

end;

if Rmin=1000001 then

Rmin:=0;

writeln(Rmin);

End.

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

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

Программа для решения задачи Б

Const delta=6; {минимальный интервал}

Var R :longint ; {минимальное произведение}

n, a:integer; {количество чисел, очередное значение}

m, m5:integer; {наименьшее, наименьшее из кратных 5}

b :array[1..delta-1] of integer; {массив промежуточных значений}

Begin

R:=1000001;

readln(n);readln(m);

if (m mod 5)=0 then

m5:=m

else

m5:=0;

for i:=1 to delta-1 do

readln(b[i]);

for i:= delta+1 to n do

begin readln(a);

{проверяем произведение с наименьшим, кратным 5}

if ((m50) and ((m5*a)

R:=a*m5;

{проверяем произведение с наименьшим и чтобы оно было кратно 5}

if ((a mod 5)=0) and (a*m

R:=a*m;

{проверяем, не является ли 1-е число в массиве наименьшим и наименьшим, кратным 5}

if b[1]

m:=b[1];

if (b[1]mod 5=0) and (b[1]

m5:=b[1];

{сдвиг в массиве}

for j:=1 to delta-2 do b[i]:=b[i+1];

b[delta-1]:=a;

end;

if Rmin=1000001 then Rmin:=0;

writeln (Rmin);

End.

Возможная формулировка задания (тип IV)

На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. Скорость, по крайней мере, одной частицы нечётна.

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

При данной формулировке задачи проще сразу рассмотреть оптимальное решение.

Поскольку задачу нужно решать в один проход (если делать оптимальное решение), то сумму надо считать одновременно с чтением данных.

Проблема 1: сумма должна быть максимальной по значению, но минимальной по количеству.

Вывод: нужно брать все положительные элементы и не брать нулевые.

Проблема 2: не все числа должны входить в эту сумму, чтобы она была нечетной.

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

Текст оптимального решения представлен ниже.

Программа оптимального решения

Var s: longint ; {сумма}

n, a:integer; {количество чисел, очередное значение}

m :integer; {наименьшее нечетное}

Begin

S:=0;

readln(n);

m:=0;

for i:= 1 to n do

begin

readln(a);

S:=s+a;

if ( (a mod 2)=1) and ((m=0) or (a

m:=a;

end;

if (s mod 2)=0 then

s:=s-m;

writeln(R);

End.

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

Возможная формулировка задания (тип V)

На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 6 и при этом была минимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются за ту из подзадач, что решена на большее количество баллов. Задача А дает 2 балла, задача Б — 4 балла. В задаче А приведите неэффективный алгоритм. При решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по времени ИЛИ памяти, дается 3 балла, по времени И памяти — 2 балла.

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

Пример входных данных:

5 4

3 2

1 1

18 3

11 12

2 5

Пример выходных данных:

23

Задача Б. Количество пар N не известно заранее и может принимать значения 2

Пример входных данных:

6

5 4

3 2

1 1

18 3

11 12

2 5

Пример выходных данных:

23

Полный перебор представляет собой вложенные циклы для перебора всех возможных пар значений.

Решение задачи А

Var a:array[1..6,1..2]of integer;

i,j1,j2,j3,j4,j5,j6,s,smin: integer;

Begin

for i:=1 to 6 do

for j1:=1 to 2 do

read(a[I,j1]);

smin:=1000*6+1;

for j1:=1 to 2 do

for j2:=1 to 2 do

for j3:=1 to 2 do

for j4:=1 to 2 do

for j5:=1 to 2 do

for j6:=1 to 2 do

begin

s:=a[1,j1]+ a[2,j2] +a[3,j3]+ a[4,j4]+ a[5,j5] +a[6,j6];

if (s0) then smin:=s

end;

if smin= 1000*6+1 then smin:=1;

writeln(smin);

End.

Идея решения задачи Б

Поскольку задачу нужно решать в один проход (если делать оптимальное решение), то сумму надо считать одновременно с чтением данных.

Проблема 1: сумма должна быть минимальной по значению.

Вывод: нужно брать из каждой пары только минимальное число.

Проблема 2: Сумма может получиться кратной 6.

Вывод: надо запоминать «кандидатов» на замену одного числа из пары на другое, если сумма вдруг получится кратной 6. Число должно иметь, во первых, минимальную разницу с заменяемым, а во-вторых, должно иметь другой остаток при делении на 6, чтобы и сумма поменяла свой остаток от деления. Сумма при этом увеличится именно на разницу между числами, поэтому проще запоминать именно ее.

Ниже приведен полный текст решения задачи.

Решение задачи Б

Var n:integer; {количество чисел}

a, b : integer; {очередная пара чисел}

dmin, d : integer; {минимальная разница между числами в паре}

s:integer; i:integer;

Begin

readln(n);

s:=0; d:=1001;

for i:=1 to n do

begin

readln(a,b);

{добавляем минимальное число в сумму}

if a

s:=s+a

else

s:=s+b;

{вычисляем разницу между числами}

d:=abs(a-b);

{если разница минимальна и не кратна 6, запоминаем ее}

if (d0) then

dmin:=d;

end;

{если сумма получилась кратной 6, увеличиваем ее на dmin}

If (s mod 6) =0 then

If dmin=1001 then

s:=0

else

s:=s+dmin;

writeln(s);

end.

Список использованных источников

В.Р. Лещинер, М.А. Ройтберг. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ для учителей, подготовленные на основе анализа типичных ошибок Участников ЕГЭ 2016 года по ИНФОРМАТИКЕ и ИКТ. – http://www.fipi.ru/ege-i-gve-11/analiticheskie-i-metodicheskie-materialy.

КИМ ЕГЭ «Информатика и ИКТ» http://www.ege.edu.ru/ru/classes-11/preparation/demovers/

Материалы сайта Полякова К.Ю. по подготовке к ЕГЭ http://kpolyakov.spb.ru/school/ege.htm.

Информатика и ИКТ. Подготовка к ЕГЭ 2016. 20 тренировочных вариантов по демоверсии на 2016 год: учебно-методическое пособие./Под ред. Л. Н. Евич, С.Ю. Кулабухова. – Ростов на Дону: Легион, 2015.

Каталог заданий сайта «Решу ЕГЭ». –

https://inf-ege.sdamgia.ru/test?a=catlistwstat

Источник

Доброго времени суток каждому жителю Хабрвилля! Давненько я не писал статей! Пора это исправить!

В сегодняшней статье поговорим о насущной для многих выпускников школ теме — ЕГЭ. Да-да-да! Я знаю, что Хабр — это сообщество разработчиков, а не начинающих айтишников, но сейчас ребятам как никогда нужна поддержка именно сообщества. Ребят опять посадили на дистант. Пока не ясно на какой период, но уже сейчас можно сказать, что ЕГЭ по информатике будет на компьютерах и его можно зарешать при помощи языка Python.

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

Всех желающих — приглашаю ниже!

Быстрый перевод из системы в систему

В Python есть интересные функции bin(), oct() и hex(). Работают данные функции очень просто:

bin(156) #Выводит '0b10011100'
oct(156) #Выводит '0o234'
hex(156) #Выводит '0x9c'

Вывод в интерпретационном режиме

Как вы видите, выводится строка, где 0b — означает, что число далее в двоичной системе счисления, 0o — в восьмеричной, а 0x — в шестнадцатеричной. Но это стандартные системы, а есть и необычные…

Давайте посмотрим и на них:

n = int(input()) #Вводим целое число
 
b = '' #Формируем пустую строку
 
while n > 0: #Пока число не ноль
    b = str(n % 2) + b #Остатот от деления нужной системы (в нашем сл записываем слева
    n = n // 2 #Целочисленное деление
 
print(b) #Вывод

Данная программа будет работать при переводе из десятичной системы счисления в любую до 9, так как у нас нет букв. Давайте добавим буквы:

n = int(input()) #Вводим целое число

b = '' #Формируем пустую строку

while n > 0: #Пока число не ноль
	if (n % 21) > 9: #Если остаток от деления больше 9...
		if n % 21 == 10: #... и равен 10...
			b = 'A' + b #... запишем слева A
		elif n % 21 == 11:#... и равен 11...
			b = 'B' + b#... запишем слева B

'''

И так далее, пока не дойдём до системы счисления -1 (я переводил в 21-ную систему и шёл до 20)

'''

		elif n % 21 == 11:
			b = 'B' + b
		elif n % 21 == 12:
			b = 'C' + b
		elif n % 21 == 13:
			b = 'D' + b
		elif n % 21 == 14:
			b = 'E' + b
		elif n % 21 == 15:
			b = 'F' + b
		elif n % 21 == 16:
			b = 'G' + b
		elif n % 21 == 17:
			b = 'H' + b
		elif n % 21 == 18:
			b = 'I' + b
		elif n % 21 == 19:
			b = 'J' + b
		elif n % 21 == 20:
			b = 'K' + b
	else: #Иначе (остаток меньше 10)
		b = str(n % 21) + b #Остатот от деления записываем слева
	n = n // 21 #Целочисленное деление

print(b) #Вывод

Способ объёмен, но понятен. Теперь давайте используем тот же функцию перевода из любой системы счисления в любую:

def convert_base(num, to_base=10, from_base=10):
    # Перевод в десятичную систему
    if isinstance(num, str): # Если число - строка, то ...
        n = int(num, from_base) # ... переводим его в нужную систему счисления
    else: # Если же ввели число, то ...
        n = int(num) # ... просто воспринять его как число
    # Перевод десятичной в 'to_base' систему
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" # Берём алфавит
    if n < to_base: # Если число меньше системы счисления в которую переводить...
        return alphabet[n] # ... вернуть значения номера в алфавите (остаток от деления)
    else: # Иначе...
        return convert_base(n // to_base, to_base) + alphabet[n % to_base] # ... рекурсивно обратиться к функии нахождения остатка

Вызвав функцию вывода print(convert_base(156, 16, 10)) мы переведём 156 из 10 в 16 систему счисления, а введя print(convert_base('23', 21, 4)) переведёт 23 из 4-ичной в 21-ичную систему (ответ: B).

Задача 2

Все задания беру из первого октябрьского варианта (он же вариант № 9325894) с сайта Решу.ЕГЭ.

Решение данной задачи совсем простое: банальный перебор.

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				print(x, y, z, F) #Выводим результат

Результат:

Нам вывелась вся таблица истинности (1 = True, 0 = False). Но это не очень удобно. Обратите внимание, что в задании, функция равно 0, так и давайте подправим код:

print('y', 'x', 'z', 'F') #Напечатаем заголовки таблицы
for y in range(2): #Берём все переменные и меняем их в циклах '0' и '1'
	for x in range(2):
		for z in range(2):
			for w in range(2):
				F = ((not x or y) == (not z or w)) or (x and w) #Записываем функцию
				if not F:
					print(x, y, z, F) #Выводим результат

Результат:

Далее — простой анализ.

Задача 5

Данная задача легко решается простой последовательностью действий в интерпретационном режиме:

Задача 6

Перепечатали и получили ответ:

s = 0
k = 1
while s < 66:
    k += 3
    s += k
print(k)

Задача 12

В очередной раз, просто заменим слова на код:

a = '9' * 1000

while '999' in a or '888' in a:
	if '888' in a:
		a = a.replace('888', '9', 1)
	else:
		a = a.replace('999', '8', 1)
print(a)

Задача 14

Компьютер железный, он всё посчитает:

a = 4 ** 2020 + 2 ** 2017 - 15
k = 0

while a > 0:
    if a % 2 == 1:
    	k += 1
    a = a // 2

print(k)

Задача 16

Опять же, просто дублируем программу в python:

def F(n):
    if n > 0:
        F(n // 4)
        print(n)
        F (n - 1)
print(F(5))

Результат:

Задача 17

Задача с файлом. Самое сложное — достать данные из файла. Но где наша не пропадала?!

with open("17.txt", "r") as f: #Открыли файл 17.txt для чтения
    text = f.read() #В переменную text запихнули строку целиком
a = text.split("n") #Разбили строку энтерами (n - знак перехода на новую строку)

k = 0 #Стандартно обнуляем количество
m = -20001 #Так как у нас сумма 2-ух чисел и минимальное равно -10000, то минимум по условию равен -20000, поэтому...

for i in range(len(a)): #Обходим все элементы массива
	if (int(a[i - 1]) % 3 == 0) or (int(a[i]) % 3 == 0): #Условное условие
		k += 1 #Счётчик
		if int(a[i - 1]) + int(a[i]) > m: #Нахождение минимума
			m = int(a[i - 1]) + int(a[i])

print(k, m) #Вывод

Немного пояснений. Функция with() открывает файл считывает данные при помощи функции read() и закрывает файл. В остальном — задача стандартна.

Задача 19, 20 и 21

Все три задачи — задачи на рекурсию. Задачи идентичны, а вопросы разные. Итак, первая задача:

Пишем рекурсивную функцию и цикл перебора S:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 3: #Условия завершения игры
		return p == 3
	return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
		   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий

for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)
		break

Немного пояснений. В рекурсивной функции существует 3 переменные x — число камней в первой куче, y — число камней во второй куче, p — позиция. Позиция рассчитывается по таблице:

	Игра	Петя	Ваня	Петя	Ваня	Петя
p	1	2	3	4	5	6

Далее — всё по условию задачи.

Вторая задача на теорию игр:

Все отличия в рамке. Ну и код, соответственно, не сильно отличается:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 4: #Условия завершения игры
		return p == 4
	if p % 2 != 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

Отличия:

Выиграл Петя, соответственно, позиция 4
Так как Петя не может выиграть за один ход — он выигрывает за 2 хода (and, а не or на нечётных позициях (играх Пети))
Убрали break, так как нам нужны все S, а не единственный

Последняя вариация задачи:

Сразу код:

def f(x, y, p): #Рекурсивная функция
	if x + y >= 69 or p > 5: #Условия завершения игры
		return p == 3 or p == 5
	if p % 2 == 0:
		return f(x + 1, y, p + 1) or f(x, y + 1, p + 1) or
			   f(x * 2, y, p + 1) or f(x, y * 3, p + 1) #Варианты действий
	else:
		return f(x + 1, y, p + 1) and f(x, y + 1, p + 1) and
			   f(x * 2, y, p + 1) and f(x, y * 3, p + 1) #Варианты действий


for s in range (1, 58 + 1): #Перебор S
	if f(10, s, 1): #Начали с 10 камней
		print(s)

Ну и всего лишь 2 отличия:

Позиции 3 или 5, а не 4, так как выиграл Ваня
На второй ход выигрывает Ваня и нам нужно or и and поменять. Я заменил только кратность 2.

Задача 22

Ctrl+C, Ctrl+V — наше всё!

for i in range(1, 100000):
	x = i
	L = 0
	M = 0
	while x > 0 :
		L = L+1
		if (x % 2) != 0:
			M = M + x % 8
		x = x // 8
	if L == 3 and M == 6:
		print(i)

Задача 23

Итак, код:

def f(x, y):
	if x > y: #Перегнали цель
		return 0
	if x == y:  #Догнали цель
		return 1
	if x < y: #Догоняем цель тремя методами
		return f(x + 1, y) + f(x + 2, y) + f(x * 2, y)

print(f(3, 10) * f(10, 12)) #Прошло через 10, значит догнали 10 и от де догоняем 12

Так как в условии задачи мы увеличиваем число, но будем числа «догонять». Три метода описаны, ну а пройти через 10 — значит дойти до него и идти от него.

Собственно, это и есть вся первая часть ЕГЭ по информатике решённая на Python.

Ссылка на репозиторий со всеми программами:

Надеюсь, что смог помочь в своей статье выпускникам и готовящимся

Остался один вопрос — нужен ли разбор второй части ЕГЭ по информатике на Python? Оставлю этот вопрос на ваше голосование.

Всем удачи!

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Делаю разбор второй части?

Проголосовали 106 пользователей.

Воздержались 15 пользователей.

Источник