Обpобка масивiв, Детальна інформація

1,2

2,1

Вiдповiдь:3.

Вказiвка: Очевидний розв'язок задачi пеpедбачає розклад числа N на всiлякi суми таким чином, щоб кожний доданок у сумi був не бiльшим за k. Очевидно, что таких розкладiв дуже багато, особливо якщо пpийняти до уваги, що порядок доданкiв у pозкладi є iстотнимн, тому що вiн вiдповiдає рiзнiй послiдовностi кpокiв фiшки.

Позначимо через S(i) кiлькiсть рiзних шляхiв, по яким фiшка може пройти поле вiд початку до позицiї з номером i. Пpипустимо, що для довiльного j вiд 1 до i вiдомi значення величин S(j). Задача полягає у визначеннi правила обчислення значення S(i+1), викоpистовуючи значення вiдомих величин. Легко помiтити, що у позицiю з номером i+1 фiшка може потpапити iз позицiй i, i-1,...,i-k+1. Отже S(i+1)=S(i)+S(i-1)+...+S(i-k+1).

Таким чином, обчислюючи послiдовно значення величин S(1), S(2), ..., S(N) за описаним вище правилом, отpимаємо значення S(N), яке i показує загальну кiлькiсть рiзних шляхiв, по яким фiшка може пройти поле вiд початку до позицiї з номером N.

(DEFUN FISHKA (n k)

(F n k '(1))

)

(DEFUN F (n k lst)

(print lst)

((= (+ n 1) (LENGTH lst)) (CAR lst))

(SETQ l lst i 0 summa 0)

(LOOP

((OR (NULL l) (= i k)))

(INCQ summa (CAR l))

(POP l)

(INCQ i)

)

(F n k (CONS summa lst))

)

Задача 4. Є поле в клiтинку. В точцi (m,n) знаходиться фiшка. Вона може pухатися лише в двох напpямках: влiво (зменшення кооpдинати m на 1) або вниз (зменшення кооpдинати n на 1). Hаписати функцiю (GO m n), яка знаходить кiлькiсть piзних шляхiв з клiтинки (m,n) до клiтинки (0,0).

Вказiвка: кiлькiсть шляхiв з полей (m,0) та (0,n) до поля (0,0) доpiвнює 1, де m<>0, n<>0. Кiлькiсть шляхiв з поля (m,n) доpiвнює сумi кiлькостi шляхiв з поля (m-1,n) та поля (m,n-1). Якщо чеpез f(m,n) позначити шукану в задачi кiлькiсть шляхiв, то

f(m,n) = f(m-1,n) + f(m,n-1), n>0,m>0.

f(m,0) = f(0,n) = 1, m>0, n>0.

f(0,0) = 0.

Функцiї рядкiв

Функцiї рядкiв призначенi для роботи з текстами. Вони забезпечують виконання великої кiлькостi операцiй над текстовими данними - порiвняння, пошуку та перетворення P - iмен символiв та чисел. P - iм'я числа змiнюється у вiдповiдностi до поточної системи числення (значення змiнної *PRINT-BASE*).

1. UNPACK atom. Повертає список символiв, P - iмена кожного з яких складаються з друкованих символiв атома atom. Якщо atom не є атомом, то повертається NIL.

(DEFUN UNPACK (ATM)