Алгоритм перехода в другую систему счисления

#алгоритм #любой_язык #системы_счисления

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


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


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

Ответы

Ответ 1

В данном случае вполне применим жадный алгоритм - сначала набираете делением с остатком
наибольшие единицы (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


Ответ 3

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


дано число X 
Делим на цело Х на 4: d = X div 4
В результирующую строку вставляем d cимволов С
Остаток от деления Х на 4: m = X mod 4
Берем остаток от деления m на 2: m1 = m mod 2 и частное d1 = m div 2
Если d1 равно 1, добавляем в результирующую строку В, если равно нулю, то ничего
Если m1 равно 1, добавляем в результирующую строку A, если равно нулю, то ничего


Ответ 4

Решение на python-3.7:

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