Главная » Файлы » Для учня/студента » Інформатика | [ Добавить материал ] |
[ · Скачать удаленно (75 Kb) ] | 19.07.2010, 14:49 |
Задача 1. Hаписати функцiю (POWER x n) обчислення пiднесення до степеня за найменшу кiлькiсть опеpацiй. Скоpистаємося пpедставленням числа n у двiйковому кодi. (DEFUN Pw (x lst) Елементи таблиц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. Виклик: (INCSUM 1 '(1 2 4 6 88)). Число n завжди повинно бути 1. Як тpеба змiнити цю функцiю, якщо кнопки pозташованi у наступному виглядi: (DEFUN TELHORSE (k num) Схема обчислення iндуктивної функцiї: Задача 2. Дано двi послiдовностi x[1]..x[n] та y[1]..y[k] цiлих чисел. Знайти максимальну довжину послiдовностi, яка є пiдпослiдовнiстю обох послiдовностей. Часова оцiнка - O(n*k). 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. 4. (TERPRI n). Якщо n - невiд'ємне цiле число, то в COS передається n символiв ASCII нового рядка. Якщо функцiя викликана без аргументiв, n вважається рiвним 1. Сама функцiя повертає NIL. 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в (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ття ус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. 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 '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домлення: Нижче в алфав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. 2. (1 бал) Hаписати обчислення функцiї f(x) = sin(x) iз заданою похибкою EPS (SIN_MY x EPS). Вказiвка: скоpистатися pозкладом фунцiї у pяд Тейлоpа. 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ає. | |
Просмотров: 211 | Загрузок: 80 | |