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

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

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

1. Арифметические операции над числами в недесятичных системах счисления

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

ЗАДАЧА 1. Даны два действительных числа в системах счисления с различными основаниями. Сравнить между собой значения данных чисел (если числа не равны, то определить, какое из них больше).

M = 0,10(110)(2)

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

Обозначим исходное число как М. Тогда:

100 M = 10,(110)

100000 M = 10110,(110)

Вычитая меньшее число из большего, получим:

10110,(110) – 10,(110) = 10100

100000 M – 100 M = 11100 M

Таким образом:

11100 M = 10100

Отсюда можно найти значение М в форме обыкновенной дроби и перевести его в десятичную систему счисления.

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

M - N < 0

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

Ответ: M < N

ЗАДАЧА 2. Вычислить значение числового выражения. Результат записать в четверичной системе счисления. Число под знаком корня является пятой степенью целого положительного числа.


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

Для левой части выражения вычисления можно выполнить в десятичной системе счисления.

Мы получили десятичное число 88. В шестнадцатиричной системе счисления это число имеет запись 58=5×16+8. Вычитая шестнадцатиричную дробь из полученного числа, получим:

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

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

( 10(16) )5 = 100000(16) < M

( 10(16)) )5 = 10000000000(16) > M

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

N = XY(16) = 16X + Y

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

20 × 20=400

400 × 20=8000

8000 × 20=100000

100000 × 20=2000000 > M

Полученное значение больше М. Это значит, что значение первой цифры N уже определено: она равна 1. Таким образом, искомое число начинается с единицы и имеет следующий вид:

N = 1Y(16) = 16 + Y

Теперь надо найти значение цифры Y. Очевидно, что при умножении четных цифровых разрядов могут получаться только четные значения. В последнем разряде числа М расположена нечетная цифра D. Следовательно, значение младшей цифры в числе N может быть только нечетным. Значение 1 можно исключить сразу, т.к. единица при умножении дает в последнем разряде только саму себя.

Y = 2n + 1; Y ǂ 1; Y ϵ { 3, 5, 7, 9, B, D, F }

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

Вторая степень:              3 × 3 = 9

Третья степень:               9 × 3 = *B

Четвертая степень:         1B × 3 = *1

Пятая степень:                51 × 3 = *3

Начиная с шестой степени цифры в последних разрядах образуют периодическую последовательность вида: ( 9, B, 1, 3, … ). Похожие результаты получаются для всех нечетных цифр от 3 до F.

5: 9, D, 1, 5, …

7: 1, 7, …

9: 1, 9, …

B: 9, 3, 1, B, …

D: 9, 5, 1, D, …

F: 1, F, …

Таким образом, только две цифры дают значение D в последних разрядах своих степеней, при этом только для цифры D это значение образуется именно для пятой степени. Это значит, что последняя цифра числа найдена: Y = D.

Итак, число N найдено.

Теперь мы можем выполнить последнюю операцию вычитания и перевод результата в четверичную систему счисления.

1D(16) – 0,2(16) = 1C,E(16)

1C,E(16) = 11100,111(2)

11100,111(2) = 130,32(4)

Ответ: 130,32(4)

ЗАДАЧА 3. Дана запись операции умножения двух целых чисел в системе счисления с основанием четыре. При этом все цифровые разряды чисел, кроме нулевых, не известны и обозначены буквами латинского алфавита X,Y,Z. Определить значения данных чисел (цифровые разряды).

Для четверичного основания найти решение задачи не очень сложно. Цифра 0 исключается. Следовательно, для неизвестных значений цифровых разрядов остаются только три допустимых значения: 1, 2, 3. Таким образом, общее количество возможных вариантов равно 6 = 3! (факториал 3). При этом нет необходимости рассматривать все варианты умножения в полном объеме. Две младшие цифры в первом частичном произведении являются равными. Если это не так, то вариант можно отбрасывать.

 

1

2

3

4

5

6

1232
23
-----
**22

1323
32
-----
**12

2131
13
-----
**13

2313
31
-----
**13

3121
12
-----
**02

3212
21
-----
**12

Из представленной таблицы видно, что необходимый результат дает только один вариант: X=1, Y=2, Z=3. Для полной уверенности подставим эти значения в текст примера и убедимся в правильности решения.

Ответ: X=1; Y=2; Z=3; Первое число 1232; Второе число 23.

ЗАДАЧА 4. Определить основания систем счисления X и Y, для которых выполняются все следующие условия:

1)  234(X) < 165(Y)

2)  543(X)) + 22(X) = 565(X)

3)  345(Y) × 44(Y) = 16522(Y)

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

X > 6; Y > 6; Y > X;

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

Дальше можно рассуждать следующим образом. Уравнение для X не дает нам однозначного решения: оно образует тождество для множества значений X:

543(7) + 22(7) = 565(7)

543(8) + 22(8) = 565(8)

543(9) + 22(9) = 565(9)

543(10) + 22(10) = 565(10)

Следовательно, надо перейти к анализу условий, заданных для Y.

Произведение 5 на 4 равно 20. Если при умножении в системе с основанием Y получено число 20, которое в этой системе счисления имеет запись вида N2, то полученный результат можно записать следующим образом:

NY + 2 = 20

NY= 18

Число 18 делится без остатка только на 1, 3, 6, 9, 18. Если учесть при этом, что Y>6, то возможными решениями остаются только 9 и 18. Но решение Y=18 не подходит, потому что в этом случае следующее умножение 4 на 4 с учетом единицы переноса дает значение 17 и следующий по порядку разряд произведения не может быть равен двум. Напротив, умножение по основанию 9 дает требуемый результат:

Следовательно, решение для Y найдено: Y = 9.

Теперь надо найти решение для X. Для X остаются возможными два значения: X=7; X=8; Чтобы выбрать единственное, остается рассмотреть данное нам неравенство.

Запишем числа в виде алгебраических функций от X и Y.

2X2 + 3X + 4 < Y2 + 6Y + 5

После подстановки значения Y=9 и несложных преобразований получим:

2X2 + 3X + 4 < 92 + 6 × 9 + 5

2X2 + 3X < 81 + 54 + 5 - 4

2X2 + 3X < 136

X(2X+3) < 136

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

7(14+3) = 119 < 136

8(16+3) = 152 > 136

Значение X=8 нарушает неравенство. Следовательно, единственным допустимым значением для X является X=7. Задача решена.

Ответ:  X=7; Y=9.

ЗАДАЧА 5. При сложении трех неизвестных чисел в двенадцатиричной системе счисления выполняется следующее равенство:

XYZ + ZY + Z = ZXY

Число X возвели в степень N=YZ и результат записали в шестнадцатиричной системе счисления. Определить значение последней цифры в записи полученного шестнадцатиричного числа.

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

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

Z + Y + Z = 1Y

2Z + Y = 12 + Y

2Z = 12

Z = 6;

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

Z + Y + Z = 2Y

2Z + Y = 24 + Y

2Z = 24

Отсюда Z=12, что невозможно в c/c с основанием 12;

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

Y + 6 + 1 = 1X

Y + 7 = 12 + X

Y = X + 5

При этом в старшем разряде суммы разряд Z=6 может образоваться только при сложении цифры X и единицы переноса.

X + 1 = 6

X = 5

Соответственно для цифры Y имеем следующее:

Y = 5 + 5 = A

Проверим значения разрядов путем подстановки.

Теперь можно приступить ко второй части задания. Показатель степени, в которую возвели число X равен:

N = YZ = A6 = 106  = 1000000(10)

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

Первая степень:             5

Вторая степень:              5 × 5= 19

Третья степень:              5 × 5 × 5 = *D

Четвертая степень:         5 × 5 × 5 × 5 = *1

Дальше образуется период с длиной 4:

( 5; 9; D; 1 )

Одинаковые цифры образуются в последнем разряде степени для всех показателей степени, которые имеют одинаковые остатки при делении на длину периода, т.е. на четыре. Например, на цифру 1 заканчиваются все степени с показателями, которые кратны четырем: 4, 8, 12, 16, и т.д. Один миллион делится на четыре без остатка. Следовательно, последняя цифра в миллионной степени шестнадцатиричного числа равна 1.

Ответ: Последняя цифра в записи полученного шестнадцатиричного числа равна 1.

ЗАДАЧА 6. Дана периодическая дробь в троичной системе счисления (M). Записать число в системе счисления с основанием шестнадцать. Определить значение цифры, которая находится в полученном шестнадцатиричном числе в позиции с троичным номером N=201211221(3) после запятой.

M = 201201,(201)(3)

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

201201(3) = 2 × 35 + 0 + 1 × 33 + 2 × 32 + 0 + 1 = 2 × 243 + 27 + 18 + 1 = 486 + 27 + 18 + 1 = 532(10)

Переводим дробную часть числа в десятичную систему счисления.

X = 0,(201)(3)

1000X = 201,(201)(3)

201,(201) (3) - 0,(201)(3) = 201

1000X - X = 222X

Теперь выполним перевод целой и дробной частей числа в шестнадцатиричную систему счисления.

532 : 16 = 33;       остаток = 4;

33 : 16 = 2;           остаток = 1;

2 : 16 = 0;             остаток = 2;

532(10) = 214(16)

19 : 16 = 1;           остаток = 3;

1 : 16 = 0;             остаток = 1;

19(10) = 13(16)

26 : 16 = 1;           остаток = A;

1 : 16 = 0;             остаток = 1;

26(10) = 1A(16)

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

Мы получили бесконечную периодическую дробь в шестнадцатиричной системе счисления.

M = 214,B(B13)(16)

Первая цифра после запятой не входит в состав периода. Поэтому удобнее нумеровать цифры, начиная со второй цифры после запятой. Другими словами, нам надо найти значение цифры с номером S=N-1 от начала периодической части числа.

S = N-1 = 201211221(3) - 1 = 201211220(3)

Значения цифр в периодической части числа повторяются через каждые три разряда. Это значит, что остаток от деления номера цифры на три позволяет нам определить значение цифры с любым номером. Если число в троичной системе счисления заканчивается на цифру 0, то это значит, что данное число делится на 3 без остатка.

Но если номер цифры делится на три без остатка, то эта цифра занимает третье место в составе периода. Третья цифра в периоде дроби это цифра три.

Ответ: Цифра с троичным номером 201211221 после запятой в шестнадцатиричной записи троичного числа 201201,(201) равна 3.

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

Читать еще:


Новые материалы:

Методическая разработка урока "Рынок труда и занятость населения" (8-й класс) :: Модель урока в 10-м класе "Ресурсы мирового океана" :: Урок по теме "Природные зоны России. Арктическая пустыня, тундра, лесотундра" :: Интеллектуальная игра "Знатоки географии". 6-й класс :: Элективный курс "Химия и здоровье" для учащихся 9-х классов :: Волшебный лагерь (Magic Camp) :: Дом и дача/Мебель/Мебель для спальни/Мебель/Спальня/Гарнитуры спальные / МСТ / Гарнитур для спальни Карина Люкс K3 ::

Отзывы (через аккаунты в социальных сетях Вконтакте, Facebook или Google+):

Оставить отзыв с помощью аккаунта ВКонтакте:

Оставить отзыв с помощью аккаунта FaceBook:

Оставить отзыв с помощью аккаунта Google+:

Поддержите сайт - подпишитесь на канал в Яндекс.Дзене!

Самое популярное:
Состояние воздуха: Карта загрязнения воздуха онлайн, обновляется в режиме реального времени

Экологическая карта состояния воздуха, которым мы дышим. В режиме реального времени.

Звуко-буквенный разбор слов

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.

Урок окружающего мира на тему Когда придет суббота и когда наступит лето?

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.

Тест по экономике для 10–11-х классов общеобразовательного учреждения с социально-экономическим профилем

Научить детей реально оперировать звуками, т.е. развивать фонетический слух.


Школьные занятия:
 
Контакты Научно-популярный портал "Познание - XXI век".
111672, г. Москва, ул. Новокосинская, д. 15, корп. 7.
Для связи E-mail: . poznanie21@yandex.ru
 
ADD