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

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

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

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. Решение логических задач с использованием аппарата алгебры логики

Читать еще:


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

Использование новых образовательных информационных технологий при изучении биологии в 6–7 классах :: Урок по теме "Семейство бобовые. Горох и фасоль – бобовые растения, особенности строения семейства, выращивание и использование человеком" :: Урок в 5-м классе (природоведение). Тема "Живые клетки" :: Урок биологии в 7-м классе "Законы России об охране животного мира. Система мониторинга". По программе Криксунов-Пасечник :: Урок внеклассного чтения во 2-м классе на тему: "Н. Носов. "Федина задача" :: Невеста Франкенштейна ( Bride of Frankenstein ), 2019 :: Дом и дача/Освещение/Новый Год/Праздничный стол/Светильники для кухни / Maytoni / Подвесной светильник California P536PL-01R ::

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

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

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

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

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

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

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

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

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

Костя Цзю прооперирован после инфаркта. 48 лет, абсолютный чемпион мира среди профи.

Вот это да. Возраст еще не старый, вес - 63 кг, легче не бывает, здоровье - железное... С чего вдруг?

Автор решающей шайбы Олимпиады-2018 не забыл своего первого тренера. И подарил ему автомобиль!

Подарок в тайне от тренера доставили прямо на ледовую арену к началу рабочего дня.

Урок литературного чтения Л.Пантелеев. "Камилл и учитель" УМК Н.Ф. Виноградовой "Начальная школа XXI века"

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

Итоговая контрольная работа по органической химии. 9-й класс

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


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