1–ma’ruza: Algoritmlarni loyihalashga kirish. Algoritmlarni vaqt va hajm bo‘yicha baholash. Ko‘phadlar qiymatlarini hisoblashda Gorner sxemasi

c_k=b_k-1x, b_k=a_k+c_k (k=1,2,…,n)
larni hisoblashga keltiriladi. b₀, b₁, b₂, … b_n-1 koeffitsientlar P(x) ko‘phadni x-x ikki hadga bo‘lishdan hosil bo‘lgan bo‘linma Q(x) ko‘phadning koeffitsientlari va b_n=P(x) esa qoldiq ekanligini ko‘rish mumkin.
Demak, (1.19) formulalar bo‘lish amalini bajarmasdan Q(x) ning koeffitsientlarini va qoldiqni topishga yordam berar ekan. Bu b₀, b₁, b₂,…, b_n koeffitsientlarni Gorner jadvali asosida quyidagicha topiladi:
a₀ a₁ a₂ … a_n
+ b₀x b₁x … b_n-1x
__________________________________
xû b₀ b₁ b₂ … b_n=P(x)

Demak, P(x)=b_i=a_i + b_i-1x , b₀= a₀ , _i=1,2,3,…,n

P_n(x) ko‘phadning qiymatini Gorner jadvali bilan hisoblashda n ta ko‘paytirish, n-k ta (k-nolga teng bo‘lgan koeffitsientlar soni) qo‘shish amallari bajariladi. Agar a₀=1 bo‘lsa, ko‘paytirish n-1 ta bo‘ladi.
1.9-masala. Quyidagi
P(x) = 3x³+2x²-5x+7
ko‘phadning x=3 bo‘lgandagi qiymatini hisoblang.
Yechish. Gorner jadvalini tuzamiz.
3 2 -5 7
+ 9 33 84
--------------------------------------
3| 3 11 28 91= P(3)
Ko‘phad qiymatini Gorner usulida hisoblashnini 1.1-blok sxemasini va dasturini tuzamiz. Masaladagi berilganlar asosida ko’rsatilgan usulda hisoblashning algoritmini 1.1-jadvalda beramiz .
1.1-jadval

Berilganlar	Belgilashlar
	matn bo‘yicha	dastur bo‘yicha
Ko‘phadning tartibi	N=3	INPUT N
Berilgan argumet	X=3	INPUT X
Ko‘phadning koeffitsentlari	a0=3, a1=2, a3=-5, a4=7	A(0)=3, A(1)=2, A(3)=-5, A(4)=7
Ko‘phad qiymatini hisoblash formulasi	b0 = a0, bi = ai + bi-1 * x i=1,2,3,..,n	b(0) = a(0), b(i) = a(i)+b(i–1)*x, i=1,2,3,..,n
Ko‘phad qiymati	p(x)=bn	p(x)=b(n)

Gorner sxemasi asosida ko’phadning qiymatini hisoblash(1.9-masala).

C++ dagi dasturi


#include
using namespace std;
int n, x, a[10], b[10];
int main()
{
cout <<"Ko'phad tartibini kiriting n=?";
cin >> n;
cout <<"Argumentni kiriting x=? ";
cin >> x;
cout << "Ko'phad koeffitsentlarini kiriting: ";
for(int i = 0 ; i <= n ; i++)
{
cin >> a[i];
}
b[0] = a[0];
for(int i = 1 ; i < n+1 ; i++)
{
b[i] = a[i] + b[i-1]*x;
}
cout << "Ko'phad qiymati: p( 3 )= " << b[n];
}
[0.5, 2] kesmadagi ko‘phadning qiymatlarini Gorner usuli asosida hisoblash dasturini tuzamiz
C++ dagi dasturi


#include
using namespace std;
int n;
float a[10], b[10], p, x;
int main()
{
cout <<"Ko'phad tartibini kiriting n=? ";
cin >> n;
cout << "Ko'phad koeffitsentlarini kiriting: ";
for(int i = 0 ; i <= n ; i++)
{
cin >> a[i];
}
b[0] = a[0], x = 0.5;
while(x <= 2)
{
for(int i = 1 ; i <= n ; i++)
{
b[i] = a[i] + b[i-1]*x;
}
p = b[n];
cout <<"p("<
x += 0.25;
}
}
2. Gorner jadvalidan foydalanib P_n(x) ko‘phadning haqiqi ildizlarining yuqori chegaraiini topish mumkin.
Aytaylik x=β(β>0)da Gorner jadvalidagi barcha koeffisientlar manfiy bo‘lmasin, ya'ni
b₀=a₀ >0, b _i ≥0 ( i=1,2,3,…,n)
bu holda P_n(x) ko‘phadning barcha x_k haqiqi ildizlari β dan chap tomonda joylashgan bo‘ladi, ya'ani
x_k≤ β( k=1,2,3,…,m, m)
bo‘ladi.
Shuningdek berilgan P_n(x) ko‘phadning haqiqi ildizlarining quyi chegarasini topish uchun ko‘phad arguenti x ni - x bilan almashtirib, quyidagi ko‘phadni hosil hilamiz:

Bu ko‘phad uchun shunday x=h(h>0) ni topamizki, bunda Gorner jadvali bo‘yicha barcha koeffisientlar manfiymas bo‘lsin, hosil bo‘lgan ko‘phadning haqiqi ildizlari uchun
x_k≤ α (k=1,2,3,…,m )
tengsizlik o‘rinli bo‘ladi. Aslida bu berilgan P_n(x) ko‘phadning haqiqi ildizlarining quyi chegarasi bshladi: - α ≤ x_k
Demak berilgan Pn(x) ko‘phadning barcha haqiqi ildizlari [- α, β] kesmada yotadi.
1.9.1-masala. Yuqorida keltirilgan 1.9-masaladagi
P₃(x) = 3x³+2x²-5x+7
ko‘phadning barcha haqiqi ildizlari yotgan soha chegarasini topamiz.
Yechish. Gorner jadvalini tuzamiz. Argumentga x=1 qiymat beramiz:
3 2 -5 7
+ 3 5 0
--------------------------------------
1| 3 5 0 7= P₃ (1)
Bunda x nig birinchi qadamidayoh manfiymas koeffisientlar aniqlandi bundan x=1 ko‘phadning barcha haqiqi ildizlarining yuqori chegarasi bo‘ladi.
Ko‘phad ildizlarining quyi chegarasini topish uchun quyidagi ko‘phadni tuzamiz:
(-1)³P₃(-x) = -(3(-x)³+2(-x)²-5(-x)+7)= -(-3x³+2x²+5x+7)= 3x³-2x²-5x-7
hosil bo‘lgan ko‘phadning haqiqi ildizlarining yuqori chegarasini topish , ya'ni Gorner jadvali bo‘yicha musbat koeffisientlar aniqlash uchun argumentga 1 dan boshlab ketma-ket qiymatlar ho‘yib, Gorner jadvalini tuzamiz x=1 da:

Bunda b₂=-4, b₃=-11 manfiy bo‘lganligi uchun, argumentga yana qiymat beramiz, x=2 da:

Bunda b₃= -1 manfiy bo‘lganligi uchun, argumentga yana qiymat beramiz, x=3 da:
3 - 2 -5 - 7
+ 9 21 48
--------------------------------------
3| 3 7 16 41= P₃(3)
Demak, hosil bo‘lgan ko‘phadning haqiqi ildizlarining yuqori chegarasi x=3 bo‘ladi. Bundan berilgan ko‘phadning haqiqi ildizlarining quyi chegarasi x=-3 bo‘lib, barcha ildizlari yotgan kasma: [-3, 1]
Endi Gorner usuli berilgan P_n(x) ko‘phadning barcha haqiqi ildizlarining yuqori chegarasini topish dasturini tuzamiz. Buning uchun P_n(x) argumenti x ga 1 dan boshlab h=1 qadam bilan ketma-ket qiymat berish bilan, bulardan Gorner jadvali bo‘yicha P_n(x) ko‘phadning barcha manfiymas koeffisientlarini aniqlovchi x ni qiymatini topamiz. Masaladagi berilganlar asosida ko’rsatilgan usulda hisoblashning algoritmini 1.1.1-jadvalda beramiz :
1.1.1-jadval

Berilganlar	Belgilashlar
	matn bo’yicha	dastur bo’yicha
Ko’phadning tartibi	N=4	INUT N
Ko’phadning haқiқi ildizlarining yuқori chegarasini aniqlash uchun argumentning birinchi qiymati	X=1	X=1
Ko’phadning koeffitsentlari	a0=3, a1=2, a3=-5, a4=7	A(0)=3, A(1)=2, A(3)=-5, A(4)=7
Ko’phad qiymatini hisoblash formulasi	b0 = a0, bi = ai + bi-1 * x i=1,2,3,..,n	B(0) = A(0), B(I) = A(I)+B(I–1)*X, I=1,2,3,..,N

Nazorat savollari

1. 
   Algoritmlar turlarini ayting.
   
2. 
   Hisoblashda algoritmlarning o‘rni.
   
3. 
   Algoritmlar orqali yechiluvchi masalalar.