Алгоритмы анализа и преобразования записей чисел в позиционной системе счисления сообщение

Обновлено: 15.05.2024

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

Классические алгоритмы

Обычно ими дело и ограничивается. Учитель даже может показать вывод или иное теоретическое обоснование алгоритмам деления с остатком, вычитания, умножения на степени. Их я трогать не буду, о них уже сказано и написано столько, что даже ленивый найдёт. И повторять учителя я не намерен.

Первоосновы

От этого посыла и будем отталкиваться.

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

Практика

Давайте подготовимся к практике. Вам стоит запастись пуговицами, гайками, шайбами, болтами и прочими мелочами разного размера. Нам надо три-четыре размера по 20-30 предметов каждого. Итого 60-120 предметов. Монеты не подойдут! На них написаны цифры. Карандаш, резинка и тетрадный лист в крупную клетку. Вот именно хорошо в крупную, обычная школьная не удобная будет, там в клеточку трудно впихнуть 2-3 цифры.

Запаслись? Я для определённости запасусь болтами , гайками и шайбами . Договоримся о правилах " размена ":

  • Болт>гайки>шайбы. Болт ценнее гайки, а гайка ценнее шайбы.
  • Есть порогразмена , который в каждой задаче мы будем устанавливать свой. Это такое количество предметов, которое можно заменить на более ценный или, наоборот, которое можно получить за один ценный.
  • Размен можно осуществлять в любое время и в любом направлении, но только на один шаг (нельзя разменивать сразу шайбы на болты, только через гайки).
  • В размене участвует только один ценный предмет. (Например, нельзя обменять сразу две гайки на шайбы, только по очереди)

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

. - 5

. - 7

. - 9

. - B

И так далее. До бесконечности.

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

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

Счёт по порядку

Установим порог размена на 10. То есть, десять шайб можно заменить на одну гайку, десять гаек - на один болт. И в обратном направлении тоже.

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

Одну шайбу заменить нельзя, я оставлю её и запишу

Возьму ещё одну. Тоже без размена.

Теперь беру ещё одну шайбу. Чтобы записать 10 шайб у меня есть буква A,

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

И так далее. Можно остановиться еще через 10-15 ходов. Ничего нового уже не будет, главное, не забыть разменять шайбы на гайку, когда их снова 10 штук наберётся. Сбрасываем все, что насобирали обратно.

Ставим порог размена на 8. Теперь мы будем разменивать уже 8 шайб на гайку, и 8 гаек на болт.

Снова берём шайбы по одной и записываем в новый столбик рядом:

Берём ещё одну, получаем 8 шайб. Их мы смело меняем на одну гайку:

Заметьте, что написано "010", но у нас не десять шайб, а восемь . Одна гайка теперь "ст о ит" как 8 шайб

Самостоятельно попытайтесь сделать это с порогами обмена 5, 3, 7, 2 и 16. В комментариях пишите, что получилось.

Пояснение

Порог обмена на самом деле принято называть основанием системы счисления . Это ключевое число, оно показывает очень много чего. Например, обратили внимание, сколько в каждои столбике используется разных цифр? Считается, что если Вы выбрали основание , то Вы полностью задали и систему счисления. Запись числа обязательно требует, чтобы основание было известно. Потому что по записи 021 не понятно, то ли Вы 2 раза по 10 шайб заменили, то ли по 8.

В восьмеричной системе "023" будет значить, что Вы взяли 19 шайб и два раза заменили 8 шайб на 1 гайку. Еще раз

Если поменять условие - задать порог размена в 6, то запись будет "31".

Перевод между системами

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

Выполним перевод числа из 12тиричной системы счисления в девятиричную.

Что эта запись означает? Что надо взять 2 гайки и 11 шайб (цифра C означает 11).

Теперь определим, сколько это в шайбах. Порог размена у нас 12, значит за одну гайку дают 12 шайб. А у нас две гайки, они "ст о ят" как 24 шайбы. И ещё 11 было. Итого 35 шайб.

Теперь их надо записать с порогом размена 9. Каждые 9 шайб меняем на одну гайку. Сколько раз получается? 3 раза. И ещё остались 8 шайб. Больше менять нечего. Запишем:

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

Тем не менее, я к этим способам ещё свой добавлю.

Зададимся порогом в 7. Сколько шайб ст о ит гайка? 7. А сколько шайб будет ст о ить болт? 7 гаек по 7 шайб каждая. То есть 49 шайб. А если возьмём более весомый предмет? Саморез, например. Он будет стоить 7 болтов, по 49 шайб, или 343 шайбы. Вес следующего предмета растёт в 7 раз по сравнению с предыдущим.

Такая запись значит:

Тут не трудно догадаться, что вообще во всех числах, которые мы записываем цифрами, вообще-то зашифрованы действия! Обычное число 176 означает 1 сотня, 7 десятков и 6 единиц. В других системах счисления (например с картинки сверху) 4 значат уже не 4 десятка, а 4 семёрки. В этом случае можно называть их семиричными десятками .

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

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

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

Надо перевести число 538 из десятичной в восьмеричную.

Веса разрядов (будем вместо болтов и гаек уже писать правильно) соответственно

. 4096, 512, 64, 8, 1 - каждый следующий в 8 раз больше предыдущего

Не знаю, как вам, а мне видно, что 4096 в 538 ни разу не поместится. А вот 512 поместится один раз и ещё останется. Остаток будет 26. В 26 64 ни разу не влезет, а вот 8ка влезет трижды. И ещё останется 2 раза по одному.

Нули слева обычно не пишут, поэтому

Получилось довольно громоздко и вместе с тем скомкано, но тема и в самом деле большая. Если что-то не понятно, обязательно спрашивайте в комментариях!

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

Требования к знаниям и умениям:

Учащиеся должны знать:

Учащиеся должны уметь:

  • приводить примеры различных систем счисления;
  • отличать позиционные и непозиционные системы счисления;
  • записывать числа в развернутой форме;
  • переводить числа из одной системы счисления в другую с использованием соответствующих алгоритмов.

У учеников формируется и развивается:

  • информационная компетентность;
  • компетентность разрешения проблем.

Презентация к уроку (приложение 2)

Ход урока

I. Постановка целей урока

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

II. Повторение закрепление пройденного.

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

Самое главное, что нужно знать о системе счисления - ее тип: позиционная она или непозиционная. По-другому еще говорят: мультипликативная (позиционная) или аддитивная. Напомню, что в первом типе каждая цифра имеет свое значение, и для прочтения числа нужно сложить все значения использованных цифр:

XXXV = 10+10+10+5 = 35; CCXIX = 100+100+10-1+10 = 219;

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

(иероглифы по порядку: 2, 1000, 4, 100, 2, 10, 5)

Здесь дважды использован иероглиф "2", и в каждом случае он принимал разные значения "2000" и "20".

2 1000 + 4 100+2 10+5 = 2425

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

Вопросы к ученикам:

  1. Чем отличается цифра от числа?
  2. Что такое основание системы счисления?
  3. Кто и когда считал пятерками и дюжинами?
  4. Какие недостатки у непозиционной системы счисления вы можете назвать?
  5. Как записать развернутую форму числа в позиционной системе счисления?
  6. Как перевести числа из разных систем счисления в десятичную?

III. Изучение нового материала.

Какая из всевозможных систем счисления применяется в компьютерах?

Нам с вами, конечно, наиболее привычна и понятна десятичная система счисления. И может показаться, что ни в каком случае лучше ее нет. Но не надо абсолютизировать роль десятичной системы: для некоторых применений вполне может оказаться гораздо удобнее другая система представления чисел. Это утверждение прекрасно подходит и к способу хранения чисел в ЭВМ. Какую же числовую систему удобно положить в основу компьютера? С точки зрения человека, конечно, лучше всего традиционная десятичная система. Но вот технически реализовать ее на ЭВМ крайне сложно: для хранения десятичной цифры требуется устройство с десятью устойчивыми состояниями! Разработать такую электрическую схему можно, но она будет достаточно сложной и дорогой (не забывайте, что таких элементов потребуется огромное количество!)

Итак, приходится отказаться от "милой сердцу" десятичной системы и использовать другую. Какую? Все остальные человеку одинаково непривычны, поэтому смело можно выбирать наиболее удобный с технической точки зрения вариант. Для инженеров наиболее просто реализовать двоичный элемент: включено/выключено, горит/не горит, проводит/не проводит и т.д. Кроме того, в двоичной системе наиболее просто реализуются все операции: например, двоичная таблица умножения состоит всего из четырех строк:

0 х 0 = 0
0 х 1 = 0
1 х 0 = 0
1 х 1 = 1.

Итак, в ЭВМ используют двоичную систему потому, что она имеет ряд преимуществ перед другими:

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

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

Восьмеричная система счисления. Используется восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7. Употребляется в ЭВМ как вспомогательная для записи информации в сокращенном виде. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада).

Шестнадцатеричная система счисления. Для изображения чисел употребляются 16 цифр. Первые десять цифр этой системы обозначаются цифрами от 0 до 9, а старшие шесть цифр - латинскими буквами: 10-A, 11-B, 12-C, 13-D, 14-E, 15-F. Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы счисления используется четыре двоичных разряда (тетрада).

IV. Закрепление пройденного.

Для закрепления материала предлагается следующие 3 задания.

Первое задание

Вид компетентности: Информационная компетентность

Аспект: планирование и поиск информации

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

Вид компетентности: компетентность разрешения проблем ;

Аспект: действия по решению проблемы;

Второе задание

Вид компетентности: компетентность разрешения проблем;

Аспект: действия по решению проблемы;

Уровень третий: конструирует (создает) алгоритм действий.

Третье задание

Вид компетентности: компетентность разрешения проблем;

Аспект: действия по решению проблемы;

Уровень первый: использует предложенный алгоритм действий.

Уровень третий: применяет им же созданный алгоритм действий.

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

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

Дополнительные задания Д1 и Д2 предназначены для наиболее сильных учеников, которые раньше других справились со всеми тремя заданиями. Результаты - также в электронном виде.

Задание 1. Прочитайте внимательно Текст №1, приведенный ниже, и на его основе:

1.1. Сформулируйте алгоритм перевода чисел из десятичной системы счисления в системы с другим основанием в виде:

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

Целые числа в любой системе счисления порождаются с помощью правила счета : Для образования целого числа, следующего за любым данным целым числом, нужно продвинуть самую правую цифру числа; если какая-либо цифра после продвижения стала нулем, то нужно продвинуть цифру, стоящую слева от неё.

Продвинуть цифру 1 значит заменить её на 2, продвинуть цифру 2 значит заменить её на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену её на 0. В двоичной системе, использующей только две цифры – 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 – замену её на 0.

Пример 1. Применяя правило счета, запишем первые десять целых чисел:

в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001;

в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100;

в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14;

в восьмеричной системе: 0, 1, 2, 3, 4, 5, 6, 7, 10, 11.

Алгоритмы перевода чисел из одной позиционной системы исчисление в другую.

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

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

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

Пример 2. Переведем число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:


Пример 3. Переведем число 0,36 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:


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

где: – i -я цифра числа; – количество цифр в целой части числа; – количество цифр в дробной части числа; – основание системы счисления.

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

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


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

Читайте также: