2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача на ДП.
Сообщение06.11.2014, 18:33 
Задача звучит так:
Обозначим через $A$ подмножество множества всех перестановок чисел
$\{ 1, 2, 3, ..., N \}$, для элементов которого истинны следующие утверждения:
Первое число $1$,
разница между любыми соседними числами не превышает $2$.

Дано: $N$
Требуется найти $|A|$

Я немножко подумал, и вот что решил:
Задача относится к семейству задач динамического программирования, значит должна быть
какая-та рекуррентная формула. Но вот найти ее не могу.
Вот решение задачи перебором для $N \le 12$
Код:
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 4
f(5) = 6
f(6) = 9
f(7) = 14
f(8) = 21
f(9) = 31
f(10) = 46
f(11) = 68
f(12) = 100

Решения надо найти для $N \le 55$.

 
 
 
 Re: Задача на ДП.
Сообщение06.11.2014, 18:37 
Аватара пользователя
A038718 же.

 
 
 
 Re: Задача на ДП.
Сообщение06.11.2014, 18:44 
Ну, тут все готовое дано, а мне именно надо освоить метод динамического программирования.
Хотя один человек сказал мне, что каждая задача дп. уникальна и что невозможно сводить
эти задачи к решенным, но я с ним несогласен, думаю можно разобрать несколько задач и
освоить технику.

 
 
 
 Re: Задача на ДП.
Сообщение06.11.2014, 19:04 
Думаю, ваш знакомый всё же ближе к истине
Конкретно, на OEIS решение дано:
Код:
Join[{a=1, b=1, c=2}, Table[d=a+c+1; a=b; b=c; c=d, {n, 100}]]

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group