"Информатика", Семакин И.Г., Залогова Л.А., Русаков С.В., Шестакова Л.В.
Программирование перевода чисел позволяет записать одно и то же значение в разных системах счисления — например, преобразовать десятичное число в двоичное или обратно. Алгоритмы основаны на позиционной записи: при переводе из десятичной системы число делят на новое основание, а при переводе в десятичную складывают вклады разрядов. В программе для этого используют целочисленное деление, остаток, умножение, сложение и циклы.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Система счисления — способ записи чисел с помощью определённого набора цифр и правил их использования. Например, в десятичной системе применяются цифры от 0 до 9, а в двоичной — только 0 и 1. Знание системы помогает понять, какие знаки допустимы в записи числа и как вычислить его значение.
Основание системы счисления — количество цифр, используемых в системе. У десятичной системы основание 10, у двоичной — 2; цифры в системе с основанием p имеют значения от 0 до p−1. Основание задаёт вес разрядов: справа налево он равен 1, p, p², p³ и так далее.
Позиционная запись числа — запись, в которой значение каждой цифры определяется её положением. Например, в числе 352 цифра 3 означает три сотни, а цифра 5 — пять десятков. Такое представление позволяет найти значение записи как сумму цифр, умноженных на веса их разрядов.
Перевод числа из одной системы счисления в другую — изменение записи числа без изменения его значения. Так, 25₁₀ и 11001₂ обозначают одно и то же число. Это нужно, чтобы представлять данные в удобной форме или выполнять вычисления в системе с другим основанием.
При переводе целого числа из десятичной системы в систему с основанием p используют деление на p, потому что остаток показывает, сколько единиц младшего разряда осталось после выделения полных групп по p. Частное содержит число таких групп и снова можно разделить на p. Повторяя действие, мы последовательно находим цифры следующих разрядов.
Остатки деления становятся цифрами новой записи: каждый из них находится между 0 и p−1, поэтому подходит для системы с основанием p. Первый остаток относится к разряду единиц, следующий — к разряду p, затем к p² и так далее. Значит, при обычном чтении результата остатки нужно переставить: последний полученный станет первой цифрой.
При переводе в десятичную систему запись раскрывают как сумму разрядных вкладов. Каждая цифра умножается на основание в степени, равной номеру разряда, если нумеровать справа с нуля. Например, в записи 101₂ значение равно 1·2² + 0·2¹ + 1·2⁰. Степени нужны именно потому, что каждый переход влево увеличивает вес разряда в p раз.
Эти действия удобно описывать циклом, который повторяет одну и ту же операцию для очередного разряда. В переводе из десятичной системы программа находит остаток оператором остатка и уменьшает число целочисленным делением на p. В обратном переводе она умножает накопленное значение на p и прибавляет цифру. Обычное деление здесь не подходит: дробное частное не соответствует следующему целому шагу алгоритма.
До вычислений программа должна проверить входные данные: основание должно быть допустимым, а каждая цифра — меньше основания. При делении нуля цикл может не запуститься ни разу, поэтому нулевую запись задают отдельной проверкой. Такая обработка предотвращает пустой результат и ошибки на некорректных данных.
| Элемент алгоритма | Из десятичной системы в систему с основанием p | Из системы с основанием p в десятичную |
|---|---|---|
| Основная операция | Последовательное деление на p | Умножение разрядов на степени p |
| Получаемая величина на каждом шаге | Остаток от деления | Значение разряда и его вклад в сумму |
| Порядок обработки результатов | Остатки записываются справа налево | Разряды обрабатываются слева направо |
| Условие окончания | Частное стало равно нулю | Обработаны все цифры записи |
| Основные программные операции | Целочисленное деление, остаток, цикл | Умножение, сложение, цикл |
Сначала определите, в каком направлении выполняется перевод: от этого зависит основная операция. Затем сравните порядок обработки и условие окончания цикла — именно здесь алгоритмы различаются. Строка о программных операциях помогает подобрать команды нужного языка.
Нужно получить цифры, деля число на 2, и сохранить остатки. Остатки возникают от младшего разряда к старшему, поэтому после вычислений их следует прочитать в обратном порядке. Каждый шаг использует целочисленное деление, иначе частное перестанет быть целым.
Читаем остатки снизу вверх: 11001. Проверка: 1·2⁴ + 1·2³ + 0·2² + 0·2¹ + 1·2⁰ = 16 + 8 + 1 = 25. Ответ: 25₁₀ = 11001₂.
Можно раскрыть запись через степени двойки, но в программе удобнее накапливать результат слева направо. Перед добавлением очередной цифры уже набранное значение сдвигается на один двоичный разряд, то есть умножается на 2. Затем к нему прибавляется новая цифра.
Все цифры обработаны, значит, цикл можно завершить. Проверка по степеням: 1·2⁵ + 1·2⁴ + 0·2³ + 1·2² + 0·2¹ + 1·2⁰ = 53. Ответ: 110101₂ = 53₁₀.
Алгоритм для двоичной системы меняется только основанием деления: вместо 2 используется введённое p. Пусть программа принимает целое неотрицательное число n и основание p от 2 до 10. Результат удобно собирать как строку, добавляя очередную цифру слева, поскольку остатки находятся в обратном порядке.
Здесь // означает целочисленное деление, а % — остаток. Например, для n = 25 и p = 3 остатки при делении — 1, 2, 2; добавление каждого остатка в начало строки даёт 221. Проверка: 2·3² + 2·3 + 1 = 25, поэтому ответ: 25₁₀ = 221₃.
Остатки выводят в порядке получения. Так делают, потому что первый остаток кажется первой цифрой результата, но он относится к самому младшему разряду. Проверьте порядок на примере 25: остатки 1, 0, 0, 1, 1 дают двоичную запись 11001, а не 10011. Обратный перевод неверной записи быстро обнаружит ошибку.
Забывают степени основания или неверно нумеруют разряды. Иногда считают первый разряд справа степенью 1, хотя его вес равен p⁰ = 1. Запишите для каждого разряда соответствующую степень, начиная с нуля справа. Затем сравните полученную сумму с исходным числом.
Вместо целочисленного деления используют обычное. Это происходит, если команда деления возвращает дробное значение, например 12 / 2 = 6.0, и его продолжают делить как число с плавающей точкой. Используйте деление нацело и отдельно вычисляйте остаток; проверьте, что частные в таблице деления остаются целыми.
Не обрабатывают ноль или допускают недопустимые цифры. Для нуля цикл деления может сразу пропустить все шаги, оставив пустой результат; в числе с основанием p цифра также не может быть равна p или больше. Проверьте нулевой ввод отдельно, а для каждой цифры выполните условие 0 ≤ цифра < p. Такие проверки помогают получить либо корректную запись, либо понятное сообщение об ошибке.
Для понимания алгоритмов нужны позиционная запись числа, основание системы счисления, степени и разряды. Если представить число как сумму разрядных вкладов, становится ясным, почему в одном направлении применяют деление, а в другом — умножение и сложение. Знание степеней помогает проверять результат перевода.
В программировании пригодятся целочисленное деление, нахождение остатка и циклы. Условия цикла определяют, когда обработка закончится, а проверка данных не позволяет использовать недопустимое основание или цифру. Эти приёмы встречаются и в других алгоритмах обработки целых чисел.
Перевод систем счисления связан с тем, как данные представлены в памяти компьютера, и с двоичной арифметикой. Те же идеи используются при обработке строк: цифры записи можно читать по одной и постепенно строить результат. Поэтому алгоритм перевода служит основой для более сложных задач с числами и текстовыми данными.
Почему остатки при переводе из десятичной системы нужно записывать в обратном порядке?
Первый остаток показывает цифру младшего разряда, то есть разряда единиц. Следующие остатки соответствуют всё более старшим разрядам, поэтому запись результата начинается с последнего полученного остатка.
Как перевести число, если основание системы больше 10 и одной цифры недостаточно?
Для цифр со значениями от 10 обычно используют буквы: например, A означает 10, B — 11. В программе каждому символу нужно сопоставить его числовое значение и проверять, что оно меньше основания системы.
Почему при переводе в десятичную систему удобнее обрабатывать цифры слева направо?
При таком порядке можно на каждом шаге умножить уже накопленное значение на основание и прибавить очередную цифру. Это равносильно сумме цифр, умноженных на степени основания, но не требует отдельно вычислять эти степени.
Как в программе отличить целочисленное деление от обычного?
Целочисленное деление оставляет только целую часть частного, а остаток получают отдельной операцией. Например, во многих языках программирования для деления нацело используют оператор //, а для остатка — %; точное обозначение зависит от языка.
Что должна вывести программа, если исходное число равно нулю?
Она должна вывести запись 0. При последовательном делении цикл может не выполниться ни разу, поэтому ноль обрабатывают отдельной проверкой до запуска цикла.
2.1. Программирование перевода чисел из одной системы счисления в другую
