Форум на Исходниках.RU

Быстро и карсиво разложить число по степеням (-2)

albom — Mon, 21 Apr 2008 13:00:36 +0000

albom:

Цитата AndreyK @ 21.04.08, 12:22

Этот, вроде, работает.

Увы, и этот вариант не работает. Неужели так сложно самостоятельно проверить хотя бы первые десять натуральных чисел? Ведь уже на них выдается неверный ответ. <_<

Цитата AndreyK @ 21.04.08, 12:22

Опять же прошу высказываться.

Я не очень понимаю смысл выкладывать вот эти исходники.
Во-первых, это не алгоритм, а код, причем код очень непонятный, который к тому же не работает.
Во-вторых, в этой теме уже приведено решение, даже есть работающий исходник. Почему не сравниваешь свою реализацию с ним?
И в-третьих, просили разложить "Быстро и карсиво", а тут увы нет ни того, ни другого.

Короче, давай, испрявляйся по всем пунктам, и показывай, что у тебя там получилось ;)

Быстро и карсиво разложить число по степеням (-2)

AndreyK — Mon, 21 Apr 2008 12:22:35 +0000

AndreyK: Приношу свои звинения за предыдущий вариант.
Этот, вроде, работает.
Раскладка натурального числа по основанию(-2)
X = k*(-2)ⁱ; где k 1 или 0,i - нумер разряда(нумерация от младшего к старшему начиная с нуля).
Опять же прошу высказываться.

#include <stdio.h>

#include <math.h>

int binarinegativ(int X){

int d =2,B,C,X1;

X1 = X;

printf("foundation (2) %d = %0.4X\n",X,X);

do{ B = X & d;

if(B) X += (d*2);

d *= 4;

C = (int)( log(X)/log(2) ) ;

C = (int)pow(2,C);

}while(d <= C );

printf("foundation (-2) %d = %0.4X\n",X1,X);

return X;

}

int main(void){

int V;

while(1){

puts("Input digit, 0 fo exit\n");

if(!V) break;

scanf("%d",&V);

binarinegativ(V);

getchar();

}

return 0;

}

Быстро и карсиво разложить число по степеням (-2)

darcus — Mon, 21 Apr 2008 06:46:25 +0000

darcus: это была попытка сделать *что*?

Быстро и карсиво разложить число по степеням (-2)

albom — Sun, 20 Apr 2008 14:39:10 +0000

albom:

Цитата AndreyK @ 20.04.08, 11:00

Прошу высказываться. только для положительный целых чисел

:no-sad:
Не работает ни для положительных, ни для отрицательных.

Кстати, можешь попробовать сделать через формулу Шреппеля:

B = (N xor 0b10101010101010...) - 0b1010101010....

Быстро и карсиво разложить число по степеням (-2)

AndreyK — Sun, 20 Apr 2008 11:00:24 +0000

AndreyK: Прошу высказываться. только для положительный целых чисел

#include <stdio.h>

#include <math.h>

int binarinegativ(int X){

int d =2,B,C,X1;

X1 = X;

printf("foundation (2) %d = %0.4X\n",X,X);

do{ B = X & d;

d *= 2;

if(B) X += d;

C = (int)( log(X)/log(2) ) ;

C = (int)pow(2,C);

}while(d < C );

printf("foundation (-2) %d = %0.4X\n",X1,X);

return X;

}

int main(void){

int V;

while(1){

puts("Input digit, 0 fo exit\n");

if(!V) break;

scanf("%d",&V);

binarinegativ(V);

getchar();

}

return 0;

}

Быстро и карсиво разложить число по степеням (-2)

kiryshka — Sat, 19 Apr 2008 18:44:49 +0000

kiryshka: :huh: сорри

Быстро и карсиво разложить число по степеням (-2)

albom — Sat, 19 Apr 2008 11:28:23 +0000

albom:

Цитата kiryshka @ 19.04.08, 11:13

может я что то недопонимаю?

Вероятно, да. А именно, как разделить одно число на другое.
Правильно деление будет выглядеть так:

10 / -2 = -5 rem 0
-5 / -2 =  3 rem 1
 3 / -2 = -1 rem 1
-1 / -2 =  1 rem 1
 1 / -2 =  0 rem 1

Правильный ответ: 10₁₀ = 11110_-2, а вовсе не то, что у тебя получилось.

Быстро и карсиво разложить число по степеням (-2)

kiryshka — Sat, 19 Apr 2008 11:13:37 +0000

kiryshka:

Цитата albom @ 19.04.08, 08:04

А какое отношение все это имеет к исходной задаче? :lol:

может я что то недопонимаю?
10:

10%-2=0
-5%-2=1
2%-2= 0
-1%-2=1

:huh:

Быстро и карсиво разложить число по степеням (-2)

albom — Sat, 19 Apr 2008 08:04:55 +0000

albom:

Цитата darcus @ 18.04.08, 14:51

А нет ли способа "мгновенно" найти разложение для -Z из разложения для +Z ?

Нет, и не может быть, так как сложность алгоритма не может быть меньше битового размера выхода.

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

 1 + 1     = 110
11 + 1     = 0
 1 + 1 + 1 = 111

Цитата kiryshka @ 18.04.08, 19:29

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

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

А какое отношение все это имеет к исходной задаче? :lol:

Быстро и карсиво разложить число по степеням (-2)

darcus — Fri, 18 Apr 2008 19:41:41 +0000

darcus: итого, как бонус мы получаем 2 = -2 ! :)

Быстро и карсиво разложить число по степеням (-2)

kiryshka — Fri, 18 Apr 2008 19:29:27 +0000

kiryshka:

Цитата albom @ 17.04.08, 19:33

А частное? ;)

Быстро и карсиво разложить число по степеням (-2)

darcus — Fri, 18 Apr 2008 14:51:34 +0000

darcus: А нет ли способа "мгновенно" найти разложение для -Z из разложения для +Z ?

+123456789

11000101011001101110100010101

-123456789

1001111001000111011100111111

+345634295858585858375757682846739644999374848484657282929292929234215673853

1110001001110001101000001100100001001010101011100110110100001111011010011000111111100

1110111010100101000101000000011110001000011011101011010000110101111010001011010000001

1100101000010011000001011010110001010111000000111100101001001011110000000001101

-345634295858585858375757682846739644999374848484657282929292929234215673853

1101001101101000011100000010110001101111111111010001001110000010100111000100110101010

1101110111110111100111100000000101001100000111011100111000001110010111001100111000001

10101111000110001000011001110010011111101000000010101111011011001010000000000111

Быстро и карсиво разложить число по степеням (-2)

albom — Thu, 17 Apr 2008 19:33:00 +0000

albom: А частное? ;)

Быстро и карсиво разложить число по степеням (-2)

kiryshka — Thu, 17 Apr 2008 19:29:22 +0000

kiryshka: да какая разница? остаток от деления что на -2, что на 2 один и тот же.....(если не учитывать отрицательный результат)

Быстро и карсиво разложить число по степеням (-2)

albom — Thu, 17 Apr 2008 06:48:27 +0000

albom: kiryshka, ну хотя бы заголовок темы нужно читать :wall:
Основание (-2).

Быстро и карсиво разложить число по степеням (-2)

kiryshka — Thu, 17 Apr 2008 06:36:04 +0000

kiryshka: Реализация на С#:
****************************************
int m=77855442;
Console.WriteLine(Convert.ToString(m,2));
****************************************
выдает типа 100101000111111101011010010
press any key......

и никаких тебе условий......

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 21:36:43 +0000

darcus: только основание системы счисления < 0

Быстро и карсиво разложить число по степеням (-2)

AndreyK — Sun, 13 Apr 2008 21:17:14 +0000

AndreyK: Ё моё, подробности: задача сводится к изменению системы исчисления из десятичной в двоичную.
Решено-перерешено.

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 18:51:16 +0000

darcus: сенькс однозначно. Получилось типа так:
Ответ собираем в строку s (и в нужном порядке):

def roo(n):

if n==0:

return '0'

s=''

while n!=0:

m=n%-2

n=n/-2

if m==0:

s='0'+s

else:

s='1'+s

if m==-1:

n=n+1

return s

print roo(input())

Быстро и карсиво разложить число по степеням (-2)

albom — Sun, 13 Apr 2008 17:48:51 +0000

albom:

Цитата darcus @ 13.04.08, 17:37

ихдежеговзять?

Написать :blink: Там же всего одна строчка.

function modNeg2(a: integer): integer;

begin

modNeg2 := abs(a mod (-2));

end;

Аналогично "исправляем" div, так как теперь перестало выполнятся тождество (a div b)*b + (a mod b) = a

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 17:37:29 +0000

darcus: ихдежеговзять? не хочется лепить кучу условий (если это минус, а это плюс , то ... и т.д.)

для 2345 ответ моего 0-кода еще страшнее:

1
0
0
-1
0
-1
0
0
1
0
0
-1

Правильный ответ: 1100101111001

Быстро и карсиво разложить число по степеням (-2)

albom — Sun, 13 Apr 2008 17:20:25 +0000

albom: В паскале mod возвращает результат со знаком равным знаку первого операнда. А тебе нужен mod, возвращающий только неотрицательные остатки.

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 17:15:59 +0000

darcus: если на пасе, то

n:=13;

repeat

writeln(n mod -2);

n:=n div -2;

until n=0;

выдает

1
0
1
-1

Быстро и карсиво разложить число по степеням (-2)

MBo — Sun, 13 Apr 2008 15:37:59 +0000

MBo: 13

div mod

-6 1

3 0

-1 1

1 1

0 1

остатки снизу вверх записываем
11101

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 15:31:05 +0000

darcus: "деление на -2 в цикле"? не догнал, виноват

можно примерчик для например числа 13?

-Added 13.04.08, 15:32

Цитата andriano @ 13.04.08, 15:18

Если по степеням 2, то битовыми проверками и сдвигами.

именно по минус 2

Быстро и карсиво разложить число по степеням (-2)

andriano — Sun, 13 Apr 2008 15:18:42 +0000

andriano: Если по степеням 2, то битовыми проверками и сдвигами.

Быстро и карсиво разложить число по степеням (-2)

albom — Sun, 13 Apr 2008 15:18:22 +0000

albom: А деление на -2 в цикле чем не нравится?

Быстро и карсиво разложить число по степеням (-2)

darcus — Sun, 13 Apr 2008 15:04:19 +0000

darcus: как?