Помогите с алгоритмом

← →
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 (2003-02-25 01:47) [14]

Не считая того ограничения, что k должно быть меньше длины массива

Помогите с алгоритмом Найти похожие ветки