![]() |
перебор всех сумм n-го количества членов массива
Здравствуйте! Ситуация следующая: есть массив с длинами. Нужно перебрать все варианты сумм, состоящих из n-го количества членов массива (my_number).
Код AS3:
|
Цитата:
Добавлено через 12 минут Вру. 759'375 (15*15*15*15*15) |
Цитата:
...многовато, конечно, получается, массив может и больше быть все перебирать скорее всего не придется, если искомая сумма(+/-) будет найдена, то можно будет цикл остановить |
Да что же такое :) Опять не правильно посчитал, будет 16^5 = 1'048'576, но это при том, что одно число не может использоваться дважды или более, если может, то будет еще больше 20^5 = 3'200'000.
Цитата:
|
Есть общий массив с длинами труб, из него нужно будет подобрать определенный метраж,трубы должны быть определенной длины (от и до). В массив Ar добавляются трубы нужной длины. Исходя из минимальной и максимальной длины можно посчитать сколько будет труб (допустим от 5 до 6). И дальше планировалось перебирать все члены массива Ar сначала по 5 штук, потом, если потребуется по 6. Или остановить, когда будет найдено...как-то так
|
Как-то все равно не понятно. Скажем нужна длина 750, можно взять трубу 250 * 3, а можно 125 * 6. Поэтому мне кажется, что вы не с того конца начинаете (я про количество труб).
Цитата:
|
Вообще, если один элемент может встречаться 1 раз, то число вариантов есть (по определению, т.к. порядок элементов в сумме не важен) число сочетаний из 20 по 5, т.е. (20!/(15!*5!)) = 20*19*18*17*16/(1*2*3*4*5) = 15504. Если может встречаться 5 раз, то задача подсчёта сводится к "найти число способов разложить n одинаковых шаров по m разным корзинам", где n = 5, m = 20. Ответ (задачка известная, накрайняк - гуглится Upd: блин, оно же и в вики есть) - C(m + n - 1, n) = 42504.
Собсно идея решения задачи - берётся 19 перегородок и между ними расставляется 5 шаров. Она же может использоваться для переборного решения. Только я думаю хотят не переборное решение, если это не реальные трубы %) Целые ли длины труб? Какая вообще точная формулировка? %) |
Цитата:
Код AS3:
Цитата:
|
Собсно вот ваша задачка, с вас
PS: если длины труб не целые, то ужос ивсётакое. |
А зачем это делать на ActionScript?
На сервере, с Java/C было бы быстрей, а на логических языках вроде Prolog/Mercury лаконичней |
Согласен с Nirth, при максимальном числе труб 24 при выборе из 30 труб, получится 30^24 = 2,82429536481e+35 вариантов.
|
Да строит оно трубу на 100км за полсекунды на флэше и не жужжит. Зачем сервер нагружать?
|
-De-, iNils, спасибо за помощь :drinks:
Остановился пока на таком варианте, надо будет доработать потом... Код AS3:
Цитата:
|
ужасные наименования. глаза ломает.
Код AS3:
|
Не интересно с допуском!
Вот, раз уж я накидал, чтоб посмотреть, за сколько же оно считает, мож пригодится. Код AS3:
|
| Часовой пояс GMT +4, время: 11:01. |
Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.