После обсуждения алгоритмов поиска цифр в строке возникла идея рассмотреть в том же ключе какие-нибудь другие задачи. Подходящей показалась задача преобразования целого числа из 16-ричной системы в десятичную: не очень громоздкая, с по меньшей мере одним очевидным алгоритмом и, может быть, многими неочевидными, и понятная.
Дана строка, содержащая целое неотрицательное число в 16-ричной системе. Число записано цифрами 0..9A..F (буквы — только большие), гарантируется, что символов, не являющихся цифрами, в строке нет. Требуется получить строку, содержащую десятичную запись такого числа. Длина входной строки не превосходит 100000 байт.
Пишите решения на любых языках — самые красивые, самые короткие, самые эффективные… Для решений на машине Тьюринга предлагаю использовать только символы «пробел, 0, 1» (новых не вводить), а цифры входа и выхода записывать четверками битов (разделенные пробелами или нет — на ваше усмотрение). На Brainfuck — входная строка должна вводиться, а выходная — печататься.
UPD. Использовать встроенный или библиотечный BigNum, конечно, хорошо, но как-то не очень интересно. Давайте обходиться без него!
Для затравки — решение на C# (которое нельзя назвать ни красивым, ни коротким, ни эффективным):
Дана строка, содержащая целое неотрицательное число в 16-ричной системе. Число записано цифрами 0..9A..F (буквы — только большие), гарантируется, что символов, не являющихся цифрами, в строке нет. Требуется получить строку, содержащую десятичную запись такого числа. Длина входной строки не превосходит 100000 байт.
Пишите решения на любых языках — самые красивые, самые короткие, самые эффективные… Для решений на машине Тьюринга предлагаю использовать только символы «пробел, 0, 1» (новых не вводить), а цифры входа и выхода записывать четверками битов (разделенные пробелами или нет — на ваше усмотрение). На Brainfuck — входная строка должна вводиться, а выходная — печататься.
UPD. Использовать встроенный или библиотечный BigNum, конечно, хорошо, но как-то не очень интересно. Давайте обходиться без него!
Для затравки — решение на C# (которое нельзя назвать ни красивым, ни коротким, ни эффективным):
static unsafe string Hex2Dec(string x) { int l=x.Length; int ll=l+l/4+3; sbyte[] m=new sbyte[ll]; int i=l; foreach(char c in x) m[--i]=(sbyte)(c<'A' ? c-'0' : c-'A'+10); int lk=ll; while(l>0) { int k=0,l1=0; while(l>0) { k=(k<<4)+m[--l]; m[l]=(sbyte)(k/10); if(l1==0 && k>=10) l1=l+1; k%=10; } m[--lk]=(sbyte)(k+48); l=l1; } string res; fixed(sbyte *c=m){ res=new string(c,lk,ll-lk); } return res; }