Отнт. А. Ю. Босова Москва бином. Лаборатория знаний 10 класс Базовый уровень Учебник
 Скачать 6.18 Mb.
|
|
Глава3.представлениеинформациивкомпьютере В непозиционных системах счисления величина, которую обозначает цифра, не зависит от положения этой цифры в числе. Примером непозиционной системы, которая сохранилась дона- ших дней, может служить система счисления, которая применялась более двух с половиной тысяч лет назад в Древнем Риме. В основе римской системы счисления лежали знаки I (один палец) для числа 1, V (раскрытая ладонь) для числа 5, X (две скрещённые ладони) для числа 10, а для обозначения чисел 100, 500 и 1000 стали применять первые буквы соответствующих латинских слов (с — сто, demimille — половина тысячи, mille — тысяча). Чтобы записать число, римляне разлагали его на сумму тысяч, полутысяч (D), сотен (C), полусотен (L), десятков (X), пятёрок (V), единиц (I). Например, десятичное число 128 представляется следующим образом = 100 + 10 + 10 + 5 + 1 + 1 + 1 одна сотня, два десятка, пять, три единицы). Для записи промежуточных чисел римляне использовали не только сложение, но и вычитание. При этом применялось следующее правило каждый меньший знак, поставленный справа от большего, прибавляется к его значению, а каждый меньший знак, поставленный слева от большего, вычитается из него. Например, XI обозначает 11, а IX обозначает Римскими цифрами пользовались очень долго. Ещё 200 лет назад в деловых бумагах числа должны были обозначаться римскими цифрами (считалось, что обычные арабские цифры легко подделать. Римская система счисления сегодня используется в основном для наименования знаменательных дат, томов, разделов и глав в книгах. Подумайте, почему римскую систему счисления нельзя считать полностью непозиционной. представление чисел в системах счисления Непозиционные системы счисления имеют ряд существенных недостатков существует постоянная потребность введения новых знаков для записи больших чисел невозможно представлять дробные и отрицательные числа сложно выполнять арифметические операции, т. к. не существует алгоритмов их выполнения. Всех перечисленных недостатков лишены позиционные системы счисления. Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (места, позиции) в записи числа. Например, используемая повсеместно десятичная система счисления позиционная. Рассмотрим число 555. Цифра 5, стоящая в записи этого числа на первом месте, обозначает количество сотен и соответствует числу 500; цифра, стоящая посередине, обозначает 5 десятков (50); последняя цифра 5 соответствует пяти единицам. Исходное число можно представить в виде суммы = 500 + 50 + Потребовалось много тысячелетий, чтобы люди научились называть и записывать числа так, как это делаем мыс вами. Начало этому было положено в Древнем Египте и Вавилоне, а завершили дело индийские математики в V–VII веках нашей эры. Важным достижением индийской науки было введение особого обозначения для пропуска разрядов — нуля. Арабы, познакомившись с этой нумерацией первыми, по достоинству её оценили, усвоили и перенесли в Европу. Получив название арабской, эта система в XII веке нашей эры распространилась по всей Европе. Итак как эта система счисления проще и удобнее остальных, быстро их вытеснила. Французский математик Пьер Симон Лаплас (1749–1827) оценил открытие позиционной системы такими словами Мысль выражать все числа немногими знаками, придавая им кроме значения по форме, ещё значение по месту, настолько проста, что именно из-за этой простоты трудно оценить, насколько она удивительна позиционные системы счисления Существует бесконечно многопозиционных систем счисления. Каждая из них определяется целым числом q > 1, называемым основанием системы счисления. Основание определяет (дат) 102 Глава3.представлениеинформациивкомпьютере название системы счисления двоичная, троичная, восьмеричная, шестнадцатеричная, q-ичная и т. д. Можно говорить система счисления с основанием q» (табл. Основное достоинство любой позиционной системы счисления возможность записи произвольного числа ограниченным количеством символов. Для записи чисел в позиционной системе счисления с основанием q нужен алфавит из q цифр 0, 1, 2, …, q – Таблица основания и алфавиты систем счисления Основание Название Алфавит q = Двоичная, 1 q = Троичная, 1, 2 q = Восьмеричная, 1, 2, 3, 4, 5, 6, 7 q = Шестнадцатеричная, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, В q-ичной системе счисления q единиц какого-либо разряда образуют единицу следующего разряда. Целое число без знака А в q-ичной системе счисления представляется в виде конечной суммы степеней числа q — суммы разрядных слагаемых: А = a n–1 · q n–1 + a n–2 · q n–2 + … + a 1 · q 1 + a 0 · q 0 = a q i i i n 0 Здесь q — основание системы счисления a i — цифры, принадлежащие алфавиту данной системы счисления весовой коэффициент разряда. Последовательность чисел, каждое из которых задаёт вес соответствующего разряда, называется базисом позиционной системы счисления. Число A, свёрнутая запись которого в системе счисления с основанием имеет вид a n–1 a n–2 …a 0 ,a –1 …a –m , может быть представлено в развёрнутой форме как a n–1 · q n–1 + a n–2 · q n–2 + … + a 0 · q 0 + + a –1 · q –1 + … + a –m · q –m представление чисел в системах счисления Свёрнутой формой записи числа мы пользуемся в повседневной жизни, иначе её называют естественной формой или цифровой. Развёрнутая форма записи чисел также всем хорошо известна. Ещё в начальной школе дети учатся записывать числа в виде суммы разрядных слагаемых. Например 248 = 1 · 100 000 + 2 · 10 000 + 5 · 1 000 + 2 · 100 + 4 · 10 + 8 · Если представить разряды в виде степей основания, то получим+ 4 · 10 1 + 8 · 10 Аналогичным образом представляются и дроби = 1 10 2 100 5 1000 + + = 1 · 10 –1 + 2 · 10 –2 + 5 · Иногда бывает полезно преобразовать развёрнутую форму записи числа так, чтобы избежать возведения основания системы счисления в степени. Например, можно записать 248 = 1 · 10 5 + 2 · 10 4 + 5 · 10 3 + 2 · 10 2 + 4 · 10 1 + 8 · 10 0 = = ((((1 · 10 + 2) · 10 + 5) · 10 + 2) · 10 + 4) · 10 + 8; 0,125 = 1 · 10 –1 + 2 · 10 –2 + 5 · 10 –3 = ((5/10 + 2)/10 + Такую форму представления числа называют разложением по схеме Горнера. Изучая десятичную систему счисления с раннего возраста и используя её в повседневной практике, многие люди не догадываются о существовании других систем счисления. Но так ли хороша десятичная система счисления Великий французский математики естествоиспытатель Блез Паскаль (1623–1662) писал Десятичная система построена довольно неразумно, конечно, в соответствии с людскими обычаями, а вовсе нес требованиями естественной необходимости, как склонно думать большинство людей. В ряде теоретических и практических задач некоторые системы счисления, отличные от десятичной, имеют определённые преиму- щества. Первые механические счётные машины были разработаны на основе десятичной системы счисления. Для реализации десяти устойчивых состояний в них использовались сложные системы зубчатых колёс (рис. 3.1). Такие машины были очень громоздки, занимали много места 104 Глава3.представлениеинформациивкомпьютере рис. 3.1. Механизм передачи десятков в арифмометре ПЛ. Чебышёва Так, если бы проект Аналитической машины Беббиджа — механического прототипа появившихся спустя столетие ЭВМ — был реализован, то по размерам такая машина сравнялась бы с локомотивом. В 1937 году немецкий инженер Конрад Цузе создал вычислительную машину, основанную на принципах действия аналитической машины Беббиджа. Она была механической, но работала на основе двоичной системы счисления, что позволило значительно уменьшить её размеры машина занимала всего 2 м на столе в квартире изобретателя! В наши дни большой практический интерес представляют двоичная, троичная, восьмеричная и шестнадцатеричная системы счисления перевод чисел из q-ичной в десятичную систему счисления Перевод числа, записанного в системе счисления с основанием q, в десятичную систему счисления основан на использовании развёрнутой формы записи чисел (рис. 3.2). представление чисел в системах счисления рис. 3.2. Перевод числа из q-ичной системы счисления в десятичную Для перевода числа А в десятичную систему счисления достаточно) записать развёрнутую форму числа А) представить все числа, фигурирующие в развёрнутой форме, в десятичной системе счисления) вычислить значение полученного выражения по правилам десятичной арифметики. Переведём числа 212 3 , 123 5 и А в десятичную систему счисления 3 = 2 · 3 2 + 1 · 3 1 + 2 · 3 0 = 2 · 9 + 1 · 3 + 2 · 1 = 23 10 ; 123 5 = 1 · 5 2 + 2 · 5 1 + 3 · 5 0 = 2 · 25 + 2 · 5 + 3 · 1 = 63 10 ; А = 1 · 16 2 + 2 · 16 1 + А · 16 0 = 1 · 256 + 2 · 16 + 10 · 1 = 298 Перевод в десятичную систему счисления целых двоичных чисел будет значительно проще, если вспомнить и использовать уже знакомую вам таблицу степеней двойки 1 2 3 4 5 6 7 8 9 10 2 n 1 2 4 8 16 32 64 128 256 512 Например 8 7 6 5 4 3 2 1 0 1001110011 2 = 1 0 0 1 1 1 0 0 1 1= 512 + 64 + 32 + 16 + 2 + 1 = 627 Для перевода двоичного числа в десятичную систему счисления можно воспользоваться схемой Горнера: 1) 1 · 2 = 2 — возьмем 1, соответствующую самому старшему разряду числа, и умножим её на 2; 2) 2 + 0 = 2 — прибавим следующую цифру 3) 2 · 2 = 4 — умножим результат на 2; 106 Глава3.представлениеинформациивкомпьютере 4) 4 + 0 = 4 — прибавим следующую цифру 5) 4 · 2 = 8 — умножим результат на 2; 6) 8 + 1 = 9 — прибавим следующую цифру 7) 9 · 2 = 18 — умножим результат на 2; 8) 18 + 1 = 19 — прибавим следующую цифру 9) 19 · 2 = 38 — умножим результат на 2; 10) 38 + 1 = 39 — прибавим следующую цифру) 39 · 2 = 78 — умножим результат на 2; 12) 78 + 0 = 78 — прибавим следующую цифру) 78 · 2 = 156 — умножим результат на 2; 14) 156 + 0 = 156 — прибавим следующую цифру) 156 · 2 = 312 — умножим результат на 2; 16) 312 + 1 = 313 — прибавим следующую цифру) 313 · 2 = 626 — умножим результат на 2; 18) 626 + 1 = 627 — прибавим последнюю цифру. Рассмотрим несколько примеров решения задач. Пример 1. Десятичное число 57 в некоторой системе счисления записывается как 212. Определим основание этой системы счисления. Запишем условие задачи иначе 212 q = 57 10 , q > Представим в виде суммы разрядных слагаемых 2 · q 2 + 1 · q 1 + 2 · q 0 =2q 2 + q + 2 = 57 Решим уравнение 2q 2 + q + 2 = 57. 2q 2 + q – 55 = Это квадратное уравнение, его корни x 1 = –5,5; x 2 = Так как основание системы счисления должно быть натуральным числом, то q = Пример 2. Все пятибуквенные слова, составленные из пяти букв АИР, СТ, записаны в алфавитном порядке. Вот начало списка 1. ААААА 2. ААААИ 3. ААААР 4. ААААС 5. ААААТ 6. АААИА … представление чисел в системах счисления Необходимо найти ответы на два вопроса 1. На каком месте от начала списка стоит слово ИСТРА 2. Сколько всего слов в этом списке Введём следующие обозначения АИР, СТ. Перепишем в новых обозначениях исходный список 1. 00000 2. 00001 3. 00002 4. 00003 5. 00004 6. Теперь перед нами последовательность чисел от 0 до 44444, записанных в пятеричной системе счисления. При этом нам месте в этой последовательности находится 0, нам месте — 1, нам месте — 2 и т. д. Это значит, что само число на единицу меньше того места (номера, которое оно занимает в последова- тельности. Представив слово ИСТРА в новых обозначениях, получим 13420 5 . Переведём это пятеричное число в десятичную систему счисления 5 = 1 · 5 4 + 3 · 5 3 + 4 · 5 2 + 2 · 5 1 + 0 · 5 0 = = 625 + 375 + 100 + 10 = 1110 Это число находится в списке нам месте. Чтобы выяснить, сколько всего слов в списке, запишем его самое последнее слово ТТТТТ. Ему соответствует число 44444 5 44444 5 = 4 · 5 4 + 4 · 5 3 + 4 · 5 2 + 4 · 5 1 + 4 · 5 0 = 3124 В списке это число стоит нам месте. Вспомните о комбинаторике и предложите другой способ подсчёта количества слов в нашем списке. Пример 3. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 60, запись которых в четверичной системе счисления оканчивается на 31? В четверичной системе счисления используются цифры 0, 1, 2 и 3; число представляется в виде суммы разрядных слагаемых 0 4 1 4 2 4 3 … 1 4 16 64 108 Глава3.представлениеинформациивкомпьютере Из этой таблицы видно, что интересующие нас числа (≤ 60) не будут более чем трёхзначными. С учётом того, что их запись заканчивается на 31, определим первую цифру (k): k · 16 + 3 · 4 + 1 ≤ 60, k · 16 ≤ 47, k ∈ {0, 1, Искомые числа 31 4 = 13 10 (k = 0), 131 4 = 29 10 (k = 1), 231 4 = 45 10 (k = самое ГЛаВное Система счисления — это способ записи (обозначения) чисел. Система счисления называется позиционной, если количественный эквивалент цифры зависит от её положения (места, позиции) в записи числа. Существует бесконечно многопозиционных систем счисления. Каждая из них определяется целым числом q > 1, называемым основанием системы счисления. Для записи чисел в позиционной системе счисления с основанием q нужен алфавит из q цифр 0, 1, 2, …, q – 1. Число A, свёрнутая запись которого в системе счисления с основанием q имеет вид a n–1 a n–2 …a 0 ,a –1 …a –m , может быть представлено в развёрнутой форме как a n–1 · q n–1 + a n–2 · q n–2 + … + a 0 · q 0 + + a –1 · q –1 + … + a –m · Для перевода числа А в десятичную систему счисления достаточно) записать развёрнутую форму числа А 2) представить все числа, фигурирующие в развёрнутой форме, в десятичной системе счисления 3) вычислить значение полученного выражения по правилам десятичной арифметики. Вопросы и задания 1. Что такое система счисления Какие классы систем счисления принято выделять 2. Дайте определение позиционной системы счисления. Что называется алфавитом системы счисления Что называется базисом позиционной системы счисления Что называется основанием позиционной системы счисления 3. Сколько цифр используется в системе счисления с основанием. Какая форма записи числа называется развёрнутой? представление чисел в системах счисления 5. Запишите в развёрнутой форме числа: а) 143,511 10 ; б) 1435,11 8 ; в) 143,511 16 6. Воспользуйтесь схемой Горнера для представления чисел: а) 12345 10 ; б) 12345 8 ; в) 0,12345 6 7. Вычислите десятичные эквиваленты следующих чисел: а) 120 3 ; б) 100,21 4 ; в) 5A,124 16 8. Существует ли треугольник, длины сторон которого выражаются числами 12 8 , 122 3 и 11011 2 ? 9. Укажите целые десятичные числа, принадлежащие следующим числовым промежуткам: а) [202 3 ; 1000 3 ]; б) [14 8 , 20 8 ]; в) [28 16 , 30 16 ]. 10. Найдите основание х системы счисления, если известно: а) 47 10 = х б) х = 6 10 11. Десятичное число 63 в некоторой системе счисления записывается как 120. Определите основание системы счисления. Какое из чисел С, записанных в двоичной системе счисления, удовлетворяет неравенству 9D 16 < C < 237 8 ? 1) 10011010 2 ; 2) 10011110 2 ; 3) 10011111 2 ; 4) 11011110 2 13. Как изменится величина чисел 311,211 4 и 23,45 6 при переносе запятой на: а) один знак вправо; б) два знака влево. При переносе запятой на два знака вправо число 240,13 х увеличилось враз. Чему равно x? 15. Какое наибольшее десятичное число можно записать тремя цифрами в двоичной, восьмеричной и шестнадцатеричной системах счисления. Найдите наименьшие основания систем счислениях и у, исходя из условий: а) 23 x = 21 y ; б) 51 x = 15 y ; в) 144 x = 441 y 17. Решите уравнение 54 7 + x = 320 5 18. Все трёхбуквенные слова, составленные из букв ИМ, Р, записаны в алфавитном порядке. Вот начало списка. ИИИ 2. ИИМ 3. ИИР 4. ИМИ 110 Глава3.представлениеинформациивкомпьютере Выясните общее количество слов в этом списке. На каких местах в этом списке стоят слова МИМ, МИР, РИМ. Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22. 20. Трёхзначное число, записанное в системе с основанием 3, при перестановке крайних цифр становится числом, выражающим тоже количество, но уже в системе с основанием 4. Найдите это число. Исполнитель умеет сравнивать однозначные числа, представленные в некоторой позиционной системе счисления. Составьте для него: а) алгоритм сравнения двух двухзначных чисел б) алгоритм сравнения двухзначных чисел перевод чисел из одной системы в другую перевод чисел из одной позиционной системы счисления в другую перевод целого десятичного числа в систему счисления с основанием Для перевода целого десятичного числа в систему счисления с основанием q следует 1) последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получится частное, равное нулю 2) полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие алфавиту новой системы счисления 3) составить число в новой системе счисления, записывая его, начиная с последнего остатка. Рассмотрим примеры перевода целых десятичных чисел в 2-ичную, 8-ричную и 16-ричную системы счисления перевод чисел из одной системы в другую §11 Пример 1. 25 10 = 11001 Пример 2. 163 10 = 243 Пример 3. 709 10 = С Пример 4. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись десятичного числа 22 оканчивается на Поскольку запись числа в системе счисления с основанием q заканчивается на 4, остаток отделения числа 22 на q равен. Следовательно, 18 mod q = 0. Это верно для q ∈ {18, 9, 6, 3, 2, Так как в новой системе счисления запись числа оканчивается на 4, то q > 4. Следовательно, условию задачи удовлетворяют основания 18, 9 и 6. 11.2. перевод целого десятичного числа в двоичную систему счисления Перевод целого десятичного числа, безусловно, может осуществляться по рассмотренному выше универсальному алгоритму. Но для чисел в пределах десяти тысяч (особенно — если число 1) Операция mod — вычисление остатка от целочисленного деления 112 |