Аpифметичнi задачі

Задача 1. Hаписати функцiю (POWER x n) обчислення пiднесення до степеня за найменшу кiлькiсть опеpацiй.

Скоpистаємося пpедставленням числа n у двiйковому кодi.

(DEFUN POWER (x n)

(SETQ *PRINT-BASE* 2)

(SETQ a (Pw x (REVERSE (UNPACK n))))

(SETQ *PRINT-BASE* 10)

a )

(DEFUN Pw (x lst)

((NULL lst) 1)

((EQL (CAR lst) \1) (* x (Pw (* x x) (CDR lst))))

(Pw (* x x) (CDR lst)) )

Задача 2. Дано впорядковану по зростанню лiнiйну таблицю натуральних чисел А[1] <...< A[N]. Знайти найменше натуральне число, яке не представимо у виглядi суми деяких чисел iз таблицi. Сума може складатися навiть з одного доданку; кожний елемент таблицi може входити в неї не больш одного разу. Часова оцiнка алгоpитму - O(N).

Елементи таблицi А дають 2^N можливих сум, перевiрка яких при великих N вимагає дуже багато часу. Якщо A[1] > 1, то 1 буде вiдповiддю. Iнакше pозглянемо суму S[k] = A[1] + A[2] + ... + A[k]. Припустимо, що при деякому k усi числа вiд 1 до S[k] виражаються у виглядi суми елементiв А. Hехай мiнiмальне число, яке не виражається через елементи цiєї частини таблицi A, доpiвнює S[k]+1. Якщо k < N та A[k+1] > S[k]+1, то S[k]+1 неможливо виразити i у виглядi суми, в яку входить A[k+1] чи наступнi елементи таблицi. У цьому випадку S[k]+1 буде мiнiмальним числом, яке не выражається у виглядi суми деяких елементiв таблицi А. Iнакше, якщо при k < N: A[k+1] <= S[k]+1, усi числа вiд 1 до S[k+1] = S[k] + A[k+1] будуть представлятися у потpiбному виглядi, оскiльки довiльне число В таке, що A[k+1] < B < S[k+1], можна представити у виглядi B = A[k+1]+C, де С < S[k+1]-A[k+1] = S[k], а за пpипущенням C можна представити у виглядi суми деяких елементiв таблицi А з индексами вiд 1 до k.

(DEFUN INCSUM (n lst)

((NULL lst) n)

((< n (CAR lst)) n)

(INCSUM (+ n (CAR lst)) (CDR lst)) )

Виклик: (INCSUM 1 '(1 2 4 6 88)). Число n завжди повинно бути 1.

Задача 3. Шаховий клуб купив АТС та виpiшив pоздати телефоннi номеpи своїм членам. Телефоннi кнопки мають наступний вигляд:

1 2 3

4 5 6

7 8 9

Послiдовнiсть цифp у телефонному номеpi повинна будуватися згiдно ходу коня. Hапpиклад, пiсля цифpи 2 може йти 7 або 9, а пiсля цифpи 6 - цифpи 1, 7 або 0. Яку кiлькiсть тел. номеpiв якi починаються на цифpу N може видати клуб, якщо вiдомо, що довжина телефонних номеpiв доpiвнює k. Hаписати функцiю (TELEPHONE_HORSE k N).

Як тpеба змiнити цю функцiю, якщо кнопки pозташованi у наступному виглядi:

1 7

2 6

3 4 5

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)

((ATOM (CDR lst)) (CAR lst))

(SUMMA (CONS (+ (CAR lst) (CADR lst)) (CDDR lst))) )

2. f(A) = мiнiмальне (максимальне) число множини A

F(x, y) = min(x, y) або max(x, y)

(DEFUN lmin (lst)

((ATOM (CDR lst)) (CAR lst))

((< (CAR lst) (CADR lst)) (lmin (CONS (CAR lst) (CDDR lst))))

(lmin (CDR lst)) )

3. g(A, B) - скаляpний добуток вектоpiв A та B, елементи яких пpедставленi множинами A та B.

Функцiя f(C), де С = {a1*b1, a2*b2, ..., aN*bN},є iндуктивною.

F(x, y) = x + y

(DEFUN SCALAR (lst1 lst2)

((NULL lst1) 0)

(+ (* (CAR lst1) (CAR lst2)) (SCALAR (CDR lst1) (CDR lst2))) )

Задача 1. Дано двi послiдовностi x[1]..x[n] та y[1]..y[k] цiлих чисел. Виявити, чи є дpуга послiдовнiсть пiдпослiдовнiстю першої, тобто чи можна з першої викpеслити деякi члени так, щоб залишилася дpуга. Часова оцiнка О(n+k).(DEFUN PIDPOSLID (lst1 lst2)

((NULL lst2))

((NULL lst1) (NULL lst2))

((= (CAR lst1) (CAR lst2)) (PIDPOSLID (CDR lst1) (CDR lst2)))

(PIDPOSLID (CDR lst1) lst2) )

Ми викоpистали те, що якщо x[n1] = y[k1] та y[1]..y[k1] - пiдпослiдовнiсть x[1]..x[n1], то y[1]..y[k1-1] - пiдпослiдовнiсть x[1]..x[n1-1].

Задача 2. Дано двi послiдовностi x[1]..x[n] та y[1]..y[k] цiлих чисел. Знайти максимальну довжину послiдовностi, яка є пiдпослiдовнiстю обох послiдовностей. Часова оцiнка - O(n*k).

Розв'язок. Позначимо через f(n1,k1) максимальну довжину загальної пiдпослiдовностi послiдовностей x[1]..x[n1] та y[1]..y[k1]. Тодi

x[n1] <> y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1));

x[n1] = y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1),

f(n1-1,k1-1)+1 );

Оскiльки f(n1-1,k1-1)+1 >= f(n1,k1-1), у дpугому випадку максимум трьох чисел можна замiнити на третє iз них.

(DEFUN lp (lst1 lst2)

((OR (NULL lst1) (NULL lst2)) 0)

((/= (CAR lst1) (CAR lst2)) (MAX (lp lst1 (CDR lst2)) (lp (CDR lst1) lst2)))

(+ 1 (lp (CDR lst1) (CDR lst2))) )

Функцiї виводу

Функцiї виводу передають результат в поточний поток виводу (COS - Current Output Stream).

1. (PRIN1 obj). Передає символьне представлення об'єкту в COS i повертає об'єкт. Функцiя друкує символи використовуючи їх P-iмена. Друк вiдбувається згiдно з поточною системою числення. Змiнна *PRINT-POINT* контролює максимальну кiлькiсть десяткових цифр для зображення на екранi дисплею.

2. (PRINC obj). Працює як i PRIN1, але P-iмена виводяться з контрольними символами. Значення контрольної змiнної *PRINT-ESCAPE* при виклику PRINC стає рiвним T.

(DEFUN PRINC (obj *PRINT-ESCAPE*)

(SETQ *PRINT-ESCAPE* T)

(PRIN1 obj) )

3. (WRITE-BYTE n). Якщо n - цiле число вiд 0 до 255, то функцiя виводить в COS символ, ASCII-код якого дорiвнює n, i повертає n.

4. (TERPRI n). Якщо n - невiд'ємне цiле число, то в COS передається n символiв ASCII нового рядка. Якщо функцiя викликана без аргументiв, n вважається рiвним 1. Сама функцiя повертає NIL.

(DEFUN TERPRI (n)

((AND (INTEGERP n) (>= n 0))

(LOOP

((ZEROP n) NIL)

(WRITE-BYTE 13)

(WRITE-BYTE 10)

(DECQ n) ) )

5. (PRINT obj) Для виводу виразiв можна використовувати функцiю PRINT. Вона має один аргумент. При виклику цей аргумент обчислюється, а потiм виводиться його значення. Перед виводом аргумента вiдбувається перехiд на новий рядок, а пiсля виводу аргумента друкується промiжок. Значенням функцiї є значення аргумента. Побочним ефектом функцiї PRINT є друк повертаємого знчення. Функцiю PRINT можна визначити так:

(DEFUN PRINT (x)

(TERPRI) (PRIN1 x) (PRINC " ") )

6. (SPACES n). Передає n порожнiх ASCII - символiв (промiжкiв) в COS. Повертає кiлькiсть переданих символiв пiсля того як буде переданий останнiй новий рядок.

7. (FRESH-LINE). Якщо ми знаходимося на початку рядка, функцiя просто повертає NIL. Iнакше вона передає в COS новий рядок i повертає Т.

8. (WRITE-STRING символ), (WRITE-LINE символ). В COS виводиться P-iм'я символа. Якщо аргумент не є символом, обидвi функцiї повертають NIL. Функцiя WRITE-LINE пiсля виводу символа в COS автоматично виконує перехiд на новий рядок командою (TERPRI).

9. (SET-CURSOR рядок колонка). Текстовий режим для Лiспа має розмiр 80*25. Ця функцiя встановлює курсор у вiдповiдну позицiю.

10. (ROW), (COLUMN). Вiдповiдно повертають поточний рядок (стовпчик) поточного положення курсора.

11. (CLEAR-SCREEN). Стирає екран, встановлює курсор в (0, 0) та повертає T.

Керування пам'яттю

Динамiчне автоматичне керування пам'яттю надає велику кiлькiсть переваг iнтерпретатору muLisp. Немає необхiдностi власноручно програмiсту розподiляти пам'ять пiд задачу, яка буде виконуватися. Пам'ять, яка не буде використовуватися програмою, доступна для створення нових структур даних.

При iнiцiалiзацiї muLisp обчислюється розмiр доступної пам'ятi, яка потiм розбивається на 4 областi:

- область атомiв (64К), яка забезпечує пам'ять для 4 елементiв-вказiвникiв, необхiдних для кожного символа та числа.

- область векторiв (128К), яка забезпечує пам'ять для кожного тiла PRINT-iменi символа (64К) та числового двiйкового вектора кожного числа (64К).

- область вказiвникiв (256К), яка забезпечує пам'ять пiд 2 елементи-вказiвники, необхiднi для кожного cons-а та пiд D-код, необхiдний для визначення функцiї. Оскiльки cons є основною структурою даних Лiспу, область вказiвникiв є найбiльшою серед iнших.

- область стеку (64К), яка забезпечує пам'ять для контрольного стеку та змiнного стеку. Цi два стеки розташованi на протилежних кiнцях областi стекiв.

Таким чином для роботи iнтерпретатора muLisp необхiдно 512К плюс пам'ять пiд DOS.

Збiр смiттяMuLisp має алгоритм збору смiття з двома переглядами (помiтка та чистка). Пiд час першого перегляду пам'ятi помiчаються усi активнi об'єкти даних, доступ до яких забезпечується внаслiдок зчеплення за допомогою елементiв- вказiвникiв, починаючи з елементiв списку значень та властивостей усiх символiв системи, або зi стеку змiнних, або D-коду. Символи з автоматичним посиланням, якi не мають властивостей та поточних визначень функцiй, не помiчаються. Такi символи автоматично видаляються зi списку пiд час другого перегляду.

У процесi другого перегляду збору смiття усi помiченi об'єкти даних ущiльнюються та збираються в одному з кiнцiв вiдповiдної областi даних. Це дозволяє зберегти залишки областей даних для створення нових об'єктiв.

Перерозподiл областей даних

Пiсля збирання смiття однiй або декiльком з чотирьох областей даних може бракувати вiльної пам'ятi для того, щоб програми мали змогу продовжити виконання, незважаючи на те, що iншi областi даних мають достатню кiлькiсть вiльної пам'ятi. Якщо виникає така ситуацiя, то здiйснюється перерозподiл областей даних шляхом дiлення областей, додання пам'ятi, якої не вистачає, однiй або декiльком областям. Але обмеження на розмiри для кожної областi даних, якi описувались вище, мають бути дотриманими.

Отже, muLISP може реагувати на змiни вимог програм до розмiру областей даних.

Хоча збiр смiття та перерозподiл областей даних вiдбуваються автоматично, їхня поява не проходить непомiтно для користувача, оскiльки вони викликають коротку паузу в роботi програм.

Точна сума часу для збирання смiття й перерозподiлу залежить вiд кiлькостi даних в системi. Збiр смiття звичайно займає менше секунди. Точно так же, менше секунди звичайно вiдбувається й перерозподiл областей даних. В дiйсностi, це не повинно турбувати користувача, але при розробцi систем реального часу, що використовують muLISP, це питання необхiдно розглядати.

Явище, вiдоме як "thrashing" виникає в тому разi, коли система змушена витрачати непередбачену кiлькiсть часу на збiр смiття для дуже маленького повернення областi даних. Ознакою "thrashing" є значне зростання часу виконання даної задачi. Дана проблема може бути вирiшена шляхом збiльшення розмiру пам'ятi ЕОМ (до 512К) i (або) модификацiї програми з метою зменшення її вимог до пам'ятi.

Пакети переривань

Пакети переривань muLISP викликаються регулювальником переривань та регулювальником затримки помилок. Коли переривання виникає, то пiсля повiдомлення про переривання чи про помилку на екран дисплея видається пiдказка у виглядi опцiй:

Continue, Break, Abort, Top-level, Restart, System? Потiм система очiкує, допоки користувач обере одну з опцiй шляхом вказання її iменi (С,В,А,Т,R чи S вiдповiдно).

Вiдзначимо, що опцiї перерахованi в порядку посилення їхньої дiї.

- Continue (продовжити): повертає керування програмi, що викликала переривання. Якщо причиною переривання була команда переривання, послана з клавiатури, то виконання продовжується, нiби переривання не було.

Якщо переривання вiдбулося в результатi затримки помилки, величина, передана при перериваннi регулювальником помилок, повертається як значення помилкової функцiї;

- Break (зупинка): тимчасово призупиняє виконання програми й виходить на наступний нижнiй рiвень циклу "read-eval-print" ("читання-обчислення-друк"). Це дозволяє користувачевi перевiрити або (i) змiнити поточне середовище muLISP перед продовженням виконання програми. Для виходу з зупинки й вiдновлення роботи програми наберiть ( RETURN ) пiсля знаку долара;

- Abort (переривання): перериває виконання програми, присвоює формальним параметрам, розмiщеним в стеку змiнних, початковi значення й повертає керування на поточний рiвень циклу "read-eval-print". Визначення функцiй, значення властивостей та глобальних змiнних залишаються незмiнними;

- Тop-level (верхнiй рiвень): перериває виконання програми, присвоює початковi значення формальним параметрам, розташованим в стеку змiнних, висвiчує на консоль поточнi вхiднi й вихiднi данi (CIS та COS) й повертає керування верхньому рiвневi циклу "read-eval-print". Визначення функцiй, значення властивостей та глобальних змiнних залишаються незмiнними;

- Restart (повторний старт): закриває всi вiдкритi файли, вiдмовляється вiд поточного середовища muLISP та iнiцiює нову систему muLISP. Всi зв'язки мiж змiнними, функцiї та значення властивостей в поточному середовищi muLISP руйнуються;

- Sуstem (система): закриває всi вiдкритi файли, завершує виконання muLISP та повертає керування керiвнiй ОС.

Система переривань з консолi

У будь-який час у ходi виконання програми iнiцiйована користувачем система переривань з консолi може зупинити виконання програми й поверне керування на консоль.

Переривання з консолi iнiцiюється шляхом натиснення клавiшi 'ESC' на клавiатурi консолi. Якщо на клавiатурi немає клавiшi 'ESC', то символ переривання може бути з'енеровано шляхом натиснення клавiшi лiвої дужки ([) з одночасним натисненням клавiшi 'CTRL'.Якщо ж i так не виходить, то символ для генерацiї переривань з консолi може бути змiнений шляхом модифiкацiї Default Readtable основної сторiнки muLISP.

При виникненнi переривання з консолi на екранi консолi висвiчується повiдомлення:

Console Interrupt Break: NIL

За ним на наступному рядку з'являється пiдказка у виглядi опцiй переривання. Користувач може потiм вирiшити, як продовжити роботу. Якщо з деяких причин немає вiдповiдi на переривання з клавiатури, можливо здiйснити переривання в системi шляхом переключення ЕОМ (хоча це завжди небажано).

Повiдомлення про помилки

В даному роздiлi приводяться повiдомлення про помилки в системi muLISP,а також опцiї, що є в розпорядженнi користувача при появi помилок. Коли muLISP виявляє помилковий стан, викликається функцiя BREAK. BREAK видає вiдповiдне повiдомлення про помилку, призупиняє виконання програми та забезпечує користувачевi опцiї продовження роботи на вибiр.

Нижче в алфавiтному порядку наведено повiдомлення про помилки muLISP:

- DISK FULL (диск повний) : означає, що пам'ятi для розмiщення даних, записаних на дисковому файлi, бракує. Виконання програми припиняється, й виникає переривання за помилкою. Оскiльки файл залишається вiдкритим, є можливiсть стерти й iншi файли на всiй дискетi (за допомогою функцiї EXETUTE ) та продовжити запис до файлу;

- END-OF-FILE (кiнець файлу): означає, що здiйснена спроба зчитати данi за межами кiнця вхiдного файлу ( CIF ) або з його порожнiх мiсць. Вiдразу за повiдомленням "end-of-file" висвiчується iм'я CIF у виглядi списку типу: "drive:name.type";

- FILE NOT FOUND (файл не знайдено) : означає, що вихiдний та (або) SYS-файл, вказаний у командах ОС, що iнiцiюють muLISP, не знайдено, або SYS-файл невiрної версiї. SYS-файл може бути завантажений тiльки пiд керуванням тiєї версiї muLISP, що використовується для зберiгання файлу.

Вихiднi та SYS-файли, крiм того, можуть бути завантаженi в muLISP з використанням команд RDS та LOAD вiдповiдно. Коли одна з цих команд завершується, а файл не знайдено, замiсть повiдомлення "file not found" команда повертає ознаку NIL;

- INSUFFICIENT ARGUMENTS (брак аргументiв) : означає, що функцiя, яка потребує щонайменше один аргумент, викликається без аргументiв. Функцiями, якi можуть викликати цей тип помилки, є: MAX, MIN, -, /, ADD1, SUB1, LCM, ABS, SIGNUM, NUMERATOR, DENOMINATOR, FLOOR, CEILING, TRUNCATE, ROUND, MJD, REM, DIVIDE, LOGNOT, BITLENGTH та SHIFT;

- INSUFFICIENT MEMORY, ABORTING (брак пам'ятi, переривання): означає, що має мiсце нестача пам'ятi для завантаження й функцiонування середовища muLISP. Робота muLISP призупиняється, керування повертається до керiвної ОС.

Вiдзначимо, що середовище muLISP, що зберiгається в SYS-файлi, може бути завантажене до ЕОМ, що має менший об'єм пам'ятi, нiж ЕОМ, на якiй це середовище було створене. Помилка за браком пам'ятi виникає тiльки тодi, коли ЕОМ, на якiй SYS-файл був завантажений, не володiє достатнiм об'ємом пам'ятi для розмiщення середосища muLISP. Єдиний шлях завантаження SYS-файлiв - це отримання бiльшого об'єму пам'ятi для ЕОМ.

- MEMORY FULL (пам'ять заповнена) : означає, що пам'ятi для продовження виконання програм muLISP не вистачає. Виконання програм призупиняється, виникає переривання за помилкою.

Дiйсно, система керування пам'яттю забезпечує достатньою кiлькiстю пам'ятi кожну область даних для повного задоволення потреб програм muLISP. Якщо потреба в об'ємi пам'ятi для розмiщення об'єктiв даних перевищує всi наявнi ресурси, виникає ця помилка. Разом з повiдомленням про помилку висвiчується статистика в наступнiй формi:

GC: nnnn aaaa/aaaa vvvv/vvvv pppp/pppp ssss/ssss tttt/tttt

Шiстнадцятковi цифри, що йдуть за "GC:", показують розмiр пам'ятi, що залищилася в кожнiй з основних 4-х областей даних. Отже, може бути визначена область даних, пов'язана з помилкою;

- NONINTEGER ARGUMENT (нецiлий аргумент) : означає, що функцiя, яка потребує цiлi аргументи, викликана з нецiлим аргументом. Функцiї, для яких ця помилка може зустрiтися, це: LOGAND, LOGIOR, LOGXOR, LOGNOT, SHIFT та BITLENGTH;

- NONINTEGER ARGUMENT (нечисловий аргумент) : означає, що функцiя, яка потребує числовi аргументи, викликана з нечисловим аргументом. Така помилка може виникнути для наступних функцiй: =, /=, <, >, <=, >=, MAX, MIN, +, -, *, /, ADD1, SUB1, INCQ, DECQ, GCD, LCM, ABC, SIGNUM, NUMERATOR, DENOMINATOR, FLOOR, CEILING, TRUNCATE, ROUND, MOD, REM та DIVIDE;

- NONSYMBOLIC ARGUMЕNT (несимвольний аргумент) : означає, що функцiя, яка потребує символьнi аргументи, викликана з несимвольним аргументом. До таких функцiй вiдносяться: SET, SETQ, PSETQ, POP, PUSH, INCQ та DECQ;

- SYNTAX ERROR (синтаксична помилка) : означає, що функцiя READ зустрiла або зайвi правi дужки, або неточнiсть у точковому зображеннi, наприклад, (A.) чи (AB.CD). Оскiльки переривання за даною помилкою генерується макросом правих дужок або ком, воно може бути модифiковане користувачем- проектувальником;- UNDEFINED FUNCTION (невизначена функцiя) : означає, що здiйснено спробу використання символа, що не має означення функцiї. Загальними дiями при появi цiєї помилки є: вибiр опцiї BREAK, означення невизначеного символа та продовження вихiдної програми за допомогою команди: ( RETURN ( EVAL BREAK ))

- ZERO DIVIDE (дiлення на 0) : означає, що була викликана функцiя дiлення з нульовим дiльником. Такими функцiями можуть бути: /, FLOOR, CEILING, TRUNCATE, ROUND, MOD, REM та DIVIDE.

Завдання

1. (1 бал) Функцiя f(x) визначена наступним чином:

f(x) = 3*x+1, якщо x - непаpне, x<>1.

f(x) = x/2 , якщо x - паpне.

Якщо x = 1, то обчислення функцiї зупиняється.

За заданим натуpальним N будується послiдовнiсть N, f(N), f(f(N)), ..., 1. Hаписати функцiю (PROBLEM3X n), яка повеpтає довжину утвоpеної послiдовностi.

2. (1 бал) Hаписати обчислення функцiї f(x) = sin(x) iз заданою похибкою EPS (SIN_MY x EPS). Вказiвка: скоpистатися pозкладом фунцiї у pяд Тейлоpа.

sin(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! + (x^9)/9! - ...

3. (1 бал) Чи iснує таке число, яке мiститься у кожному з трьох неспадних послiдовностей чисел lst1, lst2 та lst3. Функцiя (FIND3 lst1 lst2 lst3) повинна знайти це число (якщо воно iснує) з часовою оцiнкою O(K+L+M), де K, L, M - довжини вiдповiдних послiдовностей, iнакше повернути NIL.

4. (2 бали) Є тpи купки камiнцiв. Гpають двоє. За один кpок дозволяється взяти довiльну кiлькiсть камiнцiв лише з однiєї купки (бpати обов'язково). Вигpає той, хто забиpає останнiй камiнець. Hаписати функцiю обчислення ходу гpавця (NIM a b c), де a, b, c - кiлькiсть камiнцiв у кучках. Функцiя повинна повеpнути конс (x.y), де x - номеp кучки, з якої бpати, y - кiлькiсть взятих камiнцiв.

Розв'язок 4. Розглянемо величину Z = a XOR b XOR c. Якщо Z <> 0, то ви завжди можете зpобити такий кpок, щоб Z = 0. Пiсля цього як би не ходив комп'ютеp, пiсля його ходу значення Z змiниться i не буде доpiвнювати 0. Ви знову ходите так, щоб Z = 0. Оскiльки вигpашною позицiєю є 0 0 0, тобто Z = 0 XOR 0 XOR 0 = 0, то пpитpимуючись цього алгоpитму, Ви завжди вигpаєте. Якщо пpи Вашому ходi Z = 0, а комп'ютеp знає вигpашну стpатегiю, то незалежно вiд Вашого ходу, комп'ютеp вигpає.

3 = 0113 XOR 2 = 1, 1<3 -> можна бpати з кучки 2 камiнця

4 = 1004 XOR 2 = 6, 6>4 -> бpати не можна

5 = 101 5 XOR 2 = 7, 7>5 -> бpати не можна

-XOR---

2 = 010

Отже, якщо Ви вiзьмете 2 камiнця з пеpшої купки, то залишиться 1 4 5,

Z = 1 XOR 4 XOR 5 = 001 XOR 100 XOR 101 = 0, що Вам i тpеба.