Текст в кавычках дает некоторую предысторию моей программы на тот случай, если это необходимо для понимания моей проблемы, вы можете полностью разобраться с вещами в конце без кавычек, если вам не хочется читать их.
Я работаю над общим проектом сортировки в C ++, и я
в данный момент занимаюсь сортировкой radix. У меня есть это как функция, принимая в
вектор строк, целое число, содержащее максимальное количество цифр, и
целое число с основанием / основанием чисел: (числа, maxDigits, основание)Так как программа принимает числа различной базы и в виде строки,
Я использую стои, чтобы преобразовать их в целое число 10, чтобы сделать
процесс проще обобщить. Вот краткое описание алгоритма:
- создать 10 очередей для хранения значений от 0 до 9
- перебирать каждую цифру (maxDigit times)
- перебирать каждое число в векторе (здесь оно преобразуется в основание 10)
- положить их в очередь на основе текущей цифры, на которую он смотрит
- вытащить числа из очередей от начала до конца обратно в вектор
Что касается проблемы, которую я пытаюсь обернуть вокруг себя, я хочу изменить значение maxDigit (с любым основанием, введенным пользователем) на значение maxDigit после его преобразования в базу 10. Другими словами, скажем, пользователь использовал код
radixSort(myVector, 8, 2)
чтобы отсортировать вектор чисел с максимальным числом цифр 8 и основанием 2. Поскольку я преобразовываю основание числа в 10, я пытаюсь найти алгоритм, который также изменяет значения maxDigits, если это имеет смысл.
Я так старался думать об этом, пытаясь найти простой способ проб и ошибок. Если бы я мог получить несколько советов или помочь в правильном направлении, это было бы очень полезно.
Если что-то находится в основаниях 2 и максимальных цифрах 8, то его наибольшее значение это все. А также 11111111
= 255, что составляет (2 ^ 8 — 1).
Максимальные цифры в базе 10 будут теми, которые необходимы для представления этого наибольшего значения. Здесь мы видим, что это 3. Что является логарифмом основания 10 из 255 (2.40654018043), округленным до 3.
Так что в основном просто округлить log10 (radix^maxdigits - 1)
до ближайшего целого числа.