Решение сложных задач ЕГЭ по информатике Задачи С4 2011-2014 гг. - презентация

1 Решение сложных задач ЕГЭ по информатике Задачи С гг.

2 C Популярная газета объявила конкурс на выбор лучшего фильма, для которого стоит снять продолжение. На выбор читателей было предложено 10 фильмов. Вам предлагается написать эффективную, в том числе и по используемой памяти, программу, которая будет статистически обрабатывать результаты sms-голосования по этому вопросу, чтобы определить популярность того или иного фильма. Следует учитывать, что количество голосов в списке может быть очень велико. На вход программе в первой строчке подается количество пришедших sms-сообщений N. В каждой из последующих N строк записано название фильма. Пример входных данных: 6 Белое солнце пустыни Бриллиантовая рука Белое солнце пустыни Гараж Бриллиантовая рука Программа должна вывести список всех фильмов, встречающихся в списке, в порядке убывания (невозрастания) количества отданных за них голосов с указанием этого количества голосов. Название каждого фильма должно быть выведено только один раз. Пример выходных данных для приведенных входных данных: Белое солнце пустыни 3 Бриллиантовая рука 2 Гараж 1

3 Идея решения. 1. Задача «Частотный словарь»: если очередное «слово» уже есть в словаре, увеличиваем на 1 его частоту, иначе добавляем его в словарь, устанавливая его частоту в Выводим «слова» в порядке не возрастания их частот. Структура для хранения информации о словах. const nMax=10;{максимальный объем словаря} type Item = record Name: string;{ слово } Count: integer;{частота} end; type Dict = array[1.. nMax] of Item; {словарь}

4 Скелет программы. Program c4_2011; var a: Dict, nItem, {фактический объем словаря} nRec:integer; {рекордная частота} begin MakeDict; OutDict; end. При вводе удобно сразу определять рекордную частоту по всему словарю.

5 procedure MakeDict; var n,k,i :integer; str :string; {очередное введенное слово} flag:boolean; {признак наличия слова в словаре } begin nItem:=0; nRec:=0; readln(n); {ввод количества слов} for k:=1 to n do begin readln(str); {ввод очередного слова} flag:=false; for i:= 1 to nItem do {поиск слова в словаре} if a[i].Name=str then begin flag:=true; {слово уже встречалось} Inc(a[i].Count); {увеличение частоты} if a[i].Count > nRec then nRec:= a[i].Count; {проверка на рекорд юность} break; {уходим из цикла} end; if not flag then {новое слово} begin Inc(nItem); {увеличение объема словаря} a[nItem].Name:=str; {вносим слово в словарь} a[nItem].Count:=1; {с частотой 1} end;

6 procedure OutDict; var nOut, {счетчик кол-ва выведенных слов} nCurRec, {текущий рекорд частоты} k : integer; begin nOut:=0; repeat nCurRec:=nRec; nRec:=0; for k:=1 to nItem do begin if a[k].Count=0 then continue; {пропускаем выведенные слова} if a[k].Count=nCurRec then {вывод очередного слова} begin writeln(a[k].Name, ' ',nCurRec); a[k].Count:=0; {обнуляем счетчик для уже выведенного слова} Inc(nOut); end else begin if a[k].Count>nRec then nRec:=a[k].Count; {обновляем рекорд} end; until (nOut= nItem); {все слова выведены} end;

7 C На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Все скорости положительны. Чтобы в документации отличать одну серию эксперимента от другой каждую серию решили характеризовать числом, равным минимальной чётной сумме из всех сумм пар скоростей различных частиц. Если чётная сумма отсутствует, то характеристикой будет являться просто минимальная сумма. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет обрабатывать результаты эксперимента, находя искомую величину. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. На вход программе в первой строке подается количество частиц N. В каждой из последующих N суток записано одно натуральное число не превышающее Пример входных данных: Программа должна вывести характеристику данной серии экспериментов. Пример выходных данных для приведенного выше примера входных данных: 24

8 Идея решения. 1. Сумма двух чисел будет четной только в том случае, если числа имеют одинаковую четность (оба четные или оба нечетные). 2. Для вычисления минимальной суммы требуется определить по два самых маленьких числа среди четных и/или нечетных введенных чисел. 3. При N>2 среди введенных чисел обязательно найдется 2 числа одинаковой четности. 4. Отсутствие минимальной четной суммы возможно только тогда, когда N=2 и одно из чисел четно, а второе нечетно – в этом случае нужно вывести сумму этих чисел.

9 program c4_2012; const MAX = 2* ; {значение, большее удвоенного максимума} var min10,min20, {минимальное и второе по величине четные числа} min11,min21, {минимальное и второе по величине нечетные числа} n,x,k:integer; begin min10:= MAX; min20:= MAX; min11:= MAX; min21:= MAX; {инициализация} readln(n); for k:=1 to n do begin readln(x); if Odd(x) then {проверка нечетности} begin if x

10 C По каналу связи передается последовательность положительных целых чисел, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается отдельно. Признаком конца передаваемой последовательности является число 0. После числа 0 передается контрольное значение – наибольшее число R, удовлетворяющее следующим условиям: R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются); R делится на 6 Напишите эффективную программу, которая получает последовательность чисел и следующие за ней признак конца и контрольное значение, а также проверяет правильность контрольного значения. Программа должна напечатать отчет по следующей форме: Получено.. чисел Полученное контрольное значение: …. Вычисленное контрольное значение:… Контроль пройден (или – контроль не пройден) Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи. Пример входных данных: Пример выходных данных для приведенного выше примера входных данных: Получено 6 чисел Полученное контрольное значение: 3600 Вычисленное контрольное значение: 3600 Контроль пройден.

11 Идея решения. 1. Произведение двух чисел будет делиться на 6 только тогда, когда: Одно из чисел делится на 6 – тогда второй сомножитель может быть любым (в том числе может делиться на 6). Одно из чисел делится на 3, а другое делится на 2 (возможно, одно или оба делятся на 6). 2. Для ввода чисел удобно использовать оператор бесконечного цикла repeat – при вводе числа 0 цикл прерывается.

12 program c4_2013; var x, count, C, C0, max, max2, max3, max6: integer; begin count:=0; max:=0; max2:=0; max3:=0; max6:=0; repeat readln(x); if x=0 then break; count:= count + 1; if (x mod 6 = 0) and (x > max6) then {новый рекорд среди делящихся на 6} begin if max6 > max then max:= max6; {если старый рекорд больше всех вводившихся до текущего} max6:= x; continue; {можно вводить следующее число} end else if x > max then max:= x; {второе по величине число} if (x mod 2 = 0) and (x > max2) then max2:= x {макс. среди делящихся на 2} else if (x mod 3 = 0) and (x > max3) then max3:= x {макс. среди делящихся на 3, но не делящихся на 2} until false; readln(C0); if max6*max > max2*max3 then C:= max6*max else C:= max2*max3; writeln('Получено чисел: ', count); writeln('Полученное контрольное значение: ', C0); writeln('Вычисленное контрольное значение: ', C); if C = C0 then writeln('Контроль пройден.') else writeln('Контроль не пройден.'); end.

13 C На вход программы подаются результаты измерений, выполняемых прибором с интервалом 1 минуту. Все данные – целые числа (возможно, отрицательные). Требуется найти наибольшую сумму двух результатов измерений, выполненных с интервалом не менее, чем в 7 минут. Описание входных данных В первой строке вводится одно целое положительное число – количество измерений N, которое может быть очень велико. Гарантируется, что N > 7. Каждая из следующих N строк содержит по одному целому числу – результат очередного измерения. Описание выходных данных Программа должна вывести одно число наибольшую сумму двух результатов измерений, выполненных с интервалом не менее, чем в 7 минут. Пример входных данных: Пример выходных данных для приведённого выше примера входных данных: 13

14 const K = 7; var i, N, max, maxSum, next, elem: integer; Buf: array[0..K-1] of integer; begin read(N); for i:=0 to N-1 do begin read(elem); { обработка очереди } next := Buf[i mod K]; Buf[i mod K] := elem; { начальные значения для max и maxSum } if i = K then begin max := next; maxSum := next + elem; end; { обновление max и maxSum } if i > K begin if next > max then max := next; if max+elem > maxSum then maxSum := max + elem; end; writeln(maxSum); end.