Структура и интерпретация на компютърни програми (
(дефинирайте (многочленни Li L2)
(ако (празен списък с термини?li)
(добавяне на термини (мулти-член-по-всички-членове (първи член Li) L2)
(многосрочни (почивни срокове Li) L2))))
(дефиниране (мулти-член-по-всички-термини ti L)
(ако (празен списък с термини?L)
(нека ((t2 (първи член L)))
(съседен член (съставен член (+ (ред ti) (ред t2))
(mul (коеф ti) (коеф t2)))
(mul-term-by-all-terms ti (rest-terms L))))))
Това е всичко, от което се нуждаем, за да събираме и умножаваме полиноми. Обърнете внимание, че тъй като работим с термини, използвайки генеричните процедури add и mul, нашият полиномен пакет е в състояние автоматично да обработва всеки тип коефициент, за който генеричният аритметичен пакет знае. Ако включим механизъм за преобразуване на типове като този, обсъден в раздел 2.5.2, тогава автоматично ще можем да извършваме операции върху полиноми с коефициенти от различни типове, например
[Zx2 + (2 + Zi)X + 7] • [x4 + -X2 + (5 + Zr)]
2.5. Системи с обобщени операции
Тъй като сме настроили процедурите за събиране и умножение на полиномите add-poly и mul-poly в обобщената аритметична система като операции add и mul за типа полином, нашата система е в състояние автоматично да извършва операции върху полиноми като
[(y + 1)x2 + (y2 + 1)x + (y - 1)] • [(y - 2)x + (y3 + 7)]
Причината за това е, че когато системата се опитва да комбинира коефициентите, тя изпраща чрез add и mul. Тъй като самите коефициенти са полиноми (в y), те ще бъдат комбинирани с помощта на add-poly и mul-poly. Резултатът е един вид "управлявана от данни рекурсия", където,например извикването на mul-poly води до рекурсивни извиквания на mul-poly, за да се комбинират коефициентите. Ако коефициентите на коефициентите сами по себе си бяха полиноми (това може да е необходимо, ако трябваше да бъдат представени полиноми в три променливи), управляваното от данни програмиране би гарантирало, че системата преминава през още едно ниво на рекурсивни извиквания и така нататък, до толкова нива на структура, колкото се изискват данните.
Представяне на списъци с термини
И накрая, ние сме изправени пред предизвикателството да внедрим добро представяне на списъци с термини. Списъкът с термини е по същество набор от коефициенти, индексирани по реда на термина. Следователно всеки от методите за представяне на множество, описани в 2.3.3, е подходящ за тази задача. От друга страна, нашите процедури за добавяне на термини и много термини винаги обработват списъци с термини последователно от най-високия ред до най-ниския, така че ще използваме някакъв вид подредено представяне.
Как да организираме структура от данни, която представлява списък от термини? Едно съображение е "плътността" на полиномите, с които ще работим. Полиномът се нарича плътен, ако има ненулеви коефициенти по отношение на повечето порядки. Ако има много нулеви коефициенти, той се нарича разреден. Например,
A: x5 + 2g4 + 3g2 - 2g - 5
плътен полином и
B: w100 + 2w2 + 1
Списъците с членове на плътни полиноми са най-добре представени като списъци с коефициенти. Например A в горния пример е удобно представено като (т
57 За да работи всичко това перфектно гладко, трябва да добавим към нашата система от обобщена аритметика възможността да преобразуваме „число“ в типа на полином, като го разглеждаме катополином от нулева степен, чийто коефициент е даденото число. Това е необходимо, ако искаме да извършваме операции като
[x2 + (y + 1)x + 5] + [x2 + 2x + 1], където искате да добавите коефициента y + 1 към коефициента 2.
Глава 2 Изграждане на абстракции с данни
2 0 3 -2 -5). Редът на член в такова представяне е дължината на списъка, започващ с този коефициент, минус 158. За рядък полином като B, това представяне би било ужасно: ще завършите с огромен списък от нули, с случайни самотни ненулеви членове. По-разумно представяне на рядък полином е като списък от ненулеви членове, където всеки член е списък, съдържащ реда на члена и коефициента в този ред. С такава схема, полиномът B е ефективно представен като ((i00 i) (2 2) (0 i)). Тъй като мнозинството
операции върху полиноми се прилага към редки полиноми, използваме
това е презентация. Предполагаме, че списъкът с термини е представен като списък, чиито елементи са термини, подредени от по-висок към по-нисък ред. След вземане на решението, внедряването на селектори и конструктори за термини и
списъци с термини не представляват трудност59:
(дефиниране (списък с термин термин термин)
(ако (=нула? (термин коеф)) списък с термини
(против термин термин списък)))
(дефиниране (списък с термини за първи термин) (списък с термини за автомобили))
(дефиниране (списък с термини за почивка) (списък с термини на cdr))
(define (empty-termlist? term-list) (null? term-list)) Предишна 91 92 93 94 95 96 .. 269 >> Следващия