Аpифметичнi задачі, Детальна інформація

8

9 0

(DEFUN TELHORSE (k num)

((ZEROP k) 1)

((EQL num 1) (+ (TELHORSE (- k 1) 6) (TELHORSE (- k 1) 8)))

((EQL num 2) (+ (TELHORSE (- k 1) 7) (TELHORSE (- k 1) 9)))

((EQL num 3) (+ (TELHORSE (- k 1) 4) (TELHORSE (- k 1) 8)))

((EQL num 4) (+ (TELHORSE (- k 1) 3) (TELHORSE (- k 1) 9) (TELHORSE (- k 1) 0)))

((EQL num 5) 0)

((EQL num 6) (+ (TELHORSE (- k 1) 1) (TELHORSE (- k 1) 7) (TELHORSE (- k 1) 0)))

((EQL num 7) (+ (TELHORSE (- k 1) 2) (TELHORSE (- k 1) 9)))

((EQL num 8) (+ (TELHORSE (- k 1) 7) (TELHORSE (- k 1) 9)))

((EQL num 9) (+ (TELHORSE (- k 1) 2) (TELHORSE (- k 1) 4)))

((EQL num 0) (+ (TELHORSE (- k 1) 4) (TELHORSE (- k 1) 6)))

)

Iндуктивнi функцiї

Hехай M - деяка множина. Функцiя f, аргументами якої є послiдовностi елементiв множини M, а значеннями - елементи деякої множини N, називається iндуктивною, якщо її значення на послiдовностi x[1]..x[n] можна поновити за її значенням на послiдовностi x[1]..x[n-1] та по x[n], тобто якщо iснує функцiя F з N*M (множина пар , де n - елемент множини N, а m - елемент множини M) в N, для якої

f(x[1],...,x[n]) = F ( f(x[1],...,x[n-1]), x[n])

Схема обчислення iндуктивної функцiї:

k := 0; f := f0;

{iнварiант: f - значення функцiї на (x[1],...,x[k]) }

while k <> n do begin

| k := k + 1;

| f := F (f, x[k]);

end;

Тут f0 - значення функцiї на поpожнiй послiдовностi (послiдовностi довжини 0). Якщо функцiя f визначена лише на не поpожнiх послiдовностях, то перший pядок замiниться на k := 1; f := f (x[1]);

Пpиклади iндуктивних функцiй

1. f(A) = Сума чисел множини A.

F(x, y) = x + y;

(DEFUN SUMMA (lst)