powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
11 сообщений из 36, страница 2 из 2
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733461
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kefirkoу меня неизвестное кол-во элементов в массиве. Может быть 2, может быть 100.

Дополнения:
- Думаю, что уже при 15 - 20 элементах ты можешь не дождаться результата на своем компе... и причин
на это туева хуча....
- реально сделать рабочую программу при известном заранее максимально возможном количестве элементов...
- думаю, что преподу хватит вразумительной блок схемы на ватмане... (мне бы хватило)
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733462
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
var
  Values: array[0..4] of integer= (52, 41, 1, 75, 12);
  Sums: array of integer;

procedure AllSums;
var
  i, j, k: integer;
begin;
  SetLength(Sums, 1 shl Length(Values) - 1);
  k:=0;
  for i:=0 to Length(Values)-1 do begin;
    for j:=0 to k-1 do Sums[j+k]:=Sums[j]+Values[i];
    Sums[k+k]:=Values[i];
    k:=k+k+1;
    end;
  end;
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733470
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
VSVLAD, ваш пример дошел быстрее остальных, спасибо.
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733475
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov,
for i:=0 to Length(Values)-1 do begin;
for j:=0 to k-1 do Sums[j+k]:=Sums[j]+Values[i];
Sums[k+k]:=Values[i];
k:=k+k+1;
end;
end;

Как то тут маловато всего... а реально проверяли ? просто это не мой язык....


Для примера ТС нужны телодвижения и переборы:
1. Запись всего исходного массива "массив" в результат.
2. перебор всех двух цифр:
For i1 = 1 To 4
For i2 = i1 +1 to 5
' Запись в результат массив(i1) + массив(i2)
next i1
next i2
3. Перебор всех Трех цифр:
For i1 = 1 To 3
For i2 = i1 +1 to 4
For i3 = i2 +1 to 5
' Запись в результат массив(i1) + массив(i2) + массив(i3)
next i1
next i2
next i3
4. Перебор всех Четырех цифр:
For i1 = 1 To 2
For i2 = i1 +1 to 3
For i3 = i2 +1 to 4
For i4 = i3 +1 to 5
' Запись в результат массив(i1) + массив(i2) + массив(i3) + массив(i4)
next i1
next i2
next i3
next i4
5. Запись в результат массив(1) + массив(2) + массив(3) + массив(4) + массив(4)
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733536
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Готово. Посмотреть на реализацию можно тут .
Вот сам код на Javascript'е:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
array1 = [52, 41, 1, 75, 12] //задаем массив любой длины
array2 = [] //результирующий массив, пока пустой

str = ""
for (k=0; k<array1.length; k++) {
  str += array1[k] + ", "
}
str = str.substring(0, str.length-2)
alert("исходный массив: " + str)

//исходя из длины массива, собираем двоичное число из единиц, у которого разрядность = длине массива
//к примеру, если array1.length=4, то bin=1111, если array1.length=6, то bin=111111
bin = ""
for (i=0; i<array1.length; i++) {
	bin += "1"
}
//при переводе двоичного числа в десятеричное, получим кол-во переборов всех возможных сумм элементов из исходного массива array1
dec = parseInt(bin, 2)

alert("кол-во переборов 10^ / 2^ = " + dec + " / " + bin)

//собираем array2
for (i=1; i<=dec; i++) {
  bin = (i).toString(2)
  raz = array1.length - bin.length
  summ = 0
  for (k=raz+1; k<=array1.length; k++) {
    sub = bin.substring(k-raz-1, k-raz)
    summ += array1[k-1] * sub
  }
  array2[array2.length] = summ
}

str = ""
for (k=0; k<array2.length; k++) {
  str += array2[k] + ", "
}
str = str.substring(0, str.length-2)
alert("результат: " + str)



Отдельная благодарность VSVLAD и Dima T.

Кстати задачка была не для препода, а для себя. Пытался разобраться в оптимизации линейного раскроя материалов или по-другому: "как эффективнее распилить палку на заготовки нужной длины". Прог то готовых куча, а вот как они это делают мне как раз и было интересно. Теперь я беру ближайшее снизу из массива к длине палки и получаю оптимальную комбинацию.
Для вышеизложенного примера:
Заготовки должны быть длиной 52, 41, 1, 75, 12мм, а палка к примеру 100мм.
Самым оптимальным укладыванием будет 94мм (ближайшее снизу), т.е. 52+41+1мм.

Всем спасибо.
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733541
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kefirko,

в таком случае непонятно, зачем был нужен массив.

P.S. Не знаю, имеет ли смысл говорить, что имеет смысл изучить теорию вопроса.
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733554
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kefirko"как эффективнее распилить палку на заготовки нужной длины".

kefirkoЗаготовки должны быть длиной 52, 41, 1, 75, 12мм, а палка к примеру 100мм.
Самым оптимальным укладыванием будет 94мм (ближайшее снизу), т.е. 52+41+1мм.

Лже решение....

При таком подходе (при массовом использовании) останется куча отходов приличной длины,
ибо так на кусок 12 см можно и вообще не выйти, в другом случай 75см ни с чем и никак и останется
25 см...

Правильная постановка задачи:
1. Это есть набор палок (заготовок), возможно даже разной длины.
2. Есть необходимость порезать их на куски (детали) определенной длины (речь о партии).
3. Нужно это сделать так чтобы порезать минимальное количество заготовок и при этом иметь
минимум никчемных обрезков, которые уже ни туда - ни сюда...
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733576
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vmag, это уже другая задача. Для будущих разборов. Потихоньку к этому иду.
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38743782
BaurzhanS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kefirko, я отвечал как-то на такой вопрос . Там битовые маски, как у тебя, но проще реализация - зачем числа гонять с строки, когда есть битовые операции? )
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38744073
F#
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
F#
Гость
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
// Learn more about F# at http://fsharp.net
// See the 'F# Tutorial' project for more help.
let sourceArray = [52; 41; 1; 75; 12]
let rec allSumsOf xs = 
    if List.isEmpty xs then
        List.Empty
    else
        let head = List.head xs
        let tail = List.tail xs
        let tailSums = allSumsOf tail
        let tailPlusHead = tailSums |> List.map ((+) head)
        
        head :: tailSums @ tailPlusHead

[<EntryPoint>]
let main argv = 
    printfn "%A" (allSumsOf sourceArray |> List.sort)
...
Рейтинг: 0 / 0
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38744100
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kefirkoПытался разобраться в оптимизации линейного раскроя материалов или по-другому: "как эффективнее распилить палку на заготовки нужной длины". Прог то готовых куча, а вот как они это делают мне как раз и было интересно.
Это частный случай задачи о рюкзаке, упаковать в ограниченный объем вещи с максимальной общей стоимостью. Алгоритмы решения многократно описаны в инете.
...
Рейтинг: 0 / 0
11 сообщений из 36, страница 2 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]