Перевод из десятичной системы счисления в двоичную

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

Главная Форумы Программирование Помощь с решением задач на Prolog Общие вопросы Перевод из десятичной системы счисления в двоичную

В этой теме 2 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 9 мес. назад.

  • Автор
    Сообщения
  • #2134

    questioner
    Участник

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

  • #2163

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

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

    Вложения:
  • #2165

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

    decimal_to_binary(PositiveDecimal, Accuracy, Binary):-
      PositiveDecimal > 0, !,
      positive_decimal_to_binary(PositiveDecimal, Accuracy, Binary).
    decimal_to_binary(NegativeDecimal, Accuracy, Binary):-
      PositiveDecimal is -NegativeDecimal,
      positive_decimal_to_binary(PositiveDecimal, Accuracy, PositiveBinary),
      divide_list(Binary, ["-", PositiveBinary]).

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

    В алгоритме можно выделить следующие части:

    1. разделение числа на целую и дробную части;
    2. перевод частей в двоичную систему счисления;
    3. соединение частей для получения результата.

    positive_decimal_to_binary(Decimal, Accuracy, Binary):-
      devide_on_integral_fractional(Decimal, Integral, Fractional),
      integral_to_binary(Integral, IntegralBinary),
      fractional_to_binary(Fractional, Accuracy, FractionalBinary),
      divide_list(Binary, [IntegralBinary, ".", FractionalBinary]).

    Предикат разделения числа на целую и дробную части использует встроенную функцию floor, выполняющую округление числа вниз до целого. Различные диалекты могут выполнять округление отрицательных по-разному (либо понимая “вниз” как “ближе к нулю”, либо как “меньше”), однако мы используем ее для обработки положительных чисел, поэтому проблем не должно возникнуть:

    devide_on_integral_fractional(Decimal, Integral, Fractional):-
      Integral is floor(Decimal),
      Fractional is Decimal - Integral.

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

    decimal_to_binary_digit(0, 48):-!.
    decimal_to_binary_digit(1, 49):-!.

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

    integral_to_binary(Decimal, Binary):-
      integral_to_binary(Decimal, "", Binary).

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

    integral_to_binary(Integral, Buffer, [BinaryDigit|Buffer]):-
      Integral < 2, !, decimal_to_binary_digit(Integral, BinaryDigit).
    integral_to_binary(Integral, Buffer, Binary):-
      NextIntegral is Integral div 2,
      Residue is Integral mod 2,
      decimal_to_binary_digit(Residue, BinaryDigit),
      integral_to_binary(NextIntegral, [BinaryDigit|Buffer], Binary).

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

    fractional_to_binary(0.0, _Accuracy, ""):-!.
    fractional_to_binary(_Fractional, 0, ""):-!.
    fractional_to_binary(Fractional, Accuracy, [BinaryDigit|FractionalBinaryTail]):-
      NextAccuracy is Accuracy - 1,
      DoubleFractional is Fractional * 2,
      devide_on_integral_fractional(DoubleFractional, Digit, NextFractional),
      decimal_to_binary_digit(Digit, BinaryDigit),
      fractional_to_binary(NextFractional, NextAccuracy, FractionalBinaryTail).

Для ответа в этой теме необходимо авторизоваться.