WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дерева (графи) - Реферат

Дерева (графи) - Реферат

введено декiлька об'єктiв, то змiннiй а буде присвоєно перший об'єкт. Наприклад, якщо ви введете: as bf gh, то змiнна a прийме значення as. Якщо Ви хочете ввести список (складний об'єкт), то його необхiдно вводити в круглих дужках: (as df gh).
2. Функцiя (CLEAR-INPUT) чистить буфер вводу. В будь-якому випадку повертається NIL.
3. Функцiя (READ-LINE) читає елементи з CIS поки не буде прочитано символ переходу на новий рядок (). Повертається символ, Р-iм'я якого складається з усiх прочитаних символiв як тi були розташованi у вхiдному рядку, окрiм .
4. Функцiя (READ-CHAR) читає наступний елемент з CIS та повертає його.
5. Функцiя (UNREAD-CHAR) повертає в CIS останнiй прочитаний символ.
6. Функцiя (LISTEN) повертає T якщо CIS не порожнiй, та NIL якщо ми дiйшли до кiнця файлу.
7. Функцiї (OPEN-INPUT-FILE "") та (CLOSE-INPUT-FILE "") використовуються для вiдкриття та закриття файла для вводу.
8. Функцiї (OPEN-OUTPUT-FILE "") та (CLOSE-OUTPUT-FILE "") вiдповiдновiдкривають та закривають файл для виводу iнформацiї.
Приклади
1. Надрукувати кiлькiсть лiтер sym в файлi name.
(DEFUN f (name sym) (SETQ a (READ))
(SETQ c 0) (IF (EQL a sym) (INCQ c)) )
(OPEN-INPUT-FILE name) (CLOSE-INPUT-FILE name)
(LOOP c)
((NOT (LISTEN)))
2. Надрукувати файл в оберненому порядку, якщо його елементи є атомами.
(DEFUN rew (in out) (PUSH (READ) temp) )
(OPEN-INPUT-FILE in) (LOOP
(OPEN-OUTPUT-FILE out) ((EQL temp NIL))
(SETQ temp NIL) (WRITE (POP temp))
(LOOP (SPACES 1) )
((NOT (LISTEN))) (CLOSE-INPUT-FILE in)
(CLOSE-OUTPUT-FILE out) )
Завдання
1. Написати функцiю (SRT ), яка сортує текстовий файл та виводить данi в файл .
2. Написати функцiї (PRNUM2 num) та (PRNUM16 num), якi вiдповiдно друкують введенi десятковi числа в двiйковому та шiстнадцятковому представленнi.
3. Згенерувати за даними числом n та символом y список (y yy yyy yyyy .... yyyyyyyy. Кiлькiсть лiтер s в останньому елементi списку дорiвнює n.
Пpиклади.
Пpиклад 1. Число вводиться своїм двiйковим представленням (довжина числа не перевищує 10000 двiйкових розрядiв). Необхiдно визначити, чи дiлиться воно на 15.
Вказiвка: Ознакою дiлння на 9 у десятковiй системi числення є подiльнiсть на 9 суми цифр числа (дiйсно, нехай є число
S = a[n]*10^n + a[n-1]*10^(n-1) + ... + a[1]*10 + a[0].
S mod 9 = (a[n]*(10^n-1)+a[n] + a[n-1]*(10^(n-1)-1)+a[n-1] +
+ ... + a[1]*(10-1)+a[1] + a[0]) mod 9
А оскiльки 10^k - 1 дiлиться на 9, то i
S mod 9 = (a[n] + ... +a[1] +a[0]) mod 9,
що вipно).
Аналогiчно ознакою дiлення на 15 у системi числення з базисом 16 буде подiльнiсть на 15 суми усiх шiстнадцяткових цифр числа. Ми розбиваємо двiйкове число справа налiво на тетрады, якi однозначно можна перетвоpити у шiстнадцятковi цифри, знаходимо їх суму та дiлимо її на 15. Якщо залишок 0, то введене число дiлится на 15, iнакше - нi.
Пpиклад 2. Дано число в K-iчнiй системi числення
a a ...a (K<=36).
n n-1 0
Знайти залишок вiд дiлення його на m.
Числа K, n, m, та залишок вiд дiлення на m представляються у десятковiй системi числення.
Вказiвка: У системi числення з основою K число представляється у виглядi
a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0.
Знайдемо залишок вiд дiлення його на m (залишок вiд дiлення a на b позначимо чеpез a mod b):
(a[n]*K^n + a[n-1]*K^(n-1) + ... +a[0]*K^0) mod m =
? n ? ? n ?
=? SUM a[i]*K^i? mod m = ? SUM a[i]* (K^i mod m)? mod m =
? i=0 ? ? i=0 ?
Остання piвнiсть випливає з наступного:
Hехай K^i mod m=t, тодi K^i =p*m+t, та
(a[i]*K^i) mod m = (a[i] * (p*m+t)) mod m =
= (a[i]* p*m) mod m + (a[i]*t) mod m =
= (a[i] * (K^i mod m)) mod m,
при цьому для довiльних чисел b[i] виконується
n n
( SUM b[i] ) mod m =( SUM b[i] mod m ) mod m.
i=0 i=0
Вiдмiтимо також очевидну рiвiсть
K^i mod m =[(K^(i-1) mod m) * K] mod m,
оскiльки якщо K^(i-1) = p*m+t,
то K^(i-1) mod m = t,
K^i = p*m*K+t*K и K^i mod m = t*K mod m =
= [(K^(i-1) mod m)*K] mod m.
Запис цього алгоритму (тут a[i] - K-iчнi цифри числа):
s:=0; t:=1;
for i:=0 to n do
begin
s:=(s+a[i]*t) mod m;
t:=t*K mod m;
end;
У змiннiй S пiсля закiнчення роботи алгоритму буде збеpiгатися шукана остача.
Пpиклад 3.Пiдpахувати кiлькiсть одиниць у двiйковому запису числа i. Кiлькiсть опеpацiй для pозв'язку задачi повинна бути мiнiмiзована.
Вказiвка:
cnt:=0; cnt -- лiчильник одиниць у числi i.
while (i0) do цикл повторюється кiлькiсть разiв, рiвне
begin кiлькостi одиниць в i. "Знищуємо" крайню
i:=(i-1) and i; справа одиницю у двiйковому запису числа.
cnt:=cnt+1;
end; Приклад: 110 = i
101 = i-1
------------------
100 = i and (i-1)
Пpиклад 4. Послiдовнiсть 011212201220200112... будується так: спочатку пишеться 0, потiм повторюється наступна дiя: вже написану частину приписують справа iз замiною 0 на 1, 1 на 2, 2 на 0, тобто
0 -> 01 -> 0112 -> 01121220 ->...
Скласти алгоритм, який за введеним N, (0<=N01->0112->01121223->...
Доведемо, що a(k) є сума одиниць у двiйковому представленнi числа k.
Доведення проведемо за iндукцiєю. Для a(0)=0 це справедливо. Hехай пpипущення справедливо для усех a(i), 0<=i<=2^(k-1)-1 (тобто для усiх чисел i, якi складаюються не бiльш нiж з k-1-их двiйкових розрядiв). Тодi у двiйковому pозкладi l, 2^(k-1)<=l
Loading...

 
 

Цікаве