Дата : 28-08-06, Пнд, 08:39:02

Дата : 28-08-06, Пнд, 15:15:15

Дата : 28-08-06, Пнд, 15:33:48

Ты не умничай
Ты алгоритм напиши

Дата : 28-08-06, Пнд, 15:45:05

BriskaБольшой Грызь

Tak если я буду знать что это из этой области, можно подумать а так сложно..

Далее подозреваю что можно scale up and down так как average останется одинаковой..

Дата : 28-08-06, Пнд, 17:13:18

Дата : 28-08-06, Пнд, 17:16:28

Дата : 28-08-06, Пнд, 23:27:56

Если все будут знать Х, тогда из написанной "зарплаты XOR X" каждый сможет легко вычислить саму зарплату.

Да и как из "зарплаты XOR X" ты среднюю зарплату вычислишь?

Дата : 29-08-06, Втр, 02:11:27

Да пусть в уме считают - и никаких проблем

Дата : 29-08-06, Втр, 02:30:05

Дата : 29-08-06, Втр, 03:22:19

Сложить зарплаты за несколько месяцев и поделить на кол-во месяцев При такой бешеной секретности от коллег можно и поднатужиться

Дата : 29-08-06, Втр, 03:27:58

Дата : 29-08-06, Втр, 05:14:08

Дата : 29-08-06, Втр, 05:39:00

Да всё "поссибле" на самом деле

Дата : 29-08-06, Втр, 06:12:21

Тю, а я думала - каждый свою считает

Дата : 29-08-06, Втр, 06:17:07

Так а со своей - какие проблемы?? Можно и в уме подсчитать.

Дата : 29-08-06, Втр, 11:29:52

Дата : 29-08-06, Втр, 11:31:50

Думай-думай

Дата : 30-08-06, Срд, 02:32:27

А можно без пера и бумаги?   

Дата : 30-08-06, Срд, 02:33:26

Дата : 30-08-06, Срд, 02:41:29

Без всего, с условием, что инженеры умеют считать в уме. Я, по-моему, нашел неожиданное решение.

Дата : 30-08-06, Срд, 02:44:28

Давай в привате

Дата : 24-04-07, Втр, 06:36:28

Дата : 01-05-07, Втр, 06:51:58

Дата : 01-05-07, Втр, 06:57:56

Можно и так

Было еще и такое решение:
Первый со Вторым договариваются о каком-то числе. Один из них отнимает число от своей зарплаты, а второй прибавляет.
Затем тоже самое делает Второй и Третий. А затем Первый и Третий.
После чего каждый из них записывает на листке (том, который виден всем) полученное число. Числа суммируются и сумма делится на три.

Дата : 01-05-07, Втр, 07:06:11

Дата : 01-05-07, Втр, 07:09:53

Это решение не краткостью красиво, а симметрией
А по краткости есть решение наподобие твоего, но еще более короткое.
Первый не должен передавать какие-то числа двум людям сразу. Всё проще
Первый прибавляет к своей зарплате некое число и сообщает сумму Второму. Второй приплюсовывает свою зарплату и сообщает Третьему. Третий приплюсовывает свою зарплату и сообщает Первому. Первый отнимает упомянутое число и делит результат на три.

Дата : 01-05-07, Втр, 07:28:21

Дата : 01-05-07, Втр, 07:52:48

Паша, во-первых, краткость математического решения выражается в краткости его формулировки. К примеру, если есть решение в две строчки, базирующееся на индукции, то оно короче аналитического решения на две страницы, результатом которого является прямая формула вычисления значения функции в зависимости от значения аргументов. Индуктивное решение - короче. Несмотря на то, что функция вычисляется за О(1), а индукция - за О(N).

А, если уж говорить о распараллеливании процессов... И, если немного подумать, то придешь к выводу, что количество операций в решении из постинга №24 и кол-во операций в твоем решении одинаково.


В твоем решении:
1) в параллель можно выполнить две операции:
    1.1) Первый передаёт Второму произвольное число
    1.2) Первый передаёт Третьему сумму этого числа со своей зарплатой
2) Эта операция требует завершения операции 1.2:
    2.1) Третий передаёт Второму сумму полученного от Первого числа со своей зарплатой.
3) Эта операция требует завершения операции 2.1 и 1.1
    3.1) Второй отнимает от полученной от Третьего суммы число, которое сообщил ему Первый, делит результат на три и сообщает всем среднюю зарплату.

Итого три пункта, не поддающиеся распараллеливанию.
Причем самая длинная цепочка операций, не поддающаяся распараллеливанию это:
суммирование (1.2) + передача числа (1.2) + суммирование (2.1) + передача числа (2.1) + вычитание (3.1) + деление (3.1)
Итого три операции сложения/вычитания, одна операция деления и две передачи числа.


В решении из постинга №24 (слегка адаптированном)
1) в параллель можно выполнить следующие операции:
    1.1) Первый загадывает число, отнимает его от своей зарплаты и передает это число Второму.
    1.2) Второй загадывает число, отнимает его от своей зарплаты и передает это число Третьему.
    1.3) Третий загадывает число, отнимает его от своей зарплаты и передает это число Первому.
2) Следующие операции требует завершения всех распараллеленных операций из пункта (1):
    2.1) Первый прибавляет к своей зарплате число, полученное от Третьего, и записывает результат на листке
    2.2) Второй прибавляет к своей зарплате число, полученное от Первого, и записывает результат на листке
    2.3) Третий прибавляет к своей зарплате число, полученное от Второго, и записывает результат на листке
3) Следующая операция требуют завершения всех распараллеленных операций из пункта (2):
    3.1) Любой из них суммирует числа, записанные на листике, и делит результат на три.

Итого те же три пункта, не поддающиеся распараллеливанию.
И самая длинная цепочка операций, не поддающаяся распараллеливанию это:
вычитание (1.1 / 1.2 / 1.3) + передача числа (1.1 / 1.2 / 1.3) + суммирование (2.1 / 2.2 / 2.3) + запись числа (2.1 / 2.2 / 2.3) + суммирование (3.1) + деление (3.1)
Итого три операции сложения/вычитания, одна операция деления и две передачи числа (запись числа на листке - та же передача).

Паша, я нигде не ошибся? Мы получили одинаковое время выполнения алгоритмов даже с распараллеливанием?

Дата : 01-05-07, Втр, 10:28:48

Дата : 01-05-07, Втр, 10:32:25

Решений действительно много

Беда в том, что до сих пор не найдено решение без приватной передачи каких-либо данных от одного человека другому в тайне от третьего. И не найдено док-во несуществования подобного решения.

Т.е. такого решения, при котором все расчеты ведутся публично.

Дата : 01-05-07, Втр, 11:52:03

Дата : 19-07-07, Чтв, 18:31:03