Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Класика студіка
Сторінки Попередня 1 2 3 4 Наступна
Для відправлення відповіді ви повинні увійти або зареєструватися
Очевидно що якщо число не парне, то коли мінімальний крок не може бути більшим 1. Ну і так далі.
ПС: тут я щось загнався 2+3 дадут непарне число, так що крок може бути більший 1.
Припустимо що мінімальний крок 1.
Такс, а що робити з максимальним кроком.
f(n) = f(n-1)+f(n-2)+...f(n-k), де k< n
причому f(0) = 1
Як порахували вище f(k) = 2^(k-1)
Звідси f(k+1) = 2*f(k)-f(0)
f(k+2)=2^(k+1)-f(1)-f(0)==2^(k+1)+2^(2-1)
f(k+l)=2^(k+l-1)-2^(l-1)
ПС: щось я був тут намутив, поправив.
Ні.
Ще раз, як іде рішення, якщо у нас немає "правила Зеника": ми для кожної сходинки створюємо окрему змінну (тобто в результаті виходить одновимірний масив), який по одному кроку заповнюємо:
на першу сходинку можна потрапити 1 способом,
на другу - 2 (з землі і 1-ї сходинки),
на третю - 4 (з землі, 1-ї сходинки і 2-ї сходинки з її 2-ма шляхами)
і т.д.
Так, тут все зрозуміло - це навіть реалізував.
А тепер нам треба для кожної сходинки створити не одну змінну, а двовимірний масив, і заповнювати його аналогічно:
на i-у сходинку можна потрапити з землі кроком в i, це комірка A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум); можна потрапити зі сходинки 1 кроком в i-1, це комірка A[ i ][1][i-1] і т.д.
Тут вже не дуже.
Створюємо масив такий:
N=4, K=1
[
[]
[
[
[] - скількома кроками
] - з якої можна потрапити
] - масив, що містить дані про конкретну сходинку
[]
[]
]Так?
Якщо ми розглядаємо, скільки існує способів переходу зі сходинки j на сходинку i, то нам доведеться для кожної комірки сходинки j (A[j][minj][maxj], де minj та maxj - змінні циклів, якими ми ітеруємо по таблиці сходинки j) подивитися, куди потрапляє нове значення i-j - якщо воно вписується в minj...maxj, то значення додається до A[ i ][minj][maxj]; якщо не вписується - то, наприклад, якщо більше за maxj, це буде додано до A[ i ][minj][i-j].
Далі.
N=4, K=1
Треба заповнити цю трьох вимірну матрицю. A[ i ][ j ][ k ] - i - номер сходинки до якої йдемо, j - номер з якої сходинки ми в цю можемо потрапити, k - кількість сходинок, що пройдеться за крок. А ось значення цього (A[ i ][ j ][ k ] ) - це буде кількість способів дістатись до цієї сходинки (єп?)
Гм, якщо відкинути умову про К, то там взагалі проста формула виходить 2^(N-1)
Так, якщо максимальний крок дорівнює кількості сходинок.
A[ i ][ j ][ k ] - i - номер сходинки до якої йдемо, j - номер з якої сходинки ми в цю можемо потрапити, k - кількість сходинок, що пройдеться за крок
Я ж писав
A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум)
У нас є купа маршрутів із різними мінімальними і максимальними кроками. A[ i ][ j ][ k ] показує, скільки існує маршрутів до клітинки i, у яких мінімальний крок j, а максимальний - k.
Окей, а як тепер заповнювати цей масив?
Три вкладені цикли? По чому?
Чотири. Вкладених циклів буде чотири. Я вже написав, як переходити з однієї сходинки на іншу.
Припустимо що мінімальний крок 1.
Такс, а що робити з максимальним кроком.
f(n) = f(n-1)+f(n-2)+...f(n-k), де k< n
причому f(0) = 1
Як порахували вище f(k) = 2^(k-1)Звідси f(k+1) = 2*f(k)-f(0)
f(k+2)=2^(k+1)-f(1)-f(0)==2^(k+1)+2^(2-1)
f(k+l)=2^(k+l-1)-2^(l-1)
Тепер побавимось з мінімальним кроком m=2
f(n) = f(n-m)+f(n-m-1)+...f(n-m-k), де m+k< n
причому k -> нескінченності, f(0)=1, f(1)=0, f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=5
Але тут знов виникає проблема дублювання з тими шляхами, що враховані при мінімальному кроці 1.
Це класична задача динамічного програмування, і розв'язок саме такий, O(n^2) по складності і O(n) по пам'яті.
Як у 4-х вкладених циклах складність може бути O(n^2)?
Як у 4-х вкладених циклах складність може бути O(n^2)?
Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.
Гм на цю задачу можна ще дивитись я на таку де треба знайти всі можливі суми які дають число n
наприклад n =4
1+1+1+1
1+1+2 1+2+1 2+1+1
1+3 3+1
2+2
4
n=5
1+1+1+1+1
1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+1
1+2+2 2+1+2 2+2+1
1+1+3 1+3+1 3+1+1
1+4 4+1
2+3 3+2
5
Так, це вона і є - за умови, що зміна порядку доданків дає новий варіант.
Vo_Vik написав:Як у 4-х вкладених циклах складність може бути O(n^2)?
Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.
А нащо без правила Зеника n^2, якщо там одна формула?
koala написав:Vo_Vik написав:Як у 4-х вкладених циклах складність може бути O(n^2)?
Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.
А нащо без правила Зеника n^2, якщо там одна формула?
Я абсолютно певен, що із правилом Зеника теж можна вивести одну формулу.
До речі, я так і не зрозумів, яку формулу для класичної задачі ви вивели, можете її ще раз виписати?
До речі, я так і не зрозумів, яку формулу для класичної задачі ви вивели, можете її ще раз виписати?
Якщо нема обмеження по максимальній довжині кроку f(n) = 2^(n-1)
Якщо є обмеження по максимальній довжині k, то f(n,k) = 2^(n-1)-2^(k-1)
Давайте розглянемо випадок n=5, k=3. Мій спосіб:
0. 1
1. 1
2. 2
3. 4
4. 7
5. 13
Ваша формула:
2^4-2^2=12
Перебір:
1.1+1+1+1+1
2.2+1+1+1
3.1+2+1+1
4.1+1+2+1
5.1+1+1+2
6.2+2+1
7.2+1+2
8.1+2+2
9.3+1+1
10.1+3+1
11.1+1+3
12.3+2
13.2+3
Щось не спрацювало.
До речі, при k=2 там числа Фібоначчі виходять, і формула значно складніша.
Хм
Та я от щось відчуваю, що щось намутив, але не можу зрозуміти що.
Там походу f(0) має бути 0, а не одиниця, і відповідно для n<k треба приплюсовувати одиничку до суми.
Тобто f(1) = 1
f(2) = f(1)+1 = 1+1 = 2
f(3) = f(2)+f(1)+1 = f(1)+1+f(1)+1 =1+1+1+1=4
f(4) = f(3)+f(2)+f(1) = 7 = f(2)+f(1)+1+f(2)+f(1) = f(1)+1+f(1)+1+f(1)+1+f(1) = 4*f(1)+3
f(5) = f(4)+f(3)+f(2) = 13 = 4*f(1)+3+2*f(1)+2+f(1)+1 = 7*f(1)+6
f(6) = f(5)+f(4)+f(3) = 24 = 7*f(1)+6+4*f(1)+3+2*f(1)+2 = 13*f(1)+11
f(7) = 44 = 13*f(1)+11+7*f(1)+6+4*f(1)+3 = 24*f(1)+20
Нє, нема там формули, це якісь потрійні числа Фірбоначі.
http://oeis.org/wiki/N-bonacci_numbers
https://en.wikipedia.org/wiki/Generaliz … _sequences
The kth element of the n-nacci sequence is given by
where ⌊ · ⌉ denotes the nearest integer function and r is the n-nacci constant, which is the root of x + x^−n = 2 nearest to 2.
