Методические подходы к обучению способам решения задач С2 и С4 ЕГЭ по информатике (на примере записи программ на естественном языке и языке Паскаль) Учитель информатики ГБОУ СОШ 1238 Леонова Елена Валентиновна

Цель: предложить методику подготовки учащихся к решению задач С2, С4 ЕГЭ по информатике (из опыта учителя) 2

Почему стоит решать задачи С2, С4. Аргументы «за» учащемуся: 3 Во-вторых, «заработав» на них баллы, можно компенсировать возможный неуспех «по невнимательности» в заданиях частей А и В. Во-первых, если отбросить страхи, эти задания не намного сложнее, чем другие. В-третьих, при знании критериев проверки этих заданий есть шанс повысить свой итоговый балл.

Методические подходы к обучению способам решения задачи С2 ЕГЭ по информатике 4 Для подготовки обучающегося, учителю необходимо: 1) выявить специфику задания типа С2 (что именно и при каких «стартовых» условиях должен сделать учащийся); 2) предложить краткое и простое описание последовательности этапов решения задачи; 3) определить требования к подготовке учащегося, необходимые для решения задач типа С2 4) рассмотреть и проанализировать критерии проверки задач типа С2; 5) рассмотреть подходы к выполнению учащимся каждого этапа решения задачи;

5 Задачи этого типа направлены на обработку массива по некоторым критериям. От учащегося требуется «дописать» программу, приводящую к решению поставленной задачи. В итоге структура программы должна приобрести вид: 1) Организация ввода данных (уже есть) 2) Инициализация начальных значений некоторых переменных (требуется задать!) 3) Обработка данных (требуется организовать!) 4) Вывод данных (требуется организовать!). Обработка данных происходит в процессе циклической обработки элементов (или пар соседних элементов) по некоторому комбинированному условию, которое учащемуся необходимо формализовать на основе анализа условия задачи. В качестве условий могут быть как обязательное наличие признака, так и его отсутствие (например, элемент массива не делится на 2).

6 Признак Пример его формального описания для некоторого элемента массива А принадлежность к положительным /отрицательным числам A[i]>0/ A[i]=100) and (A[i] A[i]*3 Примеры формализации некоторых типичных для С2 составляющих комбинированного условия:

Требования к уровню подготовки выпускников, достижение которых проверяется на едином государственном экзамене по информатике и ИКТ, необходимые для решения С2: 7 Запись натурального числа в позиционной системе с основанием меньшим или равным 10. Обработка и преобразование такой записи числа. Нахождение сумм, произведений элементов данной конечной числовой последовательности (или массива). Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту, и т.д.). Заполнение элементов одномерного и двумерного массива по заданным правилам. Операции с элементами массива. Линейный поиск элемента. Вставка и удаление элементов в массиве. Перестановка элементов данного массива в обратном порядке. Суммирование элементов массива. Проверка соответствия элементов массива некоторому условию. Нахождение второго по величине (второго максимального или второго минимального) значения в данном массиве за однократный просмотр массива. Нахождение минимального (максимального) значения в данном массиве и количества элементов, равных ему, за однократный просмотр массива. Операции с элементами массива, отобранными по некоторому условию. (Например, нахождение минимального четного элемента в массиве, нахождение количества и суммы всех четных элементов в массиве.) Сортировка массива.

Критерии проверки С2 или на что обратить внимание учащихся. Каким должно быть решение на 2 балла: 8

Как видно из критериев проверки С2 программу можно описать и на естественном языке. Рассмотрим и проанализируем пример такого описания (по демонстрационному варианту ФИПИ) параллельно с описанием решения на Паскале на примере следующей задачи: 9 Пример С2-1. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9. Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено». Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).

10 Пример С2-1. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9. Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено». Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, MAX. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. … Верное решение на естественном языке

11 Пример С2-1. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9. Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено». const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено);

12 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных не инициализируется или неверно инициализируется переменная MAX (например, присваивается начальное значение, большее или равное 100); найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9.

13 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных неточно определяется принадлежность диапазону трёхзначных чисел (например, в сравнении со 100 вместо знака «больше или равно» используется знак «больше»; также обратите внимание, что с учётом ограничения на кратность 9 допустима проверка на принадлежность диапазону от 100 до 998); найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9. Элементы массива могут принимать целые значения от 0 до включительно.

14 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных неверно осуществляется проверка делимости на 9; на делимость на 9 проверяется не значение элемента, а его индекс; найти и вывести максимальное значение среди трёхзначных элементов массива, не делящихся на 9.

15 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных в сложном условии вместо логической операции «И» используется логическая операция «ИЛИ»;

16 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных отсутствует вывод ответа, или при выводе ответа не учитывается случай, когда требуемого числа в массиве может не быть; Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом не кратно 9, то выведите сообщение «Не найдено».

17 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Верное решение max := 99; for i := 1 to N do if (a[i]>=100) and (a[i] 0) and (a[i]>max) then max := a[i]; if max > 99 then writeln(max) else writeln(Не найдено); Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных не указано или неверно указано условие завершения цикла;

18 const N = 20; var a: array [1..N] of integer; i, j, max: integer; begin for i := 1 to N do readln(a[i]);... end. Каким может быть решение на 1 балл: Наличие только одной ошибки из нижеперечисленных используется переменная, не объявленная в разделе описания переменных;

const N=20; var a:array[1..N] of integer; i,j,max: integer; begin for i:=1 to N do readln(a[i]); … end. Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди элементов массива, которые имеют чётное значение и являются трёхзначными. Если в исходном массиве нет элемента, значение которого является чётным трёхзначным числом, то вывести сообщение «Не найдено». Задача С Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, MAX. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. …

const N=20; var a:array[1..N] of integer; i, j, max: integer; begin for i:=1 to N do readln(a[i]); end. найти и вывести максимальное значение Если в исходном массиве нет элемента, вывести сообщение «Не найдено». Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди элементов массива, которые имеют чётное значение и являются трёхзначными. Если в исходном массиве нет элемента, значение которого является чётным трёхзначным числом, то вывести сообщение «Не найдено». max:=0; for i:=1 to N do begin end; If max=0 then writeln(не найдено) else writeln(max); Элементы массива могут принимать целые значения от 0 до включительно. 20 Задача С2-1

const N=20; var a:array[1..N] of integer; i, j, max: integer; begin for i:=1 to N do readln(a[i]); end. максимальное значение среди элементов массива, которые имеют чётное значение и являются трёхзначными. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди элементов массива, которые имеют чётное значение и являются трёхзначными. Если в исходном массиве нет элемента, значение которого является чётным трёхзначным числом, то вывести сообщение «Не найдено». max:=0; for i:=1 to N do begin end; If max=0 then writeln(не найдено) else writeln(max); If (a[i]> max) and (a[i] mod 2 =0) and (a[i]>=100 ) and (a[i]

const N=20; var a:array[1..N] of integer; i, j, max: integer; begin for i:=1 to N do readln(a[i]); … end. max:=0; for i:=1 to N do begin If (a[i]> max) and (a[i] mod 2 =0) and (a[i]>=100 ) and (a[i]

Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, MAX. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. … Записываем в переменную max начальное значение, равное 0. В цикле от 1-го элемента до 20-го выполняем проверку каждого элемента массива с соответствующим индексом по следующему условию: Если элемент массива больше или равен 100 и меньше или равен 999 и в остатке от деления на 2 дает ноль и больше значения переменной max, то переменной max присваиваем значение этого элемента массива. Переходим к следующему элементу. После завершения цикла проверяем значение переменной max. Если оно равно нулю, то выводим «не найдено», иначе выводим значение переменной max. Полный вид решения на естественном языке 23 Задача С2-1

24 const N=30; var a: array [1..N] of integer; i, j, min: integer; begin for i:=1 to N do readln(a[i]); … end. Задача С2-2 Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от 150 до 200 – рост учащихся выпускного класса. В баскетбольную команду входят все учащиеся класса, чей рост не менее 180 сантиметров. Гарантируется, что такие учащиеся в классе есть. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит рост самого низкого участника баскетбольной команды. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них. Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. …

25 const N=30; var a: array [1..N] of integer; i, j, min: integer; begin for i:=1 to N do readln(a[i]); … end. Задача С2-2 учащиеся класса, чей рост не менее 180 сантиметров. Гарантируется, что такие учащиеся в классе есть. В баскетбольную команду входят все учащиеся класса, чей рост не менее 180 сантиметров. Гарантируется, что такие учащиеся в классе есть. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит рост самого низкого участника баскетбольной команды. min:=200; for i:=1 to N do begin end; writeln(min); Элементы массива могут принимать значения от 150 до 200 – рост учащихся выпускного класса.

26 const N=30; var a: array [1..N] of integer; i, j, min: integer; begin for i:=1 to N do readln(a[i]); … end. Задача С2-2 В баскетбольную команду входят все учащиеся класса, чей рост не менее 180 сантиметров. Гарантируется, что такие учащиеся в классе есть. рост самого низкого участника баскетбольной команды. В баскетбольную команду входят все учащиеся класса, чей рост не менее 180 сантиметров. Гарантируется, что такие учащиеся в классе есть. Опишите на русском языке или на одном из языков программирования алгоритм, который находит и выводит рост самого низкого участника баскетбольной команды. min:=200; for i:=1 to N do Begin end; writeln(min); If (a[i] =180) then min:=a[i];

27 const N=30; var a: array [1..N] of integer; i, j, min: integer; begin for i:=1 to N do readln(a[i]); … end. Задача С2-2 min:=200; for i:=1 to N do Begin If (a[i] =180) then min:=a[i]; end; writeln(min); Полный вид решения на языке Паскаль АВС 3.0.1

28 Задача С2-2 Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, J, MIN. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. … Полный вид решения на естественном языке Записываем в переменную min начальное значение, равное 200. В цикле от 1-го элемента до 20-го выполняем проверку каждого элемента массива с соответствующим индексом по следующему условию: Если элемент массива больше или равен 180 и меньше значения переменной min, то переменной min присваиваем значение этого элемента массива. После завершения цикла выводим значение переменной min.

Методические подходы к обучению способам решения задачи С4 ЕГЭ по информатике 29 1) выявить специфику задания типа С4 (что именно и при каких «стартовых» условиях должен сделать учащийся); 2) предложить краткое описание последовательности этапов решения задач типа С4; 3) определить требования к подготовке учащегося, необходимые для решения задач типа С4 4) рассмотреть и проанализировать критерии проверки задач типа С4; 5) рассмотреть подходы к выполнению учащимся каждого этапа решения задачи С4;

Направленость задачи С4 согласно Спецификации КИМа ЕГЭ по информатике: 30 Умение создавать собственные программы на языке программирования (30–50 строк) для решения задач средней сложности. При этом программа обязательно (на 4 балла) или желательно (на 3-2 балла) должна быть оптимальной по времени работы и используемой памяти.

Для получения максимального балла от учащегося требуется: уметь анализировать «накрученное» условие и представлять метод решения в виде формальной записи на языке программирования; 2. хорошо знать способы описания и обработки переменных целого, вещественно, строкового, логического типов данных (так, примеров описания строковых данных в КИМе нет) 3. обладать знаниями и умениями из уже рассмотренного в С2 перечня плюс следующими: A.Слияние двух упорядоченных массивов в один без использования сортировки. B.Обработка отдельных символов данной строки. Подсчет частоты появления символа в строке. C.Работа с подстроками данной строки с разбиением на слова по пробельным символам. Поиск подстроки внутри данной строки, замена найденной подстроки на другую строку. 4. Иметь достаточный опыт написания программ, чтобы «чувствовать» и исправлять возможные ошибки без использования компьютера.

Критерии проверки С4 или на что обратить внимание учащихся. Каким должно быть решение на 4 и 3 балла: 32 4 балла ставится за эффективную и правильно работающую программу, которая, возможно, содержит до трёх синтаксических ошибок. 3 балла ставится в случае, когда задача фактически решена, но программа содержит четыре-пять синтаксических ошибок, или если допущена одна содержательная ошибка, или если все входные данные сохраняются в массиве или иной структуре данных (программа неэффективна по памяти, но эффективна по времени работы).

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

Задача С4-1 (анализ решения из демоверсии КИМ 2014 года) 34 По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) R делится на 21. Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: Вычисленное контрольное значение: … Контроль пройден (или – Контроль не пройден) Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение.

35 Пример входных данных: Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: Контроль пройден По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине); 2) R делится на 21. Если такого числа R нет, то контрольное значение полагается равным 0. Напишите эффективную, в том числе по используемой памяти, программу, которая будет проверять правильность контрольного значения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее В последней строке записано контрольное значение.

Решение задачи С4 имеет следующие обязательные составляющие: 36 Описание используемых переменных Инициализация Организация ввода Организация обработки Организация вывода При оптимальном по времени решении задачи С4 организация ввода и обработки организуется параллельно, а не последовательно (как в С2). Тогда количество используемых переменных сводится к минимуму, а значит, программа будет еще оптимальна и по памяти.

37 Произведение двух чисел делится на 21, если: один из сомножителей делится на 21 (второй может быть любым) либо ни один из сомножителей не делится на 21, причём один из сомножителей делится на 7, а другой – на 3. Поэтому программа, вычисляющая кодовое число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин: М7 – самое большое число, кратное 7, но не кратное 3; M3 – самое большое число, кратное 3, но не кратное 7; M21 – самое большое число, кратное 21; МAX – самое большое число среди всех элементов последовательности, отличное от М21 (если число М21 встретилось более одного раза и оно же является максимальным, то MAX = M21). После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений М21*MAX и М7*М3. Словесное описание алгоритма решения задачи, предваряющее ее запись на языке программирования является обязательной частью решения задачи С4:

38 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. Количество чисел N известно, но может быть очень велико. все числа не превышают 1000 … R – произведение двух различных переданных элементов последовательности

39 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям: 1) R – произведение двух различных переданных элементов последовательности 2) R делится на 21

40 var M7,M3,M21,R,MAX,dat,res,i,N: longint; begin M7 := 0; M3 := 0; M21 := 0; MAX := 0; readln(N); for i := 1 to N do Begin … end; readln(R); if (M7*M3 < M21*MAX) then res := M21*MAX else res := M7*M3; writeln('Вычисленное контрольное значение: ',res); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. readln(dat); if ((dat mod 7) = 0) and ((dat mod 3) > 0) and (dat > M7) then M7 := dat; if ((dat mod 3) = 0) and ((dat mod 7) > 0) and (dat > M3) then M3 := dat; if (dat mod 21 = 0) and (dat > M21) then begin if M21 > MAX then MAX := M21; M21 := dat end else if dat > MAX then MAX := dat;

Решение задачи на 2 балла из 4 возможных 41 Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но в реализации алгоритма содержится до двух содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве (ниже n – количество прочитанных чисел), и перебираются все возможные пары элементов последовательности. Например, так: max := 0; for i := 1 to n - 1 do for j := i + 1 to n do if ((a[i]*a[j]) mod 21 = 0) and ((a[i]*a[j]) > max) then max := a[i]*a[j];

Алгоритм решения задачи: 42 Анализ условия, определение цели. Выявление связей между искомым и вводимыми данными. Запись описания алгоритма решения задачи на естественном языке. Оформление программы на языке программирования, включающее в себя: описание переменных и их типов, инициализацию нужных переменных, организацию ввода и обработки, организацию вывода. Анализ программы, выявление ошибок на 2-3 подобранных самостоятельно тестах (кроме данного в задаче), коррекция.

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

Пояснение к решению 44 Про­грам­ма чи­та­ет все вход­ные сим­во­лы до точки один раз, подсчи­ты­ вая в мас­си­ве, хра­ня­щем 26 целых чисел, ко­ли­че­ство каж­дой из букв. Сами вход­ные сим­во­лы при этом не за­по­ми­на­ют­ся. В до­пол­ни­тель­ный мас­сив, со­сто­я­щий из 26 сим­во­лов, за­но­сят­ся буквы от «а» до «z». Затем эле­мен­ты пер­во­го мас­си­ва сор­ти­ру­ют­ся по неубы­ва­нию любым ал­го­рит­мом сор­ти­ров­ки, па­рал­лель­но перестав­ля­ют­ся и эле­мен­ты вто­ ро­го мас­си­ва (воз­мож­но использование од­но­го мас­си­ва за­пи­сей, со­сто­ я­щих из двух полей). При этом эле­мен­ты с рав­ным чис­лом вхож­де­ний сим­во­лов местами не ме­ня­ют­ся. Во вто­ром из от­сор­ти­ро­ван­ных мас­си­ вов про­пус­ка­ют­ся эле­мен­ты, ко­ли­че­ство ко­то­рых равно 0, осталь­ные эле­мен­ты пе­ча­та­ют­ся под­ряд.

Немного об особенностях символьного типа 45 Переменная типа char может принимать значения из определенной упорядоченной последовательности символов. Переменная этого типа занимает 1 байт и принимает одно из 256 значений кода ASCII Обычно символы, имеющие экранное представление, записывают в явном виде, заключив в апострофы (например, 'A', 'b', '*'). Две стандартные функции позволяют поставить в соответствие данную последовательность символов множеству целых неотрицательных чисел (порядковым номерам символов последовательности). Эти функции называются функциями преобразования: ord(ch) – выдает номер символа (нумерация с нуля), chr(i) – выдает i-ый символ из таблицы символов. Пример. ord(H) выдает номер символа Н в последовательности всех символов, используемых транслятором. chr(15) выдает 15-ый символ этой последовательности.

46 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end;... i:=0; while a[i]=o do i:=i+1; for j:= i to 25 do write( b[j]); end. repeat read(c); … until c=.; …

47 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end;... i:=0; while a[i]=0 do i:=i+1; for j:=i to 25 do write( b[j]); end. repeat read(c); a[ord(c)-ord(a)]:=a[ ord(c)-ord(a)]+1; until c=.; …

48 var a: array[0..25] of integer; b: array[0..25] of a..z; c: char; i,j,k: integer; begin for i:=0 to25 do begin a[i]:=0; b[i]:=chr(ord(a)+i) end; repeat read(c); a[ord(c)-ord(a)]:=a[ ord(c)-ord(a)]+1; until c=.;... i:=0; while a[i]=0 do i:=i+1; for j:=i to 25 do write( b[j]); end. for i:=1 to 25 do begin for j := 0 to 24 do if a[j] > a[j +1] then begin k:=а[j]; с:=b[j]; а[j]:=а[j+1]; b[j]:=m[j+1]; a[j + 1] :=k; b[j+1] :=c end;

49 Спасибо за внимание!