Задачи С4 Технология программирования. Создание программ для решения задач средней сложности. Первичный балл – 4 (10%). Рекомендуемое время выполнения. - презентация

1 Задачи С4 Технология программирования. Создание программ для решения задач средней сложности. Первичный балл – 4 (10%). Рекомендуемое время выполнения – 1 час (из 4-х часов экзамена) (25%)

2 Литература Отличник ЕГЭ. Информатика. Решение сложных задач / ФИПИ авторы- составители: С.С. Крылов, Д.М. Ушаков – М.: Интеллект-Центр, kpolyakov.narod.ru – сайт Константина Полякова

3 Этапы создания программы для решения задачи С4: Анализ условия Выбор алгоритма решения задачи и языка программирования для его реализации Написание чернового варианта программы, его отладка и тестирование

4 Пример типичного условия задачи С4: На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи На вход программе в первой строке подается число данных N о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате: где – строка, состоящая не более, чем из 20 символов без пробелов, – строка, состоящая не более, чем из 20 символов без пробелов, – одно из чисел – 92, 95 или 98, – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: Синойл Цветочная Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0. Пример выходных данных:

5 Типичная постановка задачи С4 содержит: Формат входных данных Назначение программы (какую итоговую информацию программа должна извлечь из исходных данных и как их преобразовать) Формат выходных данных Дополнительные условия и рекомендации программисту.

6 1. Анализ условия: Выделяем основные элементы условия: Формат входных данных: На вход программе в первой строке подается число данных N о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате: где – строка, состоящая не более, чем из 20 символов без пробелов, – строка, состоящая не более, чем из 20 символов без пробелов, – одно из чисел – 92, 95 или 98, – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: Синойл Цветочная

7 Назначение программы Напишите …программу, которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. Формат выходных данных Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95- й и 98-й бензин соответственно. Если бензин какой- то марки нигде не продавался, то следует вывести 0. Пример выходных данных:

8 Дополнительные условия и рекомендации программисту. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, BorlandPascal 7.0)… Обратите внимание, что часть условия не вошла ни в один из приведенных выше существенных элементов. Это литературное введение, т.е. фразы, поясняющие задачу, вводящие а курс дела, но не существенные для решения задачи: На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС.

9 Внимательное чтение условия задачи ОЧЕНЬ ВАЖНО, т.к. значительное количество ошибок учащихся связано с невнимательным чтением, а, следовательно, с неверным пониманием того или иного компонента условия!!!!!!!!!!!!!!!!!!!!!!!!

10 Рассмотрим дополнительные условия и рекомендации программисту «эффективная по времени работы программа» не должна содержать лишних операций, число которых пропорционально N (объему входных данных). Например, лишней была бы сортировка цен. «эффективная по используемой памяти программа» не должна содержать лишних выделений памяти, число которых пропорционально N. Например, нерационально хранить названия компаний, их адрес, да и без хранения всех цен в данной задаче желательно обойтись

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

12 Неэффективное решениеЭффективное решение Var A: array[ ] of integer; i, N, Min, Kol: integer; Begin ReadLn (N); For i:=1 to N do ReadLn(A[i]); Min := 3001; {Min принимает значение заведомо большее любого элемента массива} For i:=1 to N do If A[i] < Min then Min:=A[i]; Kol:=0; For i:=1 to Ndo If A[i] = Min then Kol:=Kol+1; WriteLn (Min, Kol); End. Var A, i, N, Min, Kol: integer; Begin Kol:=0; Min := 3001; ReadLn (N); For i:=1 to N do Begin ReadLn (A); If A = Min then Kol:=Kol+1; If A < Min then Begin Min:=A Kol:=1; end WriteLn (Min, Kol); End.

13 Неэффективное решениеЭффективное решение DIM A(10000) AS INTEGER INPUT N FOR I=1 TO N INPUT A(I) NEXT I Min = 3001 FOR I=1 TO N IF A(I) < MIN THEN MIN = A(I) NEXT I KOL=0 FOR I=1 TO N IF A(I) = MIN THEN KOL = KOL+1 NEXT I PRINT MIN, KOL INPUT N KOL=0 Min = 3001 FOR I=1 TO N INPUT A IF A = MIN THEN KOL = KOL+1 IF A < MIN THEN MIN = A KOL=1 ENDIF NEXT I

14 Рекомендации: 1.На экзамене учащийся может решать задачи на любом языке программирования. В системе оценивания не предусмотрены бонусы за выбор «правильного» или «оригинального» языка программирования, поэтому не нужно руководствоваться принципом «удивить экзаменаторов редким или сверхновым языком программирования», а писать программу на том языке, который лучше знаете или который лучше подходит для решения поставленной задачи. 2.Несмотря на то, что некоторые версии языков программирования предусматривают автоматическую инициализацию переменных нулевыми значениями, этой возможностью пользоваться крайне не рекомендуется ни в учебном, ни в практическом программировании, т.к. очень велико число ошибок, порождаемых этим якобы упрощением. А в задачах С2 в критериях оценивания для экспертов ЯВНО прописано, что необходимо снижать оценку, если учащийся не инициализированы или неверно инициализированы переменные.

15 Типичные критерии оценивания задания С4 Содержание верного ответа и указания по оцениванию (допускаются иные формулировки ответа, не искажающие его смысла) Программа читает все входные данные один раз, не запоминая их в массиве, размер которого соответствует числу АЗС или диапазону цен. Во время чтения данных определяются минимальная цена каждой марки бензина и количество АЗС, продающих его по этой цене. Для этого используются 6 переменных или соответствующие массивы (например, для удобства из 8 элементов каждый). Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой марки бензина минимальная цена отмечена ровно на одной АЗС).

16 Указания по оцениванию Программа работает верно для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу N (количество данных мониторинга) или диапазону цен (3000). Программа просматривает входные данные один раз, используя для нахождения ответа два массива из 3-х (8- и) элементов каждый или 6 соответствующих переменных. Допускается наличие в тексте программы ОДНОЙ синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). 4 балла

17 Программа работает верно, но входные данные или только цены запоминаются в массиве, в том числе возможно в массиве (трех массивах) с индексами от 0 до 3000, обозначающем количество АЗС, продающих бензин по соответствующей цене, или входные данные считываются несколько раз. Возможно, вместо алгоритма поиска минимума используется сортировка всех цен. Допускается наличие от одной до трех синтаксических ошибок: Возможно, в принципиально верно организованном вводе данных есть одна ошибка. Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает не верно на некоторых (не типичных) наборах входных данных (например, все цены на одну из марок бензина равны 3000). 3 балла

18 Программа работает в целом верно, эффективно или нет, но, в реализации алгоритма содержатся до двух ошибок (неверная инициализация переменных, в частности значения минимума, возможно программа не верно работает, если минимальное значение равно 3000, выход за границу массива, перевод символов в числа, используется знак < вместо

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

20 Синтаксические ошибки: Ошибки в написании названий операторов или имен стандартных функций Неверно расставлены или пропущены скобки Использование неописанных переменных (Паскаль) Не расставлены или неверно расставлены знаки препинания, например «;» в Паскале

21 Пример фрагментов программ с синтаксическими ошибками. Поиск минимального значения элемента непустой входной последовательности из N элементов: var A, N, Min: integer; begin readln (N) readln(Min); for i:= 2 to N do begin readln (A); if A < Min then Min = A; end; writel (Min); end. 1.Не описана переменная I 2.После readln (N) отсутствует точка с запятой 3.= вместо := в операторе Min = A; 4.Неправильно написано имя стандартной процедуры вывода writel вместо writeln или write Повторенные синтаксические ошибки считаются за одну (т.е. если бы отсутствовали все точки с запятой, то это считалось бы за одну синтаксическую ошибку.

22 INPUT N INPUT Min FOR I = 1 N INPUT A IF A < Min THEN Min = A ENDIF NEXT K PRINT Min 1.FOR I = 1 N вместо FOR I = 1TO N 2.NEXT K вместо NEXT I Пример фрагментов программ с синтаксическими ошибками. Поиск минимального значения элемента непустой входной последовательности из N элементов:

23 Пример тех же фрагментов программ с логическими ошибками var A, i, N, Min: integer; begin readln (N); Min := 0; for i:= 1 to N do begin readln (A); if A < Min then Min := A; end; writeln (Min); end. Минимальное значение инициализирует ся нулем INPUT N INPUT Min FOR I = 1To N INPUT A IF A < Min THEN Min = A ENDIF NEXT I PRINT Min Количество вводимых значений будет равно N+1, а не N

24 Технология выполнения задания С4 Этапы создания программы для решения задачи С4: Анализ условия Выбор алгоритма решения задачи и языка программирования для его реализации Написание чернового варианта программы, его отладка и тестирование

25 1. необходимо соблюдение формата ввода- вывода! Несоблюдение формата может быть расценено при проверке как неполное решение или содержащее логические ошибки с соответствующим понижением баллов. Наглядно представьте себе структуру входных и выходных данных, а также структуры данных, которые вы будете хранить и обрабатывать. 2. необходимо уяснить постановку задачи, отбросить лишние «литературно-художественные» подробности и представить себе задачу в формальном виде. Здесь нужно быть особенно внимательными, т.к. неверно понятое условие станет причиной создания принципиально неверной программы, которая может быть оценена в 0 баллов.

26 3. детально продумайте алгоритм решения задачи. Алгоритм лучше зафиксировать на бумаге в виде решения или схемы. Так будет легче не запутаться, а эксперту будет легче и приятнее проверять вашу работу. 4. при написании текста программы нужно контролировать соответствие типов переменных и применяемых к ним операций, не допускать использование неопределенных (неинициализированных переменных).

27 5. текст программы нужно писать аккуратно и разборчиво, структурированном, выделяя отступами уровень вложенности операторов, не скупясь на комментарии и пояснения. Отсутствие комментариев не является признаком высокой квалификации программиста, скорее наоборот. Не следует писать «комментарии ради самих комментариев» типа i:=1; {присваиваем переменной i значение 1} Разумны и уместны будут комментарии типа: Repeat Read (c); Until c= ; {считана компания} Repeat Read (c); Untilc= ; {считана улица}

28 6. после того как программа написана, необходимо выполнить ее тестирование и отладку (поиск возможных ошибок и их устранение). Проблема в том, что процедура отладки и тестирования – бумажная, бескомпьютерная. Это требует особой внимательности и тренировки. При тестировании старайтесь найти ошибку в своей программе, а не продемонстрировать себе ее правильность. При бескомпьютерном тестировании рекомендуется вести на черновике таблицу значений переменных. при тестировании следует подбирать набор тестовых данных так, чтобы «пройти» по всем «веткам» программы. Особое внимание следует уделить особым случаям исходных данных, пограничным, критическим точкам. Например: - бензин одной или нескольких марок отсутствует на всех АЗС - стоимость бензина достигает минимальных (или максимальных) значений на всех или на нескольких АЗС - число АЗС равно 0 или 1

29 Приемы программирования, типичные для заданий С4 1. Ввод данных. На вход программе в первой строке подается число данных N о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате: где – строка, состоящая не более, чем из 20 символов без пробелов, – строка, состоящая не более, чем из 20 символов без пробелов, – одно из чисел – 92, 95 или 98, – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: Синойл Цветочная

30 1. Ввод данных. I способ: считать всю строку целиком в некоторую переменную строкового типа и далее обрабатывать ее посимвольно и преобразовывать символы в числа для их последующей обработки. var s, s1: string; k, m, cen, os: integer; begin readln (s); {считали строку целиком} k:=pos(,s); {находим первый пробел} delete(s,1,k); {удалили из строки название компании, т.к. оно нам не нужно} k:=pos(,s); {находим следующий пробел} delete(s,1,k); {удалили из строки название улицы} k:=pos(,s); { находим следующий пробел} s1:=copy(s,1,k-1); {в s1 – марка бензина} val(s1,m,os); {преобразовали марку бензина из строковой величины в числовую } delete(s,1,k); {удалили из строки марку бензина. Осталась только цена} val(s,cen,os); {преобразовали цену бензина из строковой величины в числовую}

31 LINE INPUT S$считали строку целиком K=1 WHILE MID$(S$,K,1)находим первый пробел K=K+1 WEND K=K+1 WHILE MID$(S$,K,1)находим второй пробел K=K+1 WEND I=K+1 WHILE MID$(S$,I,1) находим третий пробел I=I+1 WEND S1$=MID$(S$, K+1, I–K+1) в S1$ скопировали марку бензина M=VAL(S1$) преобразовали марку бензина из строковой величины в числовую S1$=MID$(S$, I+1, LEN(S$)–I) в S1$ скопировали цену бензина CEN= VAL(S1$) преобразовали цену бензина из строковой величины в числовую В Бейсике есть функция INSTR, которая является аналогом функции POS

32 II способ: комбинированный - считываем символьные данные «вручную» по символу, а числовые вводим с помощью стандартной процедуры. var c: char; m, cen: integer; begin read (c); while c do read (c); {считали название компании} read (c); while c do read (c); {считали название улицы} {Теперь в текущей строке остались два целых числа. Их можно прочитать с помощью стандартной процедуры, что избавляет нас от необходимости возиться с выделением подстрок, соответствующих числам и их преобразованием} readln(m,cen); for i:=1 to 2 do begin read (c); while c do read (c); end {считали сначала название компании, потом - улицы}

33 В заданиях С4 встречаются исходные данные, которые имеют свой внутренний формат – обычно комбинацию числового и строкового типа, возможно с использованием некоторых разделителей, например: - номер класса из одной или двух цифр от 0 до 12 и вплотную за ним буква класса – 10Б или 1а (возможность использования строчных или прописных букв оговаривается в условии) - два двузначных числа из соответствующего диапазона, разделенных двоеточием, например, 17:45; 6:15 или 06:15 (оговаривается в условии) - двузначные числа из соответствующего диапазона, разделенных точками, например, или Данные такой сложной структуры вводятся в виде строки символов с последующем «разбором», если программе нужно получить доступ к отдельным элементам комбинированных данных.

34 Рассмотри разбор поля с выделением номера класса как числа и буквы класса как символа (будем считать что это поле содержится в отдельной строке исходных данных). var c, letter: char; N: 1..12; begin … … … read (c); {считали 1-й символ} N:=Ord(c) – Ord(0);{в N – число, равное значению 1-й цифры} read (c); {считали 2-й символ} if c in ['0'..'9'] then{если 2-й символ - цифра} begin N:=N*10+ Ord(c) – Ord('0') {'вычисляем номер класса } read (c); {и читаем следующий символ – букву класса} end; Letter:=c; {в Letter – буква класса} Мы самостоятельно преобразовали символы, обозначающие цифры числа в само число: ASCII код символа минус код символа '0'

35 LINE INPUT S$ считали строку целиком … … … С$=MID$(S$, 1, 1) N=ASC(C$)-ASC("0") в N – число, равное значению 1-й цифры С$=MID$(S$, 2, 1) 2-й символ IF (C$>= "0") And (C$ = "0") And (C$">

36 Рассмотри разбор поля на целочисленные часы и минуты, причем количество часов может быть как одно-, так и двухсимвольным, например, 6:05 (будем считать что это поле содержится в отдельной строке исходных данных) var c: char; h: 0..23; m: 0..59; begin … … … read (c); {1-й символ} h:=Ord(c) – Ord(0); {в h – число, равное значению 1-й цифры часов} read (c); {2-й символ} if c in ['0'..'9'] then {если 2-й символ - цифра} begin h:=h*10+ Ord(c) – Ord('0') {вычисляем час } read (c); {и читаем след. символ – двоеточие} end; read (c); {читаем след. символ – 1-ю цифру минут} m:=Ord(c) – Ord(0); {в m – число, равное значению 1-й цифры минут} read (c); {читаем 2-ю цифру минут} m:=m*10+ Ord(c) – Ord('0') {вычисляем минуты }

37 LINE INPUT S$ считали строку целиком … … … С$=MID$(S$, 1, 1) h=ASC(C$)-ASC("0") в h – число, равное значению 1-й цифры часов С$=MID$(S$, 2, 1) 2-й символ IF (C$>= "0") And (C$ = "0") And (C$">

38 Пример задачи С4 из демо- версии ЕГЭ-2009 На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат:, где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и, а также и разделены одним пробелом. Пример входной строки: Иванов П.С. 57 Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из каких школ было меньше всего участников олимпиады (но из этих школ был хотя бы один участник). Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи Максимальный балл за задачу: 4

39 5 Иванов П.С. 57 Петров И.С. 14 Сидоров К.Д. 25 Киселев П.О. 14 Трубов Д.Ю ……131415……2526……5758…… Для каждой строки повторять: Прочитать строку Выделить из нее номер школы Значение в ячейке массива, соответствующей номеру школы, увеличить на 1 кц Просмотреть массив, найти в нем значение минимального из ненулевых элементов Просмотреть массив еще раз, вывести на экран номера элементов, значения которых совпадают с найденным

40 program demo2009; var f:text; {файловая переменная} s:string; {строка} sc:integer; { школы из строки} i,k,osh:integer; n:integer; {кол участников = кол строк} min:integer; {min кол участников из школы} msc:array[1..99] of integer; {массив школ, в кот. считаем кол-во участников из данной школы} begin assign (f,'c:\1.txt'); reset(f); readln(f,n); {обнуляем массив школ} for i:=1 to 99 do msc[i]:=0; for i:=1 to n do begin {читаем строку} readln(f,s); {Выделяем из строки номер школы} k:=pos(' ',s); delete(s,1,k); {удалили фамилию} k:=pos(' ',s); delete(s,1,k); {удалили инициалы. Остался школы} val(s,sc,osh); {->integer} {Значение в ячейке массива, соотв. номеру школы, увеличить на 1} msc[sc]:=msc[sc]+1; end; min:=32767; {макс. возможное. Можно взять число n+1} for i:=1 to 99 do if msc[i]0 then if msc[i]

41 DIM msc(99) массив школ OPEN "c:\1.txt" FOR INPUT AS #1 открываем файл для чтения из него FOR i = 1 TO 99 обнуляем кол-во участников из каждой школы msc(i) = 0 NEXT i INPUT #1, n считываем кол-во участников для каждой строки повторяем: FOR i = 1 TO n INPUT #1, s$ввод строки FOR j = LEN(s$) TO 1 STEP -1 находим последний пробел IF MID$(s$, j, 1) = " " THEN k = j: j = 1 NEXT j sc$ = RIGHT$(s$, LEN(s$) - k) вырезаем то, что после последнего пробела sc = VAL(sc$)преобразовываем символьную величину в число msc(sc) = msc(sc) + 1 увеличиваем кол-во участников из соотв. школы NEXT iк след. строке Находим минимум min = n FOR i = 1 TO 99 IF msc(i) 0 THEN IF msc(i) < min THEN min = msc(i) END IF NEXT I Вывод PRINT «меньше всего участников"; min; из школ:" FOR i = 1 TO 99 IF msc(i) = min THEN PRINT i NEXT i END

42 program demo2009var2; var c:char; {вводимый символ} sc:integer; {номер школы} i:integer; n:integer; {kol uchastnikov = kol strok} min:integer; {min kol uchastnikov iz shkol} msc:array[1..99] of integer; {massiv shkol} begin readln(n); for i:=1 to 99 do msc[sc]:=0; for i:=1 to n do begin repeat read(c); until c=' ; {ввели фамилию} repeat read(c); until c=' ; {ввели инициалы} readln(sc); {вводим номер школы} msc[sc]:=msc[sc]+1; {увеличиваем кол-во участников из этой школы} end; И т.д. Другой вариант ввода данных: 1)читаем по символам фамилию (до пробела) и игнорируем ее 2)читаем по символам инициалы (до пробела) и также игнорируем. 3)далее считываем номер школы в числовом формате

43 … FOR i = 1 TO 99 обнуляем кол-во участников из каждой школы msc(i) = 0 NEXT i INPUT n FOR i = 1 TO n INPUT fam INPUT ini INPUT sc msc(sc) = msc(sc) + 1 увеличиваем кол-во участников из соотв. школы … Нарушение формата ввода исх. данных. За такое решение получить макс. кол-во баллов нельзя, но хоть что-то… (2 балла)

44 5 Иванов П.С. 57 Петров И.С. 14 Сидоров К.Д. 25 Киселев П.О. 14 Трубов Д.Ю. 25 K=1 Массив номеров школ Кол-во участников из данной школы K=0 K=2 K=

45 program demo2009v3; var f:text; {файловая переменная} s:string; {строка} sc:integer; {номер школы из строки} i,j,p,flag,osh:integer; n:integer; {кол участников} min:integer; {min кол участников из школы} k:integer; {кол-во записей в массиве} msc:array[1..99] of integer; {массив номеров школ} mkol:array[1..99] of integer; {массив кол-ва участников из школы} begin assign (f,'c:\1.txt'); reset(f); readln(f,n);k:=0; {кол-во записей в массиве школ} {Для каждой строки выделяем номер школы любым способом} for i:=1 to n do begin readln(f,s); p:=pos(' ',s); delete(s,1,p); {удалили фамилию} p:=pos(' ',s); delete(s,1,p); {удалили инициалы, остался школы} val(s,sc,osh); {->integer}

46 k:=0; {кол-во записей в массиве школ = 0. Эта к-да стоит ДО начала цикла обработки записей} flag:=0; for j:=1 to k do begin{ищем запись в массиве номеров школ} if sc= msc[j] then begin mkol[j]:=mkol[j]+1; flag:=1; break;{если нашли, то количество участников из этой школы увеличиваем на 1, устанавливаем флаг, что нашли, и заканчиваем просмотр} end; if flag=0 then begin{если не нашли школу (флаг остался = 0)} k:=k+1;msc[k]:=sc; mkol[k]:=1;{кол-во записей в массиве школ увеличивается, записываем школы и кол- во участников из этой школы = 1} end; min:=32767; {максимально возможное число} for i:=1 to k do if mkol[i]

47 Этот вариант для предыдущей задачи менее эффективен, чем первый вариант, но в следующих задачах возможен только он: Имеется список результатов голосования избирателей за несколько партий, в виде списка названий данных партий. На вход программе в первой строке подается количество избирателей в списке N. В каждой из последующих N строк записано название партии, за которую проголосовал данный избиратель, в виде текстовой строки. Длина строки не превосходит 50 символов, название может содержать буквы, цифры, пробелы и прочие символы. Пример входных данных: Программа должна вывести список всех партий, встречающихся в исходном списке, в порядке убывания количества голосов, отданных за эту партию. При этом название каждой партии должно быть выведено ровно один раз, вне зависимости от того, сколько голосов было отдано за данную партию. Пример выходных данных для приведенного выше примера входных данных: При этом следует учитывать, что количество голосов избирателей в исходном списке может быть велико (свыше 1000), а количество различных партий в этом списке не превосходит Party one Party two Party three Party two Party three Party two Party one

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

49 На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие символы, отличные от "." и букв "a".."z", во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать эффективную программу на языке Паскаль или Бейсик, которая будет печатать буквы, встречающиеся во входной последовательности, в порядке уменьшения частоты их встречаемости. Каждая буква должна быть распечатана один раз. Точка при этом не учитывается. Если какие-то буквы встречаются одинаковое число раз, то они выводятся в алфавитном порядке. Например, пусть на вход подаются следующие символы: batat. В данном случае программа должна вывести atb Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи

50 индекс 0123 …… a:Количество встреченных букв m: abcd……xyz Заводим массив кол-ва встреченных символов a, а также массив, в котором храним символы m. Вводим символ c. Определяем его номер и увеличиваем кол-во встреченных символов на 1. Сортируем массив кол-ва символов и параллельно - массив символов Печатаем значения отсортированного массива символов, пока в массиве кол-ва символов не встретится 0.

51 var a:array[0..25] of integer; {массив кол- ва встреч. букв} m:array[0..25] of 'a'..'z'; {массив с символами букв} c: char; {вводимый символ} i,j,k: integer; begin for i:=0 to 25 do begin a[i]:=0; {обнуление массива кол-ва} m[i]:=chr(ord('a')+i) {заполнение массива букв} end; read(c); { ввод символа} while c'.' do begin k:=ord(c)-ord('a') {определяем номер символа} a[k] := a[k] + 1; {увеличиваем кол- во встреч. символов} read(c); {ввод след. символа} end; {Сортировка пузырьком массива кол- ва букв и параллельно массива символов букв} for i:=1 to 25 do for j:=0 to 24 do {если два соседних элемента стоят неправильно, меняем их местами} if a[j]

52 var a:array[0..25] of integer; {массив кол-ва встреч. букв} c: char; {вводимый символ} i,j,k,max,nmax: integer; begin for i:=0 to 25 do a[i]:=0; read(c); while c'.' do begin k:=ord(c)-ord('a'); a[k] := a[k]+1; read(c); end; Repeat {находим максимум, печатаем его и обнуляем} max:=0; nmax:=0; for j:=0 to 25 do {находим макс. и его среди ненулевых эл-тов} if (a[j]0) and (a[j]>max) then begin max:=a[j]; nmax:=j; end; if max0 then begin write(chr(nmax+ord('a'))); {если макс. 0, то выводим символ} a[nmax]:=0; {обнуляем найденный элемент массива кол-ва букв} end; until max=0; {заканчиваем, когда найденный max остался = 0} end. II способ. Без использования дополнительного массива с символами. Индекс элемента соотв. номеру буквы. Сортировку не используем. Находим максимум, печатаем символ, затем обнуляем этот элемент в массиве кол-ва букв, чтобы больше не попадался a:Количество встреченных букв инд 0123………2425

53 var a:array['a'..'z'] of integer; {массив хранит кол-во соотв. символов} c: char; i,j,nmax: char; {индексами может быть ЛЮБОЙ перечисляемый тип} max:integer; begin for i:='a' to 'z' do a[i]:=0; read(c); while c'.' do begin a[c] := a[c]+1; read(c); end; for i:='a' to 'z' do begin max:=0; for j:='a' to 'z' do if a[j]>max then begin max:=a[j]; nmax:=j; end; if max=0 then break; {если макс. = 0, то заканчиваем} write(nmax); {выводим символ} a[nmax]:=0; {обнуляем элемент в массиве кол-ва букв, чтобы больше не попадался} end; writeln a:Количество встреченных букв инд abcd……xyz III способ. C использованием в качестве индексов элементов букв от 'а' до 'z. Сортировку не используем. Находим максимум, печатаем символ, затем обнуляем элемент в массиве кол-ва букв, чтобы больше не попадался

54 На вход программе подается последовательность символов, среди которых могут быть и цифры, отличные от нуля. Ввод символов заканчивается точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая составит из тех цифр, которые не встречаются во входных данных, минимальное число (ноль не используется). Каждая цифра при этом используется ровно один раз. Если во входных данных встречаются все цифры от 1 до 9, то следует вывести "0". Например, пусть на вход подаются следующие символы: 1А734В39. В данном случае программа должна вывести a

55 Кодировка ASCII

56 DIM i, j, k, a(9) AS INTEGER FOR i=1 T0 9 a(i) = 0 NEXT INPUT c$ DO WHILE c$ ". k = ASC(c$) - ASC("0") IF (k>0) AND (k0) and (k 0) AND (k0) and (k">

57 Var a: array[1.. 9] of boolean; c: char; i, k: integer; begin for i:= 1 to 9 do a[i]:=false; read(c); while c'.' do begin k:=ord(c)-ord('0'); if (k>0) and (k

58 Пример задачи С4 из демо-версии ЕГЭ-2010 На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, СКОЛЬКО АЗС продают его дешевле всего. На вход программе в первой строке подается число данных о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате:

59 Программа читает все входные данные один раз, НЕ запоминая их в массиве, размер которого соответствует числу АЗС или диапазону цен. Во время чтения данных определяются минимальная цена каждой марки бензина и количество АЗС, продающих его по этой цене. где – строка, состоящая не более, чем из 20 символов без пробелов, – строка, состоящая не более, чем из 20 символов без пробелов, – одно из чисел – 92, 95 или 98, – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: Синойл Цветочная Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0. Пример выходных данных: Решение

60 Программа читает все входные данные один раз, НЕ запоминая их в массиве, размер которого соответствует числу АЗС или диапазону цен. Во время чтения данных определяются минимальная цена каждой марки бензина и количество АЗС, продающих его по этой цене. Для этого используются 6 переменных или соответствующие массивы (например, для удобства из 7 элементов каждый). Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой марки бензина минимальная цена отмечена ровно на одной АЗС). Решение Марка бензина92……95……98 Мин. цена соотв. марки Кол-во АЗС, продающих бензин соотв. марки по мин. цене

61 var min, azs: array[92..98] of integer; {хранит минимальную цену соотв. марки} c: char; i, k, N, b: integer; begin for i:=92 to 98 do begin min[i]:=3001; {допустимо и другое число, >3000} azs[i]:=0; end; readln(N); for i:=1 to N do begin repeat read(c); until c=' '; {считана компания} repeat read(c); until c=' '; {считана улица} readln(k,b); {считываем марку и цену} if min[k] > b then begin min[k]:=b; azs[k]:=1; end else if min[k] = b then azs[k]:=azs[k]+1; end; {если бензина какой-то марки не было, azs[k] осталось равным 0} writeln(azs[92],' ', azs[95], ', azs[98]); end.

62 Таблица перевода первичных баллов в тестовые по годам

63