Комбинации школ из 50 и 25 мест для 100 учеников

[bigarcus]

(Оффтоп)

Почему мало элегантного? Если это полный код, то видно же что нет лишнего вроде var, begin, end и прочего синтаксиса.

[gris]

Насчёт количества вариантов. Их 16 (я там поправил), просто при копировании в сообщение упустил одну строку.
На самом деле это ActionScript для Flash, но все конструкции, особенно чисто вычислительные, там стандартны. А идею я же изложил. Кратный цикл, прямой подсчёт суммы и сравнение её с результатом.
При этом, конечно, просчитывается огромное количество заведомо непроходных вариантов, но для небольших значений это несущественно.
Циклы имеет смысл оптимизировать, если счёт идёт на триллионы, да и то...
Хотя вот я сейчас запустил разложение 10000 на те же слагаемые и там считалось несколько секунд. Ведь количество проверяемых вариантов увеличилось в 1000 раз. А если взять 100000, то комп задумается надолго. Но как раз в Паскале дело будет идти гораздо быстрее. Скрипт есть скрипт.

О параметрах цикла. Вот немного приукрашенный код:

N=1000;
m1=30; m2=81; m3=125;

n1=Math.floor(N/m1)+1; n2=Math.floor(N/m2)+1;n3=Math.floor(N/m3)+1;
K=0;

for (k1=0; k1<n1; k1++) {
   for (k2=0; k2<n2; k2++) {
      for (k3=0; k3<n3; k3++) {
          NK=k1*m1+k2*m2+k3*m3;
          if (Math.abs(NK-N)<2) {K=K+1;trace (NK+"="+k1+"*"+m1+"+"+k2+"*"+m2+"+"+k3+"*"+m3)}
}}}

trace ("Всего "+K+" вариантов")

1000=0*30+0*81+8*125
999=9*30+9*81+0*125
999=10*30+4*81+3*125
1001=13*30+6*81+1*125
1001=14*30+1*81+4*125
1000=25*30+0*81+2*125
Всего 6 вариантов

На Паскале цикл будет записываться так:

for k1:=1 to n1 do begin
     for k2:=1 to n2 do begin
          for k3:=1 to n3 do begin
                ....
          end;
      end;
end;

При желании можно вычислять параметры внутренних циклов непосредственно перед их началом, но для разовых расчётов на оптимизацию уйдёт гораздо больше времени, чем на сами расчёты .

[bigarcus]

Здорово! Спасибо большое!!! Сейчас пытаюсь разобраться и переписать!

-- Вс июн 24, 2012 19:22:53 --

А как у Вас используется K ? Оно не лишнее ли?

[bigarcus]

А, понял, чтобы количество вариантов посчитать.

-- Вс июн 24, 2012 20:11:59 --

gris в сообщении #588182 писал(а):

[off]Я думал, Вы всерьёз про амфорную. Это название действительно было в Древней Греции. Вино и масло разливали в амфоры и надо было для определённого объёма жидкости подобрать набор амфор, в которые она бы вместилась. По существу, это и есть Ваша задача. Диофант Александрийский и начал свои исследования с амфорных задач.

Не подскажете, где можно об этом почитать. Гугл молчит.

[longstreet]

Стало интересно как задача решается не перебором.

-- 25.06.2012, 08:33 --

Общий вид линейного диофантова уравнения:

$$a_1 x_1+a_2 x_2 + \ldots + a_k x_k =d$$

Где $d \text{ и } a_1,\, a_2,\, \ldots,\, a_k$ берутся из условия.

Как его решить в общем виде?

-- 25.06.2012, 08:40 --

Да, в "Конкретной математике" решение задачи про размен монет с помощью производящих функций $-$ отличный хинт.

[bigarcus]

gris, а как сделать цикл в цикле, чтобы количество типов задавалось пользователем? Чтобы N, m1, m2, m3 запрашивались и задавались я сделал.

[longstreet]

Однако метод производящих функций даст только точное равенство, а не приближенное. Не знаю, можно ли это обойти.