ДВОИЧНО-ДЕСЯТИЧНАЯ СИСТЕМА
Двоично-десятичная система счисления. Десятичные цифры от 0 до 9 заменяются представляющими их двоичными тетрадами: 0=0000, 1=0001, 2=0010, 3=0011, 4=0100, 5=0101, 6=0110, 7=0111, 8=1000 и 9=1001. Такая запись очень часто используется как промежуточный этап перевода числа из десятичной системы в двоичную или обратно. Так как 10 не является точной степенью 2, то используются не все 16 тетрад, а алгоритмы арифметических операций над многозначными числами здесь более сложны, чем в основных системах счисления. И тем не менее, двоично-десятичная система счисления применяется даже на этом уровне во многих микрокалькуляторах и некоторых компьютерах (в частности, «Ямаха» стандарта MSX).
Поскольку человеку наиболее привычны представление и арифметика в десятичной системе счисления, а для компьютера — двоичное представление и двоичная арифметика, была введена компромиссная система двоично-десятичной записи чисел. Такая система чаще всего применяется там, где существует необходимость частого использования процедуры десятичного ввода-вывода. (электронные часы, калькуляторы, АОНы, и т.д.). В таких устройсвах не всегда целесообразно предусматривать универсальный микрокод перевода двоичных чисел в десятичные и обратно по причине небольшого объема программной памяти.
Принцип построения этой системы достаточно прост: каждая десятичная цифра преобразуется прямо в свой десятичный эквивалент из 4 бит, например: 369110=0011 0110 1001 0001DEC:
Десятичное число 3 6 9 1 Двоично-десятичное число 0011 0110 1001 0001
Преобразуем двоично-десятичное число 1000 0000 0111 0010 в его десятичный эквивалент. Каждая группа из 4 бит преобразуется в её десятичный эквивалент. Получим 1000 0000 0111 0010DEC = 807210:
Двоично-десятичное число 1000 0000 0111 0010 Десятичное число 8 0 7 2
Микропроцессоры используют чистые двоичные числа, однако понимают и команды преобразования в двоично-десятичную запись. Полученные двоично-десятичные числа легко представимы в десятичной записи, более понятной людям.
Преобразование двоичных чисел в двоично-десятичные
Арифметико-логическое устройство AVR-микроконтроллеров (как и других микропроцессоров) выполняет элементарные арифметические и логические операции над числами, представленными в двоичном коде. В двоичном коде считываются результаты преобразования АЦП, в двоичном коде (в формате целых чисел или чисел с плавающей точкой) удобно выполнять обработку результатов измерения. Однако, когда окончательный результат отображается на индикаторе, он должен быть преобразован в десятичный формат, удобный для восприятия человеком.
В данном разделе рассматриваются программы преобразования двоичных чисел в двоично-десятичные.
1. Форматы представления десятичных чисел
В настоящее время распространены два формата представления десятичных чисел в микропроцессорах — упакованный двоично-десятичный код (BCD-Binary-Coded Decimal) и неупакованный десятичный код [1].
Упакованный BCD-код — это такое представление десятичного числа, когда каждая десятичная цифра представляется 4-х битным двоичным позиционным кодом 8-4-2-1. При этом байт содержит две десятичные цифры. Младшая десятичная цифра занимает правую тетраду (биты 3 : 0), старшая — левую тетраду (биты 7 : 4). Многоразрядные BCD-числа занимают несколько смежных байт. Если число является знаковым, то для представления знака в BCD-формате отводится старшая тетрада старшего байта. Для кодирования знака можно использовать шесть двоичных кодовых комбинаций, которые не используются для представления десятичных цифр. Это коды 1010-1111 (A-F в шестнадцатеричном представлении). Обычно для кодирования знака плюс применяют код 1100 (С), а для знака минус — 1101 (D).
Неупакованный десятичный код является подмножеством международной таблицы кодирования символов ASCII (Таблица 1). Видно, что для хранения неупакованных десятичных чисел требуется в два раза больше памяти, так как каждая цифра представляется 8-битным кодом. Таблица 1: ASCII-коды десятичных цифр
2. Преобразование целых 16-битных чисел в двоично-десятичные числа
На сайте www.atmel.com предлагается программа «bin2bcd16» для преобразования целых 16-битных двоичных чисел в двоично-десятичные упакованные числа. В данной статье рассматривается программа «bin16bcd5» (см. Приложение, Программа 1), написанная Терешкиным А. В. согласно алгоритму, изложенному в [1], и выполняющая ту же задачу. Последняя программа по быстродействию, длине кода и количеству используемых регистров оказалась более эффективной, чем первая.
Алгоритм программы «bin16bcd5» заключается в следующем. Предположим, что имеется целое беззнаковое 16-битное число (диапазон от 0 до 65535). Очевидно, что необходимо найти 5 десятичных цифр. Способ преобразования заключается в том, чтобы, вычитая из исходного числа число 10000, сначала определить десятичную цифру десятков тысяч. Затем находится цифра тысяч последовательным вычитанием числа 1000 и т. д. Вычитание каждый раз производится до получения отрицательной разности с подсчетом числа вычитаний. При переходе к определению каждого следующего десятичного разряда в регистрах исходного числа восстанавливается последняя положительная разность. После того, как будет найдена десятичная цифра десятков, в регистрах исходного числа останется десятичная цифра единиц.
Программа «bin16ASCII5» (см. Приложение, Программа 2) преобразует целое двоичное 16-битное число в десятичное неупакованное число. При этом используется тот же алгоритм.
3. Преобразование двоичной дроби в двоично-десятичную дробь
Двоичная дробь, по определению, представляется следующим выражением:
0.A-1A-2 . A-m = A-1*2-1 + A-2*2-2 + . A-m*2-m
Из этого представления следует алгоритм преобразования (Рис. 2), который содержит m шагов. На каждом шаге к двоично-десятичному результату прибавляется очередная двоичная цифра и весь результат делится на 2.
На изображены двоичный регистр, который содержит исходную двоичную дробь и регистр двоично-десятичного упакованного результата. Для наглядности у обоих регистров также показаны разряд единиц и положение точки, которые в памяти микропроцессора никак не представлены, но положение которых всегда строго оговорено. Количество циклов рассматриваемого алгоритма равно количеству бит двоичной дроби. Разрядность двоично-десятичного регистра определяется требуемой точностью вычислений.
Сложить эту цифру с двоично-десятичным числом означает, что ее нужно поместить в разряд единиц двоично-десятичного числа, откуда при последующем делении на два цифра A-i сдвинется в старший разряд старшей тетрады десятичной дроби. При программировании мы можем представлять, что разрядом единиц десятичной дроби является бит переноса С.
При делении на два двоично-десятичного упакованного числа, так же как и при делении двоичного числа, его сдвигают вправо на один разряд. При этом на два делится каждая тетрада, то есть каждая десятичная цифра. При делении четной десятичной цифры в соответствующем разряде снова получается десятичная цифра, и никакой коррекции не требуется. При делении на 2 нечетной десятичной цифры остаток, равный 5, должен быть добавлен к более младшему десятичному разряду, но на самом деле при двоичном сдвиге в более младшую тетраду добавляется число 8 (вес старшего разряда тетрады). Поэтому требуется коррекция результата, которая заключается в вычитании числа 3 из содержимого тех тетрад, которые после сдвига вправо имеют установленные старшие разряды.
4. Преобразование чисел с плавающей точкой в двоично-десятичные числа
Представление чисел с плавающей точкой имеет следующий вид:
где М — двоичная мантисса числа, П — двоичный порядок числа.
Такое представление часто используется и в десятичной системе счисления для представления очень больших или очень малых чисел. Мантисса и порядок представляют собой целые знаковые числа. Знак мантиссы является знаком всего числа. Порядок показывает истинное положение точки вместо того, которое она занимает в изображении мантиссы. Двоичное число с плавающей точкой отличается от привычного нам десятичного тем, что точка является двоичной, то есть порядок показывает на количество двоичных (а не десятичных) разрядов, на которое необходимо переместить эту точку влево или вправо.
Нормализованным представлением числа с плавающей точкой называют такое представление, когда мантисса является правильной дробью, и старшая ее цифра отличается от нуля. Но для двоичного числа требование того, что старшая цифра отличается от нуля означает, что эта цифра равна 1. Если старшая цифра точно известна, то ее можно не хранить в памяти.
Кодирование чисел. Системы счисления.
· чтобы перевести число, скажем, 12345N, из системы счисления с основанием в десятичную систему, нужно умножить значение каждой цифры на в степени, равной ее разряду:
4 3 2 1 0 ← разряды
1 2 3 4 5N = 1·N 4 + 2·N 3 + 3·N 2 + 4·N 1 + 5·N 0
· последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на
· две последние цифры – это остаток от деления на , и т.д.
· число 2 N в двоичной системе записывается как единица и N нулей:
· число 2 N — 1 в двоичной системе записывается как N единиц:
· число 2 N – 2 K при K < N в двоичной системе записывается как N–K единиц и K нулей:
· поскольку , получаем , откуда следует, что
Пример задания:
Р-21. Сколько значащих нулей в двоичной записи числа 4 512 + 8 512 – 2 128 – 250
Решение (способ Е.А. Смирнова, Нижегородская область):
1) Общая идея: количество значащих нулей равно количеству всех знаков в двоичной записи числа (его длине!) минус количество единиц
2) приведём все числа к степеням двойки, учитывая, что 250 = 256 – 4 – 2 = 2 8 – 2 2 – 2 1 :
4 512 + 8 512 – 2 128 – 250 = (2 2 ) 512 + (2 3 ) 512 – 2 128 – 2 8 + 2 2 + 2 1 =
= 2 1536 + 2 1024 – 2 128 – 2 8 + 2 2 + 2 1
3) старшая степень двойки – 2 1536 , двоичная запись этого числа представляет собой единицу и 1536 нулей, то есть, состоит из 1537 знаков; таким образом, остаётся найти количество единиц
4) вспомним, число 2 N –2 K при K < N записывается как N–K единиц и K нулей:
5) для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2 N –2 K , причём в этой цепочке степени двойки нужно выстроить по убыванию
6) в нашем случае вы выражении
2 1536 + 2 1024 – 2 128 – 2 8 + 2 2 + 2 1
стоит два знака «минус» подряд, это не позволяет сразу использовать формулу
7) используем теперь равенство , так что – 2 128 = – 2 129 + 2 128 ; получаем
2 1536 + 2 1024 – 2 129 + 2 128 – 2 8 + 2 2 + 2 1
здесь две пары 2 N –2 K , а остальные слагаемые дают по одной единице
8) общее число единиц равно 1 + (1024 – 129) + (128 – 8) + 1 + 1 = 1018
9) таким образом, количество значащих нулей равно 1537 – 1018 = 519
Ещё пример задания:
Р-20. Сколько единиц в двоичной записи числа 4 2015 + 8 405 – 2 150 – 122
Решение (способ Е.А. Смирнова, Нижегородская область):
11) приведём все числа к степеням двойки, учитывая, что 122 = 128 – 4 – 2 = 2 7 – 2 2 – 2 1 :
4 2015 + 8 405 – 2 150 – 122 = (2 2 ) 2015 + (2 3 ) 405 – 2 150 – 2 7 + 2 2 + 2 1 = 2 4030 + 2 1215 – 2 150 – 2 7 + 2 2 + 2 1
12) вспомним, число 2 N –2 K при K < N записывается как N–K единиц и K нулей:
13) для того чтобы использовать это свойство, нам нужно представить заданное выражение в виде пар вида 2 N –2 K , причём в этой цепочке степени двойки нужно выстроить по убыванию
14) в нашем случае вы выражении
2 4030 + 2 1215 – 2 150 – 2 7 + 2 2 + 2 1
стоит два знака «минус» подряд, это не позволяет сразу использовать формулу
15) используем теперь равенство , так что – 2 150 = – 2 151 + 2 150 ; получаем 2 4030 + 2 1215 – 2 151 + 2 150 – 2 7 + 2 2 + 2 1 здесь две пары 2 N –2 K , а остальные слагаемые дают по одной единице
16) общее число единиц равно 1 + (1215 – 151) + (150 – 7) + 1 + 1 = 1210
Ещё пример задания:
Р-19. Решите уравнение .
Ответ запишите в троичной системе счисления. Основание системы счисления указывать не нужно.
Решение:
1) переведём все числа в десятичную систему счисления:
2) собирая всё в одно уравнение получаем
3) это уравнение имеет два решения, 6 и -8; основание системы счисления – натуральное число, поэтому ответ – 6
4) переводим ответ в троичную систему: 6 = 2?3 1 = 203.
Ещё пример задания:
Р-18. Сколько единиц в двоичной записи числа 4 2014 + 2 2015 – 8
Решение:
1) приведём все числа к степеням двойки:
4 2014 + 2 2015 – 8 = (2 2 ) 2014 + 2 2015 – 2 3 = 2 4028 + 2 2015 – 2 3
2) вспомним, что число 2 N -1в двоичной системе записывается как N единиц: ,
а число 2 N –2 K при K < N записывается как N–K единиц и K нулей:
3) согласно п. 2, число 2 2015 – 2 3 запишется как 2012 единиц и 3 нуля
4) прибавление 2 4028 даст ещё одну единицу, всего получается 2012 + 1 = 2013 единиц
Ещё пример задания:
Р-17. Сколько единиц в двоичной записи числа 4 2016 + 2 2018 – 8 600 + 6
Решение:
1) приведём все числа к степеням двойки, разложив 6 как 2 2 +2 1 4 2016 + 2 2018 – 8 600 + 6 = (2 2 ) 2016 + 2 2018 — (2 3 ) 600 + 2 2 + 2 1 = 2 4032 + 2 2018 – 2 1800 + 2 2 + 2 1
2) вспомним, что число 2 N -1в двоичной системе записывается как N единиц: ,
3) согласно п. 2, число 2 2018 – 2 1800 запишется как 218 единиц и 1800 нулей
4) прибавление 2 4032 даст ещё одну единицу, а прибавление 2 2 + 2 1 – ещё две, всего получается 218 + 3 = 221 единица
Ещё пример задания:
Р-16. Сколько единиц в двоичной записи числа 4 2016 – 2 2018 + 8 800 – 80
Решение:
1) приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4
4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 + (2 3 ) 800 – 2 2 – 2 1 = 2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4
2) перестроим слагаемые в порядке уменьшения степеней двойки
2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4
3) вспомним, что число 2 N -1в двоичной системе записывается как N единиц: ,
а число 2 N –2 K при K < N записывается как N–K единиц и K нулей:
4) согласно п. 2, число 2 2400 – 2 2018 запишется как 382 единицы и 2018 нулей
5) добавляем старшее слагаемое 2 4032 , получаем число 2 4032 + 2 2400 – 2 2018 , в котором 383 единицы и в конце (после последней единицы) – 2018 нулей:
6) выделим из этого значения последнюю единицу со следующими 2018 нулями как отдельное слагаемое (число 2 2018 ):
где число K содержит 382 единицы в старших разрядах; таки образом, интересующее нас число равно
7) согласно п. 2, число 2 2018 – 2 6 запишется как 2012 единиц и 6 нулей; также выделим последнюю единицу с последующими нулями как отдельное слагаемое:
где число L содержит 2011 единиц
8) теперь остаётся найти, сколько единиц будет в двоичной записи числа 2 6 – 2 4 , согласно п. 2 находим, что оно содержит 2 единицы
9) таким образом, общее число единиц равно 382 + 2011 + 2 = 2395
Решение (способ 2, Е.А. Смирнов, Нижегородская область):
1) приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4 4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 + (2 3 ) 800 – 2 2 – 2 1 = 2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4
2) перестроим слагаемые в порядке уменьшения степеней двойки 2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4
3) представим – 2 2018 = – 2 2019 + 2 2018 и – 2 6 = – 2 7 + 2 6 2 4032 + 2 2400 – 2 2019 + 2 2018 – 2 7 + 2 6 – 2 4
4) слагаемое 2 4032 в двоичной записи содержит 1 единицу
5) слагаемое 2 2400 – 2 2019 содержит 381 единицу (число 2 N –2 K при K < N в двоичной системе записывается как N–K единиц и K нулей: )
6) слагаемое 2 2018 – 2 7 содержит 2011 единиц, слагаемое 2 6 – 2 4 содержит 2 единицы
7) позиции единиц во всех этих слагаемых не совпадают, поэтому общее количество единиц равно 1 + 381 + 2011 + 2 = 2395
Решение (способ 3, А.И. Козлов, г. Северобайкальск):
1) приведём все числа к степеням двойки, разложив 80 как 2 6 +2 4
4 2016 – 2 2018 + 8 800 – 80 = (2 2 ) 2016 – 2 2018 + (2 3 ) 800 – 2 2 – 2 1 = 2 4032 – 2 2018 + 2 2400 – 2 6 – 2 4
2) перестроим слагаемые в порядке уменьшения степеней двойки
2 4032 + 2 2400 – 2 2018 – 2 6 – 2 4
3) выражение 2 2400 –2 4 дает 2396 единиц и 4 нолика в конце, откуда вычеркиваем (заменяем на ноль) единичку, стоящую на седьмом месте справа (2 6 ) и, соответственно на 2019 месте справа (2 2018 ). Следовательно, остается 2394 единички.
4) С учетом того, что 2 4032 дает нам одну единицу, в итоге получаем 2395 единиц
Ещё пример задания:
Р-15. Решите уравнение . Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.
Решение:
1) удобнее всего перевести все числа в десятичную систему, решить уравнение и результат перевести в шестеричную систему
3) уравнение приобретает вид , откуда получаем
4) переводим 15 в шестеричную систему счисления:
Ещё пример задания:
Р-14. Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?
Решение:
6) если запись числа в системе счисления с основанием N заканчивается на 0, то это число делится на N нацело
7) поэтому в данной задаче требуется найти наименьшее натуральное число, которое делится одновременно на 3 и на 5, то есть, делится на 15
8) очевидно, что это число 15.
Ещё пример задания:
Р-13. Запись числа 6710 в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления N.
Решение:
9) поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа 67 на N равен 1, то есть при некотором целом имеем
10) следовательно, основание N – это делитель числа 66
11) с другой стороны, запись числа содержит 4 цифры, то есть
12) выпишем кубы и четвертые степени первых натуральных чисел, которые являются делителями числа 66:
13) видим, что из этого списка только для числа N = 3 выполняется условие
14) таким образом, верный ответ – 3.
15) можно сделать проверку, переведя число 67 в троичную систему 6710 = 21113
Еще пример задания:
Р-12. Запись числа 38110 в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N.
Решение:
1) поскольку запись в системе счисления с основанием N заканчивается на 3, то остаток от деления числа 381 на N равен 3, то есть при некотором целом имеем
2) следовательно, основание N – это делитель числа
3) с другой стороны, запись числа содержит 3 цифры, то есть
4) неравенство дает (так как )
5) неравенство дает (так как )
6) таким образом, ; в этом диапазоне делителями числа 378 являются числа
· 9, при получаем запись числа
· 14, при получаем запись числа
· 18, при получаем запись числа
7) наибольшим из приведенных чисел – это 18 (можно было сразу искать подбором наибольший делитель числа 378, начиная с 19 «вниз», на уменьшение)
8) таким образом, верный ответ – 18.
Еще пример задания:
Р-11. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11?
Общий подход:
· вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на , а две младших цифры – это остаток от деления на и т.д.
· в данном случае , остаток от деления числа на должен быть равен 114 = 5
· потому задача сводится к тому, чтобы определить все числа, которые меньше или равны 25 и дают остаток 5 при делении на 16
Решение (вариант 1, через десятичную систему):
1) общий вид чисел, которые дают остаток 5 при делении на 16:
где – целое неотрицательное число (0, 1, 2, …)
2) среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не превосходят 25»); их всего два: 5 (при ) и 21 (при )
3) таким образом, верный ответ – 5, 21 .
| Возможные ловушки и проблемы: · выражение «не превосходящие » означает «меньшие или равные », а не строго меньшие · остаток, состоящий из нескольких цифр (здесь – 114), нужно не забыть перевести в десятичную систему · найденные числа нужно записать именно в порядке возрастания, как требуется |
Решение (вариант 2, через четверичную систему, предложен О.А. Тузовой):
1) переведем 25 в четверичную систему счисления: 25 = 1214, все интересующие нас числа не больше этого значения
2) из этих чисел выделим только те, которые заканчиваются на 11, таких чисел всего два:
это 114 = 5 и 1114 = 21
3) таким образом, верный ответ – 5, 21 .
| Возможные ловушки и проблемы: · есть риск случайно «забыть» какое-то число или найти «лишнее» (в данном случае – большее 25) · можно сделать ошибки при переводе чисел из четверичной системы в десятичную или вообще «забыть» перевести |
Еще пример задания:
Р-10. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2.
Общий подход:
· здесь обратная задача – неизвестно основание системы счисления, мы обозначим его через
· поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть
· вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на
Решение:
1) итак, нужно найти все целые числа , такие что остаток от деления 23 на равен 2, или (что то же самое)
где – целое неотрицательное число (0, 1, 2, …);
2) сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа
3) из формулы (*) получаем , так что задача сводится к тому, чтобы найти все делители числа 21, которые больше 2
4) в этой задаче есть только три таких делителя: и
5) таким образом, верный ответ – 3, 7, 21 .
| Возможные ловушки и проблемы: · нужно учесть, что основание системы счисления должно быть больше любой цифры числа, поэтому делитель не подходит (должно быть ) · числа нужно записывать в ответе в порядке возрастания, как требуется по условию |
Еще пример задания:
Р-9. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на 11.
Общий подход:
· неизвестно основание системы счисления, мы обозначим его через
· пока будем считать, что запись числа 31 в системе с основанием состоит из трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через ) нужно найти:
31 = k 1 1N = k·N 2 + N 1 + N 0 = k·N 2 + N + 1
· можно показать, что при большем количестве разрядов эта формула также верна, то есть, число 31 можно представить как при некотором целом ; например, для числа с пятью разрядами получаем:
4 3 2 1 0 ← разряды
= k·N 2 + N + 1
для (из первых трех слагаемых вынесли общий множитель )
Решение:
1) итак, нужно найти все целые числа , такие что
где – целое неотрицательное число (0, 1, 2, …);
2) сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа
3) из формулы (**) получаем , так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом , то есть, – целое число
4) выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30
5) из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0)
6) таким образом, верный ответ – 2, 3, 5, 30.
Еще пример задания:
Р-8. Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17 в системе счисления с основанием 5.
Решение (вариант 1):
1) запишем первое и последнее число в заданном диапазоне в системе счисления с основанием 5:
2) заметим, что оба они содержат цифру 2, так что, 2 цифры мы уже нашли
3) между 205 и 325 есть еще числа
4) в них 5 цифр 2 (в числе 225 – сразу две двойки), поэтому всего цифра 2 встречается 7 раз
5) таким образом, верный ответ – 7.
| Возможные ловушки и проблемы: · нужно не забыть, что в системе счисления с основанием 5 старшая цифра – 4, то есть, вслед за 245 следует 305 · помните, что нужно определить не количество чисел, в которых есть двойка, а количество самих двоек · можно не обратить внимание на то, что в числе 225 цифра 2 встречается 2 раза |
Решение (вариант 2):
1) переведем все указанные числа в систему счисления с основанием 5:
2) считаем цифры 2 – получается 7 штук
3) таким образом, верный ответ – 7 .
Еще пример задания:
Р-7. Укажите наименьшее основание системы счисления, в которой запись числа 30 трехзначна.
Решение:
1) обозначим через неизвестное основание системы счисления, тогда запись числа 30 в этой системе имеет вид
2) вспомним алгоритм перевода числа из системы счисления с основанием в десятичную систему: расставляем сверху номера разрядов и умножаем каждую цифру на основание в степени, равной разряду:
3) поскольку запись трехзначная, , поэтому
4) с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль, поэтому
5) объединяя последние два условия, получаем, что искомое основание удовлетворяет двойному неравенству
6) учитывая, что – целое число, методом подбора находим целые решения этого неравенства; их два – 4 и 5:
7) минимальное из этих значений – 4
8) таким образом, верный ответ – 4 .
Решение (без подбора):
1) выполним п.1-4 так же, как и в предыдущем варианте решения
2) найдем первое целое число, куб которого больше 30; это 4, так как
3) проверяем второе неравенство: , поэтому в системе счисления с основанием 4 запись числа 30 трехзначна
4) таким образом, верный ответ – 4 .
Еще пример задания:
Р-6. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в системе счисления с основанием 5 начинается на 3?
Решение (вариант 1):
1) нас интересуют числа от 1 до 30
2) сначала определим, сколько цифр может быть в этих числах, записанных в системе счисления с основанием 5
3) поскольку , в интересующих нас числах может быть от 1 до 3 цифр
4) рассмотрим трехзначные числа, начинающиеся на 3 в системе с основанием 5:
все они заведомо не меньше , поэтому в наш диапазон не попадают;
5) таким образом, остается рассмотреть только однозначные и двухзначные числа
6) есть всего одно однозначное число, начинающееся на 3, это 3
7) общий вид всех двузначных чисел, начинающихся на 3 в системе с основанием 5:
где – целое число из множества <0, 1, 2,3,4>(поскольку система счисления имеет основание 5 и цифр, больших 4, в записи числа быть не может)
8) используя эту формулу, находим интересующие нас двузначные числа – 15, 16, 17, 18 и 19
9) таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
Решение (вариант 2, предложен Сенькиной Т.С., г. Комсомольск-на-Амуре ):
1) нас интересуют числа от 1 до 30; сначала определим, сколько цифр может быть в пятеричной записи эти чисел
2) поскольку , в интересующих нас числах может быть не более 2 цифр (все трехзначные пятеричные числа, начинающиеся с 3, больше 30)
3) есть всего одно однозначное число, начинающееся на 3, это 3
4) выпишем все пятеричные двузначные числа, которые начинаются с 3, и переведем их в десятичную систему: 305 = 15, 315 = 16, 325 = 17, 335 = 18 и 345 = 19
5) таким образом, верный ответ – 3, 15, 16, 17, 18, 19 .
Еще пример задания:
Р-5. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 71 оканчивается на 13.
Решение (1 способ):
1) Если число в системе с основанием оканчивается на 13, то
а) , потому что в системах с меньшим основанием нет цифры 3
б) это число можно представить в виде , где – целое неотрицательное число
2) определим наибольшее возможное с учетом условия . Из уравнения следует .
3) очевидно, что чем меньше , тем больше , поэтому значение не превышает
здесь мы подставили – наименьшее допустимое значение
4) остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
относительно , причем нас интересуют только натуральные числа
б) при : решения – не целые числа
в) при : и , второе решение не подходит
6) таким образом, верный ответ: 4, 68.
Решение (2 способ, М.В. Кузнецова и её ученики):
1) запись числа71 в системе с основанием оканчивается на 13, т.е. в разряде единиц – 3, это значит, что остаток от деления 71 на равен 3, то есть для некоторого целого имеем
2) таким образом, искомые основания – делители числа 68; остается выбрать из них те, которые соответствуют другим условиям задачи
3) среди чисел, оканчивающихся на 13 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
так что первый ответ: 68.
4) остальные числа, окачивающиеся в этой системе на 13, имеют не менее 3-х знаков ( , …), т.е. все они больше
5) поэтому , следовательно,
6) по условию в записи числа есть цифра 3, поэтому (в системах с основанием £ 3 цифры 3 нет)
7) итак: , и при этом – делитель 68; единственное возможное значение (на 5,6,7 и 8 число 68 не делится)
8) таким образом, верный ответ: 4, 68.
| Возможные ловушки и проблемы: · на шаге 1 нужно вычесть из числа только число единиц, то есть младшую из двух заданных цифр (в примере – 3) · можно забыть рассмотреть двузначное число, записанное заданными в условии цифрами (в примере – 13x ), и пропустить максимальное основание · нужно помнить, что а) максимальная цифра на 1 меньше основания системы счисления б) 100 в системе с основанием p равно p 2 |
Еще пример задания:
Р-4. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 86 оканчивается на 22.
Решение (1 способ):
1) Если число в системе с основанием оканчивается на 22, то
а) , потому что в системах с меньшим основанием нет цифры 2
б) это число можно представить в виде , где – целое неотрицательное число
2) определим наибольшее возможное с учетом условия . Из уравнения следует .
3) очевидно, что чем меньше , тем больше , поэтому значение не превышает
здесь мы подставили – наименьшее допустимое значение
4) остается перебрать все допустимые значения (от 0 до ), решая для каждого из них уравнение
относительно , причем нас интересуют только натуральные числа
б) при : решения – не целые числа
в) при : и , второе решение не подходит
г) при : решения – не целые числа
6) таким образом, верный ответ: 6, 42.
Решение (2 способ, М.В. Кузнецова и её ученики):
1) запись числа 86 в системе с основанием оканчивается на 22, т.е. в разряде единиц – 2, это значит, что остаток от деления 86 на равен 2, то есть для некоторого целого имеем
2) таким образом, искомые основания – делители числа 84; остается выбрать из них те, которые соответствуют другим условиям задачи
3) среди чисел, оканчивающихся на 22 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание:
так что первый ответ: 42.
4) остальные числа, окачивающиеся в этой системе на 22, имеют не менее 3-х знаков ( , …), т.е. все они больше
5) поэтому , следовательно,
6) по условию в записи числа есть цифра 2, поэтому
7) итак: , и при этом – делитель 84; возможные значения (на 5,8 и 9 число 84 не делится)
8) переводя число 86 в системы счисления с основаниями , находим, что только для основания 6 запись числа оканчивается на 22 (при делении на 3, 4 и 7 «вторые» остатки не равны 2):
| Дальше делить нет смысла | ||
| 9… | 5… | |
| 1 | 1 | 5 |
9) таким образом, верный ответ: 6, 42.
Еще пример задания:
Р-3. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 94 начинается на 23.
Решение:
1) Из условия сразу видно, что искомое основание не меньше 4 (в записи есть цифра 3).
2) Если запись числа 94 в некоторой системе счисления с основанием двузначна (94 = 23x), то справедливо равенство ; нас интересуют натуральные решения этого уравнения, такие что , таких решений нет.
3) Предположим, что число четырехзначное. Минимальное допустимое четырехзначное число – 2300x, где . При минимальном основании ( ) оно равно , поэтому запись нужного нам числа имеет не больше трех знаков.
4) На основании (2) и (3) делаем вывод, что число трехзначное, то есть , где – целое неотрицательное число, такое что .
5) Максимальное можно определить как решение уравнения (при ); получаем одно из решений – 6,15; поэтому
6) Если мы знаем , то определится как ; пробуем подставлять в эту формулу , пытаясь получить
7) Минимальное будет при : , а при получается
8) Таким образом, верный ответ: 6.
Еще пример задания:
Р-2. Найти сумму восьмеричных чисел 178 +1708 +17008 +. +17000008, перевести в 16-ую систему счисления. Найдите в записи числа, равного этой сумме, третью цифру слева.
Решение:
1) Несложно выполнить прямое сложение восьмеричных чисел, там быстро обнаруживается закономерность:
2) Переведем последнюю сумму через триады в двоичный код (заменяем каждую восьмеричную цифру на 3 двоичных):
3) Теперь разбиваем цепочку на тетрады (группы из 4-х двоичных цифр), начиная справа, и каждую тетраду представляем в виде шестнадцатеричной цифры
4) Таким образом, верный ответ (третья цифра слева): 2.
Еще пример задания:
Р-1. Чему равно наименьшее основание позиционной системы счисления , при котором 225x = 405y? Ответ записать в виде целого числа.
Решение:
1) Поскольку в левой и в правой частях есть цифра 5, оба основания больше 5, то есть перебор имеет смысл начинать с .
2) Очевидно, что , однако это не очень нам поможет.
3) Для каждого «подозреваемого» вычисляем значение и решаем уравнение , причем нас интересуют только натуральные .
4) Для и нужных решений нет, а для получаем
5) Таким образом, верный ответ (минимальное значение ): 8.
Еще пример задания:
Р-0. Запись числа 3010 в системе счисления с основанием N оканчивается на 0 и содержит 4 цифры. Чему равно основание этой системы счисления N?
Решение (1 способ, подбор):
1) запись числа 30 в системе с основанием N длиннее, чем в десятичной (4 цифры против двух), поэтому основание N меньше 10
2) это дает шанс решить задачу методом подбора, переводя в разные системы, начиная с N = 2 до N = 9
4) дальше можно не переводить, поскольку запись 10103 удовлетворяет условию: заканчивается на 0 и содержит 4 цифры
5) можно проверить, что при N ≥ 4 запись числа 30 содержит меньше 4 цифр, то есть не удовлетворяет условию
Решение (2 способ, неравенства):
1) запись числа 30 в системе с основанием N содержит ровно 4 цифры тогда и только тогда, когда старший разряд – третий, то есть
2) первая часть двойного неравенства дает (в целых числах)
3) вторая часть неравенства дает (в целых числах)
4) объединяя результаты пп. 2 и 3 получаем, что N = 3
5) заметим, что условие «оканчивается на 0» – лишнее, ответ однозначно определяется по количеству цифр
Задачи для тренировки:
1) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.
2) В системе счисления с некоторым основанием число 12 записывается в виде 110. Укажите это основание.
3) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 39 оканчивается на 3.
4) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 29 оканчивается на 5.
5) В системе счисления с некоторым основанием десятичное число 129 записывается как 1004. Укажите это основание.
6) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 40 оканчивается на 4.
7) В системе счисления с некоторым основанием число десятичное 25 записывается как 100. Найдите это основание.
8) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 27 оканчивается на 3.
9) Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22?
10) Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в четверичной системе счисления оканчивается на 31?
11) Укажите через запятую в порядке возрастания все десятичные натуральные числа, не превосходящие 17, запись которых в троичной системе счисления оканчивается на две одинаковые цифры?
12) Укажите, сколько всего раз встречается цифра 3 в записи чисел 19, 20, 21, …, 33 в системе счисления с основанием 6.
13) Укажите, сколько всего раз встречается цифра 1 в записи чисел 12, 13, 14, …, 31 в системе счисления с основанием 5.
14) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 1.
15) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 63 оканчивается на 23.
16) Десятичное число, переведенное в восьмеричную и в девятеричную систему, в обоих случаях заканчивается на цифру 0. Какое минимальное натуральное число удовлетворяет этому условию?
17) В системе счисления с некоторым основанием десятичное число 49 записывается в виде 100. Укажите это основание.
18) Укажите наименьшее основание системы счисления, в которой запись числа 70 трехзначна.
19) Укажите наименьшее основание системы счисления, в которой запись числа 50 двузначна.
20) Сколько значащих цифр в записи десятичного числа 357 в системе счисления с основанием 7?
21) Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием 6 начинается на 4?
22) Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 20, запись которых в системе счисления с основанием 3 начинается на 2?
23) Какое десятичное число при записи в системе счисления с основанием 5 представляется как 12345?
24) Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в двоичной системе счисления оканчивается на 101?
25) Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 30 оканчивается на 8.
Сколько единиц в двоичной записи числа 205
Шестнадцатеричная система — cd.
Двоичная система — 11001101.
Посмотрите так же как пишутся десятичные цифры 21, 7, 38, 4, 323, 681, 770, 666, 9531, 106, 116, 36727, 83677, 229016, 949180 в различных системах счисления.
Число 205 в других системах счисления:
2 — 11001101, 3 — 21121, 4 — 3031, 5 — 1310, 6 — 541, 7 — 412, 8 — 315, 9 — 247, 10 — 205, 11 — 177, 12 — 151, 13 — 12a, 14 — 109, 15 — da, 16 — cd, 17 — c1, 18 — b7, 19 — af, 20 — a5, 21 — 9g, 22 — 97, 23 — 8l, 24 — 8d, 25 — 85, 26 — 7n, 27 — 7g, 28 — 79, 29 — 72, 30 — 6p, 31 — 6j, 32 — 6d.
Ответы на вопрос
николай — теннис, волейбол.
михаил — баскетбол, плавание.
решение: так как михаил не увликаеться велоспортом, волейболом и тенисом значет он занимаеться плаванием. тогда получаеться что тенисист — николай и потому как он самый старший то павел будет велосипедистом из этого выходит что волейболистом будет николай.
таблица истинности выражения a → b
теперь пример: ¬((x> 3) → (x> 4))
при х = 1: ¬((1> 3) → (1> 4))= ¬((0) → (0))=¬(1) = 0,т.е.(1> 3)=ложь(> 4)=ложь(0), а ложь(0) → ложь(0) = истина (1), а отрицание лжи (0) = истина(1)
при х = 2: ¬((2> 3) → (2> 4))= ¬((0) → (0))=¬(1) = 0
при х = 3: ¬((3> 3) → (3> 4))= ¬((0) → (0))=¬(1) = 0
при х = 4: ¬((4> 3) → (4> 4))= ¬((1) → (0))=¬(0) = 1
Данная задачка судя по всему типовая в ЕГЭ по информатике, алгоритм ее решения в общем случае следующий: перевести число в двоичную форму (например, тут — http://floatingpoint.ru/online/dec2bin.php) и подсчитать количество единиц — калькулятор нулей и единиц в двоичной записи числа
Однако в некоторых простых случаях можно попробовать разложить искомое число на сумму или разность степеней двоек, и проделать вычисления в уме.
Для этого нужно помнить несколько первых степеней двойки и двоичные записи по крайней мере некоторых чисел от 1 до 15:
1024 = 2^10, 512 = 2^9, 256 = 2^8, 128 = 2^7, 64 = 2^6, 32 = 2^5, 16 = 2^4
15 = 1111, 14 = 1110, 13 = 1101, 12 = 1100, 11 = 1011, 10 = 1010, 9 = 1001, 8 = 1000, 7 = 111, 6 = 110, 5 = 101, 4 = 100, 3 = 11, 2 = 10, 1 = 1.