Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный 'divide and conquer' / 21 сообщений из 21, страница 1 из 1
28.08.2015, 06:31
    #39037984
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Здравствуйте.
Разминался и решал такую задачу .
1. Прямой перебор не подходит, потому что имеем , при не уложимся по временным ограничениям.
2. F(a,b) = F(b,a), потому нужно найти XOR данной функции для всех возможных сочетаний пар в любом порядке.
3. Мне кажется что решением будет являться рекурсивная функция, разделяющая исходный массив на две части по значению последнего бита. Более не придумал.

Может быть у кого-то будут идеи ?

PS
предполагаю, что решение будет содержать большое число логических операций, потому идеальным языком для решения данной задачи является Си, ибо у Си очень хороший синтаксис таких операций. Не утверждаю что решить данную задачу нельзя на условном Java.
...
Рейтинг: 0 / 0
28.08.2015, 09:13
    #39038074
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Та еще задачка, можно приз давать только за то что условия понял
Три раза перечитал, но похоже приз не заработал :)

особенно повеселилоВсе операции xor выполняются слева направо, если скобки не указывают иной порядок.
всегда было
Код: plaintext
1.
(A xor B) xor C = A xor B xor C = C xor B xor A = (C xor A) xor B = и т.д.
...
Рейтинг: 0 / 0
28.08.2015, 09:23
    #39038080
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Это вероятно сделано для того чтобы запутать или по глупости, выполнять эти операции очевидно можно в любом порядке. И кроме того, массив полученных числен можно отсортировать, например, и выполнить затем все эти действия, результат не изменится (п.2)
...
Рейтинг: 0 / 0
28.08.2015, 09:28
    #39038086
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Возможно поможет:
Код: plaintext
1.
2.
A xor A = 0
A xor 0 = A



Задачу так и не понял, вечером время будет - гляну.
...
Рейтинг: 0 / 0
28.08.2015, 11:14
    #39038207
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
SashaMercuryМожет быть у кого-то будут идеи ?
Одним проходом вычисляем второй операнд, вторым проходом - первый. Стоимость O(2N).
Достаточно раскрыть все скобки и найти зависимость bi от bi+1.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.08.2015, 13:28
    #39038426
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Dimitry SibiryakovSashaMercuryМожет быть у кого-то будут идеи ?
Одним проходом вычисляем второй операнд, вторым проходом - первый. Стоимость O(2N).
Достаточно раскрыть все скобки и найти зависимость bi от bi+1.


Не могли бы вы объяснить подробнее пожалуйста
...
Рейтинг: 0 / 0
28.08.2015, 13:37
    #39038438
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
SashaMercuryНе могли бы вы объяснить подробнее пожалуйста
Проанализируй ряд b и найди (аналитически) способ вычислить b i через b i+1 . Тогда задача станет тривиальной.

Модератор: Тема перенесена из форума "C++".
...
Рейтинг: 0 / 0
28.08.2015, 13:39
    #39038439
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Dimitry SibiryakovSashaMercuryНе могли бы вы объяснить подробнее пожалуйста
Проанализируй ряд b и найди (аналитически) способ вычислить b i через b i+1 . Тогда задача станет тривиальной.

Модератор: Тема перенесена из форума "C++".

Ряд b содержит порядка n^2 элементов. Об этом я написал в п.1
...
Рейтинг: 0 / 0
28.08.2015, 13:52
    #39038458
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Например для четырех элементов
Код: sql
1.
2.
3.
b1 = f(a1,a2) xor f(a1,a3) xor f(a1,a4)
b2 = f(a2,a3) xor f(a2,a4)
b3 = f(a3,a4)


ХЗ как тут из b1 получить b2

Думаю надо для начала как-то математически записать внутренности f()
...
Рейтинг: 0 / 0
28.08.2015, 14:04
    #39038474
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
SashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1
Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ?
...
Рейтинг: 0 / 0
28.08.2015, 14:15
    #39038489
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Dimitry SibiryakovSashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1
Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ?
Думаю он про то чтобы посчитать b i надо выполнить n-i операций, т.е. в итого n 2 /2 операций

Но если возможно из b i получить b i+1 , как ты выше писал, то кол-во операций значительно сокращается.
Правда я так и не понял как ты это предлагаешь делать.
...
Рейтинг: 0 / 0
28.08.2015, 14:30
    #39038509
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Dimitry SibiryakovSashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1
Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ?


чтобы проанализировать ряд b необходимо рассчитать порядка n^2 элементов.
...
Рейтинг: 0 / 0
28.08.2015, 14:48
    #39038537
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Попробовал 3-й вариант порешать (3,1,2,4)
Код: sql
1.
2.
3.
4.
5.
6.
7.
b1 = f(3,1) xor f(3,4) xor f(3,4) = 0 xor 0 xor 0 = 0
b2 = f(1,2) xor f(1,4) = 0 xor 0 = 0
b3 = f(2,4) = 1

(3 xor 1 xor 2 xor 4) = 4
(0 xor 0 xor 1) = 1
4 xor 1 = 5


получилось 5, а там 6 пишут. Вроде четко по алгоритму. В чем косяк?
...
Рейтинг: 0 / 0
28.08.2015, 14:55
    #39038548
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Нашел косяк, получилось 4
Код: sql
1.
2.
3.
4.
5.
6.
7.
b1 = f(3,1) xor f(3,2) xor f(3,4) = 1 xor 0 xor 0 = 1
b2 = f(1,2) xor f(1,4) = 0 xor 0 = 0
b3 = f(2,4) = 1

(3 xor 1 xor 2 xor 4) = 4
(1 xor 0 xor 1) = 0
4 xor 0 = 4
...
Рейтинг: 0 / 0
28.08.2015, 15:12
    #39038569
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Дмитрий, меня уже выгоняют от компьютера( Завтра посмотрю.
Но вообще весело получается :)
...
Рейтинг: 0 / 0
28.08.2015, 17:12
    #39038720
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Засомневался в своих способностях считать в уме
закодил четко по описанию
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
int f(int a, int b)
{
	if(a == b) {
		return -1;
	} else {
		int diff = a - b;
		int n = 1;
		int ret = 0;
		while(diff % n == 0) {
			ret = n - 1;
			n *= 2;
		}
		return ret;
	}
}

int calc_b(int* a, int cnt)
{
	int* next = a;
	int ret = 0;
	for(; cnt > 0; cnt--) {
		next++;
		printf("(%d,%d = %d)", *a, *next, f(*a, *next));
		ret ^= f(*a, *next);
	}
	return ret;
}

int main() 
{
	int a[4] = {3,1,2,4};
	printf("%d", a[0]);
	int res_a = a[0];
	for(int i = 1; i < sizeof(a) / sizeof(int); i++) {
		printf("^%d", a[i]);
		res_a ^= a[i];
	}
	printf("=%d\n", res_a);

	int res_b = 0;
	for(int i = 1; i < sizeof(a) / sizeof(int); i++) {
		int b = calc_b(&a[i - 1], sizeof(a) / sizeof(int) - i);
		printf(" b%d = %d\n", i, b);
		res_b ^= b;
	}
	printf("res_b = %d\n", res_b);
	printf("%d^%d=%d\n", res_a, res_b, res_a^res_b);
}


результат3^1^2^4=4
(3,1 = 1)(3,2 = 0)(3,4 = 0) b1 = 1
(1,2 = 0)(1,4 = 0) b2 = 0
(2,4 = 1) b3 = 1
res_b = 0
4^0=4

Все равно 4, а не 6

Затестил {3,1,2,3} получилось -4 а надо 1. Фигня какая-то.

Саша проверяй, где-то я неправильно условия задачи понял.
...
Рейтинг: 0 / 0
29.08.2015, 03:22
    #39039041
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Мне кажется что в твоих расчётах участвует первый элемент элемент массива, а это только его мощность.
У меня получилось так = .

Что тоже не совпадает с ответом к тому тесту :)
...
Рейтинг: 0 / 0
29.08.2015, 03:24
    #39039042
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
опечатался
.
...
Рейтинг: 0 / 0
29.08.2015, 09:23
    #39039063
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
SashaMercuryМне кажется что в твоих расчётах участвует первый элемент элемент массива, а это только его мощность.
Точно, это же кол-во элементов. Данные (1,2,4)
Код: sql
1.
2.
3.
4.
5.
6.
b1 = f(1,2) xor f(1,4) = 0 xor 0 = 0
b2 = f(2,4) = 1

(1 xor 2 xor 4) = 7
(0 xor 1) = 1
7 xor 1 = 6


Так все сошлось.
...
Рейтинг: 0 / 0
30.08.2015, 06:48
    #39039260
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
Dima TТочно, это же кол-во элементов. Данные (1,2,4)
[src sql]
b1 = f(1,2) xor f(1,4) = 0 xor 0 = 0
b2 = f(2,4) = 1


почему так ? fe 2 4, разница 2, 2 делится максимум на 2^1, следовательно результат 1-1=0. Я что-то не так понял видимо
...
Рейтинг: 0 / 0
31.08.2015, 07:01
    #39039503
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятничный 'divide and conquer'
SashaMercuryпочему так ? fe 2 4, разница 2, 2 делится максимум на 2^1, следовательно результат 1-1=0. Я что-то не так понял видимо
Надо не степень, а 2 в степени, т.е.
Код: sql
1.
2^1 - 1 = 1
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничный 'divide and conquer' / 21 сообщений из 21, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]