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

[Введите текст].

Приднестровский государственный университет им. Т. Г. Шевченко Рыбницкий филиал Кафедра физики, математики и информатики.

Курсовая работа.

по дисциплине «Теоретические основы информатики».

на тему: «Системы счисления и их применение в различных областях».

Рыбница.

Современный человек в повседневной жизни постоянно сталкивается с числами и цифрами: запоминает номера автобусов и телефонов, в магазине подсчитывает стоимость покупок, ведет свой семейный бюджет в рублях и копейках и т. д. Числа и цифры с нами везде! Интересно, что знал человек о числах две тысячи лет назад? А пять тысяч лет назад?

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

Что же понимается под словом «число»?

Первоначально понятие отвлеченного числа отсутствовало, число было «привязано» к тем предметам, которые пересчитывали. Отвлеченное понятие натурального числа появляется вместе с развитием письменности.

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

Понятие числа — фундаментальное понятие, как математики, так и информатики. Под числом мы будем понимать его величину, а не его символьную запись.

Сегодня человечество для записи чисел использует в основном десятичную систему счисления. Что же такое — система счисления? Это мы узнаем в ходе изучения материала и в решении различного рода задач.

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

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

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

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

Язык чисел, как и любой другой, имеет свой алфавит. В том языке чисел, которым мы обычно пользуемся, алфавитом служат десять цифр — от 0 до 9. Это десятичная система счисления.

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

Причина, по которой десятичная система счисления стала общепринятой, вовсе не математическая. Десять пальцев рук — вот аппарат для счета, которым человек пользуется с доисторических времен. Древнее написание десятичных цифр (см. рис. 1):

Рис. 1 — Написание цифр в древности Довольно широкое распространение имела двенадцатеричная система счисления. Происхождение ее тоже связано со счетом на пальцах. Считали большой палец руки и фаланги остальных четырех пальцев: всего их 12 (см. Приложение, рис. 1).

По свидетельству известного исследователя Африки Стенли, у ряда африканских племен была распространена пятеричная система счисления. Долгое время пользовались пятеричной системой счисления и в Китае. Очевидная связь этой системы счисления со строением человеческой руки.

У ацтеков и майя — народов, населявших в течение многих столетий обширные области Американского континента и создавших там высочайшую культуру, в том числе и математическую, была принята двадцатеричная система счисления. Также двадцатеричная система счисления была принята и у кельтов, населявших Западную Европу начиная со второго тысячелетия до нашей эры. Основу для счета в этой системе счисления составляли пальцы рук и ног. Некоторые следы двадцатеричной системы счисления кельтов сохранились во французской денежной системе: основная денежная единица, франк, делится на 20 (1 франк = 20 су).

Особый интерес представляет так называемая «вавилонская», или шестидесятеричная, система счисления (см. Приложение, рис. 2), весьма сложная система, существовавшая в Древнем Вавилоне. Мнения историков по поводу того, как именно возникла эта система счисления, расходятся. Существуют две гипотезы. Первая исходит из того, что произошло слияние двух племён, одно из которых пользовалось шестеричной, другое — десятичной. Шестидесятеричная система счисления в данном случае могла возникнуть в результате своеобразного политического компромисса. Суть второй гипотезы в том, что древние вавилоняне считали продолжительность года равной 360 суткам, что естественно связано с числом 60. Отголоски использования этой системы счисления дошли до наших дней. Например, 1 час = 60 минут, 1 градус = 60минут. В целом шестидесятеричная система счисления громоздка и неудобна.

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

Цель исследования: выявить и систематизировать материалы по теме курсовой работы: «Системы счисления и их применение в различных областях».

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

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

систематизировать теоретический материал;

рассмотреть практические применения теоретического материала.

Объектом исследования является: различные системы счисления.

Предметом исследования — перевод чисел в различные системы счисления.

ГЛАВА 1. СИСТЕМЫ СЧИСЛЕНИЯ.

1.1 История возникновения различных систем счисления.

Первобытному человеку считать почти не приходилось. «Один», «два» и «много» — вот все его числа. Современным людям приходится иметь дело с числами буквально на каждом шагу. Нужно уметь правильно назвать и записать любое число, как бы велико оно ни было. Если бы каждое число называлось особым именем и обозначалось в письме особым знаком, то запомнить все эти слова и знаки было бы никому не под силу. Как же справиться с этой задачей? Нас выручает хорошая система обозначений.

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

Практически на всем земном шаре алфавитом в языке чисел служат 10 цифр, от 0 до 9. Девять из них используются для обозначения первых девяти натуральных чисел, а десятый — нуль — не обозначает никакого числа, он представляет собой так называемую «позиционную пробку». Этот язык называется десятичной системой счисления.

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

В последнее время с десятичной системой серьезно конкурируют двоичная и, отчасти, троичная системы, которыми «предпочитают» пользоваться современные вычислительные машины.

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

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

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

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

Специальных знаков (цифр) для записи чисел тогда не было. Но словам «один», «два», … «семнадцать» и так далее соответствовали определенные иероглифы. Их было не так уж много, так как больших чисел люди тогда не знали.

В некоторых странах (например, Китае и Японии) иероглифическое письмо сохранилось и до наших дней. Вот, для примера (см. рис. 2), несколько иероглифов:

Рис. 2 — Иероглифы У славян порядок цифр при записи числа был такой же, как в его устном названии. Говорят, например, «пятнадцать» (по-славянски — «пять на десять»), называя вперед цифру единиц, потом десяток. Славяне так и писали, то есть впереди писали пятерку, а за нею десяток. Наоборот, в числе «двадцать три» сначала называют десятки, потом единицы, у славян сначала три потом двадцать это отображалось в письме.

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

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

В более позднее время (XVI — XVII вв.) появилась своеобразная система наименования чисел, так называемое «великое славянское число», в этой системе числа до 999 999 назывались почти так же, как теперь. Слово «тьма» обозначает уже миллион. Кроме того, появляются следующие названия: «тьма тем», или «легион» (то есть миллион миллионов, или триллион, равен 10); «легион легионов», или «модр» (септиллион, 1024); наконец, «модр модров», или «ворон» (то есть 1048).

Позиционная нумерация возникла, по-видимому, в древнем Вавилоне (примерно четыре тысячи лет назад). О ней будет сказано чуть позднее. В Индии она приняла форму позиционной десятичной нумерации с применением нуля. У индусов эту систему чисел заимствовали арабы, ставшие в VIII — IX вв. одним из самых культурных народов мира. От арабов переняли ее европейцы (отсюда название — «арабские цифры»).

Особый интерес представляет вавилонская математика. Вавилонская нумерация просуществовала полторы тысячи лет (с XVIII до III в. до нашей эры) и пользовалась широким распространением на всем Ближнем Востоке. Она оказала влияние на китайскую, индийскую и греческую математику.

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

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

У аккадян основная единица — «мекель» — была примерно в 60 раз меньше единицы у сумерийцев — «мины» (примерно пол килограмма). Денежной единицей служила мина серебра.

После слияния этих народов «имели хождение» обе системы единиц: минами и мекелями пользовались так, как теперь пользуются килограммами и граммами (рублями и копейками) с той лишь разницей, что более крупная единица равнялась не 100, а 60 мелким единицам. Со временем появилась более крупная единица — «талант»: 1 талант = 60 мин, 1 мина = 60 мекелей.

Как же вавилоняне записывали числа? Они писали палочками, вдавливая их в глину, поэтому основными графическими элементами были у них клинья. Первый обозначал единицы, второй — десятки, смотри рис. 3.

Рис. 3 — Обозначение чисел в древности.

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

Однако, введя «позиционную пробку» в середине чисел, вавилоняне так и не додумались ставить ее на конце. И до самого падения вавилонской культуры числа 1, 60, 3000 записывались одинаково.

Только индусы, заимствовавшие у них позиционную нумерацию, научились правильно использовать знак нуля, и, введя вместо 60 основание 10, дали счислению его современную форму.

Три тысячи лет назад индусы уже пользовались современной нумерацией, хотя в памятниках того времени и не упоминаются числа, большие 100 000. В более поздних источниках встречаются значительно большие числа — до ста квадриллионов (1017). В одной из сравнительно молодых легенд о Будде говорится, что он знал названия чисел до 1054. Впрочем, индусы, по — видимому, не представляли себе бесконечности натурального ряда, они полагали, что существует какое-то наибольшее число, известное только богам.

Доказательство бесконечности числового ряда — заслуга древнегреческих ученых.

1.2 Непозиционные и позиционные системы счисления.

Система счисления (Нумерация) — это способ представления числа символами некоторого алфавита, которые называются цифрами.

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

Непозиционная система счисления В самой древней нумерации употреблялся лишь знак «|» для единицы, и каждое натуральное число записывалось повторением символа единицы столько раз, сколько единиц содержится в этом числе. Сложение в такой нумерации сводилось к приписыванию единиц, а вычитание — к их вычеркиванию. Для изображения сколько-нибудь больших чисел этот способ нумерации непригоден из-за своей громоздкости.

При начальном обучении в школе, когда счет ведется в пределах одного — двух десятков, этот способ нумерации успешно применяется (счет на палочках).

В непозиционных системах счисления смысл каждого знака сохраняется и не зависит от его места в записи числа.

К более современным непозиционным системам относят египетскую иероглифическую систему нумерации, в которой имелись определенные знаки для чисел: единица — I, десять — n, сто — с и так далее; эти числа называются узловыми. Все остальные натуральные числа, называемые алгоритмическими числами, записываются единообразно при помощи единственной арифметической операции — сложения. Например, число 243 запишется в виде сс nnnn III, 301 — в виде ссс I.

К непозиционным системам относят римскую нумерацию. За узловые числа в этой системе принимают числа: единица — I, пять — V, десять — X, пятьдесят — L, сто — С, пятьсот — D, тысяча — М. Все алгоритмические числа получаются при помощи двух арифметических операций: сложения и вычитания. Вычитание производится тогда, когда знак, соответствующий меньшему узловому числу, стоит перед знаком большего узлового числа, например, VI — шесть (5+1= 6), ХС — девяносто (100−10=90), 1704 — МОССIV, 193 -СХСШ, 687 — DCLXXXII.

В римской нумерации заметны следы пятеричной системы счисления, так как в ней имеются специальные знаки для чисел 5, 50 и 500.

При записи чисел использовался не только принцип сложения, но и принцип умножения.

Например, в старо — китайской системе счисления числа 20 и 30 изображались схематически, как 2,10 и 3,10. числа 10, 100, 1000 имели определенные специальные обозначения. Число 528 записывалось так: 5,100,2,10,8. Наиболее удобными среди непозиционных систем счисления являются алфавитные системы нумерации. Примерами таких систем могут служить ионийская система (Древняя Греция), славянская, еврейская, грузинская и армянская.

Во всех алфавитных системах существенным является обозначение специальными символами — буквами в алфавитном порядке всех чисел от 1 до 9, всех десятков от 10 до 90 и всех сотен от 100 до 900. Чтобы отличать запись чисел от слов над буквами, обозначающими цифры, в греческой и славянской нумерации ставилась черта.

В греческой системе счисления число 543 записывалось: цмг (ц — 500, м- 40, г- 3). В римской системе счисления это число записывается в виде DXLIII, в египетской иероглифической — в виде ссссс nnn III.

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

Рис. 4 — Переход к позиционной системе записи Наиболее удобными системами счисления оказались позиционные или поместные системы.

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

Систематической записью натурального числа N по основанию с называют представление этого числа в виде суммы: N = аnсn+…+а1с, + а0, где аn, …, а1, а0 — числа принимающие значения 0, 1, …, с — 1, причем, аn?0.

Позиционная система счисления с основанием с называется с — ичной (двоичной, троичной и так далее). На практике чаще всего применяется десятичная с= 10).

Для обозначения чисел 0, 1, …, с — 1 в с — ичной системе счисления используют особые знаки, называемые цифрами. Древнеиндийские математики открыли нуль — особый знак, который должен был показать отсутствие единиц определенного разряда.

Для с — ичной системы счисления нужно с цифр. Если с < 10, то применяются те же обозначения цифр, что и в десятичной системе счисления (только берутся цифры, меньше основания системы).

В системах с основанием с > 10 для чисел, больших или равных 10, не вводят специальных символов, а используют десятичную запись этих чисел, заключая эту запись в скобки. Например, в четырнадцатеричной системе имеется четырнадцать цифр: 0, 1, 2, 3 … 9, (10), (11), (12), (13).

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

Число N= аnс n +. .. +a1с +а0 содержит а0 единиц первого разряда, а1 единиц второго разряда, а2 единиц третьего разряда и так далее. Единица следующего разряда в с раз больше единицы предыдущего разряда.

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

Теорема. Любое натуральное число N может быть записано в системе с основание с и притом единственным образом.

Доказательство:

1. Докажем существование представления любого натурального числа в виде:

N=anсn +a n-1 сn-1 + … +ас+а0. (1).

Доказательство проведем методом полной математической индукции.

Представление числа N в виде (1) возможно для первых р-1 натуральных чисел 1, 2,…, с-1, так как n=1 и число совпадает с данным числом. Представление числа в виде (1) для чисел 1, 2,. .., с-1, очевидно, возможны только единственным способом: 1=1, 2=2,.. ., с-1=с-1.

Предположим, что все натуральные числа N? k (к?1) представимы в виде (1). Докажем что число к+1 так же представимо в виде (1). Для этого разделим с остатком число к+1 на с:

K+l=sс+r, 0<�г<�с-1, (2).

где s — неполное частное и г — остаток.

Так как число s? k, то оно по предположению индукции представимо в виде (1):

s = аnсn+. .. +a1с +а0, (3).

где 1? аn?с -1, 0? ai? сl, (i=0,1,., n-1).

Подставим выражения (2) и (3), получим:

k+l= (anс+ … +аiс +а0) с + г = аnс +… + aiс +a0с +г (4).

где 1? an? с -1, 0? aj? с -1, 0? г? с -1 0=0,1,.., n-1).

Это выражение (4) дает представление числа к+1 в виде (1):

К+1=b n+1с n+1 + bn с n + … + b1с +b0,.

где b0 =r, bi+1- ai (i=0,l,., n-l).

2. Докажем единственность представления любого натурального числа в виде (1).

Доказательство проведем методом математической индукции.

Для чисел 1, 2,…, с -1 представление в виде (1) единственно.

Предположим что для всех натуральных N? k (к?1) представление в виде (1) единственно. Докажем, что число к+1 может быть представлено в виде (1) только одним способом. Для этого разделим с остатком число к+1 на с:

K+l=sс+r, 0<�г< с -1 (5).

Предположим, что к+1 имеет два различных способа представления:

к+1=а nс n + аn-1 с n-1 + …+ а1с +а () (6).

к+1 =b mс m + bm-1 с m-1 + … + b1с +b0 (7).

Представим: равенства (6) и (7) в виде:

k+1= (а nс n-1 + an-1 с n-2+ … + а1) с+а0 (6*).

k+1 = (b mс m-1 + bm-1 с m-2+ … + b) с+b0 (7*).

Так как 0? а0? с -1 и 0? b0? с -1, то из (6*) и (7*) следует, что неполное частное s и остаток г в формуле (5) будут:

S= аnс n-1 + аn-1 с n-2 + … + a1=bmс m-1 + bm-1 с m-2+ … + b1. r = a0 = b0.

Так как s? k, из индуктивного предположения следует, что число s имеет единственно представление в виде (1), то есть:

n-l = m-l, ai =bi, (i=0,1,. ., n-1).

Из последнего равенства имеем а0=bо. Таким образом, n=m, ai=bi (i=0,l,. ., n-l), но это противоречит допущению, что число k+1. имеет два различных представления (6) и (7). Следовательно, число к+1 представляется в виде (1) единственным образом. На основании принципа математической индукции утверждение справедливо для любого N. Теорема доказана.

1.3 Десятичная система счисления, ее происхождение и применение.

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

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

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

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

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

Десятичная нумерация «изобретена» индусами; в Европу ее занесли арабы, вторгшиеся в Испанию в VIII в. нашей эры. Арабская нумерация распространилась по всей Европе, и, будучи проще и удобнее остальных систем счисления, быстро их вытеснила. До сих пор наши цифры принято называть арабскими. Впрочем, за тысячу лет все цифры, кроме 1 и 9, сильно изменились. Вот, для сравнения, наши (называемые арабскими) и настоящие арабские цифры (см. рис. 5):

Рис. 5 — Арабские цифры Названия первых шести разрядов (единицы, десятки, сотни, тысячи и так далее) очень древние и у разных народов звучат по-разному.

Слово «миллион» сравнительно недавнего происхождения. Придумал его известный венецианский путешественник Марко Поло, которому не хватало обыкновенных чисел, чтобы рассказать о необычайном изобилии людей и богатств далекой Небесной Империи (Китай). По-русски слову «миллион» могло бы соответствовать несуществующее слово «тысячища» .

Для построения числовых наименований более высоких порядков используются латинские числительные (биллионы, триллионы). Построенные таким образом названия мало удобны, латынь знают не все. Да и вообще такие числа встречаются только в сборниках математических курьезов, да в некоторых отделах теории чисел. Нет необходимости придумывать им рациональные названия. Здесь на помощь приходит понятие степени. Число, изображаемое единицей с нулями, является степенью десятки: 100= 102, 1000= 103, 10…00…00= 10n.

Эти соображения позволяют нам очень коротко и удобно записывать все числа, которые даются нам наукой и жизнью. Например, масса Земного шара — 6 000 000 000 000 000 000 000 тонн. Можно записать: 6 * 1021 тонн, и назвать «шесть на десять в двадцать первой степени», это коротко и удобно.

В практической жизни при счете предметов, которых очень много, например, жителей страны, при измерении различных величин, удается определить только первые несколько цифр результата. Любое число, данное практически, удается записать как произведение не более чем восьмизначного (чаще трех — четырехзначного) числа на «единицу с нулями». Например, поверхность Земли — 509 000 000 км2. Можно записать так: 509 * 106 км².

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

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

1.4 Системы счисления с другими основаниями, их происхождение и применение.

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

Двенадцатеричная система счисления — ее происхождение тоже связано со счетом на пальцах: так как четыре пальца руки (кроме большого) имеют в совокупности двенадцать фаланг, то по этим фалангам, перебирая их по очереди большим пальцем, и ведут счет от одного до двенадцати. Затем двенадцать принимается за единицу следующего разряда и так далее. В устной речи остатки двенадцатеричной системы сохранились и до наших дней: вместо того, чтобы сказать «двенадцать» часто говорят «дюжина». Многие предметы (ножи, вилки, тарелки) очень часто считают именно дюжинами, а не десятками; сервизы бывают, как правило, на двенадцать или шесть персон. Другой пример: двенадцать месяцев в году, двенадцать цифр на циферблате часов.

Восьмеричная система счисления — позиционная система счисления с основанием 8. Для представления чисел в ней используются арабские цифры. Используется всего восемь цифр — 0, 1, 2, 3, 4, 5, 6, 7. Восьмеричная система часто используется в областях, связанных с цифровыми устройствами. Характеризуется лёгким переводом восьмеричных чисел в двоичные и обратно, путём замены восьмеричных чисел на триады двоичных. Широко использовалась в программировании в 1950;70-ые гг. и вообще в компьютерной документации, однако в настоящее время почти полностью вытеснена шестнадцатеричной.

Шестидесятеричная система счисления существовала и возникла в Древнем Вавилоне. Мнения историков по поводу того, как именно возникла эта система, расходятся. Одна из гипотез, состоит в том, что произошло слияние двух племен, одно из которых пользовалось шестеричной системой счисления, а второе — десятичной. Шестидесятеричная система возникла как компромисс между этими двумя системами. Другая гипотеза состоит в том, что вавилоняне считали продолжительность года равной 360 суткам, что, естественно, связывалось с числом 60. однако это предположение тоже нельзя считать достаточно обоснованным: астрономические познания древних вавилонян были довольно значительны, поэтому следует думать, что погрешность, с которой определяется продолжительность года, была значительно меньше, чем пять суток.

Пятеричная система счисления была распространена у ряда африканских племен. Связь этой системы со строением человеческой руки — первоначальной «счетной машины» — достаточно очевидна. В Китае принято считать пятками, причем пятки группируются в пары; получается своеобразная система счисления, в которой каждая единица четного порядка в пять, а нечетного — в два раза больше предыдущей. Однако эта система счисления с двойным основанием, отражающая счет с помощью двух рук, довольно сложна. Гораздо чаще используется чистая пятеричная система, то есть позиционная система с основанием пять.

Двадцатеричная система счисления была принята у ацтеков и майянародов, населявших в течение многих столетий обширные области американского континента и создавших там высокую культуру, почти полностью уничтоженную испанскими завоевателями в XVI — XVII вв. Та же двадцатеричная система была принята и у кельтов, населявших Западную Европу, начиная со II в. до нашей эры.

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

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

1.5 Арифметические операции в различных системах счисления.

Сложение и вычитание В системе с основанием для обозначения нуля и первых с-1 натуральных чисел служат цифры 0, 1, 2, …, с — 1. Для выполнения операции сложения и вычитания составляется таблица сложения однозначных чисел.

Таблица 1 — Сложение в двоичной системе.

Например, таблица сложения в шестеричной системе счисления:

Таблица 2 — Сложение в шестеричной системе.

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

Например, Можно обосновать указанное правило сложения чисел, используя представление чисел в виде:

Разберем один из примеров:

3547=3*72+5*71+4*70.

2637=2*72+6*71+3*70.

Имеем:

(3*72+5*71+4*70) + (2*72+6*71+3*70) =(3+2)*72+(5+6)*7+(3+4)=.

=5*72+1*72+4*7+7=6*72+4*7+7=6*72+5*7+0=6507.

Последовательно выделяем слагаемые по степени основания 7, начиная с низшей, нулевой, степени.

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

Например, Умножение и деление Для выполнения действий умножения и деления в системе с основанием с составляется таблица умножения однозначных чисел.

Таблица 3 — Умножение однозначных чисел.

Таблица 4 — Умножение в шестеричной системе счисления.

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

Например, При умножении многозначных чисел в промежуточных результатах индекс основания не ставится:

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

Например:

Перевод чисел из одной системы счисления в другую Существует много различных способов перевода чисел из одной системы счисления в другую.

Способ деления Пусть дано число N=an an-1... a1 а0 р.

Для получения записи числа N в системе с основанием h следует представить его в виде:

N=bmhm+bm-1hm-1+… +b1h+b0 (1).

где 1.

N=bmbm-1… b1boh (2).

Из (1) получаем:

N= (bmhm-1+…+b)*h +b0 = N1h+b0, где 0? b0? h (3).

To есть, цифра b0 является остатком от деления числа N на число h. Неполное частное Nl = bmhm-1+. .. +b1 представим в виде:

Nl = (bmhm-2 + … + b2) h + b1 = N2h+b1, где 0? b2? h (4).

Таким образом, цифра bi в записи (2) числа N является остатком от деления первого неполного частного N1 на основание h новой системы счисления. Второе неполное частное N2 представим в виде:

N2 = (bmhm-3+ … +b3)h+b2, где 0? b2? h (5).

то есть цифра b2 является остатком от деления второго неполного частного N2 на основание h новой системы. Так как не полные частные убывают, то этот процесс конечен. И тогда мы получаем Nm = bm, где bm.

Nm-1 = bmh+bm.1 = Nmh+bm.1.

Таким образом, последовательность цифр bm, bm-1. ., b1, b0 в записи числа N в системе счисления с основанием h есть последовательность остатков последовательного деления числа N на основание h, взятая в обратной последовательности.

Рассмотрим пример: Выполнить перевод числа 123 в шестнадцатеричную систему счисления:

Таким образом, число 12 310=7(11)16 либо можно записать как 7B16.

Запишем число 340 227 в пятеричной системе счисления:

Таким образом, получаем, что 340 227=2333315.

1.6 Перевод с использованием десятичной системы счисления.

Любое число в любой системе счисления представимо в виде:

N = anpn+…+a1p+a0.

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

22 095=2*53+2*52+0*51+9*50=30 910.

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

2 208 097=2*75+2*74+0*73+8*72+0*71+9*70=388 177.

Таким способом можно перевести числа из одной системы в другую. Например: переведем число 6257 в 3-ичную систему счисления.

6257=6*72+2*71+5*70=6*49+2*7+5=31 310.

31 310=1*35+0*34+2*33+1*32+2*31+1*30=1*243+2*27+1*9+2*3+1=1 021 203. Ответ: 625т=1 021 203.

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

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

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

В самом общем случае смешанное число, содержащее целую и дробную части, представляется в виде суммы степеней десятки и Десятичные дроби являются частным случаем систематических дробей, которые можно строить аналогичным образом для любой позиционной системы счисления. Например, дробь 5−1 + 6−2 + 3−3 назвать восьмеричной и записать в виде: 0,5638. Правила арифметических действий над с — ичными дробями (основание системы — q) такие же, как и над десятичными, но при действиях с однозначными числами нужно пользоваться таблицами сложения и умножения для данной системы.

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

Например:

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

Общее правило перевода числа в систему счисления с основанием n:

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

Пример: 378,835 937 510 перевести в систему счисления с основанием q=8.

Итак, 378,835 937 510=572,6548.

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

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

Пример:

100 101 000 0102.

4 5 0 28.

111 111 101 000 010 000 1002.

7 7 5 0 2 0 48.

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

Например:

1001 0000 1100 0111 12.

9 0 С 7 116.

Например:

1111 1001 1101 0002.

F 9 D 016.

Данное правило работает и наоборот, то есть любое целое число можно перевести из восьмеричной в двоичную и из шестнадцатеричной в двоичную.

Например:

ГЛАВА 2. ИСПОЛЬЗОВАНИЕ ДВОИЧНОЙ СИСТЕМЫ СЧИСЛЕНИЯ НА ПРИМЕРАХ.

2.1 Деньги в конвертах и зерна на шахматной доске.

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

Конечно, можно просто заготовить конверты со всеми суммами от 1 до 1 000 000 000, но где взять столько денег на конверты?

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

Есть более рациональные подход к нашему делу. Надо положить в первый конверт 1 у.е., а в каждый следующий класть вдвое большую сумму, чем в предыдущий. Тогда, например, в 5-м конверте будет 16 у.е., в 10-м — 512 у.е., в 11-м -1024 у.е., в 21-м -1024 = 1 048 576 у.е., в 31-м -1024 = 1 073 741 824 у.е., но он, очевидно, уже не понадобится, а вот 30-й с 1 073 741 824/2 = 536 870 912 у.е. может и пригодиться. В общем случае сумма в (n + 1)-м конверте будет равна произведению n двоек, это число принято обозначать 2 и называть n-й степенью двойки. Условимся считать, что 20 = 1. проведенные выше вычисления основались на следующих свойствах операции возведения в степень: 2n2m = 2n+m, 2n /2m = 2n-m, (2n)m = 2nm.

Экспериментально легкое проверить, что любое число можно представить единственным образом в виде суммы различных меньших степеней двойки, и поэтому наша задача решена. Например, 30 000 = 214 + 213 + 212 + 210 + 28 + 25 + 24.

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

Ниже докажем, что, имея набор конвертов с суммами в 1 у.е., 2 у.е., 4 у.е., …, 2n у.е., любую сумму денег от 1 у.е. до 2n + 1 — 1 у.е. можно выдать единственным способом. Также будет доказано, что, действуя по описанному алгоритму, всегда получим этот способ выдачи требуемой суммы.

Вначале рассмотрим пример работы алгоритма с числом 2n — 1. Ясно, что на первом шаге выбрано число 2 n — 1, останется число 2n — 1 — 2 n — 1 = 2 n — 1 — 1, потом будет выбрано число 2 n — 2, и т. д., и в результате получится разложение: 2n — 1 = 2 n — 1 + 2 n — 2 + … + 22 + 21 + 20.

Но оно не показалось бы очевидным, если, не зная заранее ответа, пришлось бы вычислять сумму 1 + 2 + 4 + 8 + … + 2 n — 2 + 2 n — 1, называемую суммой геометрической прогрессии со знаменателем 2.

Ведь для этого пришлось бы выдумать какой-нибудь трюк наподобие следующего: 1 + 2 + 4 + 8 + … + 2 n — 2 + 2 n — 1 = 2 — 1 +2 + 4 + 8 + … + 2 n — 2 + 2 n — 1 = 4 — 1 + 4 + 8 + … + 2 n — 2 + 2 n — 1 = 8 — 1 + 8 + 16 + … + 2 n — 2 + 2 n — 1 = … = 2 n — 2 — 1 + 2 n — 2 + 2 n — 1 = 2 n — 1 — 1 + 2 n — 1 = 2 n — 1.

2. А теперь, используя данный трюк, вычислим произведение (2 + 1)* (22 + 1) * … *(22 n + 1).

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

Для N = 1 утверждение очевидно.

Пусть оно верно для всех N? N0. Пусть 2n — максимальная степень двойки, не превосходящая N, т. е. 2n? N0 < 2n + 1. Тогда по предположению индукции число представимо в виде суммы степеней двойки, меньших N0 — 2n? 2n. Следовательно, число N0 тоже представимо в виде суммы меньших степеней двойки (достаточно к представлению числа N0 — 2n добавить 2n). Кроме того, так как 1 + 2 + … + 2 n — 1 = 2n — 1 < 2n, то не существуют представления числа N0, не использующего 2n. Таким образом, доказана единственность такого представления.

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

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

Для краткой записи результата работы алгоритма над данным числом, а можно вместо разложения, которое и записать-то в общем виде без использования трехэтажных обозначений затруднительно, использовать последовательность показателей степеней (n1, …, nk), или, что еще удобнее (но не всегда короче), написать последовательность (am, …, a1) чисел 0 и 1, в которой ai = 1, если число 2i-1 входит в указанное выше разложение, и ai = 0 в противном случае. Тогда это разложение можно будет переписать в виде: a = a1 + 2a2 + 4a3 + … + 2m-1 am.

Ясно, что приведенный выше алгоритм позволяет строить такое представление, причем оно определяется однозначно, если предполагать, что старший его разряд am ненулевой. Это представление и называется двоичной записью числа а.

Увидите, что понятие двоичной записи очень похоже на понятие десятичной записи и в каком-то смысле даже проще.

Остался вопрос о минимальности найденной системе конвертов. В общем виде указанный выше прием предлагает для уплаты любой суммы от 1 до n использовать m конвертов с суммами 1, 2, 4, 8, …, 2m-1, где 2m-1? n < 2m. Меньшего количества конвертов может не хватить, потому что с помощью k < m конвертов можно уплатить не более чем 2k — 1 < 2m-1 ?n разных сумм, так как каждая сумма однозначно определяется ненулевым набором (a1,…, ak), в котором каждое число ai равно 1, если i-й конверт входит в эту сумму, и равно 0 в противном случае, а всего наборов длины k из нулей и единиц можно составить ровно 2k.

2.2 Применение систем счисления.

2.2.1 «Книга перемен».

Двоичная система, по крайней мере, в своей комбинаторной ипостаси, по существу была известна в Древнем Китае. В классической книге «И цзин» («Книга перемен») приведены так называемые «гексаграммы Фу-си», первая из которых имеет вид, а последняя (64-я) — вид, причем они расположены по кругу и занумерованы в точном соответствии с двоичной системой (нулями и единицами соответствуют сплошные и прерывистые линии). Китайцы не поленились придумать для этих диаграмм специальные иероглифы и названия (например, первая из них называлась «кунь», а последняя — «цянь», сплошной линии сопоставляется мужское начало янь, а прерывистой линии — женское начало инь).

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

«Книга перемен» очень древняя, возможно, одна из древнейших в мире, и кто ее написал — неизвестно. Она использовалась ранее, и используется в настоящее время, в том числе и на Западе, для гадания. В Европе с аналогичной целью используются карты Таро. В чем-то обе эти системы схожи, но Таро никак не связаны с двоичной системой, поэтому о них мы говорить не будем.

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

2.2.2 Азбука Морзе.

Сэмюель Морзе известен, однако, не только изобретением азбуки. Он был и художником-портретистом (его картина «Генерал Лафайет» до сих пор висит в нью-йоркском Сити-Холле), и одним из первых фотографов в Америке (учился делать дагерротипные фотографии у самого Луи Дагерра), и политиком (он балатировался в 1836 году на пост мэра Нью-Йорка), но самое главное его достижение — изобретение телеграфа (а азбука Морзе понадобилась ему для использования телеграфа). Заодно он изобрел устройство, которое называется реле. Именно из реле спустя сто лет после Морзе были построены первые компьютеры.

Начал свои работы в этом направление в 1832 году, запатентовал свое изобретение в 1836 году, но публичная демонстрация телеграфа произошла только 24 мая 1844 года. По телеграфной линии, соединяющей Вашингтон с Балтимором, была успешно передана фраза из Библии.

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

Азбука Морзе сопоставляет каждой букве алфавита последовательность из точек и тире. Естественней всего использовать такие последовательности длины 6, их всего 64 и хватит даже на русский алфавит. Но Морзе понимал, что длину сообщения желательно уменьшить, насколько возможно, поэтому он решил использовать последовательности длины не более 4, их всего 2 + 4 + 8 + 16 = 30. в русском алфавите пришлось не использовать буквы «э» и «ё» и отождествить мягкий и твердый знаки. Кроме того, наиболее часто используемых буквами он предложил давать самые короткие коды, чтобы уменьшить среднюю длину передаваемого сообщения. Эту идею в наше время используют с той же целью в алфавитном кодировании.