Автор Тема: Нужна помощь с задачкой  (Прочитано 1928 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн aikidoka

  • Новичок
  • *
  • Сообщений: 4
    • Просмотр профиля
    • E-mail
Нужна помощь с задачкой
« : 15 Ноябрь 2012, 20:16:32 »
расстояние между точками А и Б = n
лягушка прыгает не больше чем на расстояние k
Нужно узнать сколькими способами лягушка может достигнуть своей цели от точки А до точки Б.

P.S. Если кто может помочь то как можно скорее!!))

Оффлайн Harry

  • Старожил
  • ****
  • Сообщений: 441
    • Просмотр профиля
Re: Нужна помощь с задачкой
« Ответ #1 : 15 Ноябрь 2012, 21:58:36 »
Количество разбиений числа n на слагаемые, не превышающие k, удовлетворяет рекуррентной формуле:



с начальными значениями:

    P(0, 0) = 1,
    P(i, 0) = 0 для всех i > 0

(отсюда)

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Нужна помощь с задачкой
« Ответ #2 : 15 Ноябрь 2012, 22:46:43 »
условие не запрещает лягушке прыгать в стороны или вообще назад

Оффлайн Harry

  • Старожил
  • ****
  • Сообщений: 441
    • Просмотр профиля
Re: Нужна помощь с задачкой
« Ответ #3 : 15 Ноябрь 2012, 23:28:49 »
условие не запрещает лягушке прыгать в стороны или вообще назад

Ну, тогда бесконечно много...

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Нужна помощь с задачкой
« Ответ #4 : 15 Ноябрь 2012, 23:57:08 »
хорошо, пусть лягушка очень целеустремлённая и прыгает только вперёд
даже если n и k - целые числа (поверю вашей интуиции), то ограничение на длину прыжков лягушки 0 < x <= k вовсе не означает, что x тоже целое
если лягушка прыгает не дальше 1 метра, то что ей мешает прыгнуть на 1/√2 метра?

Оффлайн aikidoka

  • Новичок
  • *
  • Сообщений: 4
    • Просмотр профиля
    • E-mail
Re: Нужна помощь с задачкой
« Ответ #5 : 16 Ноябрь 2012, 04:27:09 »
лягушка прыгает только вперед, n и k целые.
насколько я понял что ее прыжок тоже должен быть полюбому на какое то целое число метров, иначе в ОДЗ не входит...

Оффлайн aikidoka

  • Новичок
  • *
  • Сообщений: 4
    • Просмотр профиля
    • E-mail
Re: Нужна помощь с задачкой
« Ответ #6 : 16 Ноябрь 2012, 04:40:23 »
Количество разбиений числа n на слагаемые, не превышающие k, удовлетворяет рекуррентной формуле:



с начальными значениями:

    P(0, 0) = 1,
    P(i, 0) = 0 для всех i > 0

(отсюда)


подачу принял, блин давно забытое старое иногда хорошее новое) только одно но, в разбиениях порядок не важен, то есть 123 и 132 это одно и то же, а вот в том, как прыгнет лягушка - напротив помоему важно, но идея мне нравится - поразмыслю, спасибо)

Оффлайн CD_Eater

  • Эксперт
  • ******
  • Сообщений: 1906
    • Просмотр профиля
Re: Нужна помощь с задачкой
« Ответ #7 : 16 Ноябрь 2012, 09:21:41 »

Оффлайн aikidoka

  • Новичок
  • *
  • Сообщений: 4
    • Просмотр профиля
    • E-mail
Re: Нужна помощь с задачкой
« Ответ #8 : 16 Ноябрь 2012, 17:30:25 »
вобщем задачу решил, кому интересно вот как:
N<0: F(K,N)=0
N=0: F(K,N)=1
N=1: F(K,N)=1
N>1: F(K,N)=2*F(K,N-1)-F(K,N-K-1)

программируем на любом языке и все ок))  рекурсия вам в помощь!))