nedoPC.org - View topic - Преобразование целого числа

Atom Feed | View unanswered posts | View active topics

It is currently 17 Apr 2024 18:12

Преобразование целого числа

Moderator: haqreu

Page 1 of 1

[ 4 posts ]

Previous topic | Next topic

Преобразование целого числа

Author

Message

Mac Buster

Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow

Преобразование целого числа

По-моему в нашем форуме ещё не затрагивалась тема способов преобразования целого числа из десятичной системы счисления в уравновешенную троичную. Позволю себе привести выдержку из брошюры С.В.Фомина "Системы счисления" вышедшей в серии "Популярные лекции по математике":


	Quote: Можно, однако, записать каждое число в троичной системе и несколько иначе, а именно так, чтобы в его записи участвовали цифры 0, 1 и -1 (вместо 0,1 и 2). Для получения такой записи поступим следующим образом. Переведем числа А из десятичной системы в троичную, пользуясь схемой последовательных делений на три. Но только каждый раз, когда у нас при делении на три будет получаться 2, мы будем частное увеличивать на единицу, а в остатке при этом писать -1.

К этому следует добавить, что в том случае, если мы производили преобразование отрицательного числа, то по окончании перевода потребуется инвертировать разряды полученного троичного числа (последовательно заменить все 1 на -1 и обратно).

Кроме такого способа есть несколько других, например, один (крайне странный) приводится во втором томе "Искусства программирования" Д.Кнута. В публикациях Николая Петровича Брусенцова и Хосе Рамиля Альвареса описаны способы подобных преобразований не только для десятичной, но так же для двоичной и прочих систем.

20 Feb 2006 00:21

Shaos

Admin

Joined: 08 Jan 2003 23:22
Posts: 22523
Location: Silicon Valley

Re: Преобразование целого числа

Вот мои собственные алгоритмы, придуманные из головы (никуда не глядя) для преобразования туда и обратно:


	Code: public static String toTernary(int num) { int n,m,k; String s = null; k = 387420489; for(int i=0;i<=18;i++) { n = num/k; num -= nk; m = k/2; if(num>+m){n++;num-=k;} if(num<-m){n--;num+=k;} if(n!=0 && s==null) s=""; if(n==-1) s+="N"; if(n==0 && s!=null) s+="O"; if(n==1) s+="P"; k /= 3; } return s; } public static int fromTernary(String s) { int n = 0; int k = 1; for(int i=s.length()-1;i>=0;i--) { char c = s.charAt(i); if(c!='N'&&c!='O'&&c!='P') return 0; if(c=='N') n-=k; if(c=='P') n+=k; k = 3; } return n; }

Написано на джаве, могу переписать на русский, если надо

20 Feb 2006 07:44

sva

Re: Преобразование целого числа

можно проще и быстрее
сначала преобразовать число к 3му с основанием 3 (значаения разрядов 0,1,2) а затем преобразовать к 3му симметричному коду

преобразование к 3му с основанием 3 производится итеративным делением на 3 с выделением остатка в качестве значения следующего разряда (без нализа знака)

преобразование 3го с основанием 3 к 3му симметричному коду производится прибавлением к исходному числу половины максимально представимого данным кол-вом разрядов за вычетом 1 и последующим поразрядным вычитанием 1.

т.е. для трайта (6 тритов) примерно так


	Code: int* dec2tri(int dec) //dec - исходное число (максимально представимое -364 .. +364) { char tri[6]; char tmp_tri[6]; int tmp_dec; char sign; sign = dec/abs(dec); tmp_dec = abs(dec) +364; for(i=0;i<6;i++) { tmp_tri[i] = tmp_dec % 3; tmp_dec = tmp_dec /3; } for(i=0;i<6;i++) if(sign>0) tri[i] = (tmp[i] -1); else tri[i] = (1-tmp[i]); // или что коректнее tri[i] = sign * (tmp[i] -1); return tri; }

обратное преобразование делается в обратном порядке.
и этот вариант проще реализуется в железе.
тут используется N+1 операций деления (при использовании еще одной переменной можно для вычисления остатка от деления на 3 использовать не деление, а вычитание)

21 Oct 2008 12:23

Mac Buster

Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow

Re: Преобразование целого числа

Спасибо! Если я не ошибаюсь именно этот способ предложен в книге Д.Кнута.

21 Oct 2008 12:34

Page 1 of 1

[ 4 posts ]

Who is online

Users browsing this forum: No registered users and 7 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to: