Размещено на http://www.allbest.ru

Введение

Оптимальный набор заданий ­ это минимальный набор заданий, решение которых обеспечивает подготовку к решению любых возможных задач ЕГЭ по данному разделу.

Объект исследования: процесс подготовки к ЕГЭ по информатике по разделу «Системы счисления»

Предмет исследования: оптимальный банк заданий для подготовки к ЕГЭ по информатике по разделу «Системы счисления»

Задачи исследования:

1. Проанализировать содержание обучения по разделу «Системы счисления» на профильном уровне изучения информатики и сформировать план изучения раздела;

2. Проанализировать наборы задач для подготовки к ЕГЭ по разделу “Системы счисления ” из разных источников, выделить примеры задач разных типов и выстроить типы задач в соответствии с планом изучения раздела;

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

4. Из составленного банка заданий, отобрать оптимальный набор заданий;

5. Составить план­конспект занятий для подготовки к ЕГЭ по разделу «Системы счисления». По каждому занятию описать:

а) теоретическую часть ­ необходимый и достаточный минимум теоретической информации для решения задач практической части;

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

Практическая значимость исследования:

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

информатика задача счисление обучение



1. Содержание обучения по разделу «Системы счисления» на профильном уровне изучения информатики

Содержание обучения по теме «системы счисления» на профильном уровне изучения информатики в школе было проанализировано на основе учебника К.Ю.Полякова, Е.А.Еремина «Информатика» углубленный уровень.

Системы счисления

Система счисления - это правила записи чисел с помощью специальных знаков - цифр, а также соответствующие правила выполнения операция с этими числами.

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

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

Непозиционная система счисления - это такая система счисления, в которой значение цифры не зависит от ее места в записи числа.

К непозиционным относится и десятичная египетская система счисления. Египтяне ввели 7 знаков-иероглифов, которые обозначали степени числа 10 (черточка, хомут, веревка, лотос, палец, лягушка, человек) (рис. 1)

Рис. 1

В римской системе счисления (она также считается непозиционной) в качестве цифр используются латинские буквы: I-1, V-5, X-10, L-50, C-100, D-500, M-1000. Единицы, десятки, сотни и тысячи кодировались отдельными группами, например:

2368=2000+300+60+8=(1000+1000)+(100+100+100)+(50+10)+(5+1+1+1)==MMCCCLXVIII.

Больше трех одинаковых цифр подряд не ставили, поэтому число 4 записывали как IV. В такой записи меньшая цифра (I) стоит перед большей (V), поэтому она вычитается из нее. То есть:

IV=5-1=4

Аналогично записывались числа 9,40,90,400 и 900:

IX=10-1=9, XL=50-10=40, XC=100-10=90, CD=500-100=400, CM=1000-100=900.

Из-за этой особенности римскую систему нельзя считать полностью непозиционной, потому что значение меньшей цифры, стоящей слева от большей, меняется не отрицательное.

У римской системы есть несколько серьезных недостатков:

· можно записывать только натуральные числа;

· чтобы записывать большие числа, необходимо вводить все новые и новые цифры (иногда использовались цифры с подчеркиванием или чертой сверху, что бы обозначало увеличение в 1000 раз: ;

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

Сейчас римская система применяется для нумерации веков, месяцев, глав в книгах, на циферблатах часов.

В славянской системе счисления в качестве цифр использовались буквы алфавита, над которыми ставился знак («титло»).

Рис. 2

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

Позиционные системы счисления

Позиционная система счисления - это такая система счисления, в которой значение цифры («вес») полностью определяется ее местом (позицией) в записи числа.

Пример позиционной системы счислении - привычная нам десятичная система. В десятичной системе основание - 10, алфавит состоит из 10 цифр: 0,1,2,3,4,5,6,7,8,9.

Алфавит системы счисления - это используемый в ней набор цифр.

Основание системы счисления - это количество цифр в алфавите (мощность алфавита).

В десятичной системе основание - 10, алфавит состоит из 10 цифр: 0,1,2,3,4,5,6,7,8 и 9. Число 10, вероятно, было выбрано потому, что люди сначала использовали для счета свои 10 пальцев на руках.

Разряд - это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.

В числе 6375 цифра 6 стоит в третьем разряде (тысячи), 3 - во втором разряде (сотни), 7 - в первом (десятки), а 5 - в нулевом (единицы).

разряды> 3 2 1 0

Это так называемая развернутая форма записи числа. Из этой записи видно, что последняя цифра 5 - это остаток от деления числа на 10, число составленного из двух последних цифр (75), - это остаток от деления исходного числа на 100 = и тд. Поэтому все числа, делящиеся на 100 без остатка, оканчиваются на два нуля.

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

Число 6375 можно представить в другой форме - по схеме Горнера:

6375=((6•10+3)•10+7)•10+5

Эта форма позволяет найти число, используя только умножение и деление (без возведения в степень).

Кроме десятичной системы на практике используются еще несколько позиционных систем:

· двоичная, восьмеричная и шестнадцатеричная в компьютерной технике;

· двенадцатеричная английская система мер (1 фут = 12 дюймов, 1 шиллинг = 12 пенсов);

· шестидесятеричная система измерения времени (1 час = 60 минут, 1 минута = 60 секунд).

Целые числа

Теперь можно записать аналогичные выражения для системы счисления с любым натуральным основанием p>1. Ее алфавит состоит из р цифр от 0 до р - 1, т.е. «старшая» (наибольшая) цифра в позиционной системе счисления на единицу меньше, чем основание.

Рассмотрим четырехзначное число , записанное в системе счисления с основанием р. Здесь - отдельные цифры, стоящие соответственно в третьем, втором, первом и нулевом разрядах. Это число может быть записано в развернутой форме:

разряды>3 2 1 0

или с помощью схемы Горнера:

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

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

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

,

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

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

Разделив новое получившееся число на р и отбросив остаток, получим число

,

из которого найдем как остаток от деления на р. Разделив на р еще раз, получаем последнюю цифру

Переведем, например, число 194 в пятеричную систему счисления (р=5). Найдем остаток от деления на 5:

194=38•5+4

Таким образом, мы нашли последнюю цифру - 4. Частное равно 38, повторяем ту же операцию:

38=7•5+3

Следующая (с конца) цифра числа - 3. Дальше получаем: 7=1•5+2, третья с конца цифра - 2, а четвертая - 1 (единица уже не делиться на 5). Обратим внимание, что с помощью этого способа мы находим цифры числа, начиная с последней. Поэтому полученные остатки нужно выписать в обратном порядке:

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

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

Дробные числа

Дробные числа сначала рассмотрим на примере десятичной системы. Число 0,6375 можно представить в виде:

0,6375=6•0,1+3•0,01+7•0,001+5•0,0001.

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

разряды > -1 -2 -3 -4

0, 6 3 7 5=6•

Это число можно представить также с помощью схемы Горнера:

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

разряды>-1 -2 -3 -4

0,=

или с помощью схемы Горнера:

0,=.

Умножив это число на р, получаем Если взять целую часть результата, мы получим цифру Таким же способом можно найти оставшиеся цифры дробной части: на каждом шаге умножаем дробную часть на р и запоминаем целую часть результата - это и будет очередная цифра записи числа в системе с основанием р. Например, переведем число 0,9376 в пятеричную систему (табл. 1.)



Таблица 1.

Вычисления	Целая часть	Дробная часть
0,9376•5=4,688	4	0,688
0,688•5=3,44	3	0,44
0,44•5=2,2	2	0,2
0,2•5=1	1	0

Чтобы получить ответ, нужно выписать все целые числа результата, полученные на каждом шаге:

0,9376=

Вычисления заканчиваются, когда при очередном умножении дробная часть результата равна нулю. Это означает, что все остальные цифры дробной части - нули. В любом ли случае это произойдет? К сожалению, нет. Чтобы убедиться в этом, вы можете попробовать перевести в пятеричную систему число 0,3 (должна получиться бесконечная дробь). Такая ситуация может случиться в любой системе счисления (например, вспомните, что число 1/3 записывается в виде бесконечной десятичной дроби). В этом случае обычно задают нужное количество значащих цифр и округляют число соответствующим образом.

Если нужно перевести в некоторую систему счисления число, в котором есть целая и дробная части, эти части переводят отдельно, а потом соединяют. Например, переведем число 25,375 в шестеричную систему:

25,375=25+0,375,

25=, 0,375= > 25,375=.

Двоичная система счисления

В двоичной системе счисления, т.е. в системе с основанием 2, алфавит состоит из двух цифр (0 и 1). Все данные в компьютерных устройствах хранятся и обрабатываются как числа, представленные в двоичной системе счисления.

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

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

.

Теперь выделяем старшую степень двойки в числе 13: это , так что

.

Выделяем старшую степень двойки в числе 5: это , получаем:

.

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

Это развернутая запись числа в двоичной системе счисления, эту запись можно немного упростить:

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

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

Таблица 2

Цифра числа	Вычисления	Результат
1	1	1
0	1•2+0	2
0	2•2+0	4
1	4•2+1	9
1	9•2+1	19
0	19•2+0	38
1	38•2+1	77

Арифметические операции

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

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

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

Вычитание выполняется почти так же, как и в десятичной системе. Вот правила вычисления:

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

Что бы понять принцип, временно возведем к десятичной системе. Вычислим столбик из числа 21 число 9:

Поскольку из 1 нельзя вычисть 9, нужно взять заём из предыдущего разряда, в котором стоит 2. В результате к младшему разряду добавляется 10 (основание системы счисления), а в следующем разряде 2 уменьшатся до 1. Теперь можно выполнить вычитание:

1+10-9=2. В старшем разряде вычитаем из оставшейся единицы ноль:

Здесь точкой сверху обозначен разряд, из которого берется заём. Более сложный случай - заём из дальнего (не ближайшего) разряда. Вычитаем 9 из 2001. В этом случае занять из ближайшего разряда не удается, поэтому берем заём из того разряда, где стоит цифра 2. Все промежуточные разряды в результате заполняются цифрой 9, это старшая цифра десятичной системы счисления:

Что измениться в двоичной системе? Когда берется заем, в «рабочий» разряд добавляется уже не 10, а (основание системы счисления), а все «промежуточные» разряды (между «рабочим» и тем, откуда берется заем) заполняются не девятками, а единицами (старшей цифрой системы счисления). Например:



Если требуется вычесть большее число из меньшего, вычитают меньшее из большего и ставят у результата знак «минус»:

Умножение и деление столбиком в двоичной системе выполняются практически так же, как и в десятичной системе (но с использованием правил двоичного сложения и вычитания):

Дробные числа

Для перевода дробного числа в двоичную систему используется общий подход. В данном случае нужно умножить число на 2, запоминать целую часть и отбрасывать ее пред следующим умножением. Например, для числа 0,8125 получаем (табл. 3):

Таблица 3

Вычисления	Целая часть	Дробная часть
0,8125•2=1,625	1	0,625
0,625•2=1,25	1	0,25
0,25•2=0,5	0	0,5
0,5•2=1	1	0

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

Давайте посмотрим, как храниться в памяти число 0,6. Выполняя умножение на 2 и выделение целой части, мы получим периодическую бесконечную дробь:

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

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

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

Если же все таки нужно обязательно использовать дробные числа и нельзя жертвовать точностью, приходиться хранить их в нестандартном виде, например в виде отношения целых чисел (например, 0,6=6/10), и вычислять отдельно числители и знаменатели простых дробей, переходя к вещественным числам только при выводе конечного результата. Этот подход применяется в системах символьных вычислений, например в программных системах Maple (www.maplesoft.com) и Mathematica (www.wolfram.com). Однако выполнение таких расчетов занимает очень много времени.

Восьмеричная система счисления

Восьмеричная система счисления (система с основанием 8) использовалась для кодирования команд во многих компьютерах 1950-1980-х гг. в ней используются цифры от 0 до 7.

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

Для перевода из восьмеричной системы в десятичную значение каждой цифры умножают на 8 в степени, равной разряду этой цифры, и полученные произведения складываются:

разряды>2 1 0

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

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

Теперь переведем отдельно каждую цифру в двоичную систему:

Подставим эти выражения в предыдущее равенство:

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

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

Алгоритм перевода восьмеричного числа в двоичную систему счисления:

1. Перевести значение каждой цифры (отдельно) в двоичную систему. Записать результат в виде триады, добавив, если нужно, нули в начало (табл. 4).

2. Соединить триады в одно «длинное» двоичное число.

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

Таблица 4

0	000
1	001
2	010
3	011
4	100
5	101
6	110
7	111

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

Алгоритм перевода двоичного числа в восьмеричную систему счисления:

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

2. Перевести каждую триаду (отдельно) в восьмеричную систему счисления.

3. Соединить полученные цифры в одно «длинное» число.

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

Далее по таблице Х переводим каждую триаду в восьмеричную систему:

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

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

В примере на сложение запись 1•8+2 означает, что получилась сумма, большая 7, которая не помещается в один разряд. Единица идет в перенос, а двойка остается в этом разряде. В записи операций при выполнении вычитания запись «-1» означает, что из этого разряда раньше был заем (его значение уменьшилось на 1), а запись «+8» означает заем из старшего разряда.

С помощью восьмеричной системы удобно кратко записывать содержимое областей памяти, содержащих количество битов, кратное трем. Например, 6-битные данные «упаковываются» в две восьмеричные цифры. Некоторые компьютеры 1960-х годов использовали 24-битные и 36-битные данные, они записывались соответственно с помощью 8 и 12 восьмеричных цифр. Восьмеричная система использовалась даже для компьютеров с 8-битной ячейкой памяти, но позднее была почти вытеснена шестнадцатеричной системой.

Сейчас восьмеричная система применяется, например, для установки прав на доступ к файлу в операционной системе Linux (и других Unix-системах) с помощью команды chmod. Режим доступа кодируется тремя битами, которые разрешают чтение (r, read, старший бит), запись (w, write) и выполнение файла (x, execute, младший бит). Код (rwx) означает, что все биты установлены ( полный доступ), а код (r-x) разрешает чтение и выполнение файла, но запрещает его изменение.

Шестнадцатеричная система счисления

Шестнадцатеричная система счисления ( позиционная система с основанием 16) широко используется для записи адресов и содержимого ячеек памяти компьютера. Ее алфавит содержит 16 цифр, вместе с 10 арабскими цифрами (0…9) используются первые буквы латинского алфавита:

А=10, В=11, С=12, D=13, E=14, F=15.

Таким образом, старшая цифра в шестнадцатеричной системе - F.

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



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

разряды>2 1 0

Можно так же использовать схему Горнера:

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

Таблица 5

Шестнадцатеричные числа	Двоичные числа	Шестнадцатеричные числа	Двоичные числа
0	0000	8	1000
1	0001	9	1001
2	0010	A(10)	1010
3	0011	B(11)	1011
4	0100	C(12)	1100
5	0101	D(13)	1101
6	0110	E(14)	1110
7	0111	F(15)	1111

Алгоритм перевода шестнадцатеричного числа в двоичную систему счисления:

1. Перевести значение каждой цифры (отдельно) в двоичную систему. Записать результат в виде тетрады, добавив, если нужно, нули в начало (табл. 5).

2. Соединить тетрады в одно «длинное» двоичное число.

Например, переведем в двоичную систему число (здесь показана разбивка на тетрады):

.

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

Алгоритм перевода двоичного числа в восьмеричную систему счисления:

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

2. Перевести каждую тетраду (отдельно) в шестнадцатеричную систему счисления.

3. Соединить полученные цифры в одно «длинное» число.

Например:

.

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

0	1	0	1	1	1	1	0
5	Е

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

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

При выполнении сложения нужно помнить, что в системе с основанием 16 перенос появляется тогда, когда сумма в очередном разряде превышает 15. Удобно сначала переписать исходные числа, заменив все буквы на их численные значения:

При вычитании заем из старшего разряда равен , а все «промежуточные» разряды заполняются цифрой F - старшей цифрой системы счисления:



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

.

Теперь сложим числа в 16-ричной системе: и переведем результат в двоичную систему:

.

Другие системы счисления

Троичная уравновешенная система счисления

В истории компьютерной техники применялись и другие системы счисления. Например, в 1958г. была создана электронная вычислительная машина (ЭВМ) «Сетунь» (главный конструктор - Н. П. Брусенцов), которая использовала троичную систему счисления. Всего в 1960-х гг. было выпущено более 50 промышленных образцов ЭВМ «Сетунь».

В троичной уравновешенной системе основание равно 3, используются три цифры: 1(«минус 1»), 0 и 1. Один троичный разряд называется тритом ( в отличии от двоичного бита). Система называется уравновешенной, потому что с помощью любого числа разрядов можно закодировать равное число положительных и отрицательных чисел, и число ноль. В таблице 6 показаны, например, все двухразрядные числа.

Таблица 6

-4
-3	0
-2	1
-1
0	00
1	01
2
3	10
4	11

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

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

Троичная уравновешенная система счисления дает ключ к решению задачи Баше, которая была известна еще в XIII веке Леонардо Пизанскому (Фибоначчи):

Найти такой набор из 4 гирь, чтобы с их помощью на чашечках равноплечных весов можно было взвесить груз массой от 1 до 40 кг включительно. Гири можно располагать на любой чаше весов.

Каждая гиря может быть в трех состояниях:

1. Лежать на той же чаше весов, что и груз: в этом случае ее вес вычисляется из суммы

2. Не участвовать во взвешивании (0);

3. Лежать на другой чаше: ее вес добавляется к сумма (1).

Поэтому веса гирь нужно выбрать равными степенями числа 3, т.е. 1,3,9 и 27 кг.

Двоично-десятичная система счисления

Существует еще один простой способ записи десятичных чисел с помощью цифр 0 и 1. Этот способ называется двоично-десятичной системой (ДДС), это нечто среднее между двоичной и десятичной системами. На английском языке такое кодирование называется binary coded decimal (BCD) - десятичные числа, закодированные двоичными цифрами.

В ДДС каждая цифра десятичного числа записывается двоичными знаками. Но среди цифр 0-9 есть такие, которые занимают 1, 2, 3 и 4 двоичных разряда. Чтобы запись числа была однозначной и не надо было искать границу между цифрами, на любую цифру отводят 4 бита. Таким образом, 0 записывается как 0000, а 9 - как 1001. Например:

При обратном переводе из ДДС в десятичную систему надо учесть, что каждая цифра занимает 4 бита, и добавить недостающие нули:

Важно помнить, что запить числа в ДДС не совпадает с его записью в двоичной системе:

;

Использование ДДС дает следующие преимущества:

· двоично-десятичный код очень легко переводить в десятичный, например, для вывода результата на экран;

· просто выполняется умножение и деление на 10, а также округление;

· конечные десятичные дроби записываются точно, без ошибки, так что вычисления в ДДС (вместо двоичной системы) дадут тот же результат, что и ручной расчет человека «на бумажке»; поэтому ДДС используется в калькуляторах.

Есть, однако, и недостатки:

· хранение чисел в ДДС требует больше памяти, чем стандартный двоичный код;

· усложняются арифметические операции.

Дидактические единицы и последовательность их изучения

Таблица 7

Тема	Дидактические единицы
Системы счисления	История появления систем счисления. Классификация систем счисления. Позиционные и непозиционные системы счисления
Позиционные системы счисления	Основные понятия. Формы представления числа. Алгоритм перевод числа из любой позиционной системы в десятичную систему. Алгоритм перевода дробных чисел из десятичной системы счисления в р-ричную.
Двоичная система счисления	Основные понятия. Алгоритм перевода натуральных чисел из десятичной системы счисления в двоичную. Алгоритм перевода из двоичной системы в десятичную. Арифметические операции с числами в двоичной системе счисления. Алгоритм перевод дробного числа в двоичную систему. Достоинства и недостатки двоичной системы счисления.
Восьмеричная система счисления	Основные понятия. Алгоритм перевода в восьмеричную систему счисления из других систем и наоборот. Арифметические вычисления в восьмеричной системе. Достоинства восьмеричной системы счисления.
Шестнадцатеричная система счисления	Основные понятия. Алгоритм перевода чисел в шестнадцатеричную систему счисления и наоборот. Арифметические операции в шестнадцатеричной системе счисления.
Другие системы счисления	Описание троичной уравновешенной системы счисления. Описание двоично-десятичной системы счисления. Преимущества и недостатки ДДС.

2. Типовые задачи по разделу «Системы счисления»

Изучив материал по разделу «Системы счисления», учебника К.Ю. Полякова, Е.А. Еремина «Информатика» профильный уровень, ученик должен уметь решать типовые задачи по данному раздела. Ниже представлены типовые задачи по данному разделу.

Задача 1: Как представлено число в двоичной системе счисления?

Решение: Достаточно выполнить перевод заданного числа в двоичную систему счисления путем последовательного деления «в столбик» на 2:

Задача 2: Чему равно количество значащих нулей в двоичной записи десятичного числа 126.

Решение:

1. Число переводиться в двоичную систему счисления: .

2. Подсчитывается количество значащих нулей в двоичной записи числа: 1 нуль.

Ответ: 1 нуль

Задача 3: Сколько единиц в записи десятичного числа 194,5?

Решение:

1. Число переводиться в двоичную систему счисления:

- целая часть числа: ;

- дробная часть числа: ;

-.

2. Подсчитывается количество единиц в двоичной записи числа: 4 единицы.

Ответ: 4 единицы.

Задача 4: Вычислить значение суммы в двоичной системе счисления.

Решение:

1. Перевод всех чисел в десятичную систему счисления (для упрощения):

- ;

-;

- =16;

2. Выполняются вычисления: 2+8+16=26.

3. Перевод результата вычислений в двоичную систему:

Ответ: .

Задача 5: В системе счисления с некотором основанием число 12 записывается в виде 110. Укажите это основание.

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



.

Неизвестное основание системы счисления обозначается буквой n и записывается уравнение на основе имеющихся данных:

.

В результате получается достаточно простое квадратное уравнение:

,

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

D=;

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

Ответ: 3.

Задача 6: Указать через запятую в порядке возрастания все основания системы счисления, в которых запись числа 22 оканчивается на 4.

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



Потребуется только первый шаг преобразования «канонической» записи формулу Горнера:

В этой записи - исходное десятичное число (d); цифра, которой должна заканчиваться запить числа в искомой системе счисления (; основание системы счисления (n) и некоторый сомножитель n, который обозначается, например, как x:

.

Отсюда выражается искомое значение n:

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

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

В задаче дано исходное десятичное число 22 и указанно, что его запись должна заканчиваться цифрой 4. Следовательно, n должно быть больше 4. Кроме того, можно записать:

,

т.е. требуется найти значения х, кратные 18. Очевидно, что значения 1,2,3,6,9 и 18. Но, как уже было сказано выше, значение n должно быть больше 4. Поэтому из всей найденной подборки подходят только значения 6,9 и 18.

Ответ: 6,9 и 18.

3. Теоретический минимум и типовые задания для подготовки в ЕГЭ по разделу «Системы счисления»

Анализируя задания ЕГЭ по разделу «Системы счисления» можно определить тот минимум теории, который нужен для подготовки к ЕГЭ по разделу «Системы счисления». Для того что бы удачно подготовиться к ЕГЭ по информатике по разделу «Системы счисления» необходимо уметь:

1. Переводить числа из одной системы счисления в другую;

2. Арифметические действия в системах счисления с основанием 2-8-16;

3. Представлять целые числа в памяти компьютера;

4. Совершать операции с числами вида

5. Определять количество появлений некоторой цифры в записи числа в системах счисления с известным основанием;

6. Определять неизвестное в уравнении, в котором числа в разных системах счисления;

7. Определять основание системы счисления из уравнения с одним неизвестным;

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

9. Определять основание системы счисления, если известна последняя цифра числа и количество разрядов числа;

10. Определять основание системы счисления, если известно только количество разрядов в числе;

11. Определять основание системы счисления, если известен последний знак в представлении числа;

12. Определять основание системы счисления, если известны два первых знака в представлении числа.

13. Искать основание системы счисления, если известны два последних знака в представлении числа;

14. Искать числа, в записи которых известны два последних знака в представлении числа и известно основание системы счисления;

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

Основные понятия

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

Система счисления включает в себя: алфавит, т. е. набор символов для записи чисел, способ записи чисел, способ чтения чисел. Они делятся на два класса: позиционные и непозиционные

Позиционные системы счисления - это системы, в которых величина цифры определяется ее положением (позицией) в числе.

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

Например: двоичная система счисления (А₂ ), восьмеричная система счисления (А₈) т.д.

Непозиционные системы счисления - это системы, в которых величина цифры не определяется ее положением (позицией) в числе.

Например: римская система счисления (II, V, XII)

Примеры наиболее часто используемых систем счисления (см.табл. 8):

Таблица 8

Система счисления	Основание	Алфавит системы счисления	Пример записи числа
Двоичная	2	0,1
Восьмеричная	8	0,1,2,3,4,5,6,7
Десятичная	10	0,1,2,3,4,5,6,7,8,9
Шестнадцатеричная	16	0,1,2,3,4,5,6,7,8,9, А(=10), В(=11), C(=12), D(=13), E(=14), F(=15)

Формы записи чисел в различных системах счисления

Свернутая («обычная») форма записи числа - привычная запись числа как последовательности цифр, стоящих на своих разрядах.

Развернутая форма записи числа - запись числа в виде суммы произведений его цифр на основание системы счисления в степени, равной значению разряда той или иной цифры числа.

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



Таблица соответствия чисел в различных системах счисления

Таблица 9

Десятичное число	Двоичное число	Восьмеричное число	Шестнадцатеричное число
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F
16	10000	20	10
17	10001	21	11
18	10010	22	12
19	10011	23	13
20	10100	24	14
…	…	…	…

Перевод числа из одной системы счисления в другую

Алгоритм перевода чисел из десятичной системы счисления в любую позиционную систему счисления с основанием q (2, 8, 16):

1. Разделить число на основание системы счисления нацело (остаток должен быть меньше основания).

2. Если частное больше основания системы счисления, то повторить шаг 1.

3. Если частное меньше основания, то записать число из остатков, начиная с последнего частного, справа налево.

Алгоритм перевода целого числа из системы счисления с основанием q (2, 8, 16) в десятичную систему счисления:

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

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

3. Суммировать все произведения.

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

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

Представление десятичной дроби в недесятичной системе счисления, как правило, является приближенным.

Перевод вещественного десятичного числа в недесятичную систему счисления выполняется в два этапа:

1. Отдельно осуществляется перевод целой части числа путем последовательности делений на основание системы счисления;

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

Запись целой части числа в искомой системе счисления дополняется справа запятой и записью дробной части в искомой системе счисления.

Перевод чисел между недесятичными системами счисления обычно удобнее всего производить через десятичную систему счисления:

1. Перевести исходное число в десятичную систему счисления;

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

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

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

- исходное двоичное число разбивается на группы по три цифры («триады») справа налево; при необходимости крайняя слева группа цифр дополняется незначащими нулями слева;

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

Таблица 10

Двоичная триада	000	001	010	011	100	101	110	111
Восьмеричная значение	0	1	2	3	4	5	6	7

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

- исходное восьмеричное число разбивается на отдельные цифры;

- каждая восьмеричная цифра заменяется соответствующей ей триадой двоичных цифр по таблице (табл. 10);

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

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

- исходное двоичное число разбивается на группы по четыре цифры («тетрады») справа налево; при необходимости крайняя слева группа цифр дополняется незначащими нулями слева;

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

Таблица 11

Двоичная тетрада	0000	0001	0010	0011	0100	0101	0110	0111
Шестнадцатеричное значение	0	1	2	3	4	5	6	7
Двоичная тетрада	1000	1001	1010	1011	1100	1101	1110	1111
Шестнадцатеричное значение	8	9	А	В	С	D	E	F

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

- исходное шестнадцатеричное число разбивается на отдельные цифры;

- каждая шестнадцатеричная цифра заменяется соответствующей ей тетрадой двоичных цифр по таблице (таблица 11);

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

Пример 1. Перевести число 124 из 10-ой системы счисления в 2-ую систему.

Решение: Чтобы число 124 перевести из 10- ой системы счисления в 2-ую надо это число 124 делить на 2 (основание системы счисления) до тех пор, пока остатком деления не окажется число меньше 2 (1 или 0) .



Выписываем все остатки (справа налево) начиная с частного, следовательно:

.

Ответ: .

Пример 2. Перевести число 1001 из 2-ой системы счисления в 10-ую.

Решение: Для того, чтобы перевести число 1001 из 2-ой системы счисления в 10-ую, надо представить его в виде суммы произведений цифры на основание в степени, равной номеру разряда. (при разложении целых чисел нумерация разрядов идет справа налево, начиная с «0»)

Получаем, что

Ответ:

Пример 3. Перевести число 124 из 10-ой системы счисления в 8-ую.

Решение: Чтобы число 124 перевести из 10-ой системы счисления в 8-ую надо это число делить на 8 (основание системы счисления) до тех пор, пока остатком деления не окажется число меньше 8 (0, 1, 2, 3, 4, 5, 6, 7) .



Выписать все остатки (справа налево) начиная с частного, следовательно

.

Ответ:

Пример 4. Перевести число 395 из 10-ой системы счисления в 16-ую.

Решение: Чтобы число 395 перевести из 10-ой в 16-ую систему счисления надо это число делить на 16 (основание системы счисления) до тех пор, пока остатком деления не окажется число меньше 16 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F).

Далее нужно выписать все остатки (справа налево) начиная с частного, следовательно

Ответ:

Пример 5. Перевести число 613 из 8-ой системы счисления к 10-ую.

Решение: Для того, чтобы перевести число 613 из 8-ой системы счисления в 10-ую, надо представить его в виде суммы произведений цифры на основание в степени, равной номеру разряда. (при разложении целых чисел нумерация разрядов идет справа налево, начиная с «0»)

Получаем, что .

Ответ:

Пример 6. Перевести число A7F5 из 16-ой системы счисления в 10-ую.

Решение: Для того, чтобы перевести число A7F5 из 16-ой системы счисления в 10-ую, надо представить его в виде суммы произведений цифры на основание в степени, равной номеру разряда. (при разложении целых чисел нумерация разрядов идет справа налево, начиная с «0»)

Получается .

Ответ:

Арифметические действия в системах счисления с основаниями 2, 8, 16

Примечание:

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

- Если выполнять арифметические действия с системами счисления, основание которых больше 10 и в примере встретилась буква, мысленно нужно заменить её цифрой в десятичной системе, после проведения необходимых операций нужно перевести результат обратно в исходную систему счисления.

Сложение:

Складывать легче всего в «столбик» (как и 10-ые числа), разряд с разрядом.

Если при сложении в разряде получалось число больше 9, то его нужно вычесть из 10, полученный результат записать в ответ, а 1 прибавить к следующему разряду. Полученный результат записать в нужный разряд.

Пример 1. Найти сумму чисел 1001001110 и 100111101 в двоичной системе счисления.

Решение: Для того что бы удобнее было складывать данные числа, следует записать эти числа «столбиком», разряд под разрядом:

1001001110

+ 100111101

1110001011

Нужно помнить:

1+0=1

1+1=10 («0» пишем «1» переходить в следующий разряд)

1+1+1=11 («1» пишем «1» переходит в следующий разряд)

Ответ: .

Пример 2. Найти сумму чисел 1254,2 и 1150,54 в восьмеричной системе.

Решение: Не целые числа складываются так же как и в 10-ой системе счисления. Нужно записать данные числа «в столбик» разряд под разрядом. В конце первого числа нужно добавить «0», для удобства вычисления.

1254,20

+1150,54

2424,74

Вычисления:

0+4=4

2+5=7

4+0=4

5+5= («2» пишем, «1» переходит в следующий разряд)

2+1+1=4

1+1=2

Ответ:

Пример 3. Найти сумму чисел 2Е1,8 и 19А,4 в 16-ой системе счисления.

Решение: Вычисления производятся аналогично предыдущему примеру.

2Е1,8

+ 19А,4

47В,С

Вычисления:

8+4=

1+А=1+10=

Е+9=14+9=

2+1+1=4

Ответ:

Вычитание:

Вычитание в системах счисления с основаниями 2,816, производиться по тому же принципу что и в 10-ой системе счисления. Если при вычитании в разряде получалось число меньше 0, то нужно «занять» единицу из старшего разряда и прибавить к нужной цифре (зависит он основания системы счисления), и вычитать из нового числа.

Пример 1. Найти разность чисел 100100 и 10111 в 2-ой системе счисления.

Решение: Для удобства вычисления нужно записать числа «в столбик», разряд под разрядом, как при вычитании 10-ых чисел.

100100

- 10111

001101

Вычисление:

0-1=1 занимаем из старшего разряда «2», так как вычислени...