Turbo Pascal. Задача.

[Dionix]

Есть N одинаковых предметов и M пронумерованных ящиков.
Задача: Составьте программу BOXES, определяющую, сколько существует разных способов, которыми можно разместить все эти предметы в ящиках. Способы считаются разными, если они отличаются количеством предметов хотя бы в одном из ящиков.
Ввод: В текстовом файле BOXES.IN находятся два целых числа M и N. (M >= 1, N >= 1, M + N <= 60).
Вывод: В текстовый файл BOXES.OUT вывести целое число - количество различных способов размещения.
Пример
BOXES.IN
ВВОД:
2 2
BOXES.OUT
ВЫВОД:
3


заранее благодарен! )

[Serge_Bliznykov]

а мне задача не совсем понятна...
а в одном ящике сколько может быть предметов?

[Stilet]

а мне не ясны габариты ящиков и предметов.
а вдруг ящик резиновый - тогда кол-во способов (n*m)! Если правильно помню лекции

[zumm]

А мне кажется что задача не в том разделе!

[Dionix]

предметы в ящике могут быть разложны как угодно...
например

два ящика и два предмета:

2 0
1 1
0 2

и в итоге получаем ответ 3

[Serge_Bliznykov]

Сообщение от Stilet

а вдруг ящик резиновый

Stilet, а ведь, похоже, Вы угадали — похоже ящики действительно не имеют размеров!

Dionix, а задачка действительно забавная... надо будет завтра подумать над алгоритмом.

[Gumer]

Для n<10 можно делать так: из исходных данных сделать число x:=n*10^m (10 в степени m) и дальше циклом for i:=1 to x do искать числа, сумма цифр которых будет равна n. Количество таких чисел будет ответом. Но возникнет проблема, когда число m будет больше 17.

[Gumer]

Решение еще нужно? У меня есть мысль о правильном коде программы, но мне нереально лениво его писать.

[Serge_Bliznykov]

Сообщение от Gumer

У меня есть мысль о правильном коде программы

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

НО!! у меня всё время крутиться в голове мысль, что можно вывести мат.формулу, которая для заданных N и M вернёт число вариантов без всяких переборов!!

и ещё. Меня смущает вот эта часть условия:

M + N <= 60

для чего это задано? Подозреваю, что при вычислениях могут возникнуть ограничения по разрядной сетке?....

[Gumer]

var f:text;
    mas:array [1..60] of integer;
    n,m,i,x:integer;
    v:longint;

begin
assign(f, 'boxes.in');
ReSet (f);
Readln (f,m,n);
Close (f);

v:=0;

if m=1 then v:=1 else
repeat
x:=0;
inc(mas[1]);
for i:=1 to m do
 inc(x,mas[i]);

if (x=n) or (mas[1]=n) then
 begin
  inc(v);
  for i:=1 to m-1 do
   if mas[i]>=n then
    begin
     mas[i]:=0;
     inc(mas[i+1]);
    end
   else
    break;
 end;
if mas[m]=0 then inc(v);
until (mas[m]=n);


assign (f,'boxes.out');
ReWrite(f);
Writeln (f, v);
Close(f);
end.

Как я писал выше, можно эту задачу представить иначе:
У нас есть числа m и n, из которых можно составить число x:=n*10^m (10 в степени m). Остается лишь от 1 до x найти все числа, сумма цифр которых будет равна n. Но при n>9 и/или m>18 (где-то так) возникает трудность составить такое число x, поэтому я сворганил массив и когда какая-то ячейка массива равна n, я сбрасываю ее обратно в начало (присваиваю значение 0) и повышаю следующую.

Думаю, этот алгоритм правильный, но не очень эффективный при больших значениях m и n. Ввел 30 30 и прога повисла. Можно немного повысить эффективность, например, можно не продолжать увеличивать mas[1], если x=n.