|
|
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Разминался и решал такую задачу . 1. Прямой перебор не подходит, потому что имеем , при не уложимся по временным ограничениям. 2. F(a,b) = F(b,a), потому нужно найти XOR данной функции для всех возможных сочетаний пар в любом порядке. 3. Мне кажется что решением будет являться рекурсивная функция, разделяющая исходный массив на две части по значению последнего бита. Более не придумал. Может быть у кого-то будут идеи ? PS предполагаю, что решение будет содержать большое число логических операций, потому идеальным языком для решения данной задачи является Си, ибо у Си очень хороший синтаксис таких операций. Не утверждаю что решить данную задачу нельзя на условном Java. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 06:31 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Та еще задачка, можно приз давать только за то что условия понял Три раза перечитал, но похоже приз не заработал :) особенно повеселилоВсе операции xor выполняются слева направо, если скобки не указывают иной порядок. всегда было Код: plaintext 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 09:13 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Это вероятно сделано для того чтобы запутать или по глупости, выполнять эти операции очевидно можно в любом порядке. И кроме того, массив полученных числен можно отсортировать, например, и выполнить затем все эти действия, результат не изменится (п.2) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 09:23 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Возможно поможет: Код: plaintext 1. 2. Задачу так и не понял, вечером время будет - гляну. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 09:28 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
SashaMercuryМожет быть у кого-то будут идеи ? Одним проходом вычисляем второй операнд, вторым проходом - первый. Стоимость O(2N). Достаточно раскрыть все скобки и найти зависимость bi от bi+1. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 11:14 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovSashaMercuryМожет быть у кого-то будут идеи ? Одним проходом вычисляем второй операнд, вторым проходом - первый. Стоимость O(2N). Достаточно раскрыть все скобки и найти зависимость bi от bi+1. Не могли бы вы объяснить подробнее пожалуйста ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 13:28 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
SashaMercuryНе могли бы вы объяснить подробнее пожалуйста Проанализируй ряд b и найди (аналитически) способ вычислить b i через b i+1 . Тогда задача станет тривиальной. Модератор: Тема перенесена из форума "C++". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 13:37 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovSashaMercuryНе могли бы вы объяснить подробнее пожалуйста Проанализируй ряд b и найди (аналитически) способ вычислить b i через b i+1 . Тогда задача станет тривиальной. Модератор: Тема перенесена из форума "C++". Ряд b содержит порядка n^2 элементов. Об этом я написал в п.1 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 13:39 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Например для четырех элементов Код: sql 1. 2. 3. ХЗ как тут из b1 получить b2 Думаю надо для начала как-то математически записать внутренности f() ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 13:52 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
SashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1 Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 14:04 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
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 , как ты выше писал, то кол-во операций значительно сокращается. Правда я так и не понял как ты это предлагаешь делать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 14:15 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovSashaMercuryРяд b содержит порядка n^2 элементов. Об этом я написал в п.1 Ерунду написал. В каком месте "b 1 xor b 2 xor … xor b n-1 " ты увидел N 2 ? чтобы проанализировать ряд b необходимо рассчитать порядка n^2 элементов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 14:30 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Попробовал 3-й вариант порешать (3,1,2,4) Код: sql 1. 2. 3. 4. 5. 6. 7. получилось 5, а там 6 пишут. Вроде четко по алгоритму. В чем косяк? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 14:48 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Нашел косяк, получилось 4 Код: sql 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 14:55 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Дмитрий, меня уже выгоняют от компьютера( Завтра посмотрю. Но вообще весело получается :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 15:12 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Засомневался в своих способностях считать в уме закодил четко по описанию Код: 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. результат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. Фигня какая-то. Саша проверяй, где-то я неправильно условия задачи понял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.08.2015, 17:12 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
Мне кажется что в твоих расчётах участвует первый элемент элемент массива, а это только его мощность. У меня получилось так = . Что тоже не совпадает с ответом к тому тесту :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.08.2015, 03:22 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
опечатался . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.08.2015, 03:24 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
SashaMercuryМне кажется что в твоих расчётах участвует первый элемент элемент массива, а это только его мощность. Точно, это же кол-во элементов. Данные (1,2,4) Код: sql 1. 2. 3. 4. 5. 6. Так все сошлось. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.08.2015, 09:23 |
|
||
|
Пятничный 'divide and conquer'
|
|||
|---|---|---|---|
|
#18+
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. Я что-то не так понял видимо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.08.2015, 06:48 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39038548&tid=1340944]: |
0ms |
get settings: |
6ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
72ms |
get topic data: |
6ms |
get forum data: |
1ms |
get page messages: |
33ms |
get tp. blocked users: |
1ms |
| others: | 200ms |
| total: | 332ms |

| 0 / 0 |
