Реферат: Тема : Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из 30-50 строк)

C4 (высокий уровень, время – 60 мин)
Тема: Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из 30-50 строк).

Что нужно знать:

символьная строка – это цепочка символов, которая может обрабатываться как единое целое

для обращения к символу с номером i строки s используется запись s[i], это говорит о том, что строка – особый вариант массива, в котором хранятся символы

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

s := '123' + '456'; { получили '123456' }

с помощью функции Ord можно получить код символа; цифры имеют коды от 48 (цифра 0) до 57 (цифра 9), например

k := Ord('1'); { получили 49 }

то же самое можно сделать с помощью преобразования типа (привести char к integer)

k := integer('1'); { получили 49 }

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

c := Chr(49); { получили символ '1' }

то же самое можно сделать с помощью преобразования типа (привести integer к char)

c := char(49); { получили символ '1' }

для работы со строками в наиболее распространенных Паскаль-средах (^ Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) используют стандартные функции (здесь s – это переменная типа string, символьная строка; n и r – целые переменные)

n := Length(s);

записать длину строки s в целую переменную n

s1 := Copy(s, 2, 5);

записать в символьную строку s1 подстроку строки s, которая начинается с символа с номером 2 и состоит из 5 символов (важно – не со 2-го по 5-ый символ!)

n := Pos('Вася', s);

записать в целую переменную n номер символа, с которого в строке s начинается подстрока 'Вася' (если ее нет, в переменную n записывается 0); так же можно искать отдельные символы

(важно: сначала указываем, что ищем, а потом – где)

n := StrToInt(s);

преобразовать строку s в целое число и записать результат в переменную n (PascalABC, Delphi)

и процедуры

Delete(s, 2, 5);

удалить из строки s 5 символов, начиная со второго

Insert('Вася', s, 3);

вставить в строку s фрагмент 'Вася', начиная с третьего символа (между 3-м и 4-м)

Val(s, n, r);

преобразовать строку s в целое число и записать результат в переменную n; если при этом произошла ошибка, в переменной r будет ноль, если все нормально – ненулевое значение

структура (в Паскале она называется «запись», record) – это сложный тип данных, который может включать в себя несколько элементов – полей; поля могут иметь различный тип

записи в Паскале объявляются с помощью ключевого слова record; в простейшем случае можно выделить память под одну запись так:


var x: record

name: string;

code: integer;

end;

эта запись состоит из двух полей: символьной строки name и целого числа code

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

для обращения к полям записи используют точку, например x.name означает «поле name записи x»

можно сразу объявить массив записей:

var Info: array[1..100] of record

name: string;

code: integer;

end;

это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом; в каждой структуре есть поля nаme и code; чтобы работать с полями записи с номером k используют обращения вида Info[k].name и Info[k].code

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

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

сложность имеет алгоритм с одним или несколькими простыми (не вложенными!) циклами в каждом из которых выполняется N шагов (как при поиске минимального элемента)

количество операций для алгоритма, имеющего сложность , вычисляется по формуле , где a и b – некоторые постоянные

если в одном алгоритме решения задачи используется несколько циклов от 1 до N, а во втором – только один цикл, то алгоритм с одним циклом, как правило, эффективнее (хотя оба алгоритма имеют сложность , постоянная в каждом случае своя, для алгоритма с несколькими циклами она будет больше)

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

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

иногда встречаются алгоритмы сложности (три вложенных цикла от 1 до N), при больших N они работают медленнее, чем любой алгоритм сложности , то есть, менее эффективны

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

<Фамилия> <Инициалы> <номер школы>

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

Иванов П.С. 57

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

^ Как правильно понимать условие?

на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную1

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

номер школы стоит после второго пробела в строке

«<номер школы> – не более чем двузначный номер» – крайне важная информация; собственно, только она и позволяет найти хорошее решение задачи; это значит, что школ не более 99!

что означает выражение «как можно более эффективная программа»?

прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь

в программе не выполняются никакие лишние действия

используемые алгоритмы имеют минимальную сложность (см. выше)

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

зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные

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

Решение:

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

так как номер школы состоит (по условию!) не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99)

поэтому можно ввести массив ^ C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкой-счетчиком, в которой накапливается число участников от школы с номером k; сначала во все элементы этого массива записываются нуль (обнуление счетчиков):

for k:=1 to 99 do C[k]:=0;

во многих системах программирования на Паскале все глобальные переменные автоматически обнуляются, и таким образом, этот цикл ничего не дает; однако на всякий случай нужно продемонстрировать эксперту, который будет проверять часть С вашей работы, что вы понимаете суть дела («счетчик необходимо сначала обнулить»)

основной цикл обработки вводимых строк можно записать на псевдокоде так:

for i:=1 to N do begin

{ читаем очередную строку }

{ определяем номер школы k }

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

поскольку данные вводятся в виде символьной строки, нужно выделить в памяти переменную s типа string

для чтения очередной строки будем использовать оператор readln

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

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

p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p);

первая команда определяет номер первого пробела и записывает его в целую переменную p, в вторая – записывает в строку s весь «хвост», стоящий за этим пробелом, начиная с символа с номером p+1; длина хвоста равна Length(s)-p, где Length(s) – длина строки;

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

заметим, что можно избежать дублирования двух строк, «свернув» их во внутренний цикл, но это вряд ли сильно упростит запись:

for k:=1 to 2 do begin

p := Pos(' ', s);

s := Copy(s, p+1, Length(s)-p);

end;

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

p := Pos(' ', s);

s := Copy(s,p+6,Length(s));

или так

p := Pos(' ', s);

Delete(s, 1, p+5);

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

Val(s, k, r);

эта процедура (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) преобразует символьную строку s в числовое значение k; с помощью переменной r обнаруживается ошибка: если раскодировать число не удалось (в строке не число), в r будет записан нуль (здесь мы не будем обрабатывать эту ошибку, полагая, что все данные правильные);

если вы работаете на ПаскалеABC (никто не может вам запретить написать, что этот так), вместо ^ Val можно использовать более удобную и понятную функцию StrToInt:

k := StrToInt(s);

таким образом, основной цикл выглядит так:

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{ выделяем часть после второго пробела }

p := Pos(' ', s);

Delete(s, 1, p+5);

{ определяем номер школы k }

Val(s, k, r);

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

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

Min := N;

for k:=1 to 99 do

if (C[k] <> 0) and (C[k]

здесь интересна первая строчка, Min:=N: по условию всего было N участников, поэтому минимальное значение не может быть больше N; обратите внимание, что привычный вариант (который начинается с Min:=C[1]) работает неверно, если из первой школы не было ни одного участника

и выводим на экран номера всех школ (обратите внимание – номера!), для которых C[k]=Min:

for k:=1 to 99 do

if C[k] = Min then writeln(k);

остается «собрать» программу, чтобы получилось полное решение; максимальное количество школ мы задали в виде константы LIM:

const LIM = 99;

var C:array[1..LIM] of integer;

i, p, N, k, r, Min: integer;

s:string;

begin

readln(N);

for i:=1 to N do begin

readln(s); { читаем очередную строку }

{ выделяем часть после второго пробела }

p := Pos(' ', s);

Delete(s, 1, p+5);

{ определяем номер школы k }

Val(s, k, r);

C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы }

end;

Min := N;

for k:=1 to LIM do

if (C[k] <> 0) and (C[k]

for k:=1 to LIM do

if C[k] = Min then writeln(k);

end.



^ На что обратить внимание:

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

определите, какая именно информация из условия нужна для решения задачи, а какая – не нужна

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

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

проверяйте «крайние» варианты (например, возможность выхода за границы массива)

проверьте, правильно ли заданы (и заданы ли вообще) начальные значения для всех переменных

будьте внимательны, когда в массиве есть «мертвые» элементы, которые не нужно учитывать; проверяйте, что в этом случае ваши алгоритмы (например, поиск минимального элемента) работают правильно

проверьте, правильно ли расставлены операторные скобки begin-end, ограничивающие тело цикла; их обязательно нужно ставить, если в теле цикла несколько операторов

при использовании функции Pos не забывайте, что первый параметр – что ищем (образец), а второй – где ищем

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

если это возможно, желательно работать только с целыми числами; этим вы избежите проблем, связанных с округлением и неточностью хранения дробных вещественных чисел в памяти компьютера
^ Еще пример задания:
На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Имя> <оценки>,

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:

Иванов Петр 4 5 3

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

^ Как правильно понимать условие?

как и в предыдущей задаче, данные «подаются на вход программе», то есть, их можно читать с помощью операторов read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную

«количество учеников не меньше 10, но не превосходит 100», здесь только вторая часть – полезная информация, она намекает на то, что придется все введенные данные одновременно держать в памяти, выделив массив (или массивы) размером 100 элементов

сказано, что фамилия имеет длину не более 20 символов, а имя – не более 15; здесь, по сути, важно лишь то, что фамилия и имя (вместе) занимают меньше 255 символов, то есть, «влезут» в стандартное ограничение (255 символов) для типа string в классических версиях Паскаля

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

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

следующий шаг к правильному решению: поскольку число оценок у всех учеников одинаковое, средний балл для каждого это сумма его оценок, деленная на 3; поэтому вместо среднего балла мы можем сравнивать суммы баллов – целые числа!

требуется вывести фамилии и имена (баллы не нужны!) трех худших учеников, причем их может быть и больше, если несколько «худших» набрали одинаковую сумму баллов

если бы требовался один худший – все решается поиском по массиву; первая идея – найти самого худшего (1 проход), затем – 2-ого с конца (еще 1 проход), и, наконец, 3-его (всего три прохода по массиву)

это не лучший вариант (на экзамене будут сняты баллы) по двум причинам:

в таком методе решения три прохода по массиву, а в самом деле достаточно одного (см. далее), значит, программа неэффективна

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

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

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

Решение (общий подход):

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

{ читаем все данные и запоминаем их }

{ находим три худших результата }

{ выводим фамилии и имена тех, чей результат меньше или

равен «третьему худшему» }

до того, как начать писать «нормальный» код, нужно определить, как хранить данные; в данном случае нужно запомнить несколько данных по каждому ученику, их удобнее объединить в запись с двумя полями (фамилия-имя и сумма баллов); таких записей нужно выделить в памяти не менее 100 (по условию), то есть, массив из 100 элементов:

const LIM=100;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

Чтение данных:

после того, как мы прочитали фактическое число учеников N, в цикле считываем и расшифровываем информацию о них, сохраняя все данные в структурах

for i:=1 to N do begin

{ считываем строку данных }

^ Info[i].name := { фамилия и имя };

Info[i].sum := { сумма баллов };

end;

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

сначала в поле name очередной структуры записываем пустую строку ''(в которой нет ни одного символа, длина равна нулю)

^ Info[i].name := ''; { пустая строка }

затем считываем символы фамилии и сразу приписываем их в конец поля name:

repeat

read ( c );

Info[i].name := Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

затем также читаем из входного потока имя, до пробела, и записываем его в конец того же поля name:

repeat

read ( c );

Info[i].name := Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

заметьте, что эти два цикла одинаковы, поэтому ввод имени и фамилии можно записать в виде вложенного цикла так:

^ Info[i].name := ''; { пустая строка }

for k:=1 to 2 do

repeat

read ( c );

Info[i].name := Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

важно! обратите внимание, что для организации внутреннего цикла используется другая переменная, k (а не i, потому что i – переменная главного цикла, она обозначает номер текущего ученика)

теперь во входном потоке остались три числа, которые мы можем последовательно считывать в целую переменную mark, а затем – добавлять к полю Info[i].sum:

Info[i].sum := 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum := Info[i].sum + mark;

end;

readln;

последняя команда readln пропускает все оставшиеся символы до новой строки (из этой мы прочитали все, что нужно)

вот полный цикл ввода данных, после его окончания все исходные данные будут записаны в первые ^ N записей массива Info:

for i:=1 to N do begin

{ ввод имени и фамилии }

Info[i].name := '';

for k:=1 to 2 do

repeat

read(c);

Info[i].name := Info[i].name + c;

until c = ' ';

{ ввод и суммирование оценок }

Info[i].sum := 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum := Info[i].sum + mark;

end;

readln;

end;

Поиск трех худших данных:

теперь нужно придумать, как за один проход по массиву найти три худших результата;

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

на бумажке вести записи в три столбика, в первом записывать минимальное число, в втором – следующее по величине, в третьем – «третье минимальное»

сначала пишем первое число в первый столбик, оно – минимальное, потому что других мы не еще видели; пусть это число 14:

минимум

второе

третье

14







пусть следующее число – 12; оно меньше минимального, поэтому его нужно записывать в первый столбец, а «старое» минимальное число «переедет» во второй столбец

минимум

второе

третье

14







12

14




пусть дальше идет число 10 – теперь оно станет минимальным, его нужно записывать в первый столбец; при этом 12 «переедет» из первого столбца во второй, а 14 – из второго в третий

минимум

второе

третье

14







12

14




10

12

14

пусть следующее число – 11; оно больше минимального, но меньше «второго», поэтому его нужно поставить во второй столбец; число 12 из второго столбца перемещается в третий, а число 14 из третьего столбца удаляется из кандидатов в «три минимальных»

минимум

второе

третье

14







12

14




10

12

14




11

12

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

остается только переложить этот алгоритм на язык программирования

выделим в памяти три целых переменных: min1 (минимальный), min2 («второй минимальный»), min3 («третий минимальный»), в виде начальных значений запишем в каждую из них число, заведомо превышающее максимальную возможную сумму трех оценок, например, 20 (>5+5+5)

полный цикл поиска выглядит так:

min1 := 20; min2 := 20; min3 := 20;

for i:=1 to N do begin

if Info[i].sum < min1 then begin { новый min1 }

min3 := min2; min2 := min1;

min1 := Info[i].sum;

end

else if Info[i].sum < min2 then begin { новый min2 }

min3 := min2;

min2 := Info[i].sum;

end

else if Info[i].sum < min3 then { новый min3 }

min3 := Info[i].sum;

end;

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

min3 := min2;

min2 := min1;

эти операторы нельзя менять местами, иначе «старое» значение min2 будет потеряно;

во-вторых, если проверять условие Info[i].sum < min2 нужно только тогда, когда очередная сумма не меньше, чем min1, поэтому каждый следующий условный оператор стоит в else-блоке предыдущего, то есть, выполняется только тогда, когда предыдущий не сработал

итак, мы нашли три минимальных результата, и остается вывести на экран фамилии и имена тех, у кого сумма баллов меньше или равна min3:

for i:=1 to N do

if Info[i].sum <= min3 then

writeln(Info[i].name);

на всякий случай приведем полную программу, она получилась довольно длинная

const LIM = 100;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

i, k, N, mark, min1, min2, min3: integer;

c: char;

begin

readln(N);

{ ввод исходных данных }

for i:=1 to N do begin

Info[i].name := '';

for k:=1 to 2 do

repeat

read(c);

Info[i].name := Info[i].name + c;

until c = ' ';

Info[i].sum := 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum := Info[i].sum + mark;

end;

readln;

end;

{ поиск трех минимальных }

min1 := 20; min2 := 20; min3 := 20;

for i:=1 to N do begin

if Info[i].sum

min3 := min2; min2 := min1;

min1 := Info[i].sum;

end

else if Info[i].sum

min3 := min2;

min2 := Info[i].sum;

end

else if Info[i].sum

min3 := Info[i].sum;

end;

{ вывод результата }

for i:=1 to N do

if Info[i].sum <= min3 then

writeln(Info[i].name);

end.

эту задачу можно решить и без записей, используя два массива: массив символьных строк name и массив целых чисел sum, они объявляются так:

var name: array[1..MAX] of string;

sum: array[1..MAX] of integer;

после этого в приведенной программе нужно заменить везде Info[i].name на name и Info[i].sum на sum.

На что обратить внимание:

в исходных данных выделите то, что не нужно для решения задачи; при чтении эти части можно просто пропускать;

если нам не нужны фамилия и имя отдельно, можно хранить их вместе, в виде одной строки

если нас интересует только сумма оценок, не нужно хранить их в памяти по отдельности

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

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




За что снимают баллы:

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

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

неэффективность алгоритма:

используется алгоритм, имеющий сложность , когда есть алгоритм сложности

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

лишний расход памяти ( используются дополнительные массивы или размер массива определен неверно)

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

переменная не описана или описана неверно

переменным не присвоены нужные начальные значения (например, не обнуляются счетчики) или присвоены неверные значения

нет вывода результата в конце программы

перепутаны знаки < и >, логические операции or и and

применяется недопустимая операция, например, div или mod для вещественных чисел

неверно расставлены операторные скобки begin-end

в цикле for используется вещественная переменная (Паскаль)

в цикле while или repeat не изменяется переменная цикла, из-за чего происходит зацикливание

синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов); чтобы получить 4 балла, при абсолютно верном решении нужно сделать не более одной синтаксической ошибки; на 3 балла – до трех ошибок, на 2 балла – до пяти и на 1 балл – до семи ошибок



1 Или используется перенаправление входного потока из командной строки, но это уже абсолютно неважно…