1

(6 відповідей, залишених у Кошик для сміття)

Ну заблокувати заблокували, а видаляти повідомлення хто буде?

2

(24 відповідей, залишених у Інше)

Їм не менше треба вас випустити ніж вам здати диплом.

3

(8 699 відповідей, залишених у Інше)

/KIT\ написав:

Hanter вже давно як Адріян

Значить я давно не заходив в теми де він пише.

4

(8 699 відповідей, залишених у Інше)

І кого це в Адріана перейменували?

ПС: а всьо, знайшов - Хантера.

5

(8 699 відповідей, залишених у Інше)

У мене таке було на окремих сайтах, Коли на роутері глючило одночасне включення IP і IPv6. Воно тоді бідолашка не знало по якому каналу бігати до сайтів які і те і те підтримують.

6

(1 698 відповідей, залишених у Розваги та гумор)

Покажіь лопату. Бо щось в упор.

Q-bart написав:

Та ну? Серйозно? А reddit і quora - це якась лажа

Ще скажіть, що думали, що цей форум буде прямим конкерентом стаковерфлов.

50 Активних юзерів, це дуже активний форум. В певній мірі навіть надто активний.

9

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

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

10

(59 відповідей, залишених у Алгоритми та структури даних, технології)

koala написав:

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

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

11

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

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

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

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

12

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

13

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

14

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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.

15

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

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

16

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

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

17

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

18

(59 відповідей, залишених у Алгоритми та структури даних, технології)

Тобто розв’язуємо примаючи умову, що треба опинитись на сходинці N.

19

(59 відповідей, залишених у Алгоритми та структури даних, технології)

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

Тільки треба буде прогнати це для різних мінімальних кроків, бо в нас є К.

Так це ж найцікавіше.

Vo_Vik написав:

чи можуть кроки закінчуватись в N+m чи обо’язково останній крок має закінчуватись в N?

В умові написано "скiлькома способами можна подолати N сходинок", а не "щонайменше N сходинок".

Ну так там просто ще один цикл. 0<=i<=N
min  = i, max = i+K
і в тих сумах не враховувати ті позиції які виходять за мінмакс.

Складність алгоритму десь O^3 виходить.
От чи можна за менший час, оце питання.

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

20

(59 відповідей, залишених у Алгоритми та структури даних, технології)

Треба починати з кінця.
З останньої сходинки можна зробити тільки один можливий крок.
Записуємо там 1
З перед останньої можна сходити на останню або в кінець. 1*1+1 = 2
З n-2 -> 1*2+1*1+1 = 4
Тільки треба буде прогнати це для різних мінімальних кроків, бо в нас є К.

Доречі питання, чи можуть кроки закінчуватись в N+m чи обо’язково останній крок має закінчуватись в N?