Дана последовательность чисел от 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 не получится.
И бинарный поиск, который предложил топикстартер тут тоже ни к чему.

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

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

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

V_>>Сумму посчитать.
V>Бессполезно, в условии ничего не было сказано про возможность заполнения массива самому, изходя из условия — массив уже был заполнен.

А в чём разница, если мы знаем чем он был заполнен?

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

V_>>>Сумму посчитать.
V>>Бессполезно, в условии ничего не было сказано про возможность заполнения массива самому, изходя из условия — массив уже был заполнен.
UBA>А в чём разница, если мы знаем чем он был заполнен?
Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.

V>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.

а где написано что они отсортированы?

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

V>>>Бессполезно, в условии ничего не было сказано про возможность заполнения массива самому, изходя из условия — массив уже был заполнен.
UBA>>А в чём разница, если мы знаем чем он был заполнен?
V>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.

Так быстрее или суммирование бесполезно?

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

V>>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.

D>а где написано что они отсортированы?

Опять пропускаем в условии слово "соответственно"?

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

Я думаю, бинарный поиск.

Если из массива удалили элемент N, значит, начиная с индекса N все элементы стали больше на единицу.

Берем средний элемент и смотрим: если индекс нормальный, продолжаем поиск в правом поддиапазоне, если больше на единицу, чем должен быть, продолжаем поиск в левом поддиапазоне.

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

V>>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.
D>а где написано что они отсортированы?
В условии

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

V>>>>Бессполезно, в условии ничего не было сказано про возможность заполнения массива самому, изходя из условия — массив уже был заполнен.
UBA>>>А в чём разница, если мы знаем чем он был заполнен?
V>>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.
UBA>Так быстрее или суммирование бесполезно?
Под бесполезностью я и имел ввиду что она будет сведена на нет.

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

V>>>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.
UBA>>Так быстрее или суммирование бесполезно?
V>Под бесполезностью я и имел ввиду что она будет сведена на нет.

Теперь совсем не понял.

Здравствуйте, 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
Это можно исправить добавлением или проверить только часть массива. А решение красивое.

D>>N, если N%4 == 0
D>>1, если N%4 == 1
D>>N+1, если N%4 == 2
D>>0, если N%4 == 3
B>Это можно исправить добавлением или проверить только часть массива. А решение красивое.

это нужно исправить просто учтя то что ксор всех чисел не ноль, а указанное число -- то есть сделать дополнительный ксор с указанным числом.

Решение полностью тождественно решению с суммой, только вместо суммы взят ксор (который является разновидностью суммы).
точно также своп двух чисел без временной переменной можно делать через сумму, а можно через ксор.

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

V>>>>Тем что для суммирования имеет смысл только если сам заполняешь такой отсортированный массив. Деление попалам будет в среднем здесь быстрее.
UBA>>>Так быстрее или суммирование бесполезно?
V>>Под бесполезностью я и имел ввиду что она будет сведена на нет.
UBA>Теперь совсем не понял.
Что именно?

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

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

самсунг?

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

V>>>Под бесполезностью я и имел ввиду что она будет сведена на нет.
UBA>>Теперь совсем не понял.
V>Что именно?

Что такое "сведена на нет", неправильный результат будет?

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

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

V>>>>Под бесполезностью я и имел ввиду что она будет сведена на нет.
UBA>>>Теперь совсем не понял.
V>>Что именно?
UBA>Что такое "сведена на нет", неправильный результат будет?
UBA>Согласен, для отсортированного массива глупое решение, но работает.
Микроскопом гвозди забивать глупое решение, но работает.