Пример типичного условия задачи С4 из проекта демо-версии 2010 года: На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе. - презентация

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

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

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

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

5 Поясним общие для всех заданий С4 дополнительные условия и рекомендации программисту. Что значит "эффективная по времени работы и по используемой памяти программа"? Эффективная по времени работы программа не должна содержать лишних операций, Что значит ''эффективная по используемой памяти программа"? Эффективная по памяти программа не должна содержать лишних выделений памяти. Сложность алгоритмов: О(N) - сложность алгоритма с одним или несколькими простыми (не вложенными!) циклами в каждом из которых выполняется N шагов (как при поиске минимального элемента) Если в одном алгоритме решения задачи используется несколько циклов от 1 до N, а во втором – только один цикл, то алгоритм с одним циклом, как правило, эффективнее (хотя оба алгоритма имеют сложность О(N), O(N 2 ) - сложность алгоритма, когда, например,в программе используется два вложенных цикла, в каждом из которых N шагов; такую сложность имеют простые способы сортировки массивов: метод «пузырька», метод выбора. Алгоритм, имеющий сложность O(N 2 ) всегда менее эффективен, чем алгоритм сложности О(N). Алгоритмы сложности O(N 3 ) (например, три вложенных цикла от 1 до N), работают медленнее, чем любой алгоритм сложности, то есть, менее эффективны.

6 Приведем пример идеи правильного, но неэффективного по использованию памяти решения рассматриваемой задачи: 1.при считывании исходных данных запомним цены на бензин в отдельном массиве для каждой марки бензина; 2. в цикле найдем минимум для каждого из трех массивов; 3. в следующем цикле найдем, сколько элементов в каждом массиве равны минимальному. Паскаль Неэффективное решение: Var A: Array [ ] Of Integer; I,N, Min, Count: Integer; Begin ReadLn (N); for I:=l to N do ReadLn (A[I]); Min := 3001; {все значения по условию заведомо меньше Min} For I:=l To N do If (A[I] < Min) then Min := A[i]; Count := 0; For I:=l To N Do If (A[I] = Min) Then Count := Count+1; WriteLn (Min, Count); End.

7 Паскаль Эффективное решение: Begin Count := 0; Min := 3001; ReadLn (N); For I:=l To N Do Begin ReadLn (A); If A = Min Then Count := Count+1; If A < Min Then Begin Min : = A; Count := 1; End; WriteLn (Min, Count); End. или Begin Count := 0; Min := 3001; ReadLn (N); For i:=1 To N Do Begin ReadLn (A); If A < Min Then begin Min : = A; Count := 1; end Else If A = Min Then Count := Count+1; end; WriteLn (Min, Count); End.

8 Косвенное указание на то, что надо искать алгоритм решения, не использующий копирование входных данных в массив, можно получить, анализируя условие задачи. В условии нет ограничения на количество АЗС в городе, поэтому формально оно может быть очень большим, и статическое выделение памяти определенного размера (в примере - массив из целых чисел) тем самым исключено. Необходимо пояснить, что требование эффективности по памяти и по времени не является неким искусственным ограничением, дополнительным "барьером" для учащегося, но отражает профессиональную практику программирования. Конечно, объемы памяти и быстродействие современных компьютеров растут очень быстро, но не стоит забывать, что объемы обрабатываемых данных в условиях всеобщей информатизации растут не медленнее, а иногда и опережающими темпами.

9 Вернемся к условию задачи. В нем содержится рекомендация "укажите используемую версию языка программирования, например, Borland Pascal 7.0". Для чего это нужно делать? Дело в том, что образовательные стандарты не конкретизируют обязательный для изучения язык программирования. Поэтому выбор конкретного языка (языков) программирования, на примере которого раскрывается содержание тем "Алгоритмизация и программирование" и «Технология программирования» остается за учебными заведениями. Практика показывает, что в российских школах наиболее часто изучаемыми являются Pascal и Basic. На третьем месте по частоте изучения С или C++. Гораздо реже встречаются такие "экзотические" для средней школы языки как С#, Java, PHP, Perl, Python, Лого (последний "экзотический" для решения задач рассматриваемого типа, хотя он и достаточно распространен в основной школе). На экзамене учащийся может решать задание С4 на любом языке программирования, которым он владеет, его работа будет проверена и объективно оценена. Выбор конкретного языка на оценку не влияет. В системе оценивания не предусмотрены бонусы за выбор "правильного" или "оригинального" языка программирования, поэтому выпускникам, владеющим несколькими языками программирования, следует руководствоваться следующими критериями: каким языком лучше владеет экзаменуемый; какой лучше подходит для решения поставленной задачи. Ни в коем случае не следует руководствоваться принципом "удивить экзаменационную комиссию редким или сверхновым языком программирования". Проверяющих интересует правильность предложенного решения, а не распространенность и модность языка, на котором оно выполнено.

10 Ввод данных В заданиях С4 можно выделить типичные элементы решения, в которых можно использовать стандартные программистские приемы. Одним из самых важных элементов является ввод данных. В заданиях всегда указывается источник входных данных, обычная формулировка такова: "На вход программе подаются...". Эта фраза означает что программа должна читать данные из стандартного входного потока. В Паскале для организации ввода из входного потока используются стандартные процедуры Read и ReadLn, ( ReadLn после чтения своих аргументов переходит на следующую строку). Во многих заданиях С4 входные строки состоят из значений различных типов. В данном примере они организованы следующим образом: В первой строке находится N - число строк данных о стоимости бензина. В каждой из следующих N строк находится информация в следующем формате:, где - строка, состоящая не более, чем из 20 символов без пробелов, - одно из чисел - 92, 95 или 98, - целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. и, и, а также и разделены ровно одним пробелом. Пример входной строки: МигОйл Мичуринский

11 var Street, Company : string; с: char; Mark, Price : integer; … Company:='; read(c); while с do begin Company := Company. + c; {'+' в данном случае операция конкатенации, т.е. "склеивания" символьных значений} read(с); end; {считана компания} Street:= '; read(с); while c do begin Street := Street + c; read(c); end; {считана улица} readln(Mark, Price); В этой задаче данные никак не используются, но, тем не менее, их надо корректно обработать при вводе. Приведем пример фрагмента программы, выполняющий ввод и разбор одной строки в формате.

12 … repeat read(c); until c=' '; {считана компания} repeat read(c); until c=' ' ; {считана улица} readln(Mark, Price); … ИЛИ еще пример:

13 repeat read(c); until c=' ' ; {считана улица} readln(m,pr); {ввод марки бензина и цены} if min[m] > pr then begin min[m]:=pr; ans[m]:=1 end else if min[m] = pr then ans[m]:=ans[m]+1; end; {если бензина какой-то марки не было, ans[i] осталось равным 0} writeln(ans[92],' ', ans[95],' ', ans[98]) end. Пример правильной и эффективной программы Var min, ans: array[92,.98] of integer; c: char; i, m, N, pr: integer; begin for i:=92 to 98 do begin min[i] :=3001; {допустимо и другое число, >3000} ans[i]:=0; end; readin(N); for i:=l to N do begin repeat read(c); until c=' '; {считана компания}

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

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

16 Под синтаксическими понимаются ошибки в написании названий операторов и имен стандартных функций языка программирования, неверные расстановки и пропуски скобок, использование неописанных переменных (в тех языках, где описание переменных обязательно) т.е. все нарушения синтаксических правил языка программирования. Пример фрагмента программы с синтаксическими ошибками. Фрагмент предназначен для поиска минимального значения элемента непустой входной последовательности из 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 = А; 4. неправильно написано имя стандартной процедуры вывода - 'writel' вместо правильного 'writeln' или 'write'.

17 Логическими ошибками, как следует из их названия, являются ошибки в алгоритме, в логике программы. В отличие от синтаксических ошибок, логические ошибки не выявляются транслятором. Программа с логическими ошибками будет запускаться, не исключено, что будет внешне благополучно работать, выдавать результаты, возможно, иногда правильные. Но при некоторых исходных данных программа с логической ошибкой будет работать неверно. Пример тех же фрагментов программ поиска минимума непустой последовательности, но уже с логической ошибкой: Паскаль var A, i, N, Min: integer; begin readln (N); Min := 0; for i:=l to N do begin readln (A); if (A < Min) then Min := A; end; writeln (Min);

18 Пример 2. На вход программе подается текст заклинания, состоящего не более чем из 200 символов, заканчивающийся точкой (символ "точка" во входных данных единственный). Оно было зашифровано Гарри Поттером следующим образом: он заменил каждую английскую букву в заклинании на следующую за ней вторую по счету в алфавите (алфавит считается циклическим, то есть за буквой Z следует буква А) оставив другие символы неизменными. Строчные буквы при этом остались строчными, а прописные - прописными. Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран текст расшифрованного заклинания. Например, если зашифрованный текст был таким: Bd Тс Ее Fed Тс. то результат расшифровки должен быть следующим: Zb Ra Ca Dab Ra. Обработка символьной информации Значительное число заданий С4 связано с обработкой символьной информации. Рассмотрим некоторые стандартные приемы преобразования символьных данных.

19 В данном случае можно поступить двумя способами: 1) Считывать всю строку целиком в некоторую переменную строкового и типа и далее обрабатывать ее посимвольно. 2) Читать исходные данные посимвольно и сразу их посимвольно обрабатывать. Рассмотрим сначала реализацию первого способа ввода на Турбо-Паскале. var str : string; i: integer; begin readln (str); i:=l; while str [i] '.' do begin {Обработка входной строки, которую мы рассмотрим позднее} i:=i+1; end end. Из примера видно, что строковый тип String Турбо-Паскаля позволяет обращаться к отдельному символу строки как к элементу массива - по его индексу (номеру), при этом номера символов в строке начинаются с единицы.

20 Рассмотрим посимвольный ввод строки на Паскале для нашей задачи: var с : char; begin read (с) ; {читаем самый первый символ} while с . do begin {Обработка символа, которую мы рассмотрим позднее} read (с) ; {читаем очередной символ} end end. Обратите внимание, что в двух последних примерах оператор ввода символа встречается два раза: перед циклом и внутри цикла. Это сделано для того, чтобы избежать обработки завершающего символа (точки) внутри цикла, целиком «посвятив» его непосредственно преобразованию строки.

21 Основной проблемой теперь является циклическая замена букв в строке. Решение с отдельной обработкой каждой буквы в стиле: If Strti] = 'A' Then Str[i] = ' Y' ; If Str[i] = 'В' Then Str[i] = 'Z'; If Str[i] = 'C Then Str[i] = 'A'; и т.д. или Case Str[i] Of 'A' : Str[i] := 'Y'; 'B' : Str[i] := Z'; C: Str[i]:= A … Z': Str[i] := X ; a': Str[i] := 'y'; … 'z': Str[i] := 'x'; end; является слишком громоздким. Попробуем найти более общее решение.

22 Сначала рассмотрим частный случай - когда обрабатываемые буквы находятся достаточно далеко от начала алфавита и перехода через букву А (а) при расшифровке не происходит. В этом случае перекодировка очевидно сводится к замене символа с номером (кодом) N на символ с номером N – 2. В Паскале существует функция Ord(x), которая возвращает порядковый номер символа Итак, мы можем вычислить N -2. Теперь остается только по значению N - 2 получить символ с соответствующим номером в таблице ASCII. Для этой цели в Паскале служит функция Chr(x) (обратная к Ord), которая преобразует выражение типа byte в символ и возвращает тот символ в качестве своего значения. Дешифровка буквы будет выглядеть следующим образом: if Str[i] in ['С'.. ' Z', 'c'..'z'] then Str[i] := chr (ord (Str[i]) - 2); Для того чтобы решить проблему перехода через начало алфавита, случай первых букв можно рассмотреть отдельно, например if Str[i] in ['C'..'Z', 'c'..'z'] then Str[i] = chr (ord (Str[i]) -2) else if Str[i] = B' then Str[i] := 'Z else if Str[i] = 'A' then Str[i] := 'Y'

23 Такое решение имеет право на существование, но лучше найти общую формулу. Смещение дешифрованной буквы от конца алфавита для прописных букв 'А' и 'В' определяется выражением ord (Str [i] ) – 2 - ord (A) +1. Покажем это ord (Str [i] ) -2 код дешифрованной буквы "вылезающий" за начало алфавита, в том случае, если он меньше ord('A'). Поэтому разность (ord (Str [i] ) -2) –ord (' A') показывает, на сколько единиц код новый буквы "вылезает" за пределы алфавита. Если эта разность больше нуля, то имеет место переход через начало алфавита, а именно - если она 1, то новая буква должна быть 'Z', если 2, то Y и т.д. Поэтому код дешифрованной буквы будет: ord('Z') + ord (Str[i]) -2 - ord ('A) + 1. Если бы смещение при дешифровке было бы равно не 2, а некоторому числу X (0

24 Приведем пример полного решения задачи: var с : char; begin read (с); {читаем самый первый символ} while с '.' do begin {Обработка символа} if с in ['C'..'Z', 'c'..'z'] then с := chr (ord (с) - 2) else if с in ['A'..'B, 'a..'b'] then с := chr (ord (c) + 24); write (c); read (с); {читаем очередной символ}. end; writeln; end.

25 Мы разобрали решение упрощенного задания ЕГЭ. В реальном задании величина сдвига не фиксирована, а равна минимальной длине слова в тексте, что делает задание более сложным. Вот текст реального задания. На вход программе подается текст заклинания, состоящего не более чем из 200 символов, заканчивающийся точкой (символ "точка" во входных данных единственный). Оно было зашифровано Гарри Поттером следующим образом. Сначала Гарри определил количество букв в самом коротком слове, обозначив полученное число К (словом называется непрерывная последовательность английских букв, слова друг от друга отделяются любыми другими символами, длина слова не превышает 20 символов). Затем он заменил каждую английскую букву в заклинании на букву, стоящую в алфавите на К букв ранее (алфавит считается циклическим, то есть перед буквой А стоит буква Z, оставив другие символы неизменными. Строчные буквы при этом остались строчными, а прописные - прописными. Требуется написать программу на любом языке программирования, которая будет выводить на экран текст расшифрованного заклинания. Например, если зашифрованный текст был таким: Zb Ra Ca Dab Ra. то результат расшифровки должен быть следующим: Bd Тс Ее Fed Тс. Предлагаем самостоятельно разобрать авторское решение задачи и критерии оценивания с учетом того, что задание отличается от рассмотренного нами упрощенного варианта еще и направлением сдвига при шифровке-дешифровке.

26 Из условия становится ясно, что задача решается в два этапа: прочитать символы до точки и определить длину самого короткого слова из латинских букв (обозначим ее minLen); сделать «сдвиг» кодов латинских букв на minLen влево. Начнем с первого. Простое посимвольное чтение строки s до первой встреченной точки выглядит так (здесь c – переменная типа char): s := ''; { пустая строка } repeat read(c); { прочитали символ } s := s + c; { добавили в конец строки } until c = '.'; При этом нам нужно еще определить длину самого короткого слова с учетом того, что между словами может быть сколько угодно символов-разделителей (разных!). Введем переменную len, которая будет определять длину текущего (очередного, вводимого в данный момент) слова. Как определить, что прочитанный символ – латинская буква? Конечно, можно использовать условный оператор со сложным условием: if (('a'

27 Если очередной прочитанный символ – латинская буква, нужно увеличить len на единицу (слово продолжается). Если же это не латинская буква, то слово закончилось, так как встречен символ-разделитель. Если в переменной len ненулевое значение, нужно сравнить эту длину с минимальной и, если прочитанное слово короче всех предыдущих, записать его длину в minLen. Таким образом, цикл ввода выглядит так: s := ''; minLen := 201; { любое число > 200 } len := 0; repeat read(c); s := s + c; if c in['a'..'z','A'..'Z'] then len := len + 1 else begin if (len > 0) and (len < minLen) then minLen := len; len := 0; end; until c = '.';

28 Теперь нужно в цикле пройти всю прочитанную строку и «сдвинуть» каждый символ (точнее, его код) вправо на minLen: for i:=1 to Length(s) do if s[i] in ['a'..'z','A'..'Z'] then begin code := Ord(s[i]); { старый код } k := code - minLen; { новый код } s[i] := Chr(k); end; Однако такое решение не учитывает цикличность: например, при сдвиге буквы 'A' на 2 символа влево мы не получим 'Y'. Поэтому после изменения кода нужно проверить, не вышел ли он за допустимые границы (диапазона латинских букв), а если вышел, то добавить к полученному коду 26 (число латинских букв), что обеспечит циклический сдвиг: k := code - minLen; { новый код } { цикличность } if s[i] in ['a'..'z'] then if k < Ord('a') then k := k + 26; if s[i] in ['A'..'Z'] then if k < Ord('A') then k := k + 26;

29 { сдвиг кодов на minLen влево } for i:=1 to Length(s) do if s[i] in ['a'..'z','A'..'Z'] then begin code := Ord(s[i]); { старый код } k := code - minLen; { новый код } { цикличность } if s[i] in ['a'..'z'] then if k < Ord('a') then k := k + 26; if s[i] in ['A'..'Z'] then if k < Ord('A') then k := k + 26; { запись нового кода } s[i] := Chr(k); end; writeln(s); end. Вот полная программа: var c: char; s: string; len, minLen, code, i, k: integer; begin s := ''; minLen := 201; { любое число > 200 } len := 0; { чтение данных } repeat read(c); s := s + c; if c in['a'..'z','A'..'Z'] then len := len + 1 else begin if (len > 0) and (len < minLen) then minLen := len; len := 0; end; until c = '.';

30 var f:boolean; i, k, min: integer; c,cnew:char; s: string; begin s:= ; min:=250; k:=0; f:=false; repeat read(c); s:=s+c; if f then {слово началось} if с in ['a'..z', 'A'.. 'Z' ] then k:=k+l else begin if k

31 На вход программы подается текст на английском языке, заканчивающийся точкой (другие символы. в тексте отсутствуют). Требуется написать программу, которая будет определять и выводить на экран английскую букву, встречающуюся в этом тексте чаще всего, и количество там таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть файл содержит следующую запись: It is not a simple task. Yes! Чаще всего здесь встречаются буквы I, S и T (слово Yes в подсчете не учитывается, так как расположено после точки). Следовательно, в данном случае программа должна вывести два символа, разделенных пробелом: I 3

32 Здесь нужно считать одинаковые буквы, которых всего может быть 26 (от A до Z), причем строчные и заглавные буквы считаются вместе. Поэтому создаем массив счетчиков из 26 элементов: var count: array[1..26] of integer; Для удобства можно сразу коды букв A и a и записать в целые переменные cA := Ord('A'); { заглавные } cAm := Ord('a'); { строчные } В цикле, прочитав очередной символ, находим его код с помощью функции Ord, k := Ord(c); Если это заглавная буква, то номер символа в алфавите вычисляется как k- cA+1, а для строчных k-cAm+1, соответствующий счетчик (элемент массива) нужно увеличить на 1: if ('A'

33 Полная программа: 1вариант программы var count:array[1..26] of integer; i, k, cA, cAm, iMax:integer; c: char; begin cA := Ord('A'); cAm := Ord('a'); for i:=1 to 26 do count[i] := 0; repeat read(c); k := Ord(c); if ('A'

34 2 вариант программы

35 В заданиях С4 также встречаются исходные данные, которые имеют свой внутренний формат - обычно комбинацию целочисленного и строкового типа, возможно, с использованием некоторых разделителей. Примеры: - номер класса из одной или двух цифр от 0 до 12 и вплотную за ним буква класса - 10Б или 1а (возможность использования строчных и прописных букв должна быть оговорена в условии) - два двузначных числа из соответствующего диапазона, разделенных двоеточием, например, - 17:45 или 20:07. Как правильно записывается время "6 часов 15 минут" 6:15 или 06:15 - должно быть оговорено в условии. - двузначные числа из соответствующего диапазона, разделен­ные точками, например, или Паскаль и Бейсик не предоставляют стандартных средств для ввода данных в таких форматах, поэтому данные сложной структуры следует вводить в виде строки символов (или последовательности из отдельных символов) с последующей обработкой (разбором) в том случае, если программе нужно получить доступ к отдельным элемен­там комбинированных данных. Рассмотрим разбор поля с выделением номера класса как целого числа и буквы класса как символа. Будем считать, что это поле содержится в отдельной строке исходных данных.

36 Фрагмент программы на языке Паскаль: var с, letter: char; N: 1..12; read (с); {1-й символ} N := Ord (с) - Ord ('0'); {в N - число, равное значению первой цифры} read (с) ; {2-й символ} if с in [ ' 0 '.. '9 ] Then {если 2-й символ - цифра} begin N := N*10 + ord(с) - ord ('0'); {Вычисляем номер класса} read (с); {и читаем следующий символ - букву класса} end; Letter := с; {в Letter - буква класса} Этот фрагмент требует пояснений. В Турбо Паскале есть стандартное средство преобразования символьной строки в число - процедура Val. Мы могли бы найти в строке границы числа, вырезать его в отдельную текстовую строку и вызвать эту процедуру, Но в данном случае мы выбрали простое и красивое решение. Мы самостоятельно преобразовали символы, обозначающие цифры числа в само число.

37 Для этого мы воспользовались стандартной функцией Паскаля Ord, аргументом которой является некоторый символ, а результатом - ASCII код этого символа. Итак, Ord(c) - это ASCII код символа 'с', но нам нужен не сам ASCII код символа обозначающего цифру, а число, равное значению этой цифры. Мы знаем, что в коде ASCII символы десятичных цифр расположены подряд от '0' до '9'. Поэтому значением выражения Ord(c) - Ord ('0') (где с - символ десятичной цифры) всегда будет числовое значение этой цифры. При этом нам не нужно знать значения ASCII кода ни нуля, ни остальных цифр. Такой технический прием очень часто применяется при преобразовании символьных данных в числовые "вручную". Нам заранее неизвестно, сколько цифр в номере класса - одна или две, поэтому мы проверяем 2-й считанный символ на принадлежность множеству цифр ['0'..'9']. Если он цифра, то очевидно, что предыдущей символ был числом десятков, а анализируемый символ является цифрой, в которой хранится число единиц в номере класса. Поэтому значением номера класса в этом случае будет N*10 + Ord(c) - Ord ('0'), а буквой - следующий символ.

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

39 На вход программы подается 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен. Требуется написать программу на языке Паскаль или Бейсик, которая будет выводить на экран информацию о месяце (месяцах), среднемесячная температура у которого (которых) наименее отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке в виде: номер месяца, значение среднемесячной температуры, отклонение от среднегодовой температуры.

40 В этой задаче не нужно хранить в памяти все отсчеты, нас интересуют только средние значения температуры по каждому месяцу и по году, поэтому алгоритм на псевдокоде выглядит так: { ввод данных, накопление сумм по месяцам и за год } { вычисление средних по месяцам и по году } { поиск месяца с минимальным отклонением t от средней по году } { вывод всех месяцев с таким же отклонением } В начале программы не забываем обнулить ячейки, где будут накапливаться суммарные величины: for i:=1 to 12 do tMonth[i]:= 0; tYear := 0; При вводе данных в каждой строке сначала пропускаем все символы до точки (посимвольное чтение), затем читаем номер месяца (целое число) и температуру (вещественное число); температуру добавляем к сумме нужного месяца и к годовой сумме: for i:=1 to DAYS do begin repeat read (c); until c = '.'; read (month); readln (t); tMonth[month] := tMonth[month] + t; tYear := tYear + t; end;

41 Далее находим средние по каждому месяцу и по году (важно! месяцы имеют разное число дней, 2008-ой год – високосный, поэтому в феврале 29 дней) for i:=1 to 12 do case i of 2: tMonth[i] := tMonth[i] / 29; 4,6,9,11: tMonth[i] := tMonth[i] / 30; else tMonth[i] := tMonth[i] / 31; end; tYear := tYear / DAYS; Определить среднюю температуру по месяцам можно более красиво, если ввести массив констант – дней в каждом месяце: const days: array[1..12] of integer = (31,29,31,30,31,30,31,31,30,31,30,31); а потом сделать так: for i:=1 to 12 do tMonth[i] := tMonth[i] / days[i]; но PascalABC, например, не поддерживает константные массивы. Теперь можно искать минимальное отклонение среднемесячной температуры от среднегодовой (важно! не забываем ставить модуль): min := abs(tMonth[1] - tYear); for i:=2 to 12 do if abs(tMonth[i] - tYear) < min then min := abs(tMonth[i] - tYear);

42 for i:=1 to 12 do case i of 2: tMonth[i] := tMonth[i] / 29; 4,6,9,11: tMonth[i] := tMonth[i] / 30; else tMonth[i] := tMonth[i] / 31; end; tYear := tYear / DAYS; min := abs(tMonth[1] - tYear); for i:=2 to 12 do if abs(tMonth[i] - tYear) < min then min := abs(tMonth[i] - tYear); writeln(tYear:0:2); for i:=1 to 12 do if abs(tMonth[i] - tYear) = min then writeln(i,' ',tMonth[i]:0:2,' ',tMonth[i]-tYear:0:2); end. Приведем полную программу: const DAYS = 366; var tMonth: array[1..12] of real; i, month: integer; t, tYear, min: real; c: char; begin for i:=1 to 12 do tMonth[i]:= 0; tYear := 0; for i:=1 to DAYS do begin repeat read(c); until c = '.'; read (month); readln (t); tMonth[month] := tMonth[month] + t; tYear := tYear + t; end;