Семь тестов, три задачи

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

Тесты

1. Если каждая четверка битов в каждом элементе последовательности:

000110010110,

00010001100101100110,

0001000100011001011001100110, …

кодирует десятичную цифру, то на седьмом месте последовательности находится элемент, соответствующий десятичному числу:

а) 111111196666666;

б) 111111199999996666666;

в) 111999999999666;

г) 196196196196196196196.

Ответ: а).

Обоснование ответа. Если перевести четверки битов в десятичную систему, то можно получить последовательность: 196, 11966, 1119666, … . Проанализировав закон построения последовательности, можно обнаружить, что искомое десятичное число должно выглядеть так: 111111196666666.

2. Наименьшее количество различных законов логики, максимально упрощающих выражение:

,

равно:

а) 5;

б) 4;

в) 3;

г) 2.

Ответ: в).

Обоснование ответа. Необходимо: 1) применить наименьшее количество аксиом; 2) применить аксиомы наименьшее число раз. Одним из законов, позволяющих быстро уменьшать “длину” упрощаемого выражения, является закон поглощения. Попробуем применить этот закон. Проанализируем выражение под “внешним” знаком отрицания: по закону поглощения вида: . Следовательно, (применен второй закон — закон идемпотентности: ). Применяем третий закон — закон исключенного третьего: . Получили, что z = 1.

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

В нем использовано большое количество различных законов (сколько их?).

3. Составлена программа решения квадратного уравнения вида ax² + bx + c = 0. После ввода исходных данных ее структура:

если …

то

…

иначе

если …

то

…

иначе

если …

то

…

иначе

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

а) 3;

б) 4;

в) 5;

г) 6.

Ответ: г).

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

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

1) a = 0, b = 0, c = 0 — уравнение выродилось в тождество 0 = 0;

2) a = 0, b = 0, c № 0 — уравнение не имеет смысла (нет уравнения);

3) a = 0, b № 0 — квадратное уравнение выродилось в уравнение первой степени с одним корнем;

4) дискриминант D > 0 — уравнение имеет два различных корня;

5) дискриминант D = 0 — уравнение имеет два равных корня;

6) дискриминант D < 0 — уравнение не имеет вещественных корней.

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

1) а = 0, b = 0, c = 0;

2) а = 0, b = 0, c = 1;

3) а = 0, b = 1, c = 2;

4) а = 1, b = –5, c = 6;

5) а = 1, b = –4, c = 4;

6) а = 1, b = 2, c = 5.

4. Если ряд вида 01, 01012, 01012010123, 01012010123010120101234, … образован, начиная со второго числа, по единому правилу, то в 766-м разряде (слева направо) числа ряда с номером 9 стоит цифра:

а) 0;

б) 1;

в) 7;

г) 8.

Ответ: г).

Обоснование ответа. Число номер 1 задано изначально и имеет вид: 01. Определим, анализируя остальные числа, закон построения ряда. Сравнивая каждое число ряда с предыдущим, видим, что этот закон таков: каждое новое число получается путем присоединения к предыдущему его копии и затем добавления номера нового числа. Поэтому порядковые номера чисел расположены соответственно на позициях: 2, 5, 11, 23, 47, 95, 191, 383, 767 (или в общем виде — на (2n + 1)-й позиции, где n — количество цифр в предыдущем числе ряда). Следовательно, у 9-го числа на предпоследнем, 766-м, месте стоит последняя цифра добавленной копии предыдущего числа, т.е. его номер — 8.

5. В населенном пункте численностью 50 000 человек, где в первые и вторые сутки больными были соответственно 100 и 200 человек, а эпидемия распространяется по закону: x(t + 1) = x(t) + x(t – 1)x(t), где x(t) — число больных на t-е сутки, все его население заболеет к концу:

а) пятых суток;

б) четвертых суток;

в) третьих суток;

г) вторых суток.

Ответ: б).

Обоснование ответа. Проведем расчеты по указанной рекуррентной формуле:

x(3) = x(2) + x(1)x(2) = x(2)(1 + x(1)) = 200 ґ 101 = 20 200,

x(4) = x(3)(1 + x(2)) = 20 200 ґ 201 = 4  060 200.

Итак, весь поселок заболеет к концу четвертых суток.

6. Фрагмент программы

— на языке Паскаль:

a := 1; b := 1;

d := 1; с := 1;

for i := 2 to 4 do

begin

writeln(с); a := 10 * a + i;

d := 10 * d; c := a * d + b;

b := d * i + b

end

— на языке Бейсик:

a = 1: b = 1

d = 1: с = 1

FOR i = 2 TO 4

PRINT с

a = 10 * a + i

d = 10 * d

c = a * d + b

b = d * i + b

NEXT i

 

выводит числа:

 

а) 1, 111, 112211, 111222111;

б) 1, 111, 11211, 1123211;

в) 1, 111, 12321, 1234321;

г) 1, 111, 232, 343.

Ответ: б).

Обоснование ответа. Проследим изменение значений переменных, воспользовавшись таблицей:

7. Из цифр числа х получить число y, записанное теми же цифрами, но наоборот (незначащие нули отбрасываются), можно фрагментом:

— на языке Паскаль:

а)

y := 0;

while x > 0 do

begin

y := 10 * y + x mod 10;

x := x — x div 10

end

б) y := 0;

while x >= 0 do

begin

y := 10 * y + x mod 10;

x := x div 10

end

в) y := 0;

while x > 0 do

begin

y := 10 * y + x mod 10;

x := x div 10

end

г) y := 1;

while x > 0 do

begin

y := 10 * y + x mod 10;

x := x div 10

end

— на языке Бейсик:

а) y = 0

WHILE x > 0

y = 10 * y + x mod 10

x = x — x\10

WEND

б) y = 0

WHILE x >= 0

y = 10 * y + x mod 10

x = x\10

WEND

в) y = 0;

WHILE x > 0

y = 10 * y + x mod 10;

x = x\10

WEND

г) y = 1

WHILE x > 0

y = 10 * y + x mod 10;

x = x\10

WEND

Ответ: в).

Обоснование ответа. Вариант а) — неверный, так как в нем неправильно получается новое значение х.

В остальных вариантах это значение рассчитывается правильно (x := x div 10).

Вариант г) – неверный, так как формирует число у, начиная с заданной (ошибочно) единицы (y := 1; ).

В варианте в) оператор присваивания (на языке Паскаль):

y := 10 * y + x mod 10

как раз формирует (в цикле) искомое число у — каждый раз добавляет последнюю цифру текущего значения x к текущему значению y, умноженному на 10. Тело оператора цикла выполняется, пока соблюдается условие x > 0.

Очень “правдоподобен” ответ б), но в нем будет иметь место зацикливание, т.к. условие x 0 будет в конце концов соблюдаться постоянно.

Задачи

1. Может ли при каком-то р количество 112_{p + 2} равняться количеству 1214_p?

Решение. Прежде всего ясно, что в виде индекса обозначено основание системы счисления. Допустим, что для некоторого p равенство 112_{p + 2} = 1214_p справедливо. Переведем оба числа равенства в десятичную систему — получим:

(p + 2)² + (p + 2) + 2 = p³ + 2p² + p + 4

или

p²(p + 1) = 4(p + 1).

Так как p + 1 № 0, то p² = 4, а p = 2. Так как в записи чисел равенства есть цифра 4, то p > 4, т.е. найденное значение p не подходит. Ответ — отрицательный.

2. Составить программу вычисления квадрата заданного целого числа, не используя операции умножения, возведения в степень и встроенные функции.

Решение. Прежде всего можно использовать представление x² в виде х слагаемых: x² = x + x + …+ x. Соответствующий вариант программы на школьном алгоритмическом языке:

алг Возведение_в_квадрат

нач цел x, y, i

? вывод "x = "

? ввод x

? y := 0

? нц для i от 1 до x

? | y := y + x

? кц

? вывод нс, "Квадрат х равен ", y

кон

Можно также применить формулу суммы членов арифметической прогрессии: x² = 1 + 3 + 5 + … + (2x – 1):

алг Возведение_в_квадрат

нач цел x, y, i

? вывод нс, "x = "

? ввод x

? i := 1; y := 0

? нц пока i <= x

? ? y := y + i + i — 1

? ? i := i + 1

? кц

? вывод нс, "Квадрат х равен ", y

кон

3. Записать в виде формул или формулы правило формирования последовательности десятичных чисел: 1, 10, 11, 100, 111, 1000, 1111, … .

Решение. Если пытаться найти общий закон для всех чисел, то задача значительно усложняется. Лучше сравнивать отдельно числа на четных и на нечетных местах. Тогда связь становится “прозрачной”: каждое число на четном месте получается из числа на предыдущем четном месте умножением его на 10, а каждое число на нечетном месте — умножением числа на предыдущем нечетном месте на 10 и добавлением к результату 1. Этот словесно описанный закон можно записать (формализовать) с помощью формул так:

A₁ = 1, A₂ = 10, A_{2n + 1} =10A_{2n – 1}+ 1, A_{2n + 2} = 10A_2n, n = 1, 2, … .