Решение задач с помощью систем счисления.
презентация к уроку по информатике и икт (10 класс)

Слайд 1

Задачи ЕГЭ, при решении которых используются знания о системах счисления.

Слайд 2

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

Слайд 3

Полезно помнить, что в двоичной системе : - четные числа оканчиваются на 0 , нечетные – на 1; - числа , которые делятся на 4, оканчиваются на 00, и т.д.; - числа , которые делятся на 2 k , оканчиваются на k нулей; - если число N принадлежит интервалу 2 k -1  N < 2 k , в его двоичной записи будет всего k цифр, например, для числа 123 : 2 6 = 64  123 < 128 = 2 7 , 123 = 1111011 2 (7 цифр )

Слайд 4

- числа вида 2 k записываются в двоичной системе как единица и k нулей, например: 16 = 2 4 = 10000 2 256 = 2 8 = 10000000 2 - числа вида 2 k -1 записываются в двоичной системе k единицами, например: 15 = 2 4 -1 = 1111 2 255 = 2 8 -1 = 11111111 2 - если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например: 15 = 1111 2 , 30 = 11110 2 , 60 = 111100 2 , 120 = 1111000 2

Слайд 5

задание под номером 1 Пример задания : Сколько единиц в двоичной записи десятичного числа 260? Решение: 1) проще всего представить заданное число в виде суммы степеней числа 2: 260 = 2 56 + 4 = 2 8 + 2 2 2) количество единиц в двоичной записи числа равно количеству слагаемых в таком разложении Ответ : 2

Слайд 6

Еще пример задания : Сколько единиц в двоичной записи шестнадцатеричного числа 12F0 16 ? Решение: представим заданное число в двоичной системе счисления, сопоставив каждой цифре ее код : 12F0 16 = 0001 0010 1111 0000 считаем количество единиц в двоичной записи числа Ответ: 6

Слайд 7

Ещё пример задания : Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел номер того числа, в двоичной записи которого содержится ровно 6 единиц. Если таких чисел несколько, укажите номер наибольшего из них. 63 10 * 4 10 2) F8 16 + 1 10 3 ) 333 8 4 ) 11100111 2

Слайд 8

Решение : 1) нужно перевести все заданные числа в двоичную систему, подсчитать число единиц и выбрать наибольшее и чисел, в которых ровно 6 единиц; 2) для первого варианта переведем оба сомножителя в двоичную систему: 63 10 = 111111 2 4 10 = 100 2 3) в первом числе ровно 6 единиц, умножение на второе добавляет в конец два нуля: 63 10 * 4 10 = 111111 2 * 100 2 = 11111100 2 то есть в этом числе 6 единиц

Слайд 9

4) для второго варианта воспользуемся связью между шестнадцатеричной и двоичной системами счисления: каждую цифру шестнадцатеричного числа можно переводить отдельно в тетраду (4 двоичных цифры): F 16 = 1111 2 8 16 = 1000 2 F 8 16 = 1111 1000 2 5) после добавления единицы F 8 16 + 1 = 1111 1001 2 также получаем число, содержащее ровно 6 единиц, но оно меньше, чем число в первом варианте ответа ( 11111100 2 )

Слайд 10

6) для третьего варианта используем связь между восьмеричной и двоичной системами: каждую цифру восьмеричного числа переводим отдельно в триаду (группу из трёх) двоичных цифр: 333 8 = 011 011 011 2 = 11011011 2 это число тоже содержит 6 единиц, но меньше, чем число в первом варианте ответа ( 11111100 2 ) 7) последнее число 11100111 2 уже записано в двоичной системе, оно тоже содержит ровно 6 единиц, но меньше первого числа

Слайд 11

8) таким образом, все 4 числа, указанные в вариантах ответов содержат ровно 6 единиц, но наибольшее из них – первое Ответ: 1.

Слайд 12

Задачи для тренировки: 1) Сколько единиц в двоичной записи числа 195? 2) Сколько единиц в двоичной записи числа 173? 3) Сколько единиц в двоичной записи числа A 87 16 ? 4) Сколько единиц в двоичной записи числа 754 8 ? 5) Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел номер того числа, в двоичной записи которого содержится ровно 4 единицы. Если таких чисел несколько, укажите номер наибольшего из них. 15 10 * 16 10 + 4 10 2) D 7 16 + 1 10 3 ) 3 44 8 4) 11100001 2 6) Сколько единиц в троичной записи десятичного числа 243?

Слайд 13

Ответы : 4 5 6 6 3 1 (3 5 )

Слайд 14

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

Слайд 15

Пример задания : Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. КККК 2. КККЛ 3. КККР 4. КККТ …… Запишите слово, которое стоит на 67-м месте от начала списка.

Слайд 16

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

Слайд 17

2) выполним замену К  0, Л  1, Р  2, Т  3 3) поскольку нумерация слов начинается с единицы, а первое число КККК  0000 равно 0, под номером 67 будет стоять число 66 , которое нужно перевести в четверичную систему: 66 = 1002 4 4 ) Выполнив обратную замену (цифр на буквы), получаем слово ЛККР . Ответ: ЛККР.

Слайд 18

Ещё пример задания : Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 101-м месте от начала списка.

Слайд 19

Решение : 1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) А  0, О  1, У  2 ,

Слайд 20

2) выпишем начало списка, заменив буквы на цифры: 1. 00000 2. 00001 3. 00002 4. 00010 …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д . тогда легко понять, что 101-м месте стоит число 100, записанное в троичной системе счисления

Слайд 21

3) переведем 100 в троичную систему: 100 = 10201 3 4) заменяем обратно цифры на буквы: 10201  ОАУАО Ответ : ОАУАО.

Слайд 22

Еще пример задания : Все 5-буквенные слова, составленные из букв А , К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова РУКАА .

Слайд 23

Решение : будем использовать четверичную систему счисления с заменой А  0, К  1, Р  2, У  3 2) слово РУКАА запишется в новом коде так 23100 4 3) переводим это число в десятичную систему: 23100 4 = 2  4 4 + 3  4 3 + 1  4 2 = 720 4) поскольку нумерация элементов списка начинается с 1, а числа в четверичной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ: 721 .

Слайд 24

Задачи для тренировки : 1) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова УКАРА.

Слайд 25

2) Все 5-буквенные слова, составленные из букв К, О, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ККККК 2. ККККО 3. ККККР 4. КККОК …… Запишите слово, которое стоит под номером 238 .

Слайд 26

3) Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер первого слова, которое начинается с буквы К.

Слайд 27

Ответы: 841 РРРОК 257

Слайд 28

з адание под номером 16 ( к одирование чисел) Что нужно знать : - последняя цифра записи числа в системе счисления с основанием N – это остаток от деления этого числа на N - две последние цифры – это остаток от деления на N 2 , и т.д. - число 2 N в двоичной системе записывается как единица и N нулей: 100…0 - число 2 N -1 в двоичной системе записывается как N единиц: 11…1 - число 2 N – 2 K при K < N в двоичной системе записывается как N– K единиц и K нулей

Слайд 29

Пример задания: Сколько единиц в двоичной записи числа 8 1023 + 2 1024 – 3? Решение: - приведём все числа к степеням двойки: 8 1023 + 2 1024 – 3 = 2 3069 + 2 2014 - 3 - число 2 2014 запишется как 1 единица и 2014 нулей, а 3=11 2 , тогда 2 2014 – 3 - это 100000…..0000 11 011111 ….. 1101 Т.е . единиц 2014 – 1 = 2013 - прибавление 2 3069 даст еще одну единицу, всего получается 2013 + 1 = 2014 единиц О твет : 2014.

Слайд 30

Ещё пример задания: Сколько единиц в двоичной записи числа 8 1014 – 2 530 – 12? Решение: - запишем выражение следующим образом 8 1014 – 2 530 – 12 = 2 3042 – 2 530 – 1100 2 - вспомним, что тогда 2 3042 – 2 530 = 11…100…0 это 2512 – единиц и 530 – нулей .

Слайд 31

- выделим из этого значения последнюю единицу со следующими 530 нулями как отдельное слагаемое : таким образом, общее число единиц равно 2511 + 526 + 1 = 3038 Ответ : 3038.

Слайд 32

Ещё пример задания: Значение арифметического выражения: 9 8 + 3 5 – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? Решение. - запишем выражение следующим образом: 9 8 + 3 5 – 9 = (3 2 ) 8 + 3 5 - 3 2 = 3 16 + 3 5 - 3 2 - 3 16 + 3 5 = 10000000000100000 3 - 10000000000100000 3 - 100 3 = 100...00022200 3 в полученном числе три двойки . Ответ: 3

Слайд 33

Задачи для тренировки: Сколько единиц в двоичной записи числа 4 2014 + 2 2015 – 8 ? 2. Сколько единиц в двоичной записи числа 4 2016 – 2 2018 + 8 800 – 80 3. Значение арифметического выражения: 9 2016 + 3 2015 – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи? 4. Значение арифметического выражения: 16 2016 + 4 2015 – 16 записали в системе счисления с основанием 4. Сколько цифр «3» содержится в этой записи?

Слайд 34

Ответ. 2013 2395 2013 2012

Слайд 35

Задание 5 в ЕГЭ 2016 г. Пример задания: На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления .

Слайд 36

Решение . - данный алгоритм приписывает в конце числа или 10, если изначально в его двоичной записи было нечетное количество единиц, или 00 если четное. - 126 10 = 1111110 2 может получиться в результате работы алгоритма из числа 11111 2 . 11111 2 = 31 10 . Ответ: 31.

Слайд 37

Задачи для тренировки: 1. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1 . Строится двоичная запись числа N. 2 . К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 77. В ответе это число запишите в десятичной системе счисления.

Слайд 38

2. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1 . Строится двоичная запись числа N. 2 . К этой записи дописываются справа ещё два разряда по следующему правилу: а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001; б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое минимальное число R , которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Слайд 39

Ответ . 1 ) 19 2 ) 46