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

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

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

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



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


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

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

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

Ряд b содержит порядка n^2 элементов. Об этом я написал в п.1
...
Рейтинг: 0 / 0
Пятничный 'divide and conquer'
    #39038458
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Например для четырех элементов
Код: 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
Пятничный 'divide and conquer'
    #39038474
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1
Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ?
...
Рейтинг: 0 / 0
Пятничный 'divide and conquer'
    #39038489
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Пятничный 'divide and conquer'
    #39038509
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovSashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1
Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ?


чтобы проанализировать ряд b необходимо рассчитать порядка n^2 элементов.
...
Рейтинг: 0 / 0
Пятничный 'divide and conquer'
    #39038537
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Попробовал 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
Пятничный 'divide and conquer'
    #39038548
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нашел косяк, получилось 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
Пятничный 'divide and conquer'
    #39038569
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дмитрий, меня уже выгоняют от компьютера( Завтра посмотрю.
Но вообще весело получается :)
...
Рейтинг: 0 / 0
Пятничный 'divide and conquer'
    #39038720
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Засомневался в своих способностях считать в уме
закодил четко по описанию
Код: 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
Пятничный 'divide and conquer'
    #39039041
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне кажется что в твоих расчётах участвует первый элемент элемент массива, а это только его мощность.
У меня получилось так = .

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


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