Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм нахождения всевозможных комбинаций

Автор: cosamia 12.11.2012, 12:38

Подскажите может кому попадался алгоритм выдающий всевозможные комбинации для ситуации:
Имеем начальный массив с данными (100,0,0,0)
шаг = 10
Дальнейшие комбинации будут (90,10,0,0), (80, 10, 10,0) и тд
Общая сумма всегда должны быть 100

Автор: Akina 12.11.2012, 14:24

http://algolist.manual.ru/maths/combinat/breakaddend.php

Автор: cosamia 12.11.2012, 14:56

Цитата(Akina @ 12.11.2012, 14:24)

http://algolist.manual.ru/maths/combinat/breakaddend.php

Это не совсем то
Там идет речь о разбиении числа N на все возможные комбинации те для 4 это будет комбинация из 4 чисел
В таком случае для моего примера, для 100 это будет комбинация из 100 чисел, а я могу использовать только 4 числа

Автор: Akina 12.11.2012, 15:21

Если тебе удалось разобраться в сути алгоритма, то не должна вызвать сложностей и его модификация для решения твоей задачи.

Добавлено через 4 минуты и 49 секунд
А уж если совсем туго, то

Код


for i = 0 to 100 step 10
  for j = 0 to 100-i step 10
    for k = 0 to 100-i-j step 10
      print i, j, k, 100-i-j-k
    next k
  next j
next i

Автор: cosamia 12.11.2012, 17:43

Акина, мне кажется в этом алгоритме есть ошибка - на каждой итерации сумма всех значений не будет равна 100

Добавлено через 7 минут и 46 секунд
Да проверил, данный алгоритм не правильный сумма всех элементов на каждой комбинации не равна 100

Автор: Akina 12.11.2012, 19:38

Цитата(cosamia @ 12.11.2012, 18:43

)

данный алгоритм не правильный сумма всех элементов на каждой комбинации не равна 100

Ты хочешь сказать, что сумма чисел i, j, k и 100-i-j-k не равна 100? smile

Иди учить арифметику.

Автор: cosamia 12.11.2012, 19:46

1 sec

Добавлено через 3 минуты и 19 секунд
Sorry smile

Совершенно верно! Это я ошибся добавляя 4й разряд smile

Большое спасибо за помощь!

Добавлено через 7 минут и 33 секунды
И все-таки выдается множество комбинаций где сумма меньше указанной

Вот код

    int maxVal = 10;
    for(int i=0; i<=maxVal;i ++)
    {
        for(int j=0; j<=maxVal-i; j++)
        {
            for(int k=0; k<=maxVal-i-j; k++)
            {
                for(int m=0; m<=maxVal-i-j-k; m++)
                {
                    NSLog(@"Result: %d:%d:%d:%d ", i, j, k, m);
                }
            }
        }
    }

В принципе это решаемо путем отсеивания неверной комбинации сравнивая сумму

Автор: disputant 12.11.2012, 20:53

Цитата(cosamia @ 12.11.2012, 19:46)

И все-таки выдается множество комбинаций где сумма меньше указанной

В принципе это решаемо путем отсеивания неверной комбинации сравнивая сумму

А цикл по m зачем?!!!

m определяется однозначно как 100-i-j-k...