1907967351

<9.

> Różnorodne algorytmy obliczeń i ich komputerowe realizacje

Inne instrukcje iteracyjne wprowadzimy na dalszych zajęciach. Program w tabeli 3 stuży do obliczania pola trójkąta dla n trójek, będących długościami boków trójkąta.

Ada Augusta, córka Byrona, uznawana powszechnie za pierwszą programistkę komputerów, przełomowe znaczenie maszyny analitycznej Ch. Babbage’a, pierwowzoru późniejszych komputerów, upatrywała właśnie „w możliwości wielokrotnego wykonywania przez nią danego ciągu instrukcji, z liczbą powtórzeń z góry zadaną lub zależną od wyników obliczeń”.

Ćwiczenie 3. Uruchom program Trójkąty na tych samych danych, na których testowałeś program w ćwicz. 2. Porównaj wyniki.

Podsumowując rozgrzewkę z programowania, wykonaliśmy trzy programy, o rozwijającej się strukturze:

■    pierwszy - zawiera, poza deklaracjami zmiennych, tylko listę poleceń:

■    w drugim - wykonywanie poleceń zależy od spełnienia warunku;

■    trzeci zaś wykonuje polecenia w pętli.

Z takim, niewielkim arsenałem, możemy rozpocząć programować poważniejsze algorytmy.

3 OBLICZANIE WARTOŚCI WIELOMIANU - SCHEMAT HORNERA

Jak wspomnieliśmy już, jednym z najważniejszych kroków w algorytmach jest powtarzanie tej samej czynności (operacji), czyli iteracja. W tym punkcie zilustrujemy iterację na przykładzie szybkiego sposobu obliczania wartości wielomianu.

Obliczanie wartości wielomianu o zadanych współczynnikach jest jedną z najczęściej wykonywanych operacji w komputerze. Wynika to z ważnego faktu matematycznego, zgodnie z którym każdą funkcję (np. funkcje trygonometryczne) można zastąpić wielomianem, którego postać zależy od funkcji i od tego, jaką chcemy uzyskać dokładność obliczeń.

Na przykład, obliczanie wartości funkcji cos x w przedziale 0 s x s n/2 z błędem nie większym niż 0.0009, można zastąpić obliczaniem wartości następującego wielomianu:

cos x — 1 — 0.49670x^J + 0.03705x*.

3.1 WYPROWADZENIE SCHEMATU HORNERA

Zacznijmy od prostych ćwiczeń. Jeśli dane są wartości współczynników a, b i c wielomianu stopnia 2: w(x) = ax‘ + bx + c,

to jego wartość można obliczyć wykonując zaznaczone mnożenia i dodawania: a-x-x+b-x+ c, czyli 3 mnożenia i dwa dodawania. Można także nieco inaczej - wyłączmyxz dwóch pierwszych składników - wtedy otrzymamy:

w(x) = (ox + b)x + c

i dla tej postaci obliczanie wartości tego wielomianu przyjmuje postać: (a-x+ b)-x*c, czyli są wykonywane tylko 2 mnożenia i dwa dodawania.

W podobny sposób można przedstawić wielomian stopnia 3:

y(x) = ax’ + bx¹ ■

+ cx*d