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

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

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

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

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

    questioner
    Участник

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

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

    Я напишу реализацию на SWI Prolog, однако она подойдет для любого другого диалекта. В решении я обрабатываю строки как списки символов, поэтому в Turbo/Visual Prolog вам придется выполнить такое преобразование до обработки.

    Первое, что нам потребуется — преобразование тетрады в шестнадцатеричную цифру, всего есть 16 вариантов таких тетрад:

    quartet_bin_to_hex_digit([0'0, 0'0, 0'0, 0'0], 0'0).
    quartet_bin_to_hex_digit([0'0, 0'0, 0'0, 0'1], 0'1).
    quartet_bin_to_hex_digit([0'0, 0'0, 0'1, 0'0], 0'2).
    quartet_bin_to_hex_digit([0'0, 0'0, 0'1, 0'1], 0'3).
    quartet_bin_to_hex_digit([0'0, 0'1, 0'0, 0'0], 0'4).
    quartet_bin_to_hex_digit([0'0, 0'1, 0'0, 0'1], 0'5).
    quartet_bin_to_hex_digit([0'0, 0'1, 0'1, 0'0], 0'6).
    quartet_bin_to_hex_digit([0'0, 0'1, 0'1, 0'1], 0'7).
    quartet_bin_to_hex_digit([0'1, 0'0, 0'0, 0'0], 0'8).
    quartet_bin_to_hex_digit([0'1, 0'0, 0'0, 0'1], 0'9).
    quartet_bin_to_hex_digit([0'1, 0'0, 0'1, 0'0], 0'A).
    quartet_bin_to_hex_digit([0'1, 0'0, 0'1, 0'1], 0'B).
    quartet_bin_to_hex_digit([0'1, 0'1, 0'0, 0'0], 0'C).
    quartet_bin_to_hex_digit([0'1, 0'1, 0'0, 0'1], 0'D).
    quartet_bin_to_hex_digit([0'1, 0'1, 0'1, 0'0], 0'E).
    quartet_bin_to_hex_digit([0'1, 0'1, 0'1, 0'1], 0'F).

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

    bin_to_hex(BinNumberList, HexNumberList):-
      reverse(BinNumberList, ReverseBinNumberList),
      reverse_bin_to_hex(ReverseBinNumberList, [], HexNumberList).

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

    Функция reverse_bin_to_hex должна:

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

    reverse_bin_to_hex([], HexNumberList, HexNumberList):-!.
    reverse_bin_to_hex([ADigit], Buffer, HexNumberList):-
      !, reverse_bin_to_hex([ADigit, 0'0, 0'0, 0'0], Buffer, HexNumberList).
    reverse_bin_to_hex([ADigit, BDigit], Buffer, HexNumberList):-
      !, reverse_bin_to_hex([ADigit, BDigit, 0'0, 0'0], Buffer, HexNumberList).
    reverse_bin_to_hex([ADigit, BDigit, CDigit], Buffer, HexNumberList):-
      !, reverse_bin_to_hex([ADigit, BDigit, CDigit, 0'0], Buffer, HexNumberList).
    reverse_bin_to_hex([ADigit, BDigit, CDigit, DDigit|TailNumber], Buffer, HexNumberList):-
      quartet_bin_to_hex_digit([DDigit, CDigit, BDigit, ADigit], HexDigit),
      reverse_bin_to_hex(TailNumber, [HexDigit|Buffer], HexNumberList).

    Вложения:

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