3

имеется следующий алфавит

A=1; B=2; C=4;

Число 10, например, переводится как CCB, число 7 как CBA. Как может выглядеть алгоритм, который преобразует число новую систему с наименьшим числом символов (должно быть не AAAAA, а CA) На любом языке ответ приемлем, заранее спасибо)

4 ответа 4

6

В данном случае вполне применим жадный алгоритм - сначала набираете делением с остатком наибольшие единицы (C), затем меньшие (B) и потом совсем малые(A).

Типа 11 - сколько можно набрать C? только 2, итак - CC, остается 3. Его можно представить одним B с остатком 1 - итак, CCB и остаток 1 - т.е. A, так что окончательно - CCBA.

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

Думаю, закодировать проблемы быть не должно...

P.S. Так, как вы сформулировали - это задача о размене, но не о переходе в другую систему счисления...

2

Например на Питоне с использованием словаря алфавита:

alph = {4: 'C', 2: 'B', 1: 'A'}
x = int(input())
answ = ''
Keys = list(alph.keys())
for k in Keys:
   a = x // k
   answ += a * alph[k]
   x -= a * k
4
  • Не работает, например, x = 10; answ = 'AAAAAAAAAA' .
    – nomnoms12
    25 июл 2019 в 12:45
  • @nomnoms12, Keys.reverse() была лишней, так как базовый интерпретатор изначально расставляет в верном порядке. Если необходимо, то можно использовать sorted()
    – Dareten
    26 июл 2019 в 8:12
  • Теперь работает, плюсанул Вас. Вот только упростить можно. Например, убрать Keys = list(alph.keys()) и итерировать сразу словарь (будут возвращаться ключи).
    – nomnoms12
    26 июл 2019 в 9:00
  • 1
    А питон порядок ключей гарантирует?
    – Qwertiy
    26 июл 2019 в 10:13
1

Просто опишу:

  1. дано число X
  2. Делим на цело Х на 4: d = X div 4
  3. В результирующую строку вставляем d cимволов С
  4. Остаток от деления Х на 4: m = X mod 4
  5. Берем остаток от деления m на 2: m1 = m mod 2 и частное d1 = m div 2
  6. Если d1 равно 1, добавляем в результирующую строку В, если равно нулю, то ничего
  7. Если m1 равно 1, добавляем в результирующую строку A, если равно нулю, то ничего
4
  • Пятый пункт неверный. И шестой.
    – Qwertiy
    26 июл 2019 в 8:39
  • @Qwertiy, да, увидел. Упустил кое-что.... :)) 26 июл 2019 в 9:41
  • Да, так лучше :)
    – Qwertiy
    26 июл 2019 в 10:12
  • @Qwertiy, спасибо за подсказку. Мне нужно быть внимательнее :) 26 июл 2019 в 12:05
0

Решение на :

ALPH = {4: 'C', 2: 'B', 1: 'A'}


def convert(num: int) -> str:
    assert num >= 1

    new_num = ''
    for key in ALPH:
        while num >= key:
            num -= key
            new_num += ALPH[key]

    return new_num


print(convert(int(input())))

Тесты:

print(convert(11))  # CCBA
print(convert(10))  # CCB
print(convert(7))   # CBA
2
  • А питон гарантирует порядок ключей?
    – Qwertiy
    26 июл 2019 в 10:13
  • @Qwertiy, да, начиная с версии 3.7. Уточню версию в ответе.
    – nomnoms12
    26 июл 2019 в 10:43

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.