Дана последовательность чисел от 1 до 10000, которые хранятся в массиве с индексами от 0 до 9999 соответственно. Из массива удаляется одно произвольное число.
Как вы найдете это число? Опишите свои дейсвтия.

Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

Здравствуйте, Аноним, Вы писали:

А>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

Сумму посчитать.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, Аноним, Вы писали:

А>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

V_>Сумму посчитать.

Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору. Это то же самое что пройти через весь массив поэлементно и найти удаленное число. Следовательно, ответ, думаю, должен быть другим.

Здравствуйте, Аноним, Вы писали:

А>Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору. Это то же самое что пройти через весь массив поэлементно и найти удаленное число.

Нет, не то же самое. Ты не можешь так просто пройти поэлементно, чтобы найти удалённое число. Придётся ещё вспомогательную структуру данных заводить, линейную по объёму. Накапливаемая сумма же — это «структура данных», константная по объёму.

А>Следовательно, ответ, думаю, должен быть другим.

Ещё можно ксорить, а не суммировать (а то переполнения всякие, etc.) Потом перексорить полученный результат с ожидаемым.

Здравствуйте, Аноним, Вы писали:

А>>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

V_>>Сумму посчитать.

А>Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору.
А>
А>Это то же самое что пройти через весь массив поэлементно и найти удаленное число.

Ну-ка, ну-ка. Поясните ваш "поэлементный" алгоритм на этом примере (числа от 1 до 20, одно пропущено):
5 2 8 6 19 15 12 10 4 16 3 11 7 14 9 1 20 13 18

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

V_>>>Сумму посчитать.

А>>Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору.
А>>
А>>Это то же самое что пройти через весь массив поэлементно и найти удаленное число.

A>Ну-ка, ну-ка. Поясните ваш "поэлементный" алгоритм на этом примере (числа от 1 до 20, одно пропущено):
A>5 2 8 6 19 15 12 10 4 16 3 11 7 14 9 1 20 13 18

вы слово "соответственно" пропустили когда читали.

Здравствуйте, Аноним, Вы писали:

А>Дана последовательность чисел от 1 до 10000, которые хранятся в массиве с индексами от 0 до 9999 соответственно. Из массива удаляется одно произвольное число.
А>Как вы найдете это число? Опишите свои дейсвтия.

А>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

Скорее всего имеется в виду что массив стал короче на 1-н элемент. Т.е. число не нулем заменили (или на неопределенное значение), а действительно удалили и элементов стало 9999. А дальше просто.

Здравствуйте, Аноним, Вы писали:

А>>>>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

V_>>>>Сумму посчитать.

А>>>Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору.
А>>>
А>>>Это то же самое что пройти через весь массив поэлементно и найти удаленное число.

A>>Ну-ка, ну-ка. Поясните ваш "поэлементный" алгоритм на этом примере (числа от 1 до 20, одно пропущено):
A>>5 2 8 6 19 15 12 10 4 16 3 11 7 14 9 1 20 13 18

А>вы слово "соответственно" пропустили когда читали.

Хм, и правда, мутная формулировка — надо было или явно написать, что числа идут в порядке возрастания, или явно написать обратное.
Согласен, что если числа отсортированные и одно удалили, сжав массив, то быстрее будет воспользоваться обычным бинарным поиском, за O(log N).

Здравствуйте, 0K, Вы писали:

0K>Здравствуйте, Аноним, Вы писали:

А>>Дана последовательность чисел от 1 до 10000, которые хранятся в массиве с индексами от 0 до 9999 соответственно. Из массива удаляется одно произвольное число.
А>>Как вы найдете это число? Опишите свои дейсвтия.

А>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

0K>Скорее всего имеется в виду что массив стал короче на 1-н элемент. Т.е. число не нулем заменили (или на неопределенное значение), а действительно удалили и элементов стало 9999. А дальше просто.

нет, там не говорилось что массив сжимается после удаления элемента, следовательно в месте удаления элемента что-то вроде null будет.

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>>>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

V_>>>Сумму посчитать.

А>>Когда вы начнёте считать сумму, вам нужно будет пройти через каждый элемент массива, достать его и добавить к аккумулятору.
А>>
А>>Это то же самое что пройти через весь массив поэлементно и найти удаленное число.

A>Ну-ка, ну-ка. Поясните ваш "поэлементный" алгоритм на этом примере (числа от 1 до 20, одно пропущено):
A>5 2 8 6 19 15 12 10 4 16 3 11 7 14 9 1 20 13 18

21*20/2-(5+2+8+6+19+15+12+10+4+16+3+11+7+14+9+1+20+13+18) = 17

Здравствуйте, Аноним, Вы писали:

А>нет, там не говорилось что массив сжимается после удаления элемента, следовательно в месте удаления элемента что-то вроде null будет.

Ну, тогда задачу можно упростить: найти null в массиве из 10000 элементов
В общем, что-то тут не так с формулировкой.

Здравствуйте, andy1618, Вы писали:

A>В общем, что-то тут не так с формулировкой.

С формулировкой не так, похоже, у топикстартера. Потому что задача довольно известна в формулировке, когда числа в массиве неупорядочены и их достаточно, чтобы сумма переполнила целое.

Мне кажется, что речь идет не о простом переборе всех значений, поэтому варианты посчитать сумму, найти null или т.п. несостоятельны.
Скорее всего (по моему) речь идет о дихотомии/н-хотомии в общем случае и поиск отсутствующего числа. Типа проверяем 5000 — число совпадает с позицией — да идем на 7500 позицию, нет — идем на 2500 позицию и так далее, всего лог(10000)+1 шагов алгоритма

XOR всех елементов масива в результате останется искомое число

А>XOR всех елементов масива в результате останется искомое число

не совсем так. это верно если xor всех чисел от 1 до N это ноль.
Но xor всех чисел от 1 до N равен:
N, если N%4 == 0
1, если N%4 == 1
N+1, если N%4 == 2
0, если N%4 == 3

Здравствуйте, dilmah, Вы писали:


А>>XOR всех елементов масива в результате останется искомое число

D>не совсем так. это верно если xor всех чисел от 1 до N это ноль.
D>Но xor всех чисел от 1 до N равен:
D>N, если N%4 == 0
D>1, если N%4 == 1
D>N+1, если N%4 == 2
D>0, если N%4 == 3

в условии задачи сказано "Дана последовательность чисел от 1 до 10000" а не 1 до N

А>в условии задачи сказано "Дана последовательность чисел от 1 до 10000" а не 1 до N

Тогда возникает вопрос до 10000 включительно
или исключительно.
ксор всех чисел ноль только если
исключительно до 10000.
Обычно эта фраза понимается включительно
а в этом случае ксор всех чисел равен 10000

Здравствуйте, Аноним, Вы писали:

А>Дана последовательность чисел от 1 до 10000, которые хранятся в массиве с индексами от 0 до 9999 соответственно. Из массива удаляется одно произвольное число.
А>Как вы найдете это число? Опишите свои дейсвтия.

А>Честно говоря, задач там было много и я очень быстро написал, наверное, полный бред, что можно было бы массив разделить на части, отдать части на обработку потокам, которые там уже бы бинарным поиском нашли число. А как правильно?

Используй указатели

Здравствуйте, dilmah, Вы писали:


А>>XOR всех елементов масива в результате останется искомое число

D>не совсем так.
В любом случае решение довольно остроумное.

Здравствуйте, Аноним, Вы писали:

А>Мне кажется, что речь идет не о простом переборе всех значений, поэтому варианты посчитать сумму, найти null или т.п. несостоятельны.
А>Скорее всего (по моему) речь идет о дихотомии/н-хотомии в общем случае и поиск отсутствующего числа. Типа проверяем 5000 — число совпадает с позицией — да идем на 7500 позицию, нет — идем на 2500 позицию и так далее, всего лог(10000)+1 шагов алгоритма

Что-то мне кажется в предложенном решении ни разу log(n) + 1 не получится.
И бинарный поиск, который предложил топикстартер тут тоже ни к чему.