Задан массив, состоящий из n неотрицательных чисел.
Найти в нём индекс элемента для которого сумма элементов, стоящих до него, наименее отличается от суммы элементов, стоящих после него.
( Числа хранятся в линейном односвязном списке или в файле с последовательным доступом. Найти наиболее эффективные алгоритмы для случая прямого и последовательного доступа с возможностью использовать рабочий массив размерностью n или без неё)
Спасибо за внимание,
буду благодарна за ответы.
Полная версия: массивы, линейный односвязный список , файлы +
Задание срочное?
Постараюсь за выходные подумать над этим.
{Кстати, приятно и отвечать на так корректно составленный топик}
Постараюсь за выходные подумать над этим.
{Кстати, приятно и отвечать на так корректно составленный топик}
Пусть A - указатель на список с полями inf - само число и next - указатель на следующий.
L, R, d, i - целые переменные;
p - указатель, чтобы бегать по списку.
{...Задание списка или чтение списка из файла...}
R := 0;
p := A;
while p <> nil do
begin
R := R + p.inf;
p := p.next
end; {подсчитали сумму эл-тов}
i := 1;
d := R;
L := A.inf;
p := A.next;
R := R - p.inf;
while (d >= abs(L-R)) and (p<>nil) do
begin
inc (i);
d := abs (L-R);
L := L + p.inf; {левая сумма увеличивается на текущий элемент}
p := p.next;
R := R - p.inf; {из правой суммы вычитается следующий элемент, который становится текущим}
end;
{в i будет результат}
end;
L, R, d, i - целые переменные;
p - указатель, чтобы бегать по списку.
Код
{...Задание списка или чтение списка из файла...}
R := 0;
p := A;
while p <> nil do
begin
R := R + p.inf;
p := p.next
end; {подсчитали сумму эл-тов}
i := 1;
d := R;
L := A.inf;
p := A.next;
R := R - p.inf;
while (d >= abs(L-R)) and (p<>nil) do
begin
inc (i);
d := abs (L-R);
L := L + p.inf; {левая сумма увеличивается на текущий элемент}
p := p.next;
R := R - p.inf; {из правой суммы вычитается следующий элемент, который становится текущим}
end;
{в i будет результат}
end;
zx1024 Или я совсем дурак, или я просто не допонял, что ты тут написал, может напишешь всё, что это за список такой, что за реализация??? Не видать что он динамический?!!! Да даже если и не динамический, предположим если массив статический, а указатели используются динамические, то где здесь что??? где взятие адреса для указателя @, где что???
Напиши всё пожалуйста!!!!
А это что такое, не ужто переход по полям списка? А где ^ , а если он не динамический, разьве мы имеем право проверять на пустоту nill-ом???
Напиши всё пожалуйста!!!!
Цитата
p := p.next
А это что такое, не ужто переход по полям списка? А где ^ , а если он не динамический, разьве мы имеем право проверять на пустоту nill-ом???
Flipper ,Гость_Tanya
решать вам тут никто не обязан ,если кто то захотел вам помочь то решит не захотел или задача не понравилась ,значит не поможет. А отсрелавая таких вы вообще нигде даже спросить не сможете.
Инцедент исчерпан!!! Все!
решать вам тут никто не обязан ,если кто то захотел вам помочь то решит не захотел или задача не понравилась ,значит не поможет. А отсрелавая таких вы вообще нигде даже спросить не сможете.
Инцедент исчерпан!!! Все!
Само нахождение номера элемента я понимаю так:
Во первых номер элемента не может быть первым и последним
Значит надо брать со второго элемента списка или массива и до предпоследнего,
итак берём элемент считаем сумму до него и после него, далее отнимаем от большей суммы меньшую и запоминаем её в какую-нибудь переменную, например (К), берём следующий элемент и проделываем теже действия, смотрим если разность сумм будет больше (К), то оставляем (К) таким же, иначе меняем на новую разность и так до конца, пока не найдём самую малую разность сумм, при этом нужно запоминать номер взятого элемента!!!!
В общем если сделать всё по простому, то я имею ввиду сделать что-то в этом роде, используя массив:
const
n=16;
var
mas:array[1..n] of integer;
i,j,k,Sum1,Sum2,ish,nomer:integer;
begin
clrscr; randomize;
for i:=1 to n do begin
mas[i]:=random(9);
write(mas[i]:3); end;
Sum1:=0; Sum2:=0;
{}
j:=2;
for k:=1 to j-1 do
Sum1:=Sum1+mas[k];
{}
for k:=j+1 to n do
Sum2:=Sum2+mas[k];
{}
if Sum1>Sum2 then ish:=Sum1-Sum2 else ish:=Sum2-Sum1;
nomer:=j;
{}
for j:=3 to n-1 do
begin
Sum1:=0; Sum2:=0;
{}
for k:=1 to j-1 do
Sum1:=Sum1+mas[k];
{}
for k:=j+1 to n do
Sum2:=Sum2+mas[k];
{}
if (Sum1>Sum2) then
if ish>(Sum1-Sum2) then begin ish:=Sum1-Sum2; nomer:=j; end;
if (Sum2>Sum1) then
if ish>(Sum2-Sum1) then begin ish:=Sum2-Sum1; nomer:=j; end;
if (Sum1=Sum2) then nomer:=j;
end;
{}
writeln;
write('Номер элемента ',nomer);
end.
Правда это только для наглядности, написал на скорую руку, но думаю основываться надо на этом, естественно надо сделать как то по легче, вернее по меньше шоб написано было!!!
Посмотрим как будет действовать Atos
Во первых номер элемента не может быть первым и последним
Значит надо брать со второго элемента списка или массива и до предпоследнего,
итак берём элемент считаем сумму до него и после него, далее отнимаем от большей суммы меньшую и запоминаем её в какую-нибудь переменную, например (К), берём следующий элемент и проделываем теже действия, смотрим если разность сумм будет больше (К), то оставляем (К) таким же, иначе меняем на новую разность и так до конца, пока не найдём самую малую разность сумм, при этом нужно запоминать номер взятого элемента!!!!
В общем если сделать всё по простому, то я имею ввиду сделать что-то в этом роде, используя массив:
Код
const
n=16;
var
mas:array[1..n] of integer;
i,j,k,Sum1,Sum2,ish,nomer:integer;
begin
clrscr; randomize;
for i:=1 to n do begin
mas[i]:=random(9);
write(mas[i]:3); end;
Sum1:=0; Sum2:=0;
{}
j:=2;
for k:=1 to j-1 do
Sum1:=Sum1+mas[k];
{}
for k:=j+1 to n do
Sum2:=Sum2+mas[k];
{}
if Sum1>Sum2 then ish:=Sum1-Sum2 else ish:=Sum2-Sum1;
nomer:=j;
{}
for j:=3 to n-1 do
begin
Sum1:=0; Sum2:=0;
{}
for k:=1 to j-1 do
Sum1:=Sum1+mas[k];
{}
for k:=j+1 to n do
Sum2:=Sum2+mas[k];
{}
if (Sum1>Sum2) then
if ish>(Sum1-Sum2) then begin ish:=Sum1-Sum2; nomer:=j; end;
if (Sum2>Sum1) then
if ish>(Sum2-Sum1) then begin ish:=Sum2-Sum1; nomer:=j; end;
if (Sum1=Sum2) then nomer:=j;
end;
{}
writeln;
write('Номер элемента ',nomer);
end.
Правда это только для наглядности, написал на скорую руку, но думаю основываться надо на этом, естественно надо сделать как то по легче, вернее по меньше шоб написано было!!!
Посмотрим как будет действовать 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 этот способ будет оптимальным (не видно, как его можно ещё улучшить)
Поытайся разобраться в алгоритме. Если что-то неясно, спрашивай. В принципе, желательно было бы хотя бы попробовать самостоятельно написать программу по имеющемуся алгоритму. Впрочем, если срочно надо, можно помочь и с кодом. В таком слуае напиши как можно подробнее, как он должен выглядеть?массив динамический?список уже имеется или его тоже надо реализовывать? и т. п.
1. Без использования доп. массива
А) Список или файл с последовательным доступом.
Пробегаем список, подсчитывая сумму всех его элементов, и запоминаем её.
Затем начинаем проходить его ещё один раз, опять суммируя элементы, но теперь для каждого элемента(с некоторым инднксом i) вычисляем функцию следующим образом: находим разность удвоенной текущей суммы (элементов с номерами от 1 до i) и суммы всего массива и отнимаем от этой разности значение (i+1)-го эл-та. Начиная с некоторого i полученная функция становится неотрицательной. Значит, либо i-й, либо (i+1)-й эл-т является искомым (а именно тот, для которого модуль полученной функции меньше).
Б) Массив
Начинаем суммировать элементы массива сразу с обеих сторон. Как только сумма последовательности элементов с одной стороны начнёт превосходить, переходим на другую сторону и наоборот. Там, где последовательности встретятся, и располагается искомый элемент.
2. С использованием доп. массива
Пробегаем исходный массив или список, записывая в (i+1)-й элемент доп. массива сумму его i-го эл-та и (i+1)-го исходного эл-та. Таким образом, доп. массив- это массив текущих сумм. Очевидно, функция, описанная в 1A), является неубывающей (ведь все исходные эл-ты неотрицательны), а значит, мы можем организовать бинарный поиск её нуля, используя доп. массив(ведь у нём записаны текущие суммы для любого i, а в n-м эл-те записана сумма всего исходного массива). Разумеется, не обязательно найдётся именно нулевое значение функции, но мы в любом случае сможем узнать индекс, для которого она ближе всего к нулю. Это и будет индекс искомого эл-та.
Трудоёмкость бинарного поиска O(квадратный корень из n), а по сравнению со способом 1Б) мы выигрываем О(n), так как там на каждом шаге шаге прохода массива мы делали по крайней мере на одну операцию больше (сравнение текущих сумм последовательностей и, воэможно, переход на другую сторону массива). Т. образом, для достаточно большого n этот способ будет оптимальным (не видно, как его можно ещё улучшить)
Поытайся разобраться в алгоритме. Если что-то неясно, спрашивай. В принципе, желательно было бы хотя бы попробовать самостоятельно написать программу по имеющемуся алгоритму. Впрочем, если срочно надо, можно помочь и с кодом. В таком слуае напиши как можно подробнее, как он должен выглядеть?массив динамический?список уже имеется или его тоже надо реализовывать? и т. п.
Посмотрел...
То, что у меня описано в 1А), не сильно отличается от того, что написал zx1024
Amro
Имхо, скорее всего может - в том случае если он больше суммы всех остальных.
Да, можно... хотя и неэффективно. Считая все такие суммы, мы пробегаем по массиву n раз - то есть трудоёмкость будет О(n в квадрате).
То, что у меня описано в 1А), не сильно отличается от того, что написал zx1024
Amro
Цитата
Во первых номер элемента не может быть первым и последним
Имхо, скорее всего может - в том случае если он больше суммы всех остальных.
Цитата
итак берём элемент считаем сумму до него и после него, далее отнимаем от большей суммы меньшую и запоминаем её в какую-нибудь переменную, например (К), берём следующий элемент и проделываем теже действия,
Да, можно... хотя и неэффективно. Считая все такие суммы, мы пробегаем по массиву n раз - то есть трудоёмкость будет О(n в квадрате).
Atos Дык ведь сказано
Выходит что сам элемент не берётся!!!
И что из того что он больше??? Мне кажется что не может......
Это ты прав, Неэффективно!!! Спорить не буду...
Цитата
стоящих до него, наименее отличается от суммы элементов, стоящих после него
Выходит что сам элемент не берётся!!!
Цитата
Имхо, скорее всего может - в том случае если он больше суммы всех остальных
И что из того что он больше??? Мне кажется что не может......
Цитата
хотя и неэффективно. Считая все такие суммы, мы пробегаем по массиву n раз - то есть трудоёмкость будет О(n в квадрате).
Это ты прав, Неэффективно!!! Спорить не буду...
Цитата
стоящих до него, наименее отличается от суммы элементов, стоящих после него
Ну, под суммой элементов, стоящих перед первым, можно понимать просто ноль...
Да, и в том случае, если мы всё-таки будем рассматривать элементы начиная со второго, получается, что для массива размером 1 решения вообще не существует. А было бы желательно выдавать его для любых массивов.
Цитата
И что из того что он больше???
Ой, точно, извиняюсь, не просто больше, а больше как минимум в два раза
Цитата
Да, и в том случае, если мы всё-таки будем рассматривать элементы начиная со второго, получается, что для массива размером 1 решения вообще не существует.
Получается что так, тагды понятно......Цитата
не просто больше, а больше как минимум в два раза
тоже верно ....
Amro, я, возможно подзабыл чистый Паскаль, но свой код я копировал в точности из проги на Delphi (там Object Pascal), которая была рабочая и выдавала верный результат.
А целиком всю прогу писать желания нет.
И ещё...
O(log2(n))
А целиком всю прогу писать желания нет.
И ещё...
Цитата
Трудоёмкость бинарного поиска O(квадратный корень из n)
O(log2(n))
Точно... Спасибо за поправку. Чего-то я совсем расклеился 
Спасибо за поправку. Чего-то я совсем расклеился
С помощью односвязного списка напишите, пожалуйста, на паскале программу телефонной книги: модуль - библиотека функций и процедур для работы с элементами списка, запись в файл, меню тел. книги.
Заранее благодарю.
Заранее благодарю.
Guest, во-первых, зачем было поднимать тему, которой больше года? А во вторых, может ты соизволишь и в FAQ/Поиск заглянуть, или тебе на блюдечке готовый код принести? Не будет готового кода...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.