Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №16/2008


Спецвыпуски

Алгоритмизация и программирование в школьном курсе информатики

Комментарии и решения задач урока 3
Комментарии и решения задач урока 4
Комментарии и решения задач урока 5
Комментарии и решения задач урока 6
Комментарии и решения задач урока 7
Комментарии и решения задач урока 8
Комментарии и решения задач урока 9
Комментарии и решения задач урока 10
Комментарии и решения задач урока 11
Комментарии и решения задач урока 12
Комментарии и решения задач урока 13
Комментарии и решения задач урока 14
Электронный задачник

Комментарии и решения задач урока 3

1. Напишите программу, которая по введенному не более чем четырехзначному числу k будет выдавать сумму его цифр.

Комментарий. Задача чуть сложнее приведенной в материалах урока. Она закрепляет навыки выделения цифр целого числа путем целочисленного деления с остатком.

2. Идет k-я секунда суток. Определите, сколько целых часов h и целых минут m прошло с начала суток. На вход программе подается целое число k (0 k 86399). Выведите на экран фразу: “It is ... hours ... minutes”. Вместо многоточия программа должна выводить значения h и m, отделяя их от слов ровно одним пробелом.

Решение. Эта задача практически совпадает с предыдущей, только “цифры” выделяются уже у числа в 60-ричной системе счисления. Кроме того, данное задание закрепляет умение пользоваться оператором печати с параметрами разного типа (в данном случае строковыми константами и переменными). Приведем основной фрагмент решения:

h := k div 3600;

m := k div 60 mod 60

writeln('It is ',h,' hours ', m,' minutes.')

3. Часовая стрелка повернулась с начала суток на d градусов. Определите, сколько сейчас целых часов h и целых минут m.

Решение. Один час соответствует 30о, один градус — двум минутам:

h := k div 30;

m := k mod 30 * 2;

4. Определите, является ли не более чем четырехзначное число k симметричным (например, 1331 или 0550). На вход программе подается целое число k
(0 k 9999). Выдайте 1 при положительном ответе на вопрос задачи и любое другое целое число — в противном случае.

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

В данной задаче решение остается все еще несложным. Так, если мы выделили цифры a1, a2, a3 и a4 четырехзначного числа, то выражение |a1a4| + |a2a3| + 1 приводит к требуемому ответу. Типичная ошибка в подобном решении — отсутствие модуля у разностей цифр. Поэтому в наборе тестов необходимы, например, тесты 5463, 5643 и 3465. Тогда любой способ составления разностей цифр без операции модуля приведет к неверному результату на одном из тестов.

В задаче возможен и другой способ решения — из цифр четырехзначного числа составить два двузначных числа: a1a2 (его можно получить сразу с помощью операции a div 100) и a4a3. Так как только для симметричного четырехзначного числа полученные двузначные равны между собой, искомое выражение будет иметь вид a1a2a4a3 + 1.

5. Пусть в школе пять дней в неделю ежедневно проходят шесть уроков. Тогда в неделе всего 30 уроков. По введенному номеру дня d и номеру урока l найдите порядковый номер этого урока в неделе.

Решение. Эта задача достаточно важная. Аналогичные рассуждения приходится производить при вычислении порядкового номера элемента в двумерной таблице. Порядковый номер дня можно вычислить так: lw := (d – 1)*5 + l. При составлении тестов обязательно нужно проверить ответ для первого урока, проходящего в понедельник (ответ на этот тест 1, а у школьников часто получается 0). Аналогично важными для проверки являются последний урок понедельника, первый урок произвольного дня недели и последний урок в пятницу.

6. В книге на одной странице помещается k строк. Таким образом, на 1-й странице печатаются строки с 1-й по k-ю, на второй — с (k + 1)-й по (2•k)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Решение. Данная задача, по-существу, обратна предыдущей и также важна для различных операций пересчета, связанных с таблицами, нумерация строк и столбцов в которых ведется с единицы (нумеровать с нуля проще!). Формулы, предлагаемые школьниками для ее решения, обычно оказываются неверными для одного из возможных случаев (обычно для первой или последней строки или для первой страницы), поэтому система тестов в данном случае должна быть особенно продуманной. Она обязательно должна включать самые крайние случаи (для первой страницы — первую и последнюю строчки, а для последней — последнюю), первую и последнюю строчки произвольной страницы и среднюю строчку произвольной страницы. Приведем правильное решение:

p := (n – 1) div k + 1;

{это номер страницы}

l := (n – 1) mod k + 1;

{это номер строки}

Данные формулы фактически следуют из решения задачи 5. Существует и конструктивный способ их получения. Покажем его для второй из формул. Пусть k = 3. Впишем в таблицу остатки от деления на 3 первых семи чисел:

Остатки от деления на 3 лежат в диапазоне 0..2, а искомый результат — 1..3. Значит, прибавление 1 к остатку переведет числа в требуемый диапазон. Но тогда каждые 3 последовательных результата оказываются циклически сдвинутыми на единицу относительно правильного ответа. Поэтому остаток от деления на 3 надо брать не от числа n, а от числа n – 1, что и приводит нас к желаемому результату. Составление подобных таблиц полезно и при решении других задач.

7. Обозначим дни недели числами от 1 — понедельник до 7 — воскресенье соответственно. По известному m — дню недели первого числа текущего месяца — определите день недели числа n.

Решение. Приведем основной оператор присваивания, определяющий решение этой задачи:

d := (n + m - 2) mod 7 + 1;

Способ его получения схож с решением предыдущей задачи.

8. Единица товара стоит a рублей b копеек. Было куплено n штук этого товара. Сколько рублей и копеек пришлось заплатить за всю покупку? На вход программе подаются три целых числа: 0 a 30 000, 0 b < 100 и 0 n 30 000. Выведите два искомых числа.

Решение. Эта задача неожиданно вызывает затруднения, если ее неаккуратно решать для приведенных в условии ограничений на входные данные. Дело в том, что наиболее естественный способ ее решения — перевести исходную сумму в копейки, умножить ее на n и выделить число рублей и копеек, в данном случае не подходит. При максимальных ограничениях мы получаем, что число 30 000 x 100 x 30 000 = 90 000 000 000 не умещается в стандартном типе данных integer языка Delphi (или типе longint в Borland Pascal). Проверка по тестам будет показывать ученикам, что ответ не верный (или будет происходить ошибка выполнения программы при включенной директиве компилятора {$Q+}). Сами тесты при этом школьникам показывать нужно не сразу.

Правильное решение работает непосредственно с рублями и копейками:

b1 := b * n mod 100;

a1 := a * n + b * n div 100;

Здесь мы впервые столкнулись с отличительной особенностью решения задач по программированию: помимо математических формул, необходимо осуществлять правильный выбор типов данных (в Borland Pascal тип integer не подходит для описания переменных a и n даже в правильном решении, так как вне зависимости от типа результата промежуточные вычисления будут производиться в минимальном из используемых типов, в данном случае — integer). Обратите внимание школьников, что тип данных определяется не только диапазоном значений, которые могут принимать входные переменные, но и величиной промежуточных результатов вычислений.

9. Цена товара обозначена в рублях с точностью до копеек, то есть вещественным числом с двумя цифрами после десятичной точки, например, 10.35. В целочисленных переменных получите и выдайте значения целого числа рублей и целого числа копеек в цене товара.

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

k := trunc(frac(r) * 100);

Дело в том, что вещественные числа в компьютере могут представляться точно, с избытком или с недостатком 1 (грубо говоря, вместо 0.35 в компьютере может храниться число 0.349999999…). Поэтому умножение на 100 и отбрасывание дробной части может привести к неверному результату: 34 вместо 35. В данной задаче для решения этой проблемы можно использовать функцию round, но в общем случае это не так. Для получения целого числа рублей функцию trunc использовать можно.

10. Даны значения двух моментов времени: часы, потом минуты и секунды. Известно, что второй момент времени наступил не раньше первого и оба момента времени относятся к одним суткам 2. Определите, сколько секунд прошло между двумя моментами времени.

Указание. Данную задачу проще всего решать, сразу переведя оба момента времени в секунды. В Borland Pascal при этом надо использовать тип данных longint не только для результата, но и для описания входных значений часов, минут и секунд (см. решение задачи 8).

Приведем также решение некоторых задач повышенной сложности (здесь и далее будем обозначать их символом “*”).

1*. На вход программе подаются два целых числа: m и n, по модулю не превосходящих 106. Если m делится на n или n делится на m, то требуется вывести 1, в противном случае — любое другое число.

Решение. Если значение только одного из введенных чисел равно 0, то результатом должна быть 1 (0 делится на любое другое число), а если оба числа равны 0, то ответ должен быть иным (0 на 0 не делится). Для того чтобы избавиться при делении от 0, добавим к делителю n следующее выражение: 1 div (1 + |n|). Это выражение равно 1 при n = 0 и 0 — в любом другом случае. В результате одно из возможных решений задачи выглядит так:

var

n, m, n1, m1: longint;

begin

read(m, n);

m1 := m + 1 div (abs(m) + 1);

n1 := n + 1 div (abs(n) + 1);

write(1 + (n mod m1)*(m mod n1) + 1 div (abs(m) + abs(n) + 1))

end.

Последнее слагаемое результата отлично от нуля, только когда и n, и m одновременно равны 0.

2*. На вход программе подаются два целых числа: m, n. Если m n, то требуется вывести 1, в противном случае — любое другое число.

Решение. Для произвольных целых чисел с использованием модуля решение имеет вид:

1 + (m - n) - abs(m - n).

Задача становится интереснее, если входными данными будут только натуральные числа, а использование модуля будет запрещено. Тогда ответ может выглядеть так:
1 + (m - n)*(n div m).

3*. Определите, верно ли, что в не более чем четырехзначном числе ровно две одинаковые цифры.

Решение. Приведем основной фрагмент решения данной задачи:

a1 := a mod 10;

a2 := a div 10 mod 10;

a3 := a div 100 mod 10;

a4 := a div 1000;

k := 1 div (abs(a1-a2)+1)+ 1 div (abs(a1-a3)+1)+ 1 div (abs(a1-a4)+1)+ 1 div (abs(a2-a3)+1)+ 1 div (abs(a2-a4)+1)+ 1 div (abs(a3-a4)+1);

writeln(k);

5*. На вход программе подаются два целых числа:
0 m < 60, 0 < n 12, указывающие момент времени “n часов m минут”. Определите наименьшее число полных минут, которое должно пройти до того момента, когда часовая и минутная стрелки на циферблате совпадут, не обязательно на каком-то делении. Вещественную арифметику не использовать.

Решение. В первую очередь обратите внимание на порядок ввода переменных — он отличен от традиционного. Но если не следовать описанному в условии порядку, то автоматическая проверка задачи будет невозможна.

За каждую минуту часовая стрелка проходит 0,5°, а минутная 6°. В момент их совпадения (n0 часов m0 минут) будет выполняться следующее равенство:
30n0 + 0,5m0 = 6m0 или 60n0 = 11m0. Поэтому, если в рамках текущего часа минутная стрелка еще не обогнала часовую (60n0 11m0), то ответом на вопрос задачи будет выражение 60n div 11 – m, в противном же случае стрелки встретятся уже во время следующего часа, и ответ выглядит так: 60(n + 1) div 11 + 60 – m. В окончательном решении производится совмещение этих формул:

S := 60*(n + 1 div(1 + (60*n + 1) div(11*m + 1))*12) div 11 - m;

7*. На вход программе подаются два числа (не обязательно целые, но не более чем с двумя знаками после десятичной точки). Распечатайте их в порядке возрастания.

Решение. С использованием модуля задача решается аналогично задаче 2*. Например, минимальное из двух чисел выражается так:

((m + n) - abs(m – n)) div 2.

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

a := m div n;

b := 1 div (a + 1);

{b = 1 при m < n и b = 0 при m >= n}

min := n*(1 – b) + m*b;

max := m*(1 – b) + n*b;

8*. На вход программе подается вещественное число x. Получите и выведите целое значение функции sign(x) — знак числа x.

Решение. Для всех чисел, отличных от 0, ответ выглядит как x/|x|. Для учета нуля воспользуемся практически тем же выражением, что и для целых чисел: [1/(1 + |x|)]. Оно равно единице при x = 0 и нулю для всех остальных значений x. Следует также помнить, что результат должен быть присвоен переменной целого типа. В результате получаем:

sign := trunc(x/(abs(x) + trunc(1/(abs(x) + 1))));

Комментарии и решения задач урока 4

1. На выданном вам рисунке на координатной плоскости изображены окружности, прямые, параболы, ромбы, прямоугольники (некоторые из упомянутых линий могут отсутствовать). Несколько областей, ограниченных этими линиями, заштрихованы. Данные линии можно описать уравнениями в декартовой прямоугольной системе координат (x, y) на плоскости:

у = (fx), или x = f(y), или f(x, y) = 0.

На рисунке изображены также оси координат и координатная сетка, линии которой проведены через единицу масштаба. Восстановите по рисунку уравнения всех линий, изображенных на нем.

Напишите программу, которая позволит определять, принадлежит ли точка с вещественными координатами (x0, y0) фигуре, состоящей из всех заштрихованных на рисунке областей, или нет. Точки на границах областей не рассматривать, то есть ваша программа может считать их как принадлежащими фигуре, так и не принадлежащими ей. Значения x0, y0 вводятся с клавиатуры. В качестве ответа программа выдает на экран true, если точка с введенными координатами (x0, y0) принадлежит заштрихованной фигуре, и false, если точка (x0, y0) не принадлежит ей. Условный оператор не использовать.

Пример рисунка:

Комментарий. Логические выражения в том виде, в каком они используются в программировании, школьникам немного непривычны. Поэтому, на наш взгляд, важно научить их применять не только в условных операторах и операторах цикла, но и “в чистом виде”, например, в операторах присваивания. Данное задание как раз и предназначено для этой цели. Кроме того, подобные задания включены в варианты ЕГЭ по информатике (задача С1).

Границы заштрихованных фигур в данном задании не анализируются сознательно. Это позволяет использовать логическую операцию not при описании части плоскости, находящейся по другую сторону от границы фигуры. Так, точки, лежащие внутри единичного круга с центром в начале координат, описываются неравенством x2 + y2 1. Если логической переменной с присвоить соответствующее логическое выражение c := x*x + y*y < 1, то not c будет соответствовать точкам, лежащим строго вне круга. Однако, если границу круга учитывать, такое использование переменной с для описания внешней области круга становится неправомерным. Подробнее о том, какие требования предъявляются к выполнению задания и как проверить его автоматически с применением компьютерной графики, можно прочитать в “Информатике” № 36/2001. Там же опубликованы различные варианты задания. Сложность задания (в данном случае — рисунка) варьируется согласно уровню математической подготовки учащихся.

Еще один важный момент, который отрабатывается на этом задании, — порядок выполнения операций. Заметим, что в различных языках программирования этот порядок различный. Например, в языке С операции сравнения имеют больший приоритет, чем логические связки и скобки в логических выражениях, аналогичных выражениям из упражнения 1 урока 4, не нужны. В языке Pascal без скобок в подобных выражениях не обойтись. В противном случае можно получить не только выражение с синтаксической ошибкой, но и синтаксически верное выражение, имеющее другой смысл. Так, в выражении с целочисленными переменными a и b

not a < b

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

Решение

var x, y: real;

incircle, upline1, upline2,

answer: boolean;

begin

readln (x, y);

incircle := (((x+0.5)*(x+0.5)+(y-1)*(y-1)) <= 2*2);

upline1 := (y >= 5*x/3+2);

upline2 := (y >= -3*x/2);

answer := incircle and upline2 and

not upline1 or upline1 and not upline2 and not incircle;

writeln(answer)

end.

3. Напишите программу, которая будет считывать значения целых переменных a, b и с и распечатывать их в порядке возрастания.
Значения a, b и с по модулю не превосходят 30 000.

Решите задачу двумя способами:

1) не используя операторы присваивания и логическую операцию and;

2) используя операторы присваивания.

Решение. Приведем фрагменты решения для каждого из требуемых вариантов решения:

1) if a < b then

if b < c then writeln(a,b,c)

else {a < b, c < b}

if a < c then writeln(a,c,b)

else writeln(c,a,b)

else {b < a}

if a < c then writeln(b,a,c)

else {b < a, c < a}

if b < c then writeln(b,c,a)

else writeln(c,b,a)

2) if a > b then

begin

d := a; a := b; b := d

end;

if b > c then

begin

d := c; c := b; b := d

end;

if a > b then

begin

d := a; a := b; b := d

end;

При реализации первого способа решения отрабатывается умение использовать вложенные условные операторы. Необходимо проконтролировать, что в программе нет сложных логических выражений, таких, как (a < b) and (b < c), а общее количество сравнений равно 5.

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

4. Напишите программу для решения уравнения ax = b относительно х в целых числах. Учтите, что a может принимать любые значения, в том числе и 0.

На вход программе подаются целые числа a, b, по модулю не превосходящие 30000. Требуется вывести целый корень уравнения, если он существует и единственный. Если уравнение не имеет корней, то вывести no solution. Если уравнение имеет больше одного целого корня, то вывести many solutions 3.

Примеры входных данныхПримеры выходных данных
1 22
2 3no solution

Решение. Несмотря на кажущуюся простоту, данное задание редко выполняется школьниками полностью правильно. Предложите им сначала решить задачу математически, а затем уже написать соответствующую программу. Учтите, что ученики 7–9-х классов практически не знакомы с методами решения задач с параметрами. Общая схема решения такая: сначала задача решается для общего случая, затем анализируется, в каком случае такое решение некорректно (при
a = 0). Затем уравнение переписывается уже с нулевым значением a: b = 0. Проанализировать последний случай также не у всех получается корректно. Обратите внимание, что в задаче требуется найти только целочисленное решение.

Приведем основной фрагмент решения данной задачи:

if a <> 0 then

if b mod a = 0

then writeln(b div a)

else writeln('no solution')

elseb = 0

then writeln('many solutions')

else writeln('no solution');

6. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8. По введенным координатам двух полей (k, l) и (m, n) выясните, угрожает ли ферзь, находящийся на поле (k, l), полю (m, n)?

Решение. В данной задаче наиболее сложная часть — построить компактное логическое выражение, описывающее нахождение двух фигур на одной диагонали. Приведем основной фрагмент решения задачи:

if (abs(k - m) = abs(l - n)) or

(k = m) or (l = n) then writeln('YES')

else writeln('NO');

7. Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит 8. По введенным координатам двух полей (k, l) и (m, n) выясните, являются ли эти поля полями одного цвета?

Решение. Решение основано на том, что сумма координат клеток одного цвета обладает одной и той же четностью (для одних клеток эта сумма четна, а для клеток другого цвета — нечетна):

if (k + 1) mod 2 = (m + n) mod 2

then writeln('YES')

else writeln('NO');

8. По введенному номеру года — положительному целому числу, не превосходящему 10 000, требуется определить, является ли данный год високосным. Напомним, что високосными являются года, номера которых кратны 4, но не кратны 100, а также года, номера которых кратны 400. Выведите YES или NO в зависимости от ответа на вопрос задачи.

Решение. Задачи, связанные с календарем, встречаются достаточно часто, однако вызывают затруднения у школьников (несомненно, это связано с достаточно сложным устройством календаря). На примере данного задания предлагается научить школьников отделять високосный год от не високосного. Основной фрагмент решения:

readln(a);

if (a mod 400 = 0) or ((a mod 4 = 0) and (a mod 100 <> 0))

then writeln('YES')

else writeln('NO');

9. Узник замка Иф.

За многие годы заточения узник замка Иф проделал вилкой в стене прямоугольное отверстие размером D x E. Замок Иф сложен из кирпичей размером
A x B x C. Узник хочет узнать, сможет ли он выкидывать кирпичи в море из этого отверстия, для того чтобы сделать подкоп. Помогите ему, считая, что стороны кирпича будут параллельны сторонам отверстия.

Указание. В данной задаче нужно понять, что достаточно найти две минимальных стороны кирпича, упорядочить D и E по возрастанию и проверить, что меньшая сторона не больше D, и вторая по величине сторона не больше E.

10. Даны три натуральных числа — длины стороны треугольника. Определите, существует ли треугольник с такими сторонами, и если “да”, то определите его тип (остроугольный, тупоугольный, прямоугольный).

Решение. Найдем сначала максимальную из трех сторон и обозначим ее a. После этого в решении фактически анализируется знак косинуса угла, лежащего напротив стороны a:

if a >= b + c then writeln('impossible')

else

begin

if a*a = b*b + c*c then

writeln('rectangular') else

if a*a < b*b + c*c then

writeln('acute') else

writeln('obtuse');

11. Решить в действительных числах уравнение ax2 + bx + c = 0.

На вход программе подаются a, b, c (a, b, c целые, по модулю не превосходят 100). Выдать код ситуации и значения корней:

–1 — бесконечное множество решений;

0 — нет действительных корней;

1 — уравнение вырождается в линейное, выдать x;

2 — уравнение квадратное, два различных корня, выдать x1 и x2;

3 — уравнение квадратное, кратный корень, выдать x.

Решение. Несмотря на стандартную для школьников постановку задачи, ее решение обычно вызывает сложности, как с точки зрения выделения различных случаев, так и при записи программы. Рассуждать проще всего так. Если a 0, то для нахождения корней используются известные формулы, при этом существование корней зависит от знака дискриминанта квадратного уравнения (проверка равенства дискриминанта нулю корректна только для целых коэффициентов уравнения). Если же a = 0, то уравнение становится линейным. Однако при b = 0 оно вырождается в равенство c = 0. Поэтому, если c действительно равно 0, то все действительные числа являются корнями данного уравнения, в противном случае — корней нет.

Приведем реализацию решения, соответствующую изложенной логике:

readln(a,b,c);

if a = 0 then

if b = 0 then

if c = 0 then writeln(–1)

else writeln(0)

else writeln('1 ', —c/b)

else {a <> 0}

begin

D := b*b – 4*a*c;

if D < 0 then writeln(0)

else {D >= 0}

if D > 0 then

begin

x1 := (-b + sqrt(D))/(2*a);

x2 := (-b - sqrt(D))/(2*a);

writeln('2 ',x1:0:2,' ',x2:0:2)

end

else writeln('3 ',-b/(2*a):0:2)

end;

Из возможных ошибок, которые допускают школьники, необходимо обратить внимание на следующую: при вычислении значений корней квадратного уравнения отсутствуют скобки у выражения (2*a). Найти такую ошибку сложно, так как при самотестировании школьники в основном рассматривают уравнения, в которых a = 1, и наличие указанной ошибки не влияет на результат. Поэтому при составлении набора тестов учителем очень важно предусмотреть случаи, в которых a 0 и a 1.

1*. На столе лежат коробка размера A1 x B1 x C1 и коробка размера A2 x B2 x C2. Выясните, можно ли одну из этих коробок положить в другую, если разрешены повороты коробок вокруг любого ребра на угол 90°.

Указание. Задача лишь немного сложнее уже рассмотренной задачи 9.
Достаточно упорядочить размеры каждой из коробок так, чтобы A B C, а затем проверить, что A1 A2, B1 B2 и С1 С2 или A2 A1, B2 B1 и С2 С1.

2*. Яша плавал в бассейне размером N ? M метров и устал. В этот момент он обнаружил, что находится на расстоянии x метров от одного из длинных бортиков (не обязательно от ближайшего) и y метров от одного из коротких бортиков. Какое минимальное расстояние должен проплыть Яша, чтобы выбраться из бассейна на бортик?

Комментарий. Данная задача предлагалась в 2006 году на Московской командной олимпиаде по программированию для восьмиклассников. Ее решение заключается в том, чтобы внимательно прочитать условие, правильно его понять и аккуратно запрограммировать.

3*. Узник замка Иф-2.

За многие годы заточения узник замка Иф проделал вилкой в стене прямоугольное отверстие размером D x E. Замок Иф сложен из кирпичей размером A x B x C. Узник хочет узнать, сможет ли он выкидывать кирпичи в море из этого отверстия, для того чтобы сделать подкоп. Помогите ему, считая, что стороны кирпича могут произвольно располагаться относительно сторон отверстия.

Указание. Несмотря на сходство с уже рассмотренной задачей 9, решение данной задачи существенно сложнее. Теперь мы можем произвольно поворачивать кирпич относительно сторон отверстия. Тем не менее можно доказать, что одна из граней кирпича должна быть параллельна плоскости отверстия. После этого надо совместить центр кирпича и центр наименьшей грани (а именно, той грани, стороны которой минимальны) и провести окружность, радиус которой равен половине длины диагонали стороны кирпича (см. рисунок).

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

4*. По координатам трех точек на плоскости требуется определить их взаимное расположение.

На ввод программе подаются 6 чисел: x1, y1, x2, y2, x3, y3. Все числа целые, по модулю не превосходят 100. Они задают 3 точки плоскости: a(x1, y1), b(x2, y2),
c(x3, y3). Следует определить взаимное расположение точек и выдать на экран код ситуации:

0 — 3 точки совпадают;

1 — ровно 2 точки из трех совпадают;

2 — точки не совпадают, лежат на одной прямой;

3 — точки образуют остроугольный треугольник;

4 — точки образуют прямоугольный треугольник;

5 — точки образуют тупоугольный треугольник.

Постарайтесь использовать как можно меньше логических операций (операций сравнения и логических связок).

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

begin

readln(AX,AY,BX,BY,CX,CY);

a2 := sqr(BX - CX) + sqr(BY - CY);

b2 := sqr(AX - CX) + sqr(AY - CY);

c2 := sqr(BX - AX) + sqr(BY - AY);

d2 := a2; {ищем максимальное значение}

if d2 < b2 then d2 := b2;

if d2 < c2 then d2 := c2;

d := (BX - CX)*(BY - AY) – (BX - AX)*(BY - CY);

if a2*b2*c2 = 0 then

if a2 + b2 + c2 = 0 then writeln(0)

else writeln(1)

else

if d = 0 then writeln(2)

else

if 2*d2 < a2 + b2 + c2

then writeln(3)

else

if 2*d2 = a2 + b2 + c2

then writeln(4)

else writeln(5)

end.

5*. Задана система двух линейных уравнений относительно x и y:

Требуется решить данную систему. На вход программе подаются 6 чисел: a, b, c, d, e, f (все числа целые, по модулю не превосходят 100; обратите внимание, что сначала вводятся значения a, b, c, d, а потом e и f). Выдать на экран описание решения в следующем виде:

· 0 — решений нет;

· 1 — решение имеет вид y = kx + b, k 0;

· 1X c — решение представляет собой пары вида (x, c), c фиксированно, x любое. Вывести с с точностью до двух знаков после десятичной точки;

· 1Y с — решение представляет собой пары вида (c, y), c фиксированно, y любое. Вывести с с точностью до двух знаков после десятичной точки;

· 2 x y — решение системы единственно, вывести x и y с точностью до двух знаков после десятичной точки;

· 2XY — любая пара (x, y) является решением данной системы.

Решение. Сначала решим задачу для общего случая: умножим первое уравнение на d, а второе на b, вычтем из одного другое и найдем значение x, затем умножим первое из данных уравнений на с, а второе — на a и легко найдем значение y (решение, в котором одна из переменных выражается из первого уравнения и подставляется во второе, существенно сложнее). Из полученных формул видно, что подобное решение невозможно лишь когда ad – bc = 0. В последнем случае решений будет или бесконечно много, или не будет совсем. Разобрать получающиеся случаи помогает графическая интерпретация решения данной системы уравнений: результатом является либо точка, либо прямая, либо вся плоскость, либо пустое множество точек. С учениками математических классов решение данной задачи нужно разобрать обязательно.

Приведем тело программы для решения данной задачи:

D := a*d - c*b;

Dx := e*d - f*b;

Dy := a*f - c*e;

if D <> 0 then

begin {решение единственное}

x := Dx/D;

y := Dy/D;

writeln('2 ',x:0:2,' ',y:0:2)

end

else

if abs(a) + abs(b) + abs(c) + abs(d) = 0 then

if abs(e) + abs(f) = 0

then writeln('2XY')

else writeln('0')

else

if (dx <> 0) or (Dy <> 0) then writeln('0')

{коэффициенты уравнений непропорциональны}

elseb = 0

then writeln('1Y ',e/a:0:2)

else if a = 0

then writeln('1X ',e/b:0:2)

else writeln(1)

Комментарии и решения задач урока 5

1. По заданным вещественному значению x и целому значению n вычислите xn (операция возведения в степень в языке Pascal отсутствует).

Решение. Как сказано в условии задачи, операция возведения в степень в языке Pascal отсутствует.
И это не случайно. Дело в том, что для реализации этой операции в других языках программирования используется тождество: xy = eylnx, т.е. фактически запрограммированно сначала вычисление натурального логарифма, а потом — экспоненты. И то и другое представляет собой суммирование соответствующего ряда. Для целых степеней это неэффективно и ведет к потере точности. Простое возведение x в целую неотрицательную степень n:

readln(x,n);

p := 1;

i := 0;

while i < n do

begin

i := i + 1;

p := p * x

end;

Обратите внимание учеников, что, хотя переменная i не используется непосредственно при подсчете результата, она все равно необходима в качестве счетчика, причем на каждом шаге цикла p = xi это так называемый “инвариант цикла”.

2. Найдите сумму цифр введенного целого числа. (На каждом шаге выделяется последняя цифра числа, а затем число делится на 10. Процесс повторяется, пока число не станет равным 0.)

Решение. Данную задачу обязательно нужно разобрать со школьниками. Она служит примером решения различных задач, связанных с выделением цифр из числа. Приведем основную часть ее решения без комментариев.

readln(n);

m := n;

s := 0;

while m > 0 do

begin

k := m mod 10;

m := m div 10;

s := s + k

end;

writeln(s);

3. На вход программе подается натуральное число n 109. Проверьте, является ли оно простым. Выведите YES или NO в зависимости от ответа на вопрос задачи.

Решение. Для чисел 1, 2, а также всех четных чисел ответ можно выписать сразу. Проверку нечетного числа на простоту будем осуществлять с помощью деления на числа, меньшие n. Обратите внимание учащихся, что проверку следует осуществлять только до .

read(n);

if (n = 1) or (n mod 2 = 0)

then writeln('NO') else

if n = 2 then writeln('YES') else

begin

prime := true;

i := 3;

mx := trunc(sqrt(n));

while i <= mx do

begin

if n mod i = 0 then

prime := false;

i := i + 2

end;

if prime then writeln('YES')

else writeln('NO');

end;

5. Найдите все целочисленные решения уравнения ax3 + bx2 + cx + d = 0 и выведите их в произвольном порядке. На вход программе подаются 4 целых числа: a, b, c и d, по модулю не превосходящие 109, a 0. Максимальное время работы программы на одном тесте — 1 секунда.

Решение. При d = 0 одним из корней уравнения является 0, а также целочисленные корни квадратного уравнения ax2 + bx + c = 0. При d 0 все корни уравнения, отличные от 0, являются делителями числа d. То есть решение сводится к перебору положительных и отрицательных делителей числа d и подстановки их в исходное уравнение. Для вычисления значения многочлена при конкретном значении x при использовании схемы Горнера можно либо все операции проводить в вещественном типе данных extended, либо игнорировать переполнение целого типа, так как, если значение многочлена равно 0, то все промежуточные значения окажутся не больше 109. Для того чтобы решение работало достаточно быстро, необходимо искать делители числа d только среди натуральных чисел, не превосходящих . Но если мы нашли один из таких делителей k, то проверить нужно также числа –k, n/k и – n/k.

Приведем часть решения задачи для случая d 0:

mx := trunc(sqrt(d));

i := 1;

repeat

if d mod i = 0 then

begin

if ((a*i+b)*i+c)*i+d=0

then writeln(i);

if ((a*-i+b)*-i+c)*-i+d=0

then writeln(-i);

j := d div i;

if i < j then

{есть другой делитель}

begin

if ((a*j+b)*j+c)*j+d=0

then writeln(j);

if ((a*-j+b)*-j+c)*-j+d=0

then writeln(-j)

end;

i := i + 1

until i > mx;

6. На вход программе подается натуральное число n 109. Проверьте, можно ли представить его в виде суммы двух квадратов натуральных чисел. Выведите YES или NO в зависимости от ответа на вопрос задачи. В случае положительного ответа во второй строке выведите два числа, сумма квадратов которых равна n. Числа следует выводить в порядке неубывания. Максимальное время работы программы на одном тесте — 0,1 секунды.

Решение. Будем искать разложение n вида n = i2 + j2, где i j. В этом случае . При решении большое внимание следует обращать на точность вычислений и правомочное округление вещественных чисел. Приведем основную часть решения:

read(n);

mx := trunc(sqrt(n/2));

i := 0;

repeat

i := i + 1;

j := round(sqrt(n - i*i));

until (i*i + j*j = n) or (i >= mx);

if i*i + j*j = n then

begin

writeln('YES');

writeln(i, ' ', j)

end

else writeln('NO');

7. Вкладчик положил на банковский счет n рублей. Каждый год на сумму вклада начисляется k процентов годовых (будем считать, что процент всегда округляется до целого числа рублей по формуле [xk/100], где x — сумма вклада на начало года). Начисленные проценты добавляются к сумме вклада. Через сколько лет сумма вклада станет не менее m рублей?

Решение. Задачи 7–8 позволяют показать школьникам, в каком случае лучше использовать цикл с предусловием, а в каком — с постусловием. Так как в данном случае сумма может сразу быть не меньше m, то лучше использовать цикл while:

readln(n, k, m);

ans := 0;

while n < m do

begin

n := n + trunc(n*k/100);

ans := ans + 1

end;

writeln(ans);

8. Вкладчик положил на банковский счет некоторую сумму n. Каждый год на сумму вклада начисляется k процентов годовых (будем считать, что процент всегда округляется до целого числа рублей по формуле [xk/100], где x — сумма вклада на начало года). Начисленные проценты добавляются к сумме вклада. Через сколько лет сумма вклада как минимум удвоится?

На вход программе подаются два натуральных числа 4: n 106, k 100. Выведите одно число — количество лет, через которое сумма вклада как минимум удвоится.

Решение. Заметим, что при отсутствии округления при вычислении процентов можно было бы не указывать начальную сумму вклада — любая сумма удваивалась бы за один и тот же срок, и вычислить его можно было бы по формуле. В случае с округлением это не всегда так. Поэтому будем, как и в предыдущей задаче, моделировать увеличение средств на счете, пока сумма не удвоится. Очевидно, что для этого деньги на счету должны пролежать как минимум год, поэтому в данном случае для решения больше подходит цикл repeat:

readln(n, k);

ans := 0;

m := 2*n;

repeat

n := n + trunc(n*k/100);

ans := ans + 1

until n >= m;

writeln(ans);

9. На вход программе подаются два натуральных числа: n, m 109. Выведите их наибольший общий делитель. Для решения задачи используйте алгоритм Евклида, основанный на следующем тождестве: НОД(n, m) = НОД(m, r), где r — остаток от деления n на m. Если r = 0, то m = НОД(n, m).

Решение. Алгоритм Евклида является одним из важнейших целочисленных алгоритмов, обязательно разберите его с учащимися. Приведем наиболее короткую его реализацию:

read(n, m);

while m > 0 do

begin

r := n mod m;

n := m;

m := r

end;

writeln(n);

Заметим, что в решении не нужно проверять, какое из чисел больше — n или m. Если после считывания данных n < m, то после первого выполнения оператора цикла значения просто поменяются местами.

10. На вход программе подается последовательность целых чисел, заканчивающаяся 0. Выведите минимальное и максимальное значения среди чисел этой последовательности, 0 при этом не учитывается. При решении задачи массив использовать нельзя.

Решение. Эта задача также является очень важной при изучении программирования. Она относится к классу задач на обработку числовых последовательностей без использования массивов. Кроме того, при ее решении используются такие базовые алгоритмы, как поиск максимального и минимального значения элементов последовательности. Необходимо добиться, чтобы все школьники данные алгоритмы освоили. Приведем основной фрагмент решения задачи:

read(a);

min := a;

max := a;

while a <> 0 do

begin

if a < min then min := a else

if a > max then max := a;

read(a)

end;

writeln(min,' ',max);

Обратите внимание, что если все значения элементов последовательности считывать в цикле, а начальные значения минимума и максимума проинициализировать заведомо большим и заведомом маленьким числом соответственно, то программа может неправильно работать, например, на убывающей последовательности. Кроме того, школьники в качестве “маленького” числа часто выбирают 0, и программа неправильно работает с отрицательными числами. Все это надо учитывать при подготовке системы тестов.

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

Решение. Задача решается аналогично предыдущей. Типичные ошибки — учет числа ноль при подсчете количества чисел, а также использование неверной рекуррентной формулы для подсчета среднего арифметического: si+1 = (si + a)/2, где a — очередной элемент последовательности. Правильное решение задачи:

read(a);

i := 0;

s := 0;

while a <> 0 do

begin

i := i + 1;

s := s + a;

read(a)

end;

if i <> 0 then

writeln(s/i:0:2);

12. Программа получает на вход последовательность целых чисел, по модулю не превосходящих 109. Признак окончания последовательности — число –2x109. Программа должна определить вид последовательности — возрастающая, убывающая, случайная или постоянная.

Ответ следует выдать в следующем формате — в 1-й строке напечатать количество элементов последовательности (без учета –2?109), во 2-й строке — тип последовательности:

ASCENDING (строго возрастающая);

WEAKLY ASCENDING (нестрого возрастающая, т.е. неубывающая);

DESCENDING (строго убывающая);

WEAKLY DESCENDING (нестрого убывающая, т.е. невозрастающая);

CONSTANT (постоянная);

RANDOM (случайная).

При решении задачи массивы использовать нельзя.

Решение. Так как массив в программе использовать нельзя, будем хранить в двух переменных соседние элементы входной последовательности. Будем также считать, что, помимо последнего (барьерного) элемента, который не надо учитывать в решении, в последовательности есть по крайней мере 2 элемента. Тогда решение может выглядеть так:

ac := true;

wac := true;

dc := true;

wdc := true;

cn := true;

read(a, b);

while b <> –2000000000 do

begin

if a >= b then ac := false;

if a > b then wac := false;

if a <= b then dc := false;

if a < b then wdc := false;

if a <> b then cn := false;

a := b;

read(b)

end;

if ac then writeln('ASCendING') else

if dc then writeln('DESCendING') else

if cn then writeln('CONSTANT') else

if wac then writeln('WEAKLY ASCendING') else

if wdc then writeln('WEAKLY DESCendING')

else writeln('RANDOM');

Обратите внимание, что после анализа последовательности проверять признаки на истинность в произвольном порядке нельзя. Так, если последовательность является слабо возрастающей, то она же может оказаться и постоянной, обратное же неверно, поэтому признаки слабого возрастания и слабого убывания проверяются в последнюю очередь.

Комментарии и решения задач урока 6

1. По заданному натуральному значению n вычислить 1 – 1/3 + 1/5 – 1/7 + ... 1/(2n + 1). На вход программе подается натуральное число n 10 000. Выведите с точностью 6 значащих цифр после десятичной точки значение указанного выражения.

Решение. Подобная задача рассматривалась в материалах урока, поэтому приведем решение без комментариев:

k := 1;

s := 1;

for i := 1 to n do

begin

k := -k;

s := s + k/(2*i + 1)

end;

2. В последовательности a1, a2, ..., an найти номер самого большого числа. На вход программе сначала подается натуральное число n 106. Далее следуют n целых чисел, по модулю не превосходящих 30 000, — сами члены последовательности. Выведите номер максимального числа. Если таких чисел несколько, то выведите номер последнего из них. Нумерация чисел начинается с единицы. Массив в программе не использовать.

Решение. Данная задача закрепляет полученные ранее умения обрабатывать числовые последовательности без сохранения их в массиве, а также находить максимальный элемент последовательности. Кроме того, учащиеся должны почувствовать связь между параметром цикла и номером элемента последовательности. Пример решения:

read(n);

read(a);

max := a;

num := 1;

for i := 2 to n do

begin

read(a);

if max <= a then

begin

max := a;

num := i

end

end;

writeln(num);

Вторую и третью строчки приведенного фрагмента программы можно заменить на одну:

read(max);

— но в этом случае программа становится менее понятной, поэтому экономия в данном случае вряд ли нужна.

3. Дана последовательность, состоящая из n чисел. Выяснить, сколько раз в ней встречается минимальное число. На вход программе сначала подается натуральное число n 106. Далее следуют n целых чисел, по модулю не превосходящих 30 000, — сами члены последовательности. Выведите число, которое является ответом на вопрос задачи. Массив в программе не использовать.

Решение. Отсутствие массива в решении указывает в этой задаче на то, что решить ее нужно за один просмотр данных (решение за два просмотра очевидно). Тем не менее и при таких ограничениях решение не становится намного сложнее:

read(n);

read(a);

min := a;

kol := 1;

for i := 2 to n do

begin

read(a);

if a < min then

begin

min := a;

kol := 1

end

else if a = min then

kol := kol + 1;

end;

write(kol);

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

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

read(n);

read(a);

min := a;

max := a;

sum := a;

for i := 2 to n do

begin

read(a);

sum := sum + a;

if a > max then max := a;

if a < min then min := a

end;

writeln((sum – min - max)/(n - 2):0:2);

5. По заданному натуральному числу n и вещественному x вычислить

.

На вход программе подаются натуральное n 100 и вещественное x, по модулю не превосходящее 10. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

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

read(n, x);

ans := 1;

a := 1;

{первое слагаемое учтено}

for i := 1 to n do

{i соответствует степени x}

begin

a := a*x/i;

ans := ans + a

end;

writeln(ans:0:6);

6. По заданному натуральному числу n и вещественному x вычислить

.

На вход программе подаются натуральное n 100 и вещественное x, по модулю не превосходящее 10. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

Решение. Данная задача немного сложнее предыдущей. Поэтому приведем решение, в котором степени, факториалы, а также знак слагаемого пересчитываются по отдельности:

read(n, x);

ans := 1;

p := 1;{степень x}

f := 1;{факториал}

k := 1;{знак слагаемого}

for i := 1 to n do

begin

p := p*x*x;

f := f*(2*i-1)*2*i;

k := -k;

ans := ans + k*p/f

end;

writeln(ans:0:6);

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

7. По заданным натуральным числам n и m вычислить

.

На вход программе подаются натуральные n 100 и m 100. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки.

Решение. Данная задача является примером задачи на рекуррентные соотношения другого вида. Научите ребят сначала находить формулу для пересчета выражения “верхнего уровня” через нижестоящее выражение, а уже потом его программировать. В виде рекуррентного соотношения условие задачи можно записать так: Требуется найти s1. Программа для решения этой задачи оказывается совсем простой, однако на ее примере можно вспомнить правила использования цикла с downto:

read(n, m);

ans := 0;

for i := n downto 1 do

ans := sqrt(i*m + ans);

writeln(ans:0:6);

8. Числа Фибоначчи определяются следующими формулами: f0 = f1 = 1; fn = fn–1 + fn–2, при n 2.

На вход программе подается целое неотрицательное n 40. Выведите n-е число Фибоначчи. Массив в программе не использовать.

Решение. Числа Фибоначчи и в математике, и в программировании используются достаточно часто. Поэтому познакомиться с ними полезно. Для того чтобы решить задачу без использования массива, нам придется завести три переменных для хранения трех соседних чисел Фибоначчи и аккуратно их переопределять по мере вычислений. Заметим, что 40-е число Фибоначчи заведомо невозможно найти с использованием типа integer языка Borland Pascal. Кроме того, необходимо следить за тем, чтобы программа корректно находила и первое, и нулевое числа Фибоначчи:

read(n);

f1 := 1;

f2 := 1;

f := f1 + f2;

for i := 3 to n do

begin

f2 := f1;

f1 := f;

f := f1 + f2

end;

if n > 1 then writeln(f)

else writeln(1);

9. Дана последовательность, состоящая из n чисел. Найти в ней два самых маленьких числа. На вход программе сначала подается натуральное число n 106. Далее следуют n целых чисел, по модулю не превосходящих 30 000, — сами члены последовательности. Выведите минимальное число и второе по величине число (оно может совпадать с минимальным).

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

Решение. Единственная сложность при решении данной задачи — аккуратная обработка входной последовательности за один просмотр:

read(n);

mn1 := 31000;

mn2 := 31000;

for i := 1 to n do

begin

read(a);

if a <= mn1 then

begin

mn2 := mn1;

mn1 := a

end

else if a < mn2 then

mn2 := a;

end;

writeln(mn1, ' ', mn2);

10. Вычислите по схеме Горнера значение полинома anxn + an–1xn–1 + … + a1x + a0 в точке x0.

На вход программе сначала подается целое неотрицательное число n 20. Затем вещественное число x0, по модулю не превосходящее 10. Далее следуют n + 1 вещественных чисел, по модулю не превосходящих 10. Выведите значение полинома с точностью до трех значащих цифр после десятичной точки. При решении задачи массив использовать нельзя.

Решение. Без массива данную задачу можно решать с помощью схемы Горнера только в случае, когда коэффициенты полинома задаются в порядке: от коэффициента при максимальной степени x до коэффициента при нулевой степени (a0):

read(n, x0);

ans := 0;

for i := n downto 0 do

begin

read(a);

ans := ans*x0 + a;

end;

writeln(ans:0:3);

Комментарии и решения задач урока 7

1. Для заданного натурального числа n найти все тройки натуральных чисел a, b, c таких, что a + b + c = n и a b c. Минимизируйте количество условий, которые используются в программе.

Решение. Указанное в предыдущей публикации ограничение на n, видимо, необходимо уменьшить, например, до 30 000. В противном случае решение, в котором не используется формула, будет работать более одной секунды. Тем не менее программу можно написать так, что и без применения условных операторов будут генерироваться все необходимые тройки:

read(n);

for i := 1 to n div 3 do

for j := i to (n - i) div 2 do

ans := ans + 1;

writeln(ans);

2. a) Автобусный билет считается счастливым, если в его шестизначном номере сумма первых трех цифр равна сумме трех последних цифр. Подсчитайте и выведите число счастливых билетов с различными номерами (от 000001 до 999999).

б) Билет считается счастливым, если в его n-значном номере сумма первых [n/2] цифр равна сумме [n/2] последних цифр (при нечетном n центральная цифра в “проверке на счастье” не участвует и может быть любой). Подсчитайте число счастливых билетов с различными n-значными номерами (ведущие нули в номерах возможны, но номера, состоящего из одних нулей, не существует).

Решение. На примере задачи a) можно просто поучиться писать вложенные циклы (в данном случае их будет 6, каждый от 0 до 9). Номер, состоящий из одних нулей, исключать из перебора не нужно, гораздо проще от полученного ответа отнять единицу. Окончательным ответом на данную задачу является число 52 251.

Задача б) является практически олимпиадной. Основная идея ее решения. Подсчитаем сумму цифр у левой половины номера. Счастливыми окажутся все билеты, у которых сумма правых цифр будет такой же. Так, для шестизначного билета, если мы обозначим количество трехзначных чисел, сумма цифр у которых равна, например, 15, за S15, то количество счастливых билетов, сумма первых трех цифр которых равна сумме трех последних и равна 15, выражается формулой S15 x S15. Общее число счастливых билетов для шестизначных билетов равно S12 + S22 + … + S272. Для произвольных четных n ответ получается аналогично. Для нечетных n ответ получается домножением ответа, полученного для n – 1, на 10 (средняя цифра может быть любой, в том числе и нулевой) и прибавлением 9 (билеты, у которых все цифры, за исключением средней, равны 9). В этом случае однозначные билеты не являются исключением. Их количество просто равно 9, и все они счастливые. Приведем возможную реализацию данного решения:

var n, i, s,

a1, a2, a3, a4, a5, a6,

n1, n2, n3, n4, n5, n6: integer;

a, ans: extended;

begin

read(n);

if n > 3 then n1 := 9 else n1 := 0;

if n > 5 then n2 := 9 else n2 := 0;

if n > 7 then n3 := 9 else n3 := 0;

if n > 9 then n4 := 9 else n4 := 0;

if n > 11 then n5 := 9 else n5 := 0;

if n > 13 then n6 := 9 else n6 := 0;

ans := 0;

for s := 1 to (n div 2)*9 do

begin

a := 0;

for a1 := 0 to n1 do

for a2 := 0 to n2 do

for a3 := 0 to n3 do

for a4 := 0 to n4 do

for a5 := 0 to n5 do

for a6 := 0 to n6 do

if s-a1-a2-a3-a4-a5-a6 in [0..9]

then a := a + 1;

ans := ans + a*a

end;

if n mod 2 = 1 then ans := ans*10 + 9;

writeln(ans:0:0)

end.

Заметим, что с использованием массивов (n1[1..7], в котором бы указывалось количество цифр в соответствующем разряде, и s[1..63], где s[i] — количество [n/2]-значных чисел, сумма цифр которых равна i) задача решается проще. Обратите также внимание, что ответ не умещается в целый тип longint, поэтому для нахождения результата используется вещественный тип extended.

3. Определите количество различных способов выплаты сдачи в размере n < 100 рублей купюрами 10 рублей и монетами 5, 2 и 1 рубль. Так, 5 рублей можно выплатить четырьмя различными способами:

5 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1.

Решение. Задача решается перебором всех возможных вариантов выдачи сдачи. Однако после того, как мы зафиксировали количество 10-рублевых купюр и монет в 5 и 2 рубля, количество рублевых монет определяется однозначно, поэтому мы перебираем только три старших номинала денежных единиц. Возможно, в условие задачи можно добавить и 50-рублевые купюры. Но увеличение n до 5000 и добавление более крупных купюр (100 и 1000 рублей) могут привести к тому, что ответ уже нельзя будет получить перебором вариантов. Приведем решение задачи в изначальной формулировке:

read(n);

ans := 0;

for i := 0 to n div 10 do

for j := 0 to (n - i * 10) div 5 do

for k := 0 to (n - i * 10 - j * 5) div 2 do

ans := ans + 1;

writeln(ans)

4. Напишите программу, которая будет разлагать натуральное число n > 1 на простые множители.

На вход программе подается натуральное n 30 000. Выведите его разложение на простые множители, располагая их в порядке неубывания так, как показано в примерах.

17-0.gif (6467 bytes)

Решение. Задача относится к числу задач базовых проблем, которые можно рекомендовать для обязательного рассмотрения. Алгоритм решения задачи следующий. Возьмем первое простое число — 2. Пока n делится на 2, будем делить его на 2 и двойки сразу печатать. Если число на 2 уже не делится, будем пытаться делить его на 3 и т.д. Интересно, что проверять при этом делители на простоту не нужно! Дело в том, что если число уже разделили на 2 и на 3 максимально возможное число раз, то ни на 4, ни на 6, ни на 9 оно не разделится автоматически. Поэтому делители можно проверять подряд, но делать это только до квадратного корня из исходного числа n. Если оставшееся число больше единицы, то оно тоже простое и его нужно напечатать. Основную техническую сложность представляет в данном случае аккуратный вывод результата. Приведем возможный вариант решения:

read(n);

write(n, '=');

for i := 2 to round(sqrt(n)) do

while n mod i = 0 do

begin

n := n div i;

write(i);

if n > 1 then write('*');

end;

if n > 1 then write(n);

5. Дано число n. Найдите число из диапазона от 1 до n с максимальной суммой своих делителей (включая непростые делители, 1 и само число). Если таких чисел несколько, выведите минимальное из них.

Решение. Эта задача просто закрепляет умение работать со вложенными циклами. Приведем ее без комментариев:

read(n);

s := 0;

r := 0;

for i := 1 to n do

begin

s1 := 0;

for j := 1 to round(sqrt(n)) do

if i mod j = 0 then

if j*j = i then s1 := s1 + j

else s1 := s1 + j + i div j;

if s1 > s then

begin

r := i;

s := s1

end

end;

writeln(r)

6. Цифровой корень натурального числа получается следующим образом. Складываются все цифры данного числа. Процесс повторяется, пока в результате не будет получено однозначное число, которое и называется цифровым корнем числа.

Решение. Задача на вложенные циклы с пост- или предусловием:

read(n);

while n > 9 do

begin

n1 := 0;

while n > 0 do

begin

n1 := n1 + n mod 10;

n := n div 10

end;

n := n1

end;

writeln(n)

7. Напишите программу для подсчета числа точек c целочисленными координатами, находящихся внутри и на границе круга c центром в начале координат и заданным радиусом r. На вход программе подается целое неотрицательное число r 1 000 000. Выведите количество искомых точек в этом круге.

Решение. Перебрать все точки в данном случае не удастся. Решим задачу для четверти круга. Целочисленные точки будем суммировать по столбцам. На оси координат Oy выше оси Ox лежит ровно r целочисленных точек круга. В каждом следующем столбце будет либо столько же целочисленных точек круга, либо меньше (см. рисунок). На сколько меньше — проще всего выяснить, вычитая точки по одной и подставляя результат в уравнение окружности (на самом деле в неравенство, которое позволяет определить, лежит ли точка внутри круга). В этом случае все вычисления будут производиться точно (но при больших r придется использовать тип extended). Количество точек в столбце можно определять и по формуле, но тогда могут возникнуть проблемы с точностью.

Приведем возможный вариант решения задачи:

readln(r);

ans := r;

s := r;

for i := 1 to r - 1 do

begin

while r*r < i*i + s*s do

s := s - 1;

ans := ans + s

end;

ans := 4*ans + 1;

{начало координат учитывается отдельно}

writeln(ans);

8. Экспериментальным путем определите, факториал каких чисел может быть точно вычислен в 32-битном целом типе (integer в Delphi и longint в Borland Pascal), 64-битном целом типе (int64 в Delphi и comp в Borland Pascal) и типе extended. Затем напишите программу, которая будет работать следующим образом. Сначала запрашивается число K — количество факториалов, которые надо вычислить (K 100). Затем K раз считывается значение N (N 100), для очередного N сразу вычисляется значение N!, если это можно точно сделать хотя бы в одном из указанных типов данных, и выводятся в строке через пробел найденное значение факториала и число 1, 2 или 3 соответственно в зависимости от типа данных, в котором можно это значение посчитать точно (выводится минимально возможное значение). Если точно факториал в стандартной компьютерной арифметике вычислить невозможно, то выводится только 0.

Пример диалога программы:

3 {введено значение K}

3 {введено первое значение N}

6 1 {это вывод результата для первого факториала}

15 {введено второе значение N}

1307674368000 2 {это вывод результата для второго факториала}

100 {введено третье значение N}

0 {это вывод результата для третьего факториала}

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

Для значений целых типов ответ получить не сложно — достаточно сравнивать результат вычислений в таком типе с результатом вычислений в типе extended. Для анализа последнего достаточно заметить, что при последовательном получении факториалов после домножения 22! на 23 у результата появляется лишний ноль, чего не может быть. Соответственно максимальное n, для которого в стандартной компьютерной арифметике можно вычислить факториал точно, равно 22. Часто возникает вопрос: почему в типе extended результат можно вычислить для большего значения n, нежели для типа int64? Ведь в первом из них на хранение мантиссы (цифр числа) отводятся те же 64 бита. Дело в том, что факториалы, записанные в двоичной системе счисления, начиная с 2! имеют на конце несколько нулей. Например, 5! = 120 = 11110002. Поэтому в мантиссе будут записываться двоичные цифры, начиная с правой единицы, а количество нулей в конце числа будет учтено в его порядке.

Приведем пример диалоговой программы, отвечающей условию задачи:

var f: extended;

g: int64;

i,k,n,j: integer;

begin

read(k);

for j := 1 to k do

begin

f := 1;

g := 1;

read(n);

for i := 2 to n do

begin

f := f * i;

g := g * i

end;

if f <= maxlongint

then writeln(g,' ',1) else

if g = f

then writeln(g,' ',2) else

if n < 23 then

writeln(f:0:0,' ',3)

else writeln(0)

end

end.

9. По заданным вещественному значению x и целому неотрицательному значению n вычислите xn (операция возведения в степень в языке Pascal отсутствует). Для решения задачи используйте алгоритм эффективного возведения в степень.

Алгоритм основан на тождестве x2n = xnxn. Тогда, если n = 2k, то значение xn можно получить из x, домножая результат сам на себя (таким образом, мы будем последовательно получать значения 2-, 4-, 8-й и т.д. 2k-й степеней числа x). В свою очередь, произвольное n можно представить как сумму степеней двойки (фактически перевести в двоичную систему счисления):
n = 2k1 + 2k2 + … Соответственно Фактически алгоритм быстрого возведения в степень сводится к последовательному получению 2-, 4-, 8-й
и т.д. степеней числа x и перемножению необходимых степеней.

Решение. Так как алгоритм решения задачи изложен в ее условии, просто приведем его реализацию:

readln(x, n);

p := 1;

q := x;

m := n;

while m > 0 do

begin

if odd(m) then

begin

m := m - 1;

p := p * q

end

else

begin

m := m div 2;

q := q * q

end

end;

10. По заданным натуральным числам n и m вычислите . На вход программе подается натуральное m 100. Выведите значение указанного выражения с точностью 6 значащих цифр после десятичной точки (известно, что это выражение, состоящее из бесконечного числа вложенных корней, для всех указанных значений m конечно).

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

read(m);

ans1 := 0;

ans2 := 1;

n := 5;

while ans2 – ans1 > 1e-7 do

begin

ans1 := ans2;

ans2 := 0;

for i := n downto 1 do

ans2 := sqrt(i*m + ans2);

n := n + 1

end;

writeln(ans2:0:6);

Комментарии и решения задач урока 8

1. Выдайте на экран все символы, по порядку их номеров, помещая по 60 символов в строке (в первой строке — символы с 0-го по 59-й, во второй — с
60-го по 119-й и т.д.). На эффект от спецсимволов, таких, как звуковой сигнал и перевод строки, не обращайте внимания. Вложенные циклы или несколько последовательных циклов не использовать.

Решение. При решении этой задачи основные сложности вызывает выдача на экран именно по 60 символов в строке. Перевод строки следует производить после 59-, 119-, 179-го и т.д. символов, естественно, не указывая их явным образом в программе. Перевод строки, осуществляющийся в результате печати соответствующего управляющего символа, при этом учитывать не нужно. Приведем фрагмент одного из возможных решений:

for c := #0 to #255 do

begin

write(c);

if (ord(c) + 1) mod 60 = 0

then writeln

end;

2. Напишите программу, которая будет для любой нажатой клавиши, генерирующей один символ, выдавать ее символьный код (номер). На экране должен быть как нажатый символ, так и его код. Программа заканчивает свою работу тогда, когда какой-либо символ был введен два раза подряд (код последнего символа второй раз не выводится).

Пример диалога программы:

A

65

1

49

1

Решение. Эта задача достаточно проста. Школьникам необходимо лишь придумать, как программным путем определять, что какая-то клавиша была нажата два раза подряд. Массивы в этой программе использовать нецелесообразно (количество вводимых символов по условию не ограничено). Возможный вариант решения задачи:

var c1, c2: char;

begin

readln(c2);

repeat

c1 := c2;

writeln(ord(c1));

readln(c2)

until c1 = c2

end.

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

Решение. Цифры шестнадцатеричных чисел в языке Pascal можно считать только в символьный тип, а потом перевести в числовой аналог. В этой задаче впервые отрабатывается такое умение:

var i, s1, s2: integer;

c1, c2: char;

begin

readln(c1,c2);

c1 := upcase(c1);

c2 := upcase(c2);

if c1 in ['0'..'9'] then

s1 := ord(c1) - ord('0') else

if c1 in ['A'..'F'] then

s1 := ord(c1) - ord('A') + 10;

if c2 in ['0'..'9'] then

s2 := ord(c2) - ord('0') else

if c2 in ['A'..'F'] then

s2 := ord(c2) - ord('A') + 10;

writeln(s1*16+s2);

end.

4. Выведите на экран последовательность символов:

a

ab

abc

abcd

— и т.д. до строки, заканчивающейся символом “z”.

Решение. В наиболее элегантном решении данной задачи не используются числовые переменные и знание того, что в латинском алфавите 26 букв:

var c1, c2: char;

begin

for c1 := 'a' to 'z' do

begin

for c2 := 'a' to c1 do

write(c2);

writeln

end

end.

5. Определите, сколько раз в последовательности символов, заканчивающейся точкой, встречаются цифры и сколько — латинские буквы.

Решение.

koldig := 0;

kollet := 0;

read(b);

while b <> '.' do

begin

if (b <= '9') and (b >= '0') then

koldig := koldig + 1

else

if (b >= 'A') and (b <= 'Z') or

(b >= 'a') and (b <= 'z') then

kollet := kollet + 1;

read(b)

end;

writeln(koldig, ' ', kollet);

6. Дана непустая последовательность слов, состоящих из латинских букв. Соседние слова отделены друг от друга символом запятой, за последним словом следует точка. Определите количество слов, которые начинаются с буквы “a” (как строчной, так и заглавной).

На вход программе подается последовательность слов, разделенных запятыми. Последовательность заканчивается точкой. Выведите количество слов этой последовательности, начинающихся с буквы “a” (как строчной, так и заглавной).

Решение. Если указанный в условии формат входных данных строго соблюдается и, кроме запятых, между словами нет других символов, например, пробелов, то задача решается достаточно легко:

k := 0;

repeat

read(c);

if upcase(c) = 'A' then k := k + 1;

{пропуск остальных букв слова}

repeat

read(c)

until (c = ',') or (c = '.')

until c = '.';

writeln(k);

7. Для введенного натурального числа k от 1 до 120 напечатайте фразу:

Мне k лет

Учтите, что при некоторых значениях k слово лет надо заменить на слово год или года. В программе обязательно используйте оператор case. Фразу надо выводить в кодировке Windows-1251. Соблюдайте регистр при выводе символов и разделяйте слова ровно одним пробелом.

Решение. Решение этой задачи дает единый ключ к пониманию того, как грамотно распечатать результат работы программы на русском языке. Это касается, например, и денежных расчетов (рубль, рубля, рублей), причем правила выбора нужного падежа остаются неизменными. Школьники быстро замечают, что в основном определяющей здесь является последняя цифра числа. Однако исключение составляют числа, дающие при делении на 100 остатки 11..14, причем в нашей задаче это касается и чисел 111..114 (про них ученики очень часто забывают). Приведем основной фрагмент решения задачи:

if k mod 100 in [10..20] then

writeln('Мне ',k,' лет')

else

case k mod 10 of

0,5..9: writeln('Мне ',k,' лет');

1: writeln('Мне ',k,' год');

2..4: writeln('Мне ',k,' года');

end;

8. Напишите программу, вычисляющую значение простейшего арифметического выражения. Пользователь вводит выражение, такое, как 1+2 или 7*8 без пробелов (цифра, знак операции: +, – или *, цифра), и программа печатает результат.

Решение. Данная задача призвана научить переводить символ цифры в соответствующее число. Заметим, что делать это обязательно лишь для первой цифры, вторая, несмотря на то что стоит сразу за знаком операции, может быть сразу считана в целочисленную переменную. Обратите внимание учеников на эту особенность смешанного ввода данных. Явным образом код цифры ноль (48) при выполнении преобразования использовать не нужно. Во-первых, мы оказываемся привязанными к знанию конкретной кодовой таблицы, во-вторых, программа становится менее понятной. Приведем основной фрагмент решения данной задачи:

read(c); {считали первую цифру}

i := ord(c) - ord('0');

readln(c,j);{считали знак и вторую цифру}

case c of

'+': k := i + j;

'-': k := i - j;

'*': k := i * j;

end;

writeln(k);

9. Даны следующие описания:

type direction = (north, east, south,west);

curs = (forwrd,left,right,back);

var k1,k2:direction;

p: curs;

n: integer;

Корабль шел по курсу k1 (тип direction), ему был дан приказ p (тип curs). Определить значение курса (тип direction), которое получит корабль в результате выполнения приказа. Задачу следует решать путем непосредственных операций над переменными перечислимого типа без использования их числовых аналогов. При использовании вложенных операторов case подумайте, какой из них сделать внешним, а какой — внутренним.

Решение. Данная задача отрабатывает умение работать с перечислимыми типами данных, в том числе решать вопросы ввода и вывода соответствующих значений, а также требует уверенного использования операторов case. Предложите школьникам решить задачу так, чтобы разбор вариантов происходил непосредственно для констант перечислимого типа, а не для их числовых аналогов. В данном случае необходимо использовать вложенные операторы варианта, причем для получения компактной программы важно, какой из операторов будет внешним, а какой — внутренним. Приведем возможное решение данной задачи:

begin

write('Введите номер курса корабля

(0-север, 1-восток, 2-юг, 3-запад): ');

readln(n);

k1 := direction(n);

write('Введите номер изменения курса

(0-прямо, 1-налево, 2-направо, 3-назад): ');

readln(n);

p := curs(n);

case p of

forwrd: k2 := k1;

left: if k1 = north then k2 := west

else k2 := pred(k1);

right: if k1 = west then k2 := north

else k2 := succ(k1);

back: case k1 of

north,east: k2 := succ(succ(k1));

south,west: k2 := pred(pred(k1));

end

end;

writeln('Новый курс ', ord(k2))

end.

10. Подсчитайте число пятниц, приходящихся на 13-е числа в XX веке, если известно, что 13 января 1901 года было воскресенье. Выдайте полученное значение.

Указание. Переберите последовательно все 13-е числа XX века, для каждого такого числа определяя его день недели через день недели предыдущего тринадцатого числа. Для учета числа дней в месяце используйте оператор case.

Решение. Приведем программу, которая соответствует приведенной логике решения задачи. Дни недели будем обозначать с помощью остатков от деления на 7. При этом воскресенье будет обозначаться шестеркой, а пятница — четверкой:

d := 6;

s := 0;

for i := 1 to 100 do

for j := 1 to 12 do

begin

if d = 4 then s := s + 1;

case j of

1,3,5,7,8,10,12: d := (d + 3) mod 7;

4,6,9,11 : d := (d + 2) mod 7;

2: if i mod 4 = 0 then

d := (d + 1) mod 7

end {case}

end;

writeln(s);

Комментарии и решения задач урока 9

1. Заполните числовой массив так, чтобы значения элементов были равны квадратам индексов. На вход программе подаются два целых числа — a и b, по модулю не превосходящие 100, a b. Требуется вывести массив с индексами от a до b, элементы которого равны квадратам своих индексов.

Решение. Задача не требует комментариев:

var a, b, i: integer;

c: array[-100..100] of integer;

begin

readln(a, b);

for i := a to b do

c[i] := i*i;

for i := a to b do

write(c[i],' ');

end.

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

Решение. Несмотря на то что аналогичная задача приведена в материалах урока, очень редко ученики решают ее правильно с первого раза. Обычно они предлагают следующий вариант:

с := a[n];

for i := 2 to n do

a[i] := a[i - 1];

a[1] := c;

Дайте им реализовать эту программу на компьютере и изучить, а потом и объяснить результаты ее работы. При необходимости помогите им прийти к правильному решению:

с := a[n];

for i := n downto 2 do

a[i] := a[i - 1];

a[1] := c;

3. Найдите максимальный и минимальный элементы в массиве и поменяйте их местами.

Решение. Алгоритм поиска максимального и минимального элементов массива по реализации несколько отличается от аналогичного алгоритма для последовательностей. Оказывается, в массиве правильнее искать не значение максимального или минимального элемента, а индексы соответствующих элементов, тогда автоматически мы будем знать и сами значения. Таким образом, делать двойную работу не нужно (в одной переменной хранить значение максимального элемента, а в другой — ее индекс). Приведем основную часть наиболее экономичного решения данной задачи.

imax := 1; {индекс максимального элемента}

imin := 1; {индекс минимального элемента}

for i := 2 to n do

if a[i] > a[imax] then imax := i else

if a[i] < a[imin] then imin := i;

c := a[imin];

a[imin] := a[imax];

a[imax] := c;

4. Распечатайте те элементы массива, которые равны сумме двух своих соседей. Первый и последний элементы имеют только по одному соседу, поэтому искомыми быть не могут.

Решение. Задача отрабатывает операции с индексами элементов массива, но является очень простой. Приведем основной фрагмент решения:

for i := 2 to n - 1 do

if c[i] = c[i - 1] + c[i + 1] then

write(c[i],' ');

5. Текст на английском языке записан в массиве a[1..1000] of char. Помимо английских букв, в нем могут встречаться пробелы и знаки препинания. В массиве b['A'..'Z'] of integer получите сведения о том, сколько каких букв встречается в этом тексте. При подсчете строчные и прописные буквы не различать. На вход программе сначала подается значение n 1000 — количество букв в тексте. В следующей строке входных данных расположены сами буквы (без разделителей). Выдайте 26 чисел — значения элементов массива b.

Решение. Эта задача фактически отрабатывает идею “подсчета” — встретив очередную букву, будем учитывать ее в соответствующем элементе массива. Задачи на подобную идею часто встречаются на ЕГЭ по информатике (задачи С4). Кроме того, на примере этой задачи можно наглядно показать, что индексировать элементы массивов иногда очень удобно не числовыми порядковыми величинами. Обратите внимание, что при правильном решении данной задачи текст просматривается ровно один раз, а массив результатов заполняется не по порядку, а по мере прочтения текста. Программа должна также учитывать, что в тексте могут встречаться символы, отличные от букв. Приведем основной фрагмент решения данной задачи:

for c := 'A' to 'Z' do b[c] := 0;

for i := 1 to 1000 do

if a[i] in ['A'..'Z','a'..'z'] then

begin

c := upcase(a[i]);

b[c] := b[c] + 1

end

6. На вход программе подается последовательность чисел от 1 до 9, заканчивающаяся нулем. Всего будет введено не более 100 000 чисел. Подсчитайте в этой последовательности количество единиц, количество двоек, количество троек и так далее и выдайте результат. В выходных данных всегда должно быть 9 чисел.

Решение. Задача решается аналогично предыдущей:

for i := 1 to 9 do

b[i] := 0;

{массив для подсчета количества каждой из цифр}

read(a);

while a <> 0 do

begin

b[a] := b[a] + 1;

read(a)

end;

for i := 1 to 9 do

write(b[i]],' ');

7. Подсчитайте за один проход массива, сколько его элементов равны максимальному элементу.

Указание. Подобная задача уже решалась для числовой последовательности (см. задачу 3 урока 6). С массивом задача решается аналогично.

8. В массиве, заполненном произвольными целыми числами, найдите два числа, произведение которых максимально. Вложенные циклы не используйте.

Решение. Искомыми числами являются либо два максимальных элемента массива, либо два минимальных (это возможно при наличии как минимум двух отрицательных чисел). Поэтому сначала найдем эти 4 числа, а затем выясним, произведение какой пары чисел больше:

max1 := c[1];

max2 := c[1];

min1 := c[1];

min2 := c[1];

for i := 2 to n do

begin

if c[i] > max1 then

begin

max2 := max1;

max1 := c[i];

end

else

if c[i] > max2 then

max2 := c[i];

if c[i] < min1 then

begin

min2 := min1;

min1 := c[i];

end

else

if c[i] < min2 then

min2 := c[i]

end;

if min1*min2 > max1*max2 then

write(min1,' ',min2)

else

write(max2,' ',max1);

9. На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Распечатайте только те значения элементов массива, которые встречаются в нем ровно один раз. Элементы следует распечатывать в том порядке, в котором они встречаются в массиве.

Решение. При данных ограничениях никакая эффективность при решении задачи не требуется, проще всего каждый элемент проверить на уникальность. Но и здесь ученики часто делают ошибки. Например, чтобы проверить, не равен ли рассматриваемый элемент какому-то другому, они сравнивают его со всеми элементами массива, а следовательно, и с самим собой, что приводит к неверному результату. Приведем вариант правильного решения:

for i := 1 to n do

begin

cnt := 0;

for j := 1 to n do

if a[i] = a[j] then

cnt := cnt + 1;

if cnt = 1 then write(a[i],' ')

end;

10. На вход программе сначала подается значение n 100 — количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 30 000. Распечатайте только те значения элементов массива, которые встречаются в нем более одного раза, при этом каждое найденное значение должно быть распечатано только один раз. Элементы следует распечатывать в том порядке, в котором они встречаются в массиве.

Решение. Данная задача лишь немного сложнее предыдущей. Приведем очевидное решение, использующее булевские переменные:

for i := 1 to n do

begin

f1 := true;

for j := 1 to i - 1 do

if c[j] = c[i] then

f1 := false;

f2 := false;

for j := i + 1 to n do

if c[i] = c[j] then

f2 := true;

if f1 and f2 then

write(c[i],' ')

end;

1*. По введенному натуральному числу k, не превосходящему 100 000, выдать k-е по счету простое число. Используйте массив для запоминания уже найденных простых чисел.

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

var n, i, j, k, l: longint;

p: array[0..100000] of longint;

begin

for i := 0 to 100000 do

p[i] := 0;

read(n);

k := 0;

p[0] := 1;

i := 2;

repeat

j := 0;

l := 0;

while (l = 0) and (j < k) and

(p[j]*p[j] < i) do

begin

j := j + 1;

if i mod p[j] = 0 then l := 1;

end;

if l = 0 then

{нашли очередное простое число}

begin

k := k + 1;

p[k] := i;

end;

i := i + 1

until k = n;

writeln(p[k])

end.

2*. Определите, сколько раз число n! (факториал n) нацело делится на натуральное число k (1 < n, k < 231).

Решение. Задача носит олимпиадный характер и действительно не очень простая. Поскольку N! может быть очень велико (см. задачу 8 урока 7), непосредственное вычисление ответа невозможно. Разложим число K на простые множители. Тогда, если , то если N! делится на для каждого i, то N! делится на KZ, где . Единственная оставшаяся проблема — как для простого числа P найти максимальную его степень, на которую делится N!.

Для решения этой проблемы применим следующие соображения: количество чисел, кратных P и не превышающих N, равно . Каждое из этих чисел даст по одному простому множителю P в N!. Но, кроме того, чисел дадут еще по одному P, — еще по одному и т.д.

Значит,

Заметим, что суммирование можно остановить, когда очередное слагаемое равно 0.

3. Задан массив, содержащий несколько нулевых элементов. Требуется “сжать” его, переместив нулевые элементы в правую часть массива. Порядок ненулевых элементов между собой не менять. Дополнительный массив не использовать.

Примечание. В этой задаче требуется изменить массив, а не просто распечатать ненулевые элементы. Последнее сделать существенно проще.

Решение. Эта задача понятная, но технически ее нужно выполнять аккуратно. Приведем возможный вариант ее решения:

j := 0;{количество ненулевых элементов}

for i := 1 to m do

if а[i] <> 0 then

begin

j := j + 1;

if i <> j then

begin

а[j] := а[i];

а[i] := 0

end

end;

4. Дан массив натуральных чисел a1, a2, …, an, по модулю не превосходящих 100, и натуральные числа k и m. Укажите минимальное значение i такое, что ai + ai+1 +
+… + ai+k = m (т.е. сумма k + 1 подряд идущих элементов массива равна m 10 000, 0 < k < n 30 000). Если такого значения нет, то выведите 0. Вложенные циклы не использовать.

Решение. В данной задаче достаточно заметить, как меняется сумма соседних элементов массива при переходе к следующим k + 1 элементам:

for i := 1 to n do

read(c[i]);

sum := 0;

for i := 1 to k + 1 do

sum := sum + c [i];

if sum = m then

write(1) else

begin

for i := 2 to n - k do

begin

sum := sum - c[i - 1] + c[i + k];

if sum = m then

begin

write(i);

halt

end

end;

write(0);

end;

5. В одномерном массиве, заполненном произвольными целыми числами, за один проход найдите непрерывный кусок, сумма чисел в котором максимальна.

Фактически требуется найти такие i и j (i j), что сумма всех элементов массива от ai до aj включительно будет максимальна.

Указание. Эта задача подробно разбирается в брошюре Я.Зайдельмана “Эффективность алгоритмов. Простые задачи и наглядные примеры”, изд-во “Чистые пруды”.

6. Заданы два неупорядоченных массива целых чисел, по модулю не превосходящих 10 000. Будем рассматривать их как множества с повторяющимися элементами. Не используя дополнительной памяти, требуется распечатать пересечение двух множеств. Так, массивы {2, 1, 2, 3} и {2, 4, 2, 2} имеют пересечение {2, 2}. По окончании работы программы сами массивы должны быть такими же, какими они были после заполнения.

Решение. Возможно, например, такое решение данной задачи. Будем последовательно просматривать элементы первого массива и считать, сколько элементов, равных рассматриваемому, расположены в первом массиве до него. Затем подсчитаем, сколько элементов с таким же значением во втором массиве. Если их не меньше, то рассматриваемый элемент можно распечатывать. Приведем следующую реализацию этого алгоритма:

for i := 1 to n do

begin

kol := 1;

for j := 1 to i - 1 do

if a[j] = a[i] then

kol := kol + 1;

for j := 1 to m do

if b[j] = a[i] then

kol := kol - 1;

if kol <= 0 then

write(a[i], ' ')

end;

Другой способ решения задачи основан на том, что элементы массива не превосходят 10 000. Поэтому мы можем помечать использованные элементы, прибавляя к ним число 20 001. После решения задачи это число надо снова вычесть из значений тех переменных, которые превосходят 10 000.

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

Решение. Красивое решение этой задачи предложено в книге А.Шеня “Программирование: теоремы и задачи”, изд-во МЦНМО. Там эта задача формулируется в следующем виде: требуется поменять местами первые n – k элементов с последними k элементами. Решается она так: если мы перевернем весь массив, затем перевернем первые k элементов и, наконец, последние n – k элементов, то получим искомый сдвинутый массив:

readln(n, k);

for i := 1 to n do

read(a[i]);

for i := 1 to n div 2 do

begin

j := a[i];

a[i] := a[n – i + 1];

a[n – i + 1] := j

end;

for i := 1 to k div 2 do

begin

j := a[i];

a[i] := a[k – i + 1];

a[k – i + 1] := j

end;

for i := 1 to (n - k) div 2 do

begin

j := a[k + i];

a[k + i] := a[n – i + 1];

a[n – i + 1] := j

end;

for i := 1 to n do

write(a[i],' ');

8. Числовая последовательность называется пилообразной, если каждый ее элемент (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.

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

Решение. Эта задача решается за один или два прохода массива. Очевидно, что если рядом стоят несколько одинаковых элементов, то оставить нужно только один из них. Аналогично, если мы имеем строго возрастающую (убывающую) подпоследовательность из подряд идущих элементов нашей последовательности, то все элементы, кроме минимального и максимального, нужно удалять (на этом участке мы лишний “зубец пилы” сделать не сможем). Например, последовательность 1 2 3 4 3 1 5 преобразуется в 1 4 1 5. Тогда решение может выглядеть так: сначала удалим одинаковые элементы, первый и последний элементы оставим, а среди элементов со 2-го по (n – 1)-й оставим только те элементы, которые либо строго больше своих соседей, либо строго меньше них.

Комментарии и решения задач урока 10

2. Разделим квадратную матрицу диагональю, обычно называемой “побочной”:

Распечатайте в виде треугольной таблицы элементы матрицы, стоящие на местах, обозначенных цифрами 3 и 4.

Решение. Как и в случае главной диагонали, сначала нужно выписать уравнение “побочной” диагонали: j = n – i + 1, — а потом распечатать требуемые элементы:

for i := 1 to n do

begin

for j := 1 to n – i + 1 do

begin

write(a[i,j]:2,' ')

end;

writeln

end;

3. В кинотеатре n рядов по m мест в каждом. В соответствующем двумерном массиве хранится информация о проданных билетах на определенный сеанс (единицы означают, что на данные места билеты уже проданы, нули — что данные места еще свободны). Поступил запрос на продажу k билетов на соседние места в одном ряду. Определить, можно ли удовлетворить такой запрос.

В первой строке входных данных находятся числа n, m, k 100. В следующих n строках входных данных расположены по m чисел (0 и 1), разделенных пробелами. Выведите YES или NO в зависимости от ответа на вопрос задачи.

Решение. Задача скорее техническая, нежели алгоритмическая, поэтому просто приведем ее решение:

readln(n, m, k);

for i := 1 to n do

for j := 1 to m do

read (a[i,j]);

f := false;

for i := 1 to n do

for j := 1 to m – k + 1 do

begin

f1 := true;

for z := j to j + k - 1 do

if a[i,z] = 1 then

f1 := false;

if f1 then f := true;

end;

if f then writeln('YES')

else writeln('NO');

4. Треугольник Паскаля строится следующим образом. Первая строка состоит из одной единицы. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним, и числа, стоящего в предыдущей строке слева от него. По введенному n 30 выведите n первых строк треугольника Паскаля.

Решение. Задача предназначена для отработки умения индексировать соседние элементы матрицы. Но она важна и сама по себе. Полученные числа i-й строки соответствуют числу сочетаний из i элементов по j элементов (где j — номер соответствующего столбца). Несмотря на наличие формулы для нахождения этих чисел, в программировании их достаточно часто находят именно так, как описано в данной задаче. Объясняется это тем, что растут такие числа быстро и для их вычисления приходится применять так называемую “длинную арифметику”, а в приведенном алгоритме придется программировать только одно действие — сложение, а для вычисления по формуле — умножение и деление. Приведем решение данной задачи с использованием двумерного массива (хотя можно было бы ограничиться и двумя одномерными):

for i := 2 to n do

for j := 1 to i do

a[i,j] := 0;

a[1,1] := 1;

for i := 2 to n do

for j := 1 to i do

a[i,j] := a[i - 1,j] + a[i - 1,j - 1];

for i := 1 to n do

begin

for j := 1 to i do

write (a[i,j],' ');

writeln

end;

6. По введенным значениям n, m (1 n 20, 1 m 20) заполните массив размерностью n x m числами от 1 до mn, расположив их горизонтальной “змейкой” так, как показано в примере.

Решение. В задаче возможно “математическое” и “техническое” решения. В первом случае для элементов каждой строки будем вычислять, какие числа следует ставить на каждое из мест. Во втором случае можно обходить двумерный массив “змейкой” и расставлять последовательные числа. Приведем первое решение:

readln(n, m);

for i := 1 to n do

begin

if i mod 2 = 1 then

for j := 1 to m do

a[i,j] := (i - 1)*m + j

else

for j := 1 to m do

a[i,j] := (i - 1)*m + m – j + 1;

end;

for i := 1 to n do

begin

for j := 1 to m do

write (a[i,j]:3,' ');

writeln

end;

7. По введенным значениям n, m (1 n 20, 1 m 20) заполните массив размерностью n x m числами от 1 до mn, расположив их по спирали, закрученной по часовой стрелке, так, как показано в примере.

Решение. А для этой задачи приведем техническое решение, использующее “барьерные” элементы, расположенные вокруг основного массива. Идея решения в следующем: будем заполнять матрицу, двигаясь в одном направлении, пока стоящие на пути элементы равны нулю. После этого направление меняется:

readln(m,n);

for i := 0 to m + 1 do

for j := 0 to n + 1 do

a[i,j] := -1;

{сначала весь массив заполним -1,а потом обнулим собственно элементы,таким образом получим барьер из -1}

for i := 1 to m do

for j := 1 to n do

a[i,j] := 0;

k := 0;

i := 1;

j := 0;

repeat

while a[i,j + 1] = 0 do

begin

j := j + 1;

k := k + 1;

a[i,j] := k

end;

while a[i + 1,j] = 0 do

begin

i := i + 1;

k := k + 1;

a[i,j] := k

end;

while a[i,j - 1] = 0 do

begin

j := j - 1;

k := k + 1;

a[i,j] := k

end;

while a[i - 1,j] = 0 do

begin

i := i - 1;

k := k + 1;

a[i,j] := k

end;

until k = n * m;

for i := 1 to m do

begin

for j := 1 to n do

write(a[i,j]:3,' ');

writeln

end;

8. Дан квадратный массив. Требуется повернуть его на 90° по часовой стрелке (результат можно записать в другой массив).

Решение. При возможности использовать дополнительный массив задача становится несложной:

for i := 1 to n do

for j := 1 to n do

b[j,n – i + 1] := a[i,j];

9. В двумерном массиве размерностью n x m, все элементы которого различны, найти такие элементы, которые одновременно являются минимальными в своей строке и максимальными в своем столбце. Если искомых элементов нет, то выведите 0.

Решение. Методом “от противного” несложно показать, что в матрице, в которой нет одинаковых элементов, если искомый элемент существует, то он единственный.

var a: array[1..100,1..100] of integer;

maxa: array[1..100] of integer;

{массив для запоминания индексов строк максимумов в каждом столбце}

i,j,min,max,n,m: integer;

begin

b := false;

for i := 1 to m do

for j := 1 to n do

read(a[i,j]);

for i := 1 to n do

maxa[i] := 0;

for i := 1 to m do

begin

min := 1;

for j := 2 to n do

{ищем столбец, в котором находится минимум}

if a[i,j] < a[i,min] then min := j;

if maxa[min] = 0 then

{максимум в этом столбце еще не искали}

begin

max := 1;

{для найденного столбца ищем строку, в которой находится максимум}

for j := 2 to m do

if a[j,min] > a[max,min] then

max := j;

maxa[min] := max;

end;

if maxa[min] = i then

begin

writeln(i,' ',min);

halt

end

end;

writeln(0)

end.

Комментарии и решения задач урока 11

1. В строке имеется несколько слов, разделенных одним или несколькими пробелами. Требуется убрать из текста лишние пробелы: два и более пробелов подряд, а также все пробелы в начале и в конце строки.

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

readln(s);

{пока в строке встречаются два пробела подряд, удаляем один из них}

while pos(' ',s) > 0 do

delete(s,pos(' ',s),1);

if s[1] = ' ' then delete(s,1,1);

if s[length(s)] = ' '

then delete(s,length(s),1);

2. Фраза называется палиндромом (перевертышем), если после удаления пробелов и замены всех букв на заглавные она читается одинаково как слева направо, так и справа налево. Требуется определить, является ли введенная фраза палиндромом.

Примечание. Для русских букв, записанных в кодировке Windows-1251, можно считать, что коды заглавных и строчных букв отличаются на 32.

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

s1 := '';

for i := 1 to length(s) do

if s[i] <> ' ' then

if s[i] in ['A'.. 'Z','А'..'Я'] then

s1 := s1 + chr(ord(s[i]) + 32) else

s1 := s1 + s[i];

f := true;

for i := 1 to length(s1) div 2 do

if s1[i] <> s1[length(s1) – i + 1] then

f := false;

if f then writeln('YES')

else writeln('NO');

3. Слово называется палиндромом, если оно читается одинаково как слева направо, так и справа налево. Требуется определить, какое минимальное количество букв надо добавить ко входному слову справа, чтобы оно стало палиндромом.

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

var s,s1,s2: string;

i,j,k: integer;

begin

readln(s);

j := length(s);

s1 := '';

for k := j downto 1 do

s1 := s1 + s[k];

{в s1 перевернутая строка s}

for i := 1 to j do

if s[i] = s[j] then

begin

s2 := copy(s,i,(j – i + 1) div 2);

if s2 = copy(s1,1,length(s2)) then

begin writeln(i - 1); halt end

end

end.

4. Строка состоит из двух слов. Поменяйте эти слова местами.

На вход программе подается строка, состоящая не более чем из 255 символов. Строка содержит ровно один пробел, разделяющий два слова. Выведите преобразованную строку, по-прежнему разделяя слова ровно одним пробелом.

Решение. В этой задаче вводится понятие “слова”, которое является очень важным при обработке текстов. Сама же задача является относительно простой:

readln (s);

s1 := '';

i := 1;

while s[i] <> ' ' do

begin

s1 := s1 + s[i];

inc(i)

end;

s2 := copy(s,i + 1,length(s) – i);

writeln(s2,' ',s1);

5. Дана строка, являющаяся параграфом в тексте. Текст необходимо отформатировать так, чтобы длина каждой строки не превосходила числа M, слова при этом не разрывать.

На вход программе сначала подается число 0 < M 255. В следующей строке находится исходный текст. Длина слов в нем не превышает M, слова разделены ровно одним пробелом. Выведите разбиение этого текста на строки длиной не более чем M символов (слово переносится на следующую строку только если в текущей строке его разместить уже невозможно). Новая строка не должна начинаться с пробела.

Решение. Заметим, что размер входных данных в задаче не ограничен (ограничение приведено только для одного слова), поэтому считывание всех символов сразу в одну строку может оказаться невозможным. Приведем решение задачи с использованием посимвольного считывания:

readln(m);

read(c);

n := 0;

s := c;

repeat

while not eoln and (c <> ' ') do

{выделение одного слова}

begin

read(c)

s := s + c;

end;

if c = ' ' then delete(s,length(s),1);

if n + length(s) <= m then

begin

write(s);

n := n + length(s)

end

else

begin

writeln;

if n > 0 then delete(s,1,1);

write(s);

n := length(s)

end;

if not eoln then

begin

read(c);

s := ' ' + c

end

until eoln;

6. Определить, сколько букв содержит самое длинное слово во введенной строке символов. На вход программе подается строка, состоящая не более чем из 255 символов. Слова разделяются одним или несколькими пробелами. Выведите искомое число.

Решение. Подобная подзадача встречается в задачах ЕГЭ по информатике (задачи С4). Задача решается проще, если в конце исходной строки приписать пробел (фактически добавить “барьерный” элемент). Тогда признаком окончания очередного слова всегда будет являться пробел.

readln(s);

s := s + ' ';

max := 0;

cur := 0;

f := false;

for i := 1 to length(s) do

begin

if s[i] <> ' ' then

cur := cur + 1;

else

begin

if cur > max then

max := cur;

cur := 0;

end

end;

writeln(max);

7. Дана строка, содержащая по крайней мере один не ведущий пробел, за которым следует отличный от пробела символ. За счет изменения групп пробелов внутри строк (количества пробелов между словами) добиться того, чтобы в начале и в конце каждой из строк пробелы отсутствовали. Количество пробелов в разных группах внутри одной строки должно различаться не более чем на единицу. Количество символов в строке должно остаться неизменным.

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

Решение. Чтобы количество пробелов (blanks) в n группах отличалось не более чем на единицу, их число должно быть равно (blanks div n) в (n - blanks mod n) группах и (blanks div n + 1) в (blanks mod n) группах, причем хотя бы в одной группе будет ровно (blanks div n) пробелов. Поэтому именно столько пробелов разместим в первой группе, а далее сведем задачу к задаче меньшей размерности: уменьшим на (blanks div n) количество пробелов для дальнейшего распределения и на единицу количество групп пробелов. Тогда на последнем шаге n будет равно 1 и все оставшиеся пробелы будут напечатаны. Легко показать, что при таком подходе мы получим необходимое разбиение. Приведем основную часть реализации изложенной идеи:

readln(s);

blanks := 0;

{количество пробелов, которые нужно расставить в текущей строке}

n := 0;

{количество групп пробелов в строке}

for i := 1 to length(s) do

if s[i] = ' ' then

begin

blanks := blanks + 1;

if (i < length(s)) and

(s[i + 1] <> ' ') then n := n + 1

end;

for i := 1 to length(s) do

if s[i] <> ' ' then

begin

if (i > 1) and (s[i - 1] = ' ') then

begin

for j := 1 to blanks div n do

write(' ');

blanks := blanks - blanks div n;

n := n - 1

end;

write(s[i])

end;

writeln;

8. Напишите модификацию функции pos, которая находит все вхождения искомой подстроки в данной строке. В первой строке вводится исходная строка, в следующей — подстрока. В качестве ответа выведите в порядке возрастания все такие числа i, что, начиная с i-го символа, начинается некоторое вхождение подстроки в исходную строку.

На вход программе сначала подается строка, состоящая не более чем из 255 символов, а затем искомая подстрока, длина которой не превышает длину первой строки. Выведите число 0, если искомая подстрока не найдена, или искомые номера символов, с которых начинается подстрока в строке.

Решение. Заметим, что удалять найденные вхождения из строки (или из ее копии) нельзя, так как тогда не все вхождения образца, например aaa, могут быть найдены. Кроме того, при удалении подстроки нумерация символов будет нарушена. Если не заботиться об эффективности решения, то можно просто первый символ очередного вхождения подстроки в строку заменять на несуществующий, например, нулевой. А затем искать подстроку заново. Приведем фрагмент соответствующего решения:

readln(s1);

readln(s2);

s := s1;

f := false;

repeat

i := pos(s2,s);

if i > 0 then

begin

writeln(i);

f := true;

s[i] := #0

end

elsenot f then writeln(0)

until i = 0;

9. Дана последовательность символов, имеющая следующий вид: P1*P2*P3…*Pn, где Pi — цифра. Вычислите значение выражения. На вход программе подается строка указанного вида, состоящая не более чем из 9 цифр, разделенных символами умножения ‘*’. Выведите результат перемножения этих цифр.

Решение. Если формат выходных данных строго соблюдается, то решение получается простым:

max := 1;

for i := 1 to length(s) do

begin

if s[i] in ['0'..'9'] then

max := max * (ord(s[i]) – ord('0'))

end;

writeln(max);

10. Даны два “длинных” целых неотрицательных числа. Требуется найти результат их сложения. В качестве типа данных для хранения чисел используйте строки.

Решение. Задача полезна как упражнение по реализации “длинной” арифметики. Для удобства входные строки можно первоначально перевернуть. Тогда в первых элементах строк будут храниться младшие разряды чисел, с которых и начинается процедура сложения. Кроме того, более короткую строку можно дополнить до более длинной нулями:

readln(s1);

readln(s2);

for i := 1 to length(s1) div 2 do

{перевернем первую строку}

begin

c := s1[i];

s1[i] := s1[length(s1) – i + 1];

s1[length(s1) – i + 1] := c

end;

for i := 1 to length(s2) div 2 do

{перевернем вторую строку}

begin

c := s2[i];

s2[i] := s2[length(s2) – i + 1];

s2[length(s2) – i + 1] := c

end;

k := 0; {перенос в следующий разряд}

if length(s1) > length(s2)

then

begin

l := length(s1);

for i := length(s2) + 1 to l do

s2 := s2 + '0'

end

else

begin

l := length(s2);

for i := length(s1) + 1 to l do

s1 := s1 + '0'

end;

s := '';

for i := 1 to l do

begin

b := ord(s1[i]) + ord(s2[i])- 2*ord('0') + k;

k := b div 10;

s := s + chr(b mod 10 + ord('0'))

end;

if k > 0 then

s := s + chr(k + ord('0'));

for i := 1 to length(s) div 2 do

{перевернем результат}

begin

c := s[i];

s[i] := s[length(s) – i + 1];

s[length(s) – i + 1] := c

end;

2*. Дана последовательность символов, имеющая следующий вид: p1q1p2q2p3…qn–1pn, где pi — цифра, а qi — знак арифметического действия из набора {+, –, *}. Вычислите значение выражения, предполагая, что действия выполняются согласно правилам арифметики.

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

var

pq,p1,p2: string;

m,n,k,l,j: word;

begin

writeln('Введите арифметическое выражение');

readln(pq);

while Pos('*',pq) > 0 do

{цикл для выполнения всех действий умножения}

begin

p1 := '';

k := Pos('*',pq);

while (k > 1) and

(pq[k - 1] in ['0'..'9']) do

{формируем число, стоящее слева от знака '*'}

begin

k := k - 1;

p1 := pq[k] + p1

end;

p2 := '';

l := Pos('*',pq);

while (l < length(pq))

and (pq[l + 1] in ['0'..'9']) do

{формируем число, стоящее справа от знака '*'}

begin

l := l + 1;

p2 := p2 + pq[l]

end;

val(p1,n,j);

val(p2,m,j);

j := m*n;

str(j,p1);

delete(pq,k,l – k + 1);

{удаляем часть строки}

insert(p1,pq,k)

{вставляем результат умножения}

end;{все умножения выполнены}

{далее выполняем все сложения и вычитания подряд}

3*. Текст был зашифрован следующим образом. Сначала определяется количество букв в самом длинном слове, его длину обозначим К (словом называется непрерывная последовательность английских букв, слова друг от друга отделяются любыми другими символами, длина слова не превышает 20 символов). Затем каждая английская буква заменяется на букву, стоящую в алфавите на K букв ранее (алфавит считается циклическим, то есть перед буквой A стоит буква Z), оставив другие символы неизменными. Строчные буквы при этом остаются строчными, а заглавные — заглавными. Расшифруйте введенную шифровку.

Решение. Подобные задачи встречались в демоверсии ЕГЭ по информатике (задача С4). Приведем ее решение:

var f: boolean;

i, k, max: integer;

c,cnew: char;

s: string;

begin

s := '';

max := 0;

k := 0;

f := false;

repeat

read(c);

s := s + c;

if f then {слово началось}

if c in ['a'..'z','A'..'Z']

then k := k + 1

else

begin

if k > max then max := k;

f := false

end

else {f = false}

if c in ['a'..'z','A'..'Z']

then

begin

f := true;

k := 1

end

until c = '.';

for i := 1 to length(s) do

begin

cnew := chr(ord(s[i]) + max);

case s[i] of

'a'..'z':cnew > 'z' then

write(chr(ord(cnew)-26))

else write(cnew);

'A'..'Z':cnew > 'Z' then

write(chr(ord(cnew)-26))

else write(cnew);

else write(s[i])

end

end

end.

4*. У Васи на клавиатуре не работает клавиша пробел. Поэтому все тексты он теперь набирает слитно. Напишите программу, которая будет разделять набранный Васей текст на слова из данного словаря.

На вход программе сначала подается текст, введенный Васей, — строка из не более чем 100 латинских строчных букв. В следующей строке записано количество слов в словаре N — натуральное число, не превосходящее 2000. В следующих N строках записаны слова из словаря?— по одному слову в каждой строке, каждое слово длиной не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.

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

Комментарий. Данная задача предлагалась в 2007 году на Московской олимпиаде по информатике для 7–9-х классов в качестве наиболее сложной задачи олимпиады. Она решается методом динамического программирования. Пусть мы знаем, разбивается ли на слова из словаря начало нашей строки длины 1, 2, …, i. Тогда, чтобы узнать, разбивается ли на слова из словаря начало строки длины i + 1, возьмем префикс строки длины k, который на слова разбивается, и попробуем найти в словаре слово, которое составляется из символов с k + 1-го по i + 1-й нашей строки. Перебрав все префиксы, для которых ранее был получен положительный ответ, мы и получим ответ для префикса длины i + 1 (достаточно, чтобы слово, дополняющее один “хороший” префикс до другого, нашлось хотя бы один раз). Сложность такого алгоритма равна L2 ? (время поиска в словаре). Здесь L — длина исходной строки. Время поиска в словаре зависит от выбранного алгоритма. Так, бинарный поиск будет иметь сложность MlogN, где N — количество строк в словаре, а M — средняя длина слов словаря.

Комментарии и решения задач урока 12

1. Напишите функцию для нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида и используйте ее в программе для нахождения НОД уже N чисел.

Указание. Решение основывается на том факте, что НОД(a, b, c) = НОД(НОД(a, b), c). Как запрограммировать сам алгоритм Евклида, уже было рассказано в решении задачи 9 урока 5. В результате основная программа может выглядеть так:

begin

read(N);

read(a);

for i := 2 to N do

begin

read(b)

a := nod(a, b);

end

writeln(a)

end.

5. Напишите процедуру, которая по входному параметру n — нечетному числу, не превосходящему 21, будет печатать с помощью символов “*” равнобедренный треугольник следующего вида:

*

***

*****

Используя эту процедуру, нарисуйте на экране елочку. Для этого введите в процедуру дополнительный параметр: количество пробелов, на которое должен отстоять треугольник от левого края экрана.

Решение. Приведем решение данной задачи полностью:

procedure aaa(b,n: integer);

var i,j,k: integer;

begin

k := 1;

for i := 1 to n div 2 + 1 do

begin

for j := 1 to b do

write(' ');

for j := 1 to (n - k) div 2 do

write(' ');

for j := 1 to k do

write('*');

writeln;

k := k + 2

end

end;

begin

aaa(2,5);

aaa(1,7);

aaa(0,9)

end.

6. Напишите процедуры печати одномерного массива и его сортировки одним из алгоритмов. В программе задайте массив случайным образом, распечатайте его с использованием процедуры, затем отсортируйте и распечатайте массив еще раз.

Комментарий. С помощью данной задачи отрабатывается передача массивов в качестве параметра процедур или функций. Покажем это на примере процедуры печати массива:

type aa = array[1..100] of integer;

var a: aa;

procedure print(var m: aa; n: integer);

var i: integer;

begin

for i := 1 to n do

write(m[i],' ');

writeln

end;

7. Напишите процедуру swap обмена местами значений двух целочисленных переменных без использования вспомогательной переменной. Объясните, почему данная процедура работает некорректно при обращении к ней с одной и той же переменной, например, swap(a,a).

Ответ. Для того чтобы в процедуре поменять местами значения переменных, они должны передаваться по ссылке (указателю), с добавлением слова var:

procedure swap(var a,b: integer);

begin

a := a + b;

b := a – b;

a := a - b

end;

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

8. Напишите функцию, вычисляющую значение интеграла функции f(x) на интервале [a; b] (или площадь под графиком функции) одним из численных методов (например, методом трапеций, прямоугольников или методом “Монте-Карло”). Параметрами такой функции должны быть сама функция f (функцию тоже можно передавать как параметр), вещественные значения a и b, а также точность вычислений . Результатом является значение площади.

Решение. Покажем, как решить данную задачу методом трапеций. Разбиваем отрезок [a; b] на n частей, h = (b – a)/n (шаг интегрирования). По формуле вычисления площади трапеций получаем I0 = = h((f(a) + f(b))/2 + f(x1) + f(x2) + ... + f(xn–1)), где xi = a + ih, i = 1, ..., n – 1. Уменьшаем шаг в 2 раза: h1 = h/2,
n1 = 2n, тогда I1 = I0/2 + h1(f(x1) + f(x3) + ... + f(x2n–1)), то есть вычисления необходимо производить только для нечетных точек xi = a + (2i – 1)h1, i = 1, ..., n. Если |I1I0| <, то I1 можно считать решением, в противном случае шаг уменьшается еще в 2 раза, I2 вычисляется через I1, сравниваются I1 и I2 и т.д. В результате функция может выглядеть так:

type func = function(x: real): real;

function integ(f: func; a,b,eps: real): real;

var i,n: longint;

s0,sum,h: real;

begin

n := 1;

h := b - a;

sum := (f(a) + f(b))/2*h;

repeat

s0 := sum;

h := h/2;

sum := 0;

for i := 1 to n do

sum := sum + f(a + (2*i - 1)*h);

sum := s0/2 + sum*h;

n := n*2

until abs(sum - s0) < eps;

integ := sum

end;

9. Напишите функцию, решающую уравнение f(x) = 0 на интервале [a; b] в предположении, что на этом интервале функция непрерывна и уравнение содержит ровно один корень. Используйте один из численных методов (например, метод деления пополам или метод хорд). Параметрами такой функции должны быть сама функция f, вещественные значения a и b, а также точность вычисления корня . Результатом является искомый корень.

Решение. Приведем пример решения данной задачи методом хорд. Найдем такой интервал [a; b], что f(a)f(b) < 0 и корень на этом интервале единственный. Проводим прямую через точки (a; f(a)) и (b; f(b)). Находим точку пересечения прямой с осью Oх (назовем эту точку с). Если f(a)??f(c) > 0, то a := c, в противном случае b := c. Далее проводим новую прямую, соединяющую точки a и b. Условие окончания алгоритма (проверяется до очередного переприсваивания значений a или b): |a – с| < или |b –с| < . Соответствующая функция может выглядеть так:

function chord(f: func; a,b,eps: real): real;

{решение уравнения методом хорд}

var c,fa: real;

begin

repeat

fa := f(a);

c := a + fa*(b - a)/(fa - f(b));

if fa*f(c) > 0 then

begin

fa := c - a;

a := c

end

else

begin

fa := b - c;

b := c

end

until abs(fa) < eps;

chord := c

end;

Комментарии и решения задач урока 13

1. Числа Фибоначчи задаются следующими соотношениями:

f0 = f1 = 1; fn = fn–1 + fn–2, n > 1.

Напишите рекурсивную и нерекурсивную функции, вычисляющие n-е число Фибоначчи, и сравните скорость их работы. Попробуйте объяснить результаты сравнения.

Комментарий. Рекурсивная функция для нахождения чисел Фибоначчи пишется чрезвычайно просто — буквально следуя определению этих чисел:

function f(n: integer): longint;

begin

if n in [0,1] then f := 1

else f := f(n - 1) + f(n - 2)

end;

Нерекурсивная реализация была приведена в разборе задачи 8 урока 6. Рекурсивная версия будет работать намного дольше. Объясняется это тем, что одни и те же числа Фибоначчи в ней будут неоднократно перевычисляться. Так, чтобы найти f(6), приходится находить f(4) и f(5), в свою очередь, f(5) снова будет вычислять f(4). Количество рекурсивных вызовов при этом растет экспоненциально. Нерекурсивный же вариант использует линейный алгоритм.

2. Напишите рекурсивную подпрограмму, осуществляющую поиск числа K в упорядоченном по неубыванию числовом массиве, используйте метод деления пополам.

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

var a: array[1..1000] of integer;

function BinarySearch(l,r,k: integer):

integer;

var m: integer;

begin

if l < r then

begin

m := (r + l) div 2;

if a[m] < k

then BinarySearch(m + 1,r)

else BinarySearch(l,m);

end

else

if a[r] = k then := r

else BinarySearch := 0

end;

begin

{заполнение массива}

writeln(BinarySearch(1,n,k)

end.

3. Реализуйте следующий рекурсивный алгоритм сортировки: если массив содержит не более одного элемента, то он упорядочен. Иначе, преобразовываем его следующим образом: вначале идут элементы, меньшие первого, затем первый элемент, затем элементы, большие первого. Далее алгоритм применяется к первой и второй группам еще не упорядоченных элементов.

Комментарий. Здесь фактически описан один из вариантов так называемой “быстрой сортировки”. Наиболее эффективную ее реализацию можно найти в примерах к Borland Pascal: bp\examples\dos\qsort.pas.

4. Опишите рекурсивную функцию, которая определяет, является ли симметричной часть строки S, начиная с i-го элемента и заканчивая j-м. Решите с помощью этой функции задачу 3 к уроку 11.

Решение. Возможная реализация такой функции:

function check(var s: string; i,j:

integer): boolean;

begin

if i > j then check := true

else

if s[i] <> s[j] then check := false

else check := check(s,i + 1,j - 1)

end;

5. Напишите рекурсивную функцию для перевода десятичного числа в P-ичную систему счисления, не использующую в своей работе массив.

Решение. Приведем пример процедуры, которая будет печатать результат перевода:

procedure c(n,p: integer);

var a: integer;

begin

a := n div p;

if a > 0 then c(a,p);

write(n mod p)

end;

6. Запишите рекурсивную функцию, вычисляющую сумму целых m и n, в которой из арифметических операций используется только прибавление и вычитание единицы.

Решение. Данная задача полезна для понимания рекурсии начинающими. Приведем решение данной задачи для натуральных чисел, но и для произвольных целых чисел она имеет решение:

function sum(a,b: integer): integer;

begin

if a = 0 then sum := b

else sum := sum(a – 1,b + 1)

end;

7. Запрограммируйте процедуру, которая будет печатать все сочетания из n первых натуральных чисел по k чисел.

Решение. Задача относится к базовым олимпиадным алгоритмам. Она может быть решена, например, так:

var i, k, n: integer;

a, p: array[0..60] of integer;

procedure print(k: integer);

var j: integer;

begin

for j := 1 to k do

write(a[p[j]]:4);

writeln

end; {print}

procedure cnk(n, k: integer);

procedure gen(i: integer);

{заполняет i-е место сочетания}

var j: integer;

begin

if i > k then print(k)

{все элементы выбраны}

else

for j := p[i - 1] + 1 to n — (k – i) do

begin

p[i] := j;

gen(i + 1)

end

end; {gen}

begin {cnk}

gen(1)

end; {cnk}

begin {main}

readln(n, k);

for i := 1 to n do a[i] := i;

{заполнить массив можно и по-другому}

cnk(n, k)

end.

8. В первой строке входных данных записано n — число строчек и m — число столбцов в двумерном массиве. В последующих n строчках записано m чисел, каждое из которых равно либо 0, либо 1. Числа разделены пробелами. Требуется вывести количество объектов, состоящих из единичек. Если две единички являются соседями по вертикали или горизонтали, то они принадлежат одному и тому же объекту.

Решение. Задача решается методом рекурсивной “заливки” каждого из объектов:

procedure mark(i,j,l: integer);

begin

if a[i,j] = 1 then

begin

a[i,j] := l;

mark(i + 1,j,l);

mark(i - 1,j,l);

mark(i,j + 1,l);

mark(i,j - 1,l);

end

end;

begin

read(n,m);

for i := 0 to n + 1 do

for j := 0 to m + 1 do

a[i,j] := 0;

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

l := 1;

for i := 1 to n do

for j := 1 to n do

if a[i,j] = 1 then

begin

l := l + 1;

mark(i,j,l)

end;

writeln(l - 1)

end.

В качестве результата выдается число l – 1, так как первый объект “красится” числом 2, второй — 3 и т.д. Кроме того, вокруг массива формируется барьер из нулей, которые позволяют не проверять выход рекурсии за границу массива.

9. Дана шахматная доска n?n. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.

Решение. Приведем процедуру, которая заполнит двумерный массив соответствующим образом:

const dx: array[1..8] of integer = (1,1,-1,-1,2,2,-2,-2);

dy: array[1..8] of integer = (2,-2,2,-2,1,-1,1,-1);

var a: array[-1..10,-1..10] of integer;

x,y,n: integer;

procedure rec(i,x,y: integer);

var j,x1,y1: integer;

begin

a[x,y] := i;

if i = n*n then print

else

for j := 1 to 8 do

begin

x1 := x + dx[j];

y1 := y + dy[j];

if a[x1,y1] = 0 then

rec(i + 1,x1,y1)

end;

a[x,y] := 0

end;

begin

read(n);

for x := -1 to 10 do

for y := -1 to 10 do

a[x,y] := -1;

for x := 1 to n do

for y := 1 to n do

a[x,y] := 0;

rec(1,1,1)

end.

Комментарии и решения задач урока 14

2. Сведения об ученике, записанные в файле f.txt, состоят из его фамилии и названия класса (год обучения и буква), а также оценок, полученных за четверть. Число оценок в разных классах может быть разным. Запишите в файл g.txt фамилии тех учеников, которые не имеют двоек и троек, а их средний балл больше, чем 4,5.

Решение. Подобные задачи встречаются на ЕГЭ по информатике (задача С4). Приведем ее решение:

var p: record

name: string;

sum: integer;

end;

c: char;

n, m: integer;

b: boolean;

f, g: text;

begin

assign(f, 'f.txt');

reset(f);

assign(g, 'g.txt');

rewrite(g);

repeat

p.name := '';

repeat

read(f,c);

p.name := p.name + c

until c = ' '; {считана фамилия}

repeat

read(f,c);

until c = ' '; {считан класс}

p.sum := 0;

n := 0;

b := true;

while not seekeoln(f) do

begin

read(f,m);

if m in [2,3] then b := false

else p.sum := p.sum + 1;

n := n + 1

end;

readln(f);

if b and p.sum >= 4.5*n then

writeln(g,p.name)

until seekeof(f);

close(g)

end.

Обратите внимание, что массив для хранения искомых фамилий, а также оценок одного человека не используется. При вычислении среднего арифметического деление заменено умножением.

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

Требуется написать программу, которая будет выводить в файл avr.dat информацию о месяцах, у которых среднемесячная температура наименее отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке в виде:

<номер месяца> <среднемесячная температура> <отклонение от среднегодовой>.

Средние значения выводить с точностью до одного знака после десятичной точки. Массив для хранения всех введенных значений не использовать.

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

const d: array[1..12] of integer =

(31,29,31,30,31,30,31,31,30,31,30,31);

var m: array[1..12] of real;

t:real;

i,j: integer;

c1,c2: char;

f,g: text;

begin

assign(f, 'meteo.dat');

reset(f);

assign(g, 'avr.dat');

rewrite(g);

for j := 1 to 12 do

m[j] := 0;

for i := 1 to 366 do

begin

readln(f,c1,c1,c1,c1,c2,t);

j := (ord(c1) - ord('0'))*10 +

ord(c2) - ord('0');

m[j] := m[j] + t

end;

for j := 1 to 12 do

writeln(m[j]/d[j]:0:1)

close(g)

end.

8. Даны 2 текстовых файла: f1.txt и f2.txt. В каждом из файлов находится неотрицательное количество целых чисел, отсортированных по неубыванию. Каждое из чисел по модулю не превосходит 106. Числа разделены между собой пробелами и/или символами перевода строки. Получите новый файл output.txt слиянием двух исходных в отсортированном виде.

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

var f1,f2,f3: text;

a,b: integer;

begin

assign(f1,'f1.txt');

assign(f2,'f2.txt');

assign(f3,'output.txt');

rewrite(f3);

reset(f1);

reset(f2);

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

read(f1,a);

read(f2,b);

if a < b then write(f3,a)

else write(f3,b);

while (a < b) and not eof(f1) or

(b <= a) and not eof(f2) do

begin

if a < b then read(f1,a)

else read(f2,b);

if a < b then write(f3,a)

else write(f3,b)

end;

{один из файлов исчерпан}

while not eof(f2) do

begin

write(f3,b);

read(f2,b)

end;

while not eof(f1) do

begin

write(f3,a);

read(f1,a)

end;

if a > b then write(f3,a)

else write(f3,b);

close(f3)

end.

9. Ученики, недавно изучающие программирование, употребляют слишком много операторов goto, что является почти недопустимым для структурированной программы. Помогите преподавателю информатики написать программу, которая будет оценивать степень структурированности отлаженной программы школьника на языке Pascal, для начала просто подсчитывая количество операторов goto в ней.

В синтаксически верной программе ключевое слово оператора перехода goto может стоять или в начале строки, или после пробела, или после одного из символов — ‘;’ , ‘:’, ‘}’, а после него может стоять или пробел, или перевод строки, или символ ‘{’.

Напомним, что, кроме обозначения действительно оператора перехода, слово goto может встречаться в тексте программы в строковых константах, заключенных в апострофы, или в комментариях, причем для простоты будем считать, что комментарий всегда начинается с символа ‘{’, а заканчивается первым встретившимся после этого символом ‘}’. Будем считать, что это единственный вид комментариев. В этих случаях слово goto подсчитывать не нужно. Строчные и прописные буквы в Pascal не различимы.

Во входном файле goto.in находится текст программы на языке Pascal без синтаксических ошибок. Размер программы не превосходит 64 Кб. В выходном файле goto.out должно оказаться одно число — количество операторов goto в этой программе.

Решение. Подобные задачи проще всего решать с помощью математического аппарата, называемого “конечным автоматом”. В процессе считывания текста автомат находится в различных состояниях, таких, как “внутри комментария”, “внутри строки” и “программа”. В каждом состоянии одни и те же входные символы обрабатываются по-разному. Например, если мы находимся внутри комментария, то автомат просто ждет, когда появится символ, завершающий комментарий. Приведем подобное решение данной задачи:

const sr:set of char = [' ',';',':','}'];

var cgoto: word;

s,s1: string;

i,j: integer;

state: (com,str,prog);

f,g: text;

begin

assign(f,'goto.in');

reset(f);

cgoto := 0;

state := prog;

while not eof(f) do

begin

readln(f,s);

for i := 1 to length(s) do

case state of

com:s[i] = '}' then state := prog;

str:s[i] = '''' then state := prog;

prog:

if s[i] = '''' then state := str else

if s[i] = '{' then state := com else

if (s[i] in ['g','G']) and

((i = 1) or (s[i - 1] in sr)) then

begin

s1 := copy(s,i,5);

for j := 1 to length(s1) do

s1[j] := upcase(s1[j]);

if (s1 = 'GOTO') or (s1 = 'GOTO')

or (s1 = 'GOTO{') then inc(cgoto)

end

end {case}

end; {while}

assign(g,'goto.out');

rewrite(g);

writeln(g,cgoto);

close(g)

end.

Электронный задачник

Методические аспекты использования Электронного задачника

1. Методика использования предлагаемого Электронного задачника (ЭЗ) достаточно проста и для учащихся, и для учителей. Использование ЭЗ позволяет изменить форму организации учебного процесса и методику обучения теме “Алгоритмизация и программирование”. Основной характеристикой изменения методики обучения является возможность перехода к личностно ориентированному и дифференцированному обучению при одновременной экономии сил и времени учителя.

2. Использование ЭЗ позволяет внести изменения и в содержание учебного процесса. Неотъемлемой частью ЭЗ является методически продуманная БД задач концентрической структуры, позволяющих обучать школьников современным технологиям программирования и отладки. Целесообразность использования предлагаемой БД задач основана на успешном опыте обучению программированию авторами в течение более 10 последних лет. С одной стороны, многие задачи, включаемые в БД, имеют концентрическую структуру, что позволяет обучать школьников с разным уровнем знаний и умений практически на одинаковых задачах, а с другой стороны, все эти задачи выстроены по определенной методике, суть которой состоит в последовательном достижении основных дидактических целей при изучении каждой конкретной темы.

3. Использование ЭЗ позволяет перейти к более прогрессивным формам оценки и мониторинга учащихся, в частности, позволяет перейти к рейтинговой системе оценки. При этом со стороны учителя для этого не надо затрачивать дополнительных усилий, идея рейтинговой оценки заложена в ЭЗ изначально. Кроме того, заложенная система контроля и мониторинга за учебной деятельностью учащихся позволяет учителю иметь перед глазами в режиме реального времени картину работы каждого ученика: какие задачи он решал, какие решил полностью, а какие — частично, за сколько “подходов” ученику удалось сдать задачу ЭЗ и т.д.

4. С внедрением компьютера в процесс обучения впервые появилась возможность, в несколько раз повысив учебную активность учащихся, обеспечить цикличность функционирования традиционного контура обратной связи “преподаватель – ученик” в реальном масштабе времени. В результате намного проще стало реализовывать ведущие принципы развивающего обучения: индивидуализацию и дифференциацию. Кроме того, компьютер, позволяя ошибаться, разрешая ошибаться, создавая возможность ошибаться, дает возможность познавать через противоречия. А, как показано Ж.Пиаже, ошибочные теории учеников являются существенной частью процесса овладения мышлением. Поэтому использование ЭЗ в учебном процессе повысит интенсивность, эффективность, а главное — качество обучения.

5. Использование ЭЗ, работа которого построена на основе “клиент–сервер” или web-сервера, познакомит учащихся с современными ИКТ, позволит наиболее оптимальным образом использовать школьную компьютерную технику (локальную сеть, Интернет).

Описание содержания Электронного задачника

Электронный задачник построен на технологии “клиент–сервер”. Задачник-сервер находится на преподавательском компьютере, на каждой рабочей станции есть клиентская часть, с которой, собственно, и работает ученик.

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

Для преподавателя в ЭЗ реализованы следующие функции:

- создание групп пользователей и отдельных пользователей (учеников);

- назначение задачи конкретному ученику или группе (классу) учащихся;

- просмотр статистики выполнения назначенных заданий каждым учащимся;

- просмотр рейтинга по группе (классу);

- добавление/удаление задачи для конкретного пользователя.

Для ученика клиентская часть ЭЗ предоставляет следующие возможности:

- просмотр списка задач, назначенных конкретному пользователю;

- выбор задачи и поиск соответствующего файла с текстом программы, который будет отправляться ЭЗ для проверки;

- получение краткого или полного отчета о прохождении задачи на системе проверочных тестов, в зависимости от настройки сервера учителем.

Минимальные технические требования — компьютерный класс, компьютеры в котором объединены в локальную сеть (сервер должен быть доступен по протоколу TCP/IP). В случае, если в сети установлен firewall, для взаимодействия сервера и клиентов на компьютере с сервером должен быть открыт порт 60 000. Для проверки решений задач по программированию, выполненных на языках C и С++, часто требуется, чтобы пользователь, во время сеанса которого запущена программа-сервер, должен иметь права администратора. Компьютер, на котором работает программа-сервер, должен быть доступен (должен “пинговаться”) компьютерам с программами-клиентами по IP адресу или имени компьютера в локальной сети.

Необходимо наличие на сервере по крайней мере одного компилятора для языка высокого уровня (например, Паскаль, С++), способного создавать WIN32-приложения (компиляторы Borland Pascal и Quick Basic для этих целей не подходят). Для программирующих на Паскале оптимально, если на компьютере установлен компилятор с языка Delphi. В документации по работе с системой описывается, как изменить или расширить набор компиляторов, например, добавив Visual Basic (самое сложное — научить учеников создавать консольные приложения на Visual Basic :).

Для того чтобы программа была успешно проверена задачным сервером, необходимо, чтобы она удовлетворяла следующим требованиям.

1. Программа должна компилироваться одним из поддерживаемых сервером компиляторов, работающих на платформе WIN32.

2. Программа должна для любого допустимого набора входных данных заканчиваться кодом возврата 0. Для этого, например, в языках C и C++ необходимо использовать инструкцию return 0; в функции main().

3. Если в задаче предполагается ввод данных с клавиатуры, то программа не должна использовать модуль crt в языке Pascal и библиотеку conio в С и С++.

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

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

1. Инсталлируйте программное обеспечение на компьютере, на котором предполагается работа задачного сервера. Если на данном компьютере уже установлены системы программирования Delphi или Visual C (в том числе и для версии .net), то при инсталляции от установки соответствующих компиляторов стоит отказаться.

2. Ознакомьтесь с руководством по настройке и использованию системы (см. ниже) и требованиями к программам-решениям.

3. Скопируйте файл client.exe на другой компьютер той же локальной сети для проверки работоспособности системы в сети.

4. Запустите программу server.exe.

5. Создайте новую группу пользователей и какого-нибудь пользователя в этой группе.

6. Назначьте данной группе пользователей одну или несколько задач.

7. Запустите программу client.exe.

8. Выберите одну из задач и попробуйте сдать на проверку ее решение, которое можно найти в папке соответствующей задачи. Если возникли сложности с проверкой решения на языке Pascal (по умолчанию это делается с помощью компилятора Free Pascal 2.0), то можно файл с решением переименовать средствами операционной системы в solution.dpr и снова попробовать его проверить, но уже с использованием компилятора Delphi.

9. Внесите в решение какие-нибудь ошибки и проверьте, как изменятся результаты проверки.

10. Попробуйте написать свое решение одной из задач, назначить эту задачу и послать ее на проверку.

Подготовленные задачи находятся в каталоге tasks, но это не является требованием к размещению задач. Набор задач также является открытым для добавления или изменения. Каждая задача представляет собой набор файлов, размещенных в одной папке. Обязательными в этом наборе являются следующие файлы:

- config — текстовый конфигурационный файл с описанием способа проверки задачи.

- Файлы с тестами к задаче.

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

- Description.* — файл с описанием условия задачи, он пересылается сервером программе-клиенту по запросу.

- Solution.* — файл с эталонным решением задачи на одном из языков программирования (Pascal, Delphi или С++), позволяет корректировать время работы решения задачи на разных компьютерах (в некоторых задачах на настоящее время данный файл отсутствует).

Подробнее с правилами подготовки и форматом текстовых конфигурационных файлов можно ознакомиться в документации.

Администрирование Электронного задачника (сервера)

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

Преподаватель в программе-сервере может выполнить следующие действия:

- просмотреть список группы (класса);

- создать новую группу или изменить имя существующей группы;

- удалить группу;

- наполнить группу фамилиями;

- назначить группе задачу или несколько задач;

- настроить режим работы сервера;

- посмотреть сведения о выполнении задания школьниками.

1) Просмотреть список группы (класса).

Выберите элемент меню Contest/Participants.

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

2) Создать новую группу пользователей или изменить уже существующее имя группы.

Именно группе назначаются задачи. Группой является, как правило, весь класс или подгруппа класса, поэтому в качестве имен групп можно, например, брать названия классов (например, 10g — имя для группы пользователей — учеников 10-го “Г” класса).

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

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

Способ 2. Всей группе (классу) назначить все задачи, но на уроке сказать, кто что делает.

Рассмотрим создание/модификацию групп пользователей.

Выберите элемент меню Contest -> Groups.

41-0.gif (9653 bytes)

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

Для создания новой группы нажмите New. Если вы введете уже существующее имя группы, то, к сожалению, сообщения об этом выдано не будет. Имена групп можно набирать как латинскими буквами, так и кириллицей.

3) Удаление группы.

Выберите элемент меню Contest -> Groups.

Любая из отображаемых групп может быть удалена или восстановлена (кнопки Remove и Show Remove соответственно).

4) Создание учетных записей пользователей (наполнение группы фамилиями).

Выберите элемент меню Contest/Participants.

41-1.gif (9910 bytes)

В появившемся диалоговом окне в списке Member Of выберите группу пользователей, которую вы хотите модифицировать. Изменить параметры любого пользователя можно в соответствующих полях ввода (name и password).

Для создания нового пользователя нажмите New. Эта кнопка создает пользователя с именем new_user и пустым паролем. После этого вы должны отредактировать имя и пароль, чтобы установить нужные параметры для пользователя, которого хотели создать.

5) Назначение задач.

Выберите элемент меню Contest/Problems.

В данном диалоге вы можете назначать группам пользователей задачи. Для этой цели используются кнопки Add и Add Directory.

При нажатии Add появится диалоговое окно выбора каталога задачи, которую следует добавить.

41-2.gif (10436 bytes)

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

42-0.gif (10204 bytes)

Add Directory следует использовать для добавления нескольких задач, расположенных в одном каталоге (к примеру, все задачи одного урока). Здесь следует выбрать каталог, в котором расположены все каталоги добавляемых задач. Каталог также должен быть не просто выделен, а открыт.

42-1.gif (11153 bytes)

6) Настройка параметров олимпиады.

Данный раздел необходимо изучить лишь в случае, когда задачник предлагается использовать для проверки в режиме on-line задач личных или командных олимпиад по информатике и программированию.

Выберите элемент меню Contest/Options.

42-2.gif (10811 bytes)

На данной вкладке устанавливается время начала и окончания олимпиады. Члены группы Contest Participants могут посылать свои решения только в указанный здесь промежуток времени.

42-3.gif (11190 bytes)

По умолчанию решения членов группы Contest Participants проверяются до первого неудачного теста. При включении опции Personal решение сначала проверяется на “предварительных тестах” (чаще всего они совпадают с примерами, приведенными в условии задачи). Если решение не прошло эти тесты, то оно не сохраняется на сервере, и никакая дальнейшая проверка не производится. Если же решение прошло предварительные тесты, то оно проверяется на всех основных тестах, вне зависимости от того, успешно ли оно прошло предыдущие.

Также эта опция влияет на формирование таблицы рейтинга для членов группы Contest Participants. В режиме team contest рейтинг участника определяется на основании количества полностью решенных задач и на основании времени, затраченного участником на решение задач (включая штрафные 20 минут за каждое неверное решение). В режиме personal contest рейтинг участника определяется только количеством заработанных баллов.

Опция Defer Verification позволяет отложить проверку решений, присылаемых во время олимпиады. А именно, решение проверяется только на предварительных тестах. При прохождении предварительных тестов решение сохраняется на сервере, и больше никаких действий не предпринимается. Проверка решений на всех тестах затем осуществляется выбором элемента меню Contest/Check Solutions. Данная опция полезна в том случае, когда полная проверка решения занимает много времени и вы хотите ее отложить до окончания тура олимпиады.

Опция Don’t Count Time в случае team contest изменяет критерий составления рейтинга участников: рейтинг составляется только на основе количества полностью решенных задач, без учета затраченного времени.

Опция Use Last Result влияет на то, результат какой из попыток участника учитывается при составлении рейтинга: результат последней попытки или лучший результат, показанный решением участника.

Опция Keep All Solutions изменяет правила сохранения решений на сервере в случае personal contest. По умолчанию сохраняются только решения, прошедшие предварительные тесты. При установке данной опции будут сохраняться все программы, посланные участником.

Опция Report Type позволяет выбирать уровень детализации отчета, посылаемого участникам. В случае team contest значения данной опции имеют следующий смысл:

1) minimal — отсылать только количество баллов, набранное программой;

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

3) detailed — отсылать полную информацию о проверке. Включается показ содержимого теста, вывода программы и правильного ответа.

В случае personal contest пункты 2) и 3) имеют тот же смысл, а minimal означает, что участнику только сообщается, прошло его решение предварительные тесты или нет.

Опция Send Rankings указывает, отсылать ли участникам таблицу рейтинга.

Опция Detailed Ranking имеет смысл только для personal contest. В этом случае по умолчанию участники в таблице рейтинга не видят своего распределения по местам, и им указывается только то, прошли их решения предварительные тесты или нет. При включении данной опции участники будут в рейтинге видеть баллы, которые заработали их решения, и свое распределение по местам.

43-0.gif (12761 bytes)

На вкладке Paths вы можете установить имена файлов, в которые проверяющая система записывает отчеты (contest log), и файла, в котором сервер хранит информацию о посланных ему решениях (results). Оба имени файла отсчитываются от рабочего каталога сервера практикумов. При этом путь к contest log должен совпадать с путем, установленным в файле .checkerrc.

43-1.gif (11268 bytes)

7) Просмотр результатов работы школьников.

Результаты работы любой из групп пользователей можно посмотреть с помощью элемента меню Info сервера. Меню Ranking позволяет для выбранной группы пользователей посмотреть, сколько и какие задачи решил каждый из них, сколько попыток при этом сделал, а если задача не решена, то сколько первых тестов по ней все же проходят. Меню Contest Log позволяет получить подробную информацию о каждой посылке каждого пользователя:

43-2.gif (16043 bytes)

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

Руководство по использованию клиента

1. Подключение к программе-серверу.

При вызове программы-клиента (client.exe) открывается следующее диалоговое окно:

44-0.gif (8900 bytes)

В нем необходимо указать имя пользователя, его пароль и IP-адрес компьютера, на котором работает программа-сервер. Вместо IP-адреса может быть указано имя этого компьютера в локальной сети. Далее следует нажать кнопку Login.

2. На вкладке Problems можно выбрать одну из задач, назначенную данному пользователю учителем.

44-1.gif (10171 bytes)

Описание условия задачи можно получить, нажав кнопку Description. В общем случае клиенту будет переслан файл в формате txt, rtf или doc, который следует сохранить, а затем открыть с помощью стандартного программного обеспечения. Иногда файл открывается автоматически.

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

3. Отсылка решения на проверку.

В списке Files of type следует выбрать расширение файла с решением, которое фактически привязано к одному из компиляторов.

44-2.gif (10774 bytes)

Затем следует найти соответствующий файл с решением и путем нажатия на кнопку Open послать его на проверку. Результаты проверки можно посмотреть на вкладке Reports:

44-3.gif (13161 bytes)

Вкладка Ranking предназначена в основном для отображения текущих результатов on-line-соревнований.

Составление конфигурационного файла задачи

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

Формат каждого параметра в конфигурационном файле следующий:

option = value

44-4.gif (10924 bytes)

45-0.gif (18963 bytes)

Пути в параметрах tests, answers задаются в соответствии со следующими правилами:

1) одиночный символ “#” заменяется на номер теста: 1, 2, …, 9, 10, 11, …

2) группа символов “#” заменяется на номер теста, дополненный слева нулями так, чтобы заместить все символы “#”. К примеру, “###” заменятся на 001, 002, …, 010, 011, …, 099, 100, …

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

Следует отметить, что в маске имени файла должна присутствовать не более чем одна группа символов “#”. В маске имени файла может не быть ни одного символа “#”.

45-1-0.gif (50312 bytes)

45-1-1.gif (15205 bytes)

45-2.gif (49086 bytes)

Правила задания компараторов. В стандартную поставку проверяющей системы входят следующие проверяющие программы:

1) numbers — сравнивает вывод программы ученика и правильный ответ, рассматривая их как последовательность действительных чисел. Можно проводить сравнение на совпадение с заданной точностью. Длина десятичной записи обрабатываемых чисел не ограничена;

2) numberset — сравнивает вывод программы ученика и правильный ответ, рассматривая их как множества действительных чисел. Можно проводить сравнение на совпадение с заданной точностью. Длина десятичной записи обрабатываемых чисел не ограничена;

3) tokens — сравнивает каждую строку вывода программы ученика с соответствующей строкой в правильном ответе, рассматривая строку как последовательность слов (без учета разделителей);

4) words — сравнивает вывод программы ученика с ответом, рассматривая строку как последовательность слов. Отличие от tokens состоит в том, что файлы предварительно не разбиваются на строки. Возможно сравнение ответов без учета регистра символов;

5) exactly — сравнивает вывод программы ученика с ответом на побайтовое совпадение.

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

checker = <standard_checker>

Здесь standard_checker — одно из приведенных выше имен стандартных компараторов.

Также предоставляется возможность использовать внешние компараторы. Для этого следует в качестве checker указать

checker = path_to_your_verifier

Здесь path_to_your_checker — имя исполнимого файла вашей программы-компаратора. Это имя файла отсчитывается относительно каталога задачи.

Пример. Предположим, что условия тестов хранятся в файлах 1, 2, 3; ответы — в файлах 1.a, 2.a, 3.a. При этом решение ученика должно читать входные данные из файла input.txt и выдавать ответ в файл output.txt. Предположим, что ожидаемый ответ есть последовательность действительных чисел. При этом пусть решению отводится 1 секунда на тест. Конфигурационный файл для этой задачи можно составить так:

title = A Simple Problem

ntests = 3

tests = #

answers = #.a

consoleio = false

input = input.txt

output = output.txt

checker = <numbers>

timelimit = 1

Методика использования Электронного задачника

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

Методика использования ЭЗ делится на две части:

1) методика внесения нового задания в БД, назначение заданий учащимся (эта часть работы, как правило, выполняется учителем во внеурочное время);

2) методика использования ЭЗ на уроке.

Методика внесения нового задания в БД формально — проста, но фактически требует высокого профессионального мастерства. Начинающему учителю рекомендуется использовать ту БД задач, которая будет поставляться в комплекте ЭЗ.

Если учитель решит включить какую-либо новую задачу в БД задач ЭЗ, то он обязательно должен продумать систему тестов, прорешать эту задачу и получить ответы на подобранной системе тестов. Именно наличие всех трех компонент (условие задачи с подробным описанием форматов входных и выходных данных, система тестов, ответ к каждому тесту) необходимо для включения задачи в ЭЗ. Без сомнения, это большой труд, а главное — творческий. Например, при подобной работе могут возникнуть ситуации, когда вроде бы всем известная задача при небольшом изменении условия или ограничений на входные данные приобретает методическую значимость по сравнению с первоначальным условием. И эту ситуацию учитель должен уметь увидеть и оценить!

Проводя деятельность по включению задачи в БД, учитель проводит жесткий отбор задач в реальной ситуации — сдаче своего решения своей же задачи электронному задачнику. Кроме того, он всегда может воспользоваться уже внесенными задачами своих коллег: ведь требования по включению задач в ЭЗ унифицированы. Эта методическая работа учителя очень важна в первую очередь для него самого, а косвенно она приносит положительный результат и для учащихся.

Методика использования ЭЗ на уроках достаточно проста и понятна.

После объяснения теоретического материала и разбора базовых заданий каждому школьнику выдается свое собственное задание из соответствующего практикума (раздела ЭЗ). В этот момент и включается в учебный процесс работа с ЭЗ. Учащиеся работают в основном самостоятельно, “общаясь” с компьютером. Получая информацию от ЭЗ о тех наборах входных данных, на которых их программа работает неверно, они могут исправить ошибки в программе, зачастую не прибегая к помощи учителя. Основной функцией учителя является в этот период оказание консультаций, ответы на возникающие вопросы, помощь тем ученикам, которые в ней нуждаются. В силу того, что учитель обладает всей информацией о работе каждого ученика (были ли попытки сдачи задания ЭЗ, сколько попыток, сколько заданий выполнено полностью успешно, а сколько — частично), он может ненавязчиво контролировать учебную деятельность учащихся. Но на этом функции учителя конечно же не исчерпываются. После того как программа ученика была признана ЭЗ правильной, учителю, несомненно, имеет смысл посмотреть текст самой программы и обсудить ее с учеником. Иногда при этом достаточно указать на отдельные недостатки кода, а иногда оказывается, что программа ученика неприемлема по тем или иным причинам, например, задача решена не эффективно (хотя и этот факт ЭЗ зачастую может отследить путем ограничения на время работы программы). Тогда, после обсуждения с учителем, ученик снова начинает работу с ЭЗ.

Использование ЭЗ позволяет выстраивать ход урока в соответствии с учебными потребностями конкретного класса. Например, если в классе есть “продвинутые” ученики (а они есть всегда), то их можно загрузить работой с ЭЗ, а с остальными еще раз прорешать базовые (модельные) задачи, остановиться на теоретических аспектах темы и т.д. Более того, урок можно построить и таким образом: слабым ребятам назначить задачи базового уровня и переключить их на работу с ЭЗ, а с сильной частью класса провести занятие по углубленному изучению данной темы.


* Глава подготовлена совместно с И.Н. Фалиной

1 См., например, книгу Е.Андреевой, И.Фалиной “Системы счисления и компьютерная арифметика”. М.: БИНОМ. Лаборатория знаний, 2004.

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

3 При публикации данного задачника в № 14/2008 в примерах к данной задаче была допущена опечатка

4 Припубликации данной задачи в № 14/2008 в описании входных данных ошибочно опущено число n

Ел. Вл. Андреева

TopList