Текущий архив: 2003.03.13;
Скачать: CL | DM;
Вниз
Помогите с алгоритмом Найти похожие ветки
← →
Pat © (2003-02-24 18:13) [0]Дан одномерный массив А, состоящий из n элементов. Задано число k. Необходимо вычислить сумму всевозможных произведений элементов массива из k сомножителей.
Пример:
Массив: 1 5 3 2 8
k = 3
Summa = 1*5*3 + 1*5*2 + 1*5*8 + 1*3*2 + 1*3*8 + 1*2*8 + 5*3*2 + 5*3*8 + 5*2*8 + 3*2*8
Может что и упустил.. :-))
← →
Pat © (2003-02-24 19:08) [1]А ну да, вопрос забыл...Как это сделать? :-))
← →
SGh © (2003-02-24 19:39) [2]Детский сад :))))
for n1:=1 to L-k+1 do begin
for n2:=n1+1 to L-k+2 do begin
for n3:=n2+1 to L-k+3 do begin
Summa:=Summa+M[n1]*M[n2]*M[n3];
end;
end;
end;
Где М - массив,
L - длина массива,
остальное как у тебя
← →
nikkie © (2003-02-24 20:24) [3]>SGh
Замечательное решение для конкретного значения k=3. К сожалению, в общем случае не работает.
← →
nikkie © (2003-02-24 20:30) [4]>Pat
1. Необходимо решить задачу перебора всех сочетаний k элементов из N существующих. Вычисление суммы произведений тогда - технически просто.
← →
nikkie © (2003-02-24 20:32) [5]2. Итак, надо перечислить все наборы из k различных чисел от 1 до N.
Вариант 1 - рекурсивный. Пишем функцию f(N,k), которая будет перечислять все такие наборы. Считаем, что числа в наборе упорядочены по возрастанию. В конце - максимальное число, которое может иметь значение от k до N. Перебираем
for M := k to N
и если k > 1, то рекурсивно вызываем f(M-1, k-1)
← →
nikkie © (2003-02-24 20:41) [6]Вариант 2 - итеративный. Потребуем, чтобы наша функция выводила наши последовательности не абы как, а упорядоченно, например, лексикографически. То есть идти они долны так:
(1, 2, 3, ... k-1, k)
(1, 2, 3, ... k-1, k+1)
(1, 2, 3, ... k-1, k+2)
(1, 2, 3, ... k-1, k+3)
...
(1, 2, 3, ... k-1, N)
(1, 2, 3, ... k, k+1)
(1, 2, 3, ... k, k+2)
(1, 2, 3, ... k, k+3)
...
Сделаем две функции
- init() - заполняет последовательность значениями (1, 2, ... k)
- next() - осуществляет переход от одной последовательности к следующей за ней соответсвенно нашему порядку. Возвращает False, когда дальше ничего нет.
Тогда основная функция будет выглядеть как
init();
repeat
...
until not next();
Реализацию функции next продумай сам.
← →
NetBreaker666 © (2003-02-24 23:49) [7]var Result :Integer;
M :array[ 1 ..N ] of Integer;
procedure PRV(CurV :Integer ;v :Integer ;depth :Integer );
var i :Integer ;
Begin
if (v >N ) then exit ; // for any case
inc (depth );
if (depth =K ) then
for i :=v to N do Result :=Result +CurV *M [v ]
else
for i :=v to N do PRV (CurV *M [v ],i ,depth );
End;
Объяснить ?
← →
NetBreaker666 © (2003-02-24 23:55) [8]Да, запускать надо так
PRV(1,1,0)
K,N - глобальные
← →
Pat © (2003-02-25 00:29) [9]>nikkie © (24.02.03 20:32)
С рекурсией как-то в голову ничего не приходит
Вариант 2 - итеративный Какая разница, в каком порядке идут числа? Работать надо будет все равно с индексами в массиве.
>NetBreaker666 © (24.02.03 23:49)
Stack overflow. С рекурсией перемудрил где-то. Да и как-то не очень понятно, объясни, плиз....
← →
AK-74 © (2003-02-25 00:44) [10]Если предыдущие примеры показались вам нерабочими или сложными в отладке, то просто попробуйте это:
m={1,5,3,2,8}
ind={1,2,3,4,5}
L=Len(m)
k=3
sum=0
i=k
do while i>0
if ind[i+1]-ind[i]>1
ind[i]++
end if
do while ind[i+1]-ind[i]>1
ind[i+1]=ind[i]+1
i++
end do
do while ind[i]<=L+i-k
mul = 1
for j=1 to k
mul *= m[ind[j]]
next
sum+=mul
ind[i]++
end do
ind[i]--
i--
end do
?"Sum=",sum
← →
nikkie © (2003-02-25 01:21) [11]>Pat
>Какая разница, в каком порядке идут числа? Работать надо будет все равно с индексами в массиве.
Разумеется. Про них и речь. Перечислить надо все сочетания индексов. Заданные конкретные числа хранятся в отдельном массиве.
>С рекурсией как-то в голову ничего не приходит
А что должно в голову приходить? То, что я написал - рекурсивный алгоритм русским языком, его надо только на паскаль переписать.
← →
AK-74 © (2003-02-25 01:25) [12]Дословный перевод:
program Summa(Input,Output);
{$APPTYPE CONSOLE}
var
m: array [1..5] of integer = (1,5,3,2,8);
ind: array [1..5] of integer = (1,2,3,4,5);
L,k,sum,i,j,mul : integer;
begin
L:=Length(m);
k:=3;
sum:=0;
i:=k;
while i>0 do begin
if (ind[i+1]-ind[i]) > 1 then
Inc(ind[i]);
while (ind[i+1]-ind[i]) > 1 do begin
ind[i+1] := ind[i]+1;
Inc(i)
end;
while ind[i]<=L+i-k do begin
mul := 1;
for j:=1 to k do
mul := mul * m[ind[j]];
sum := sum + mul;
Inc(ind[i])
end;
Dec(ind[i]);
Dec(i)
end;
WriteLn("Сумма=",sum);
ReadLn;
end.
← →
Pat © (2003-02-25 01:44) [13]>AK-74 © (25.02.03 01:25)
Большое спасибо. Все работает :-))
← →
AK-74 © (2003-02-25 01:47) [14]Не считая того ограничения, что k должно быть меньше длины массива
Страницы: 1 вся ветка
Текущий архив: 2003.03.13;
Скачать: CL | DM;
Память: 0.5 MB
Время: 0.022 c
