Задачка.

[pinmix]

Мне нужна помощь в решении некоторой задачки, вернее задачка уже решена, ее нужно доказать.

Дело в том, что я учусь на ф-ке защиты информации, и на лекции "введение в специальность" мы решили задачу которая называется "Задача о разбиении целого числа" (может кто знаком с такой, если да - уточните об этом (просто интересно кто еще с таким сталкивался));

Условие задачи таково:

есть целое число: "N",

N=n1+n2+...+ni

P(N) - к-во разбиений числа N (количество способов)

Q(N,M) - к-во разбиений N на слагаемые не превышающие M

Вывели некоторые формулы:

*Q(N,M)=Q(N,M-1)+Q(N-M,M)

*Q(N,M)=Q(N,N), если M>N

*Q(N,N)=1+Q(N,N-1)

*Q(N,1)=1

*Q(1,M)=1

Пример: Число: 5

Q(5,3)=Q(5,2)+Q(2,3)=

=Q(5,2)+Q(2,2)=

=Q(5,2)+1+Q(2,1)=

=Q(5,2)+1+1=Q(5,2)+2=

=2+Q(5,1)+Q(3,2)=

=2+1+Q(3,2)=3+Q(3,2)=

=3+Q(3,1)+Q(1,2)=

=3+1+Q(1,2)=4+Q(1,2)=

=4+1=5

В этой задаче можно сократить время выполнения, если использовать формулу №5: *Q(1,M)=1, но при этом, если каждый раз проверять алгоритм на наличие "1" в ячейке "N" - то время можно и потерять, так что использование этой формулы правильно не в каждом алгоритме.

А вопрос для вас такой: "Докажите правильность формулы №5: *Q(1,M)=1, откуда ее взять? Как ее вывести? Как ее доказать?

[Max]

На сколько я понял, то так:

Q(1,M)=Q(1,1) (в силу 2-ой формулы) (т.к. М>1). Если М=1 то эта формула тем более верна.

Q(1,1)=1 (в силу 4-ой формулы)

[pinmix]

Спасибо, точняк!!!

А вот по поводу:

Если М=1 то эта формула тем более верна.

210272[/snapback]

Я не согласен, ведь М должно быть > N (по формуле 2)!!!

[Max]

Я имел ввиду следующее:

при M>1: Q(1,M)=Q(1,1)=1 в силу формул 2 и 4

при М=1: Q(1,M)=Q(1,1)=1 в силу того, что М=1 и формулы 4

Вот и всё!

[pinmix]

Ок. Извиняюсь...

Хотя, вообще задача ведь для общего случая...

Так что ни каких "если бы" быть не должно.

[Max]

Ок. Извиняюсь...

Хотя, вообще задача ведь для общего случая...

Так что ни каких "если бы" быть не должно.

210776[/snapback]

Поэтому и надо рассмотреть все случаи - ведь М может равняться и 1, и 2, и 3 и т.д.