Jump to content
СофтФорум - всё о компьютерах и не только

Задачка.


pinmix
 Share

Recommended Posts

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

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

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

есть целое число: "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, откуда ее взять? Как ее вывести? Как ее доказать?

Link to comment
Share on other sites

  • 2 weeks later...

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

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

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

Link to comment
Share on other sites

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

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

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

210272[/snapback]

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

Link to comment
Share on other sites

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

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

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

Вот и всё!

Link to comment
Share on other sites

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

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

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

Link to comment
Share on other sites

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

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

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

210776[/snapback]

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

Link to comment
Share on other sites

Guest
This topic is now closed to further replies.
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...