Mrrl Feb 13 2011 at 23:34

Преобразование hex->dec — ищем красивые решения

1 min

31K

Abnormal programming*

Comments 46

blo Feb 13 2011 at 23:46

Javascript

function hex2dec(n){
    return parseInt(n, 10)
}

-2

Mrrl Feb 13 2011 at 23:54

Тогда уж parseInt(n,16). И что она сделает, если подать на вход строку в 100 мегабайт длиной?

blo Feb 14 2011 at 00:06

как раз parseInt(n, 16) вернет число в 16-тиричной системе счисления, у нас то на выходе должна быть десятичная?

по поводу 100 мегабайт — в условии про это ни слова.

max7 Feb 14 2011 at 00:14

Ась?

function hex2dec(n) { return parseInt(n, 16).toString(10) }

blo Feb 14 2011 at 00:17

может мне пора спать, но попробуйте hex2dec(0xff)

Mrrl Feb 14 2011 at 00:31

По условию, входная строка состоит только из 16-ричных цифр (большими буквами) безо всяких 0x.

barmaley_exe Feb 14 2011 at 01:39

parseInt возвращает число. Все числа в JS десятичные. 0xFF — всего-лишь другой способ записи десятичных чисел.
Зато метод toString для объектов типа Number возвращает строковое представление числа в соответствующей аргументу системе счисления.

Таким образом, правильным решением будет parseInt(n, 16)

Mrrl Feb 14 2011 at 00:30

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

seagull Feb 14 2011 at 00:09

.bat файл

@echo off

setlocal enabledelayedexpansion

set /a result=0

set all=%1

set /a mult=1

:START

set dig=!all:~-1,1!

set all=!all:~0,-1!

if '!dig!'=='0' set /a number=0

if '!dig!'=='1' set /a number=1

if '!dig!'=='2' set /a number=2

if '!dig!'=='3' set /a number=3

if '!dig!'=='4' set /a number=4

if '!dig!'=='5' set /a number=5

if '!dig!'=='6' set /a number=6

if '!dig!'=='7' set /a number=7

if '!dig!'=='8' set /a number=8

if '!dig!'=='9' set /a number=9

if '!dig!'=='A' set /a number=10

if '!dig!'=='B' set /a number=11

if '!dig!'=='C' set /a number=12

if '!dig!'=='D' set /a number=13

if '!dig!'=='E' set /a number=14

if '!dig!'=='F' set /a number=15

set /a result=!result!+(!mult!*!number!)

set /a mult=!mult!*16

if not '!all!'=='' goto START

echo !result!

Shuichi Feb 14 2011 at 10:21

Месье?

seagull Feb 14 2011 at 20:46

Можно короче:

@echo off && setlocal enabledelayedexpansion && set all=%1

set mult=1

:START

set dig=!all:~-1,1!

set all=!all:~0,-1!

if '!dig!'=='A' set dig=10 

if '!dig!'=='B' set dig=11

if '!dig!'=='C' set dig=12

if '!dig!'=='D' set dig=13

if '!dig!'=='E' set dig=14 

if '!dig!'=='F' set dig=15

set /a result=!result!+(!mult!*!dig!)

set /a mult=!mult!*16

if not '!all!'=='' goto START

echo !result!

kk86 Feb 14 2011 at 00:33

Может я чего не понял, но как связано ненормальное программирование и поставленная задача? И как можно приглашать написать своё решение, а потом давать такое решение на С#? Уж извините за неконструктивную критику.

Mrrl Feb 14 2011 at 00:39

Я же предлагаю писать красивые, короткие и эффективные решения. Поэтому предложить вариант, который не является ни тем, ни другим, ни третьим вполне можно — хлеб ни у кого не отбиваю. Наоборот, предлагаю улучшить. А ненормальное — потому что набор языков не ограничен, решения на эзотерических языках только приветствуются. Но может быть, я неправильно понимаю предполагаемый смысл «ненормальности».

kk86 Feb 14 2011 at 00:44

Теперь ясно. Просто читать и понимать представленный код было очень тяжело. Более человечное (человекоснисходительное) именование не помешает.

Mrrl Feb 14 2011 at 00:53

Понятно. Придумывать имена локальным переменным, область существования которых меньше одного экрана, я так и не научился. А программу немного исправил — теперь она не будет перезахватывать строку много раз.

kk86 Feb 14 2011 at 00:57

А я пока не научился читать код. У меня напарник пишет в похожем стиле, а я никак не привыкну. )

LighteR Feb 14 2011 at 01:00

python:

reduce(lambda x,y:x+y, [(int© if c<'A' else ord©-ord('A')+10)*16**p for p,c in zip(xrange(len(str)),str[::-1])])

Mrrl Feb 14 2011 at 01:03

А оно выдает строку? Или только число?

LighteR Feb 14 2011 at 01:03

парсер — лох:
везде вместо © необходимо c в круглых скобках

Mrrl Feb 14 2011 at 06:20

В этом языке тип bignum используется по умолчанию? Если нет — то 16**p начиная с не очень больших значений (32? 64?) даст потерю точности. Думаю, что на таком функционале было бы несложно написать и полное решение для любой длины.

LighteR Feb 14 2011 at 11:09

Все будет в порядке:

>>> 16**1024

10443888814131525066917527107166243825799642490473837803842334832839539079715574

56848826811934997558340890106714439262837987573438185793607263236087851365277945

95697654370999834036159013438371831442807001185594622637631883939771274567233468

43445866174968079087058037040712840487401186091144679777835980290066869389768817

87785946905630190260940599579453432823469303026696443059025015972399867714215541

69383555988529148631823791443449673408781187263949647510018904134900841706167509

36683338505510329720882695507699836163694119330152137968258371880918336567512213

18492846368125550225998300412344784862595674492194617023806505913245610825731835

38008760862210283427019769820231316901767800667519548507992163641937028537512478

40149071591354599827905133996115517942711068311340905842728842797915548497829543

23534517065223269061394905987693002122963395687782878948440616007412945674919823

05057164237715481632138063104590291613692670834285644073044789997190178146576347

32238502672530598997959960907994692017746248177184498674556592501783290704731194

33165550807568221846571746373296884912819520317457002440926616910874148385078411

92980452298185733897764810312608590300130241346718972667321649151113160292078173

8033436090243804708340403154190336L

youlose Feb 14 2011 at 16:07

Попробовал… с str = 'ffff', получил результат 205343, а где 65535?

Mrrl Feb 14 2011 at 16:12

Это неправильная строка. По условию, надо писать 'FFFF'.

youlose Feb 14 2011 at 16:34

точно, тогда всё в порядке

youlose Feb 14 2011 at 01:26

Perl:

use Math::BigInt;

sub hex2dec { Math::BigInt->from_hex('0x'. shift) }

Mrrl Feb 14 2011 at 06:33

А без BigNum?

youlose Feb 14 2011 at 20:56

ну да точно… bignum:

use 5.012;

use bignum;



say hex('f' x 1000);

выведет результат для числа состоящего из 1000 'f'

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

mas Feb 14 2011 at 01:50

python:
def hex2dec(s): return str(int(s,16))

mas Feb 14 2011 at 02:03

>>> import timeit; timeit.timeit('b=hex2dec(a)','hex2dec,a=lambda s:str(int(s,16)),«123456789ABCDEF0»*(100000//16)',number=1)
11.107685383580531

karlicos Feb 14 2011 at 02:38

int base = 16;
string s;
cin >> s;

long long bp = 1;
long long ans = 0;
for (int i = s.size() — 1; i >= 0; --i) {
char c = s[i];
if (isdigit©)
ans += (c — '0') * bp;
else
ans += (c — 'A') * bp;
bp *= base;
}
cout

karlicos Feb 14 2011 at 02:46

int base = 16;
string s;
cin s;

long long bp = 1;
long long ans = 0;
for (int i = s.size() — 1; i >= 0; --i) {
char c = s[i];
if (isdigit(c ))
ans += (c — '0') * bp;
else
ans += (c — 'A') * bp;
bp *= base;
}
cout r;

Почему-то парсер не хочет кушать тег source :( Еще ему ужасно не нравятся двойные угловые скобки в cin и cout.
Работает по идее для любой системы счисления с основанием от 1 до 36. Естественно, ans очень быстро переполнится для строки в 100000 байт, в C++ надо использовать длинную арифметику, в питон она встроена.

Ckpyt Jan 22 2013 at 17:17

длина строки может быть больше 16 байт. Но меньше 100 000.

pro100tak Feb 14 2011 at 05:04

Ооооо — многие из отписавшихся использовали написанные до них функции, встроенные в языки! Нечестно и не спортивно!

Mrrl Feb 14 2011 at 06:17

И более того — я не уверен, что хотя бы одно из решений будет работать для больших чисел (например, больше, чем 2^256).

runcore Feb 14 2011 at 06:10

php:

function hex2dec2($h) {
	$a = array_flip(str_split('0123456789ABCDEF',1));
	$l = strlen($h)-1;
	for($d=0,$x=$l; $x>=0; $x--)
		$d += $a[$h[$x]]*pow(16,$l-$x);
	return $d;
}

Mrrl Feb 14 2011 at 06:35

Еще поправил условие. Давайте обходиться без BigNum-ов, а то в самом деле неинтересно.

Mrrl Feb 14 2011 at 07:26

Впрочем, задача 16-ричного ввода тоже имеет право на существование.
C#:


        static long ReadHex(string s) {
            long l=0;
            foreach(char c in s) l=(l<<4)+(((c+4)%23-6)&15);
            return l;
        }

Интересно, почему большинство авторов просматривают строку с конца. Неужели так проще?

Ckpyt Jan 22 2013 at 17:21

Потому что в случае строчки с начала, вам придется в варианте 99999 + A передавать единицу в самое начало. А конечные разряды не меняются.

Mrrl Jan 22 2013 at 17:34

И где используется, что они не меняются? В одном числе накапливается ответ, в другом держат 16^n, потом второе число на что-то умножают и складывают с первым. Компьютеру всё равно придётся перелопачивать все нули. А в десятичную систему потом переводит добрый дядя…

Ckpyt Jan 22 2013 at 17:47

Не посмотрел на код.
Задание — перекодировать строку в строку, а не строку в число :-) Т.е. ваш вариант успешно загнется при строке более 16 байт.

Mrrl Jan 22 2013 at 17:51

Исходный вариант (который в основном посте) — не загнётся. А то, что написано в этой ветке, это так… ввод 16-ричного long. К поставленной задаче прямого отношения не имеет.

Mrrl Feb 14 2011 at 09:23

Алгоритм Маркова. 60 правил, * — любой символ.
Кто меньше?


b* -> *b
b -> c
a0c -> 0 FIN
a0 -> a
*j -> i*
s*iF -> js*6
diF -> jd6
i0 -> 1
i1 -> 2
i2 -> 3
i3 -> 4
i4 -> 5
i5 -> 6
i6 -> 7
i7 -> 8
i8 -> 9
i9 -> A
iA -> B
iB -> C
iC -> D
iD -> E
iE -> F
iF -> j0
ia -> a1
s9 -> s8i
s8 -> s7i
s7 -> s6i
s6 -> s5i
s5 -> s4i
s4 -> s3i
s3 -> s2i
s2 -> s1i
s1 -> di
*dA -> i*d0
*dB -> i*d1
*dC -> i*d2
*dD -> i*d3
*dE -> i*d4
*dF -> i*d5
d*c -> c*
d0 -> 0d
d1 -> 1s6
d2 -> 3s2
d3 -> 4s8
d4 -> 6s4
d5 -> 8d
d6 -> 9s6
d7 -> Bs2
d8 -> Cs8
d9 -> Es4
aAc -> 10 FIN
aA -> a10d
aB -> a1d1
aC -> a1d2
aD -> a1d3
aE -> a1d4
aF -> a1d5
a*c -> * FIN
a* -> ad*
* -> ab*

dima_eam Feb 14 2011 at 10:17

Функция на APL:

runcore Feb 14 2011 at 11:13

SQL (Oracle):

SELECT t3.hexval, SUM(t3.el) decval 
FROM(
  SELECT t2.hexval
    ,decode(t2.p,'A',10
     ,decode(t2.p,'B',11
      ,decode(t2.p,'C',12
       ,decode(t2.p,'D',13
        ,decode(t2.p,'E',14
         ,decode(t2.p,'F',15, to_number(t2.p)
    ))))))*power(16,length(t2.hexval)-t2.lvl-1) el
  FROM(
    WITH t as ( SELECT 'DEADBEAF' hexval, '[0-9A-F]' rg FROM dual)
    SELECT hexval, regexp_substr (hexval, rg, 1, level) p, level-1 lvl 
    FROM t
    CONNECT BY regexp_substr(hexval, rg, 1, level) IS NOT NULL
  ) t2
) t3 GROUP BY t3.hexval

)))

Mrrl Feb 14 2011 at 14:54

Машина Тюринга — 33 состояния:


; отодвинем на 3 символа влево
1: 0L2 0L5 _L33
2: _S0 _S0 _L3
3: _S0 _S0 _L4
4: _S0 _S0 0R8
5: _S0 _S0 _L6
6: _S0 _S0 _L7
7: _S0 _S0 1R8
8: _R1 _S0 _R8
9: 0L9 1L9 _R10
; начнем делить на 5
10: _R10 _R11 _R18
11: _R12 _R13 _R19
12: _R14 1R15 _R20
13: 1R16 1R17 _R21
14: 1R13 1R14 _R22
15: 0R15 0R16 _R18
16: 0R17 0R13 _R19
17: 0R14 1R15 _R20
; напечатаем остаток и прибавим 5, если надо
18: 0R19 _S0 0R23
19: 0R20 1R20 0R24
20: 0R21 1R21 0R25
21: 1L22 0L23 0R26
22: 0L24 1L24 1R23
23: 1L24 0L25 0R27
24: 1L26 0L27 0R28
25: 0L27 1L27 1R27
26: 0L30 _S0 1R28
27: 1L30 _S0 0L29
28: _S0 _S0 1L29
29: 0L29 1L29 0L30
; Есть ли цифры?
30: _L31  _R18 _L31
31: 0L32 1L32 _S0  ; настоящий стоп
32: 0L32 1L32 _R1  ; конец цикла
33: 0L9 1L9 _L33 ; забытое состояние между 8 и 9

Здесь в каждой строчке — номер состояния и три команды: для символа 0, символа 1 и пробела (его роль играет подчеркивание). Состояние 0 — выход из программы. Команда _S0 (поставить пробел, остаться на ленте и выйти) во всех случаях, кроме одного (состояние 31), соответствует невозможной ситуации.
Цифры записаны четверками бит, подряд. Каретка на самой левой цифре.

VarLog Feb 18 2011 at 23:38

sed:

:a;s;F;Ex;;s;E;Dx;;s;D;Cx;;s;C;Bx;;s;B;Ax;;
   s;A;9x;;s;9;8x;;s;8;7x;;s;7;6x;;s;6;5x;;
   s;5;4x;;s;4;3x;;s;3;2x;;s;2;1x;;s;1;0x;;
s;0;;;s;y;xxxxxxxxxxxxxxxx;g;y;x;y;;/[0-9A-F]/ba;
:s;s;y\{10\};x;g;
s;y\{9\};9;;s;y\{8\};8;;s;y\{7\};7;;s;y\{6\};6;;
s;y\{5\};5;;s;y\{4\};4;;s;y\{3\};3;;s;y\{2\};2;;s;y\{1\};1;;
y;x;y;;/y/bs;