powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Опримальный Алгоритм; перебор; думаю интерестно.
3 сообщений из 3, страница 1 из 1
Опримальный Алгоритм; перебор; думаю интерестно.
    #33274970
Фотография GroZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача:
Даны четыре числа, A, B, C, D >= 0 а также число N , где 1 <= N <= (A + B + C + D) div 2
Требуется перебрать все варианты четвёрок a, b, c, d где:
0 <= a <= A ,
0 <= b <= B ,
0 <= c <= C ,
0 <= d <= D ,
a + b + c + d = N
и например вывести их на экран.

Другими словами задачу можно сформулировать так:
Имеется мешок с цветными шариками, среди них A белых шариков, B синих, C зелёных и D красных.
Также имеем корзину в которую помещается N шариков.
Нужно перебрать все возможные (различные) варианты наборов шариков которые могут оказаться в корзине, когда корзина заполнится.

Если просто вложить в циклы то скорость алгоритма будет порядка O((A+1)*(B+1)*(C+1)*(D+1)) .
Есть ли у вас, уважаемые, более оптимальные предложения/соображения?
...
Рейтинг: 0 / 0
Опримальный Алгоритм; перебор; думаю интерестно.
    #33275018
Фотография GroZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сообразил, можете закрыть тему ...
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
 procedure  GetAll;
 var 
   A, B, C, D, N, ia, ib, ic, id : integer;
 begin 
   Memo1.Clear;
   A := SpinEdit1.Value;
   B := SpinEdit2.Value;
   C := SpinEdit3.Value;
   D := SpinEdit4.Value;

   N := SpinEdit5.Value;

    for  ia := Max( 0 , N - (B + C + D))  to  Min(A, N)  do 
      for  ib := Max( 0 , N - (ia) - (C + D))  to  Min(B, N - (ia))  do 
        for  ic := Max( 0 , N - (ia + ib) - (D))  to  Min(C, N - (ia + ib))  do 
          for  id := Max( 0 , N - (ia + ib + ic))  to  Min(D, N - (ia + ib + ic))  do 
           Memo1.Lines.Add(IntToStr(ia) + ', ' + IntToStr(ib) + ', ' + IntToStr(ic) + ', ' + IntToStr(id) + '.');
    Memo1.Lines.Add('Total = ' + IntToStr(Memo1.Lines.Count));

 end ;
Прямо выводит все варианты, т.е. самый оптимальный ...
...
Рейтинг: 0 / 0
Опримальный Алгоритм; перебор; думаю интерестно.
    #33277557
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну в общем примерно так. Разве что для пущей красоты можно подумать над избавлением от вложенных циклов.

На эту тему был хороший пример задачи в одной старой книге. Там строилась некая экономическая модель и требовалось сделать нечто вроде данных для what-if анализа - было порядка полусотни параметров, влияющих на результат, и требовалось по каждому из них пробежать по указанному диапазону с указанным шагом и соответственно вывести результат для всех возможных комбинаций значений. Как говорит автор, он встречался с решениями на основе пятидесяти вложенных циклов :)
...
Рейтинг: 0 / 0
3 сообщений из 3, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Опримальный Алгоритм; перебор; думаю интерестно.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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