21 Востаннє редагувалося Vo_Vik (29.05.2018 16:22:37)

Re: Класика студіка

Очевидно що якщо число не парне, то коли мінімальний крок не може бути більшим 1. Ну і так далі.

ПС: тут я щось загнався 2+3 дадут непарне число, так що крок може бути більший 1.

22 Востаннє редагувалося Vo_Vik (29.05.2018 17:12:55)

Re: Класика студіка

Припустимо що мінімальний крок 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)

ПС: щось я був тут намутив, поправив.

23

Re: Класика студіка

koala написав:

Ні.
Ще раз, як іде рішення, якщо у нас немає "правила Зеника": ми для кожної сходинки створюємо окрему змінну (тобто в результаті виходить одновимірний масив), який по одному кроку заповнюємо:
на першу сходинку можна потрапити 1 способом,
на другу - 2 (з землі і 1-ї сходинки), 
на третю - 4 (з землі, 1-ї сходинки і 2-ї сходинки з її 2-ма шляхами)
і т.д.

Так, тут все зрозуміло - це навіть реалізував.

koala написав:

А тепер нам треба для кожної сходинки створити не одну змінну, а двовимірний масив, і заповнювати його аналогічно:
на i-у сходинку можна потрапити з землі кроком в i, це комірка A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум); можна потрапити зі сходинки 1 кроком в i-1, це комірка A[ i ][1][i-1] і т.д.

Тут вже не дуже.

Створюємо масив такий:

N=4, K=1

[
    []
    [ 
        [
           [] - скількома кроками
        ] - з якої можна потрапити

    ] - масив, що містить дані про конкретну сходинку 
    []
    []
]

Так?

koala написав:

Якщо ми розглядаємо, скільки існує способів переходу зі сходинки 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 ] ) - це буде кількість способів дістатись до цієї сходинки (єп?)

24

Re: Класика студіка

Vo_Vik написав:

Гм, якщо відкинути умову про К, то там взагалі проста формула виходить 2^(N-1)

Так, якщо максимальний крок дорівнює кількості сходинок.

25

Re: Класика студіка

Q-bart написав:

A[ i ][ j ][ k ] - i - номер сходинки до якої йдемо, j - номер з якої сходинки ми в цю можемо потрапити, k - кількість сходинок, що пройдеться за крок

Я ж писав

koala написав:

A[ i ][ i ][ i ] (індекси: номер сходинки, мінімум, максимум)

У нас є купа маршрутів із різними мінімальними і максимальними кроками. A[ i ][ j ][ k ] показує, скільки існує маршрутів до клітинки i, у яких мінімальний крок j, а максимальний - k.

Подякували: Q-bart1

26

Re: Класика студіка

Окей, а як тепер заповнювати цей масив?

Три вкладені цикли? По чому?

27

Re: Класика студіка

Чотири. Вкладених циклів буде чотири. Я вже написав, як переходити з однієї сходинки на іншу.

28 Востаннє редагувалося Vo_Vik (29.05.2018 17:15:21)

Re: Класика студіка

Vo_Vik написав:

Припустимо що мінімальний крок 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.

29

Re: Класика студіка

Це класична задача динамічного програмування, і розв'язок саме такий, O(n^2) по складності і O(n) по пам'яті.

30

Re: Класика студіка

Як у 4-х вкладених циклах складність може бути O(n^2)?

Подякували: Q-bart1

31

Re: Класика студіка

Vo_Vik написав:

Як у 4-х вкладених циклах складність може бути O(n^2)?

Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.

32

Re: Класика студіка

Гм на цю задачу можна ще дивитись я на таку де треба знайти всі можливі суми які дають число 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

33

Re: Класика студіка

Так, це вона і є - за умови, що зміна порядку доданків дає новий варіант.

34

Re: Класика студіка

koala написав:
Vo_Vik написав:

Як у 4-х вкладених циклах складність може бути O(n^2)?

Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.

А нащо без правила Зеника n^2, якщо там одна формула?

35

Re: Класика студіка

Vo_Vik написав:
koala написав:
Vo_Vik написав:

Як у 4-х вкладених циклах складність може бути O(n^2)?

Класична задача без правила Зеника, там O(n^2). А з правилом - інша, там O(n^4), я ж вище писав.

А нащо без правила Зеника n^2, якщо там одна формула?

Я абсолютно певен, що із правилом Зеника теж можна вивести одну формулу.

36

Re: Класика студіка

До речі, я так і не зрозумів, яку формулу для класичної задачі ви вивели, можете її ще раз виписати?

37

Re: Класика студіка

koala написав:

До речі, я так і не зрозумів, яку формулу для класичної задачі ви вивели, можете її ще раз виписати?

Якщо нема обмеження по максимальній довжині кроку f(n) = 2^(n-1)
Якщо є обмеження по максимальній довжині k, то f(n,k) = 2^(n-1)-2^(k-1)

38 Востаннє редагувалося koala (29.05.2018 20:45:41)

Re: Класика студіка

Давайте розглянемо випадок 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 там числа Фібоначчі виходять, і формула значно складніша.

39

Re: Класика студіка

Хм
Та я от щось відчуваю, що щось намутив, але не можу зрозуміти що.
Там походу 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

Нє, нема там формули, це якісь потрійні числа Фірбоначі.

40

Re: Класика студіка

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
https://wikimedia.org/api/rest_v1/media/math/render/svg/17f92a91dc81fead50687dacb6a59bd437ff71b1
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.

Подякували: Vo_Vik, leofun01, Arete3