массивы, линейный односвязный список , файлы +, +последовательного и прямого доступа Опции

[Ира]

Задан массив, состоящий из n неотрицательных чисел.
Найти в нём индекс элемента для которого сумма элементов, стоящих до него, наименее отличается от суммы элементов, стоящих после него.
( Числа хранятся в линейном односвязном списке или в файле с последовательным доступом. Найти наиболее эффективные алгоритмы для случая прямого и последовательного доступа с возможностью использовать рабочий массив размерностью n или без неё)

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

[Atos]

Ого, сколько уже ответов... Сейчас начну смотреть... А я вообще-то
пока написал и хотел выложить вот это:

Наиболее эффекивные алгоритмы:

1. Без использования доп. массива

А) Список или файл с последовательным доступом.

Пробегаем список, подсчитывая сумму всех его элементов, и запоминаем её.
Затем начинаем проходить его ещё один раз, опять суммируя элементы, но теперь для каждого элемента(с некоторым инднксом i) вычисляем функцию следующим образом: находим разность удвоенной текущей суммы (элементов с номерами от 1 до i) и суммы всего массива и отнимаем от этой разности значение (i+1)-го эл-та. Начиная с некоторого i полученная функция становится неотрицательной. Значит, либо i-й, либо (i+1)-й эл-т является искомым (а именно тот, для которого модуль полученной функции меньше).

Б) Массив

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

2. С использованием доп. массива

Пробегаем исходный массив или список, записывая в (i+1)-й элемент доп. массива сумму его i-го эл-та и (i+1)-го исходного эл-та. Таким образом, доп. массив- это массив текущих сумм. Очевидно, функция, описанная в 1A), является неубывающей (ведь все исходные эл-ты неотрицательны), а значит, мы можем организовать бинарный поиск её нуля, используя доп. массив(ведь у нём записаны текущие суммы для любого i, а в n-м эл-те записана сумма всего исходного массива). Разумеется, не обязательно найдётся именно нулевое значение функции, но мы в любом случае сможем узнать индекс, для которого она ближе всего к нулю. Это и будет индекс искомого эл-та.

Трудоёмкость бинарного поиска O(квадратный корень из n), а по сравнению со способом 1Б) мы выигрываем О(n), так как там на каждом шаге шаге прохода массива мы делали по крайней мере на одну операцию больше (сравнение текущих сумм последовательностей и, воэможно, переход на другую сторону массива). Т. образом, для достаточно большого n этот способ будет оптимальным (не видно, как его можно ещё улучшить)


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