Оптимальный алгоритм преобразования в натуральное цело число...

← →
Suntechnic © (2003-06-18 17:31) [0]

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

Какие будут мнения господа программисты/математики?

← →
alxx © (2003-06-18 17:35) [1]

Так и запиши:

Массив: 1, 4, 54, 123, 245

Строка: 001004054123245

← →
Vlad Oshin © (2003-06-18 17:37) [2]

посимвольно в строку, потом строку в число?

← →
nikkie © (2003-06-18 17:39) [3]

написать процедуру деления на 10 с остатком числа, представленного массивом байт. оптимальней вряд ли получится.

← →
Suntechnic © (2003-06-18 17:41) [4]

>alxx ©, Vlad Oshin ©.

Может я недостаточно чётко выразился... но массив произвольной длины это и есть наше натуральное целое число. Если вам так проще, то представьте себе массив из 16 байт т.е. 128 бит т.е. наше натуральное целое число размером 128 бит.

← →
Suntechnic © (2003-06-18 17:44) [5]

>nikkie ©
Что на 10 то делить? Не совсем понял алгоритм. Поподробнее можно?

← →
Vlad Oshin © (2003-06-18 17:48) [6]

Int64 –2^63..2^63–1 signed 64-bit
а дальше как?
только нестандартно если

← →
Suntechnic © (2003-06-18 17:52) [7]

>Vlad Oshin ©
Я поэтому и подчеркнул в вопросе строковое .
Это ведь понятно, что ни один стандартный тип такое число вместить не может, иначе массив байт был бы ни к чему. Да это и не требуется. Требуется написать строковое представление этого числа.

← →
nikkie © (2003-06-18 17:54) [8]

>Что на 10 то делить? Не совсем понял алгоритм. Поподробнее можно?
воспринимай свое число как число записанное в 256-ричной системе счисления. реализуй алгоритм деления столбиком. чтобы перевести число в 10-чную систему, делим на 10, остаток - inttostr, а частное опять делим на 10 и т.п.

← →
Suntechnic © (2003-06-18 18:04) [9]

>nikkie ©
Ок. Спасибо, попробую.

← →
uw © (2003-06-18 18:57) [10]

>Suntechnic © (18.06.03 18:04)
>nikkie © (18.06.03 17:54)

Весь вопрос, как все делить на 10!

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

"1234"
+
" 345"
------
"1579"

Потом строчного умножения, потом перевода байта в 10-ю строку, а потом честно переводить, умножая и складывая, начиная с младшего байта. Т.е. берем младший байт, переводим в 10-ю систему, записываем в результирующую строку. Берем следующий байт, переводим в 10-ю систему, строчно умножаем на 256, складываем с результирующей строкой. И т.д., но каждый раз множитель увеличивается в 256 раз (его мы вычисляем в отдельной строке).

Насколько это оптимально – не знаю, но в постановке этого слова нет.

← →
nikkie © (2003-06-18 19:24) [11]

>Весь вопрос, как все делить на 10!
столбиком

>Насколько это оптимально – не знаю, но в постановке этого слова нет.
Оптимальный алгоритм преобразования в натуральное цело число...

← →
Suntechnic © (2003-06-19 00:43) [12]

Кому интересно вот имплементация на С#. Честно говоря использование 256-ричной системы не самый оптимальный подход, но на С# так удобнее обращаться с исходным массивом. Отдельное спасибо nikkie © за наводку :)

public static string ToNaturalNumberString(byte [] sourceArray) { StringBuilder targetString = new StringBuilder(); DivideByTen(sourceArray, targetString); return targetString.ToString(); } private static void DivideByTen(byte [] sourceArray, StringBuilder targetString) { byte quotient = 0; byte remainder = 0; ArrayList newByteArray = new ArrayList(); for(int i = 0; i < sourceArray.GetLength(0); i++) { quotient = (byte)((remainder * 256 + sourceArray[i]) / 10); remainder = (byte)((remainder * 256 + sourceArray[i]) % 10); if (quotient > 0) { newByteArray.Add(quotient); } } if (newByteArray.Count > 0) { DivideByTen((byte[])newByteArray.ToArray(typeof(byte)), targetString); } targetString.Append(remainder.ToString()); }

Если я правильно понял задачу, то возможен и немного другой подход - хранить в массиве сразу десятичные цифры, по две в каждом байте (BCD). Тогда преобразование в строку и обратно сводится к простейшему, а для арифметических операций наверняка есть готовые библиотеки (да и даже в модуле DB уже есть тип TBCD и функции BCDToCurr и CurrToBCD).

>Юрий Зотов © (19.06.03 08:45)
Дело в том, что исходный массив не формируется мной. Он передаётся в таком виде. Можно его конечно преобразовать в какой-нибудь другой формат, если конечно будет действительно оптимальнейший алгоритм, а так, ихмо, овчинка выделки не стоит. Реализация нужна именное на С#... всем хорош язык, но вот отдельные операции с массивами просто suxx... то что на С++ делается в одну строчку требует достаточно сложных телодвижений в С#.

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