Mavzu: Polinomlarni hisoblash algoritmlari. Gorner sxemasi Chekli tenglamalar va sistemalarni yechishning taxminiy usullari

911-20 guruh talabasi
Jumaniyazov Sanjarning
Algoritm loyihalash fanidan
4-Laboratoriya ishi.
Mavzu: Polinomlarni hisoblash algoritmlari. Gorner sxemasi
Chekli tenglamalar va sistemalarni yechishning taxminiy usullari.
Tenglamalarni echish muhandisning amaliyotida eng ko'p uchraydigan vazifalardan biridir.
Biroq, massiv masala sifatida, tenglamaning yechimini topish masalasi algoritmik jihatdan yechilmaydi, chunki amallar soni chekli bo'lgan formula ko'rinishidagi yechimning umumiy ifodasi yo'q. Aynan shu holatda har qanday oldindan belgilangan aniqlik bilan berilgan tenglamaning taxminiy yechimini topishga imkon beradigan usullarga murojaat qilish kerak.
Agar M1 va M2 raqamlar to'plami bo'lsa, u holda chekli tenglamalar (algebraik va transsendental) haqida gapiriladi. Agar M1 va M2 ko'p o'lchovli bo'shliqlar nuqtalari bo'lsa, unda chekli tenglamalar tizimi to'plami haqida gapiriladi. Agar M1 va M2 funksiyalar to’plami bo’lsa, u holda F1(x) va F2(x) ko’rinishiga qarab differensial tenglamalar, integral, integro-differensiallar haqida gapiramiz.
Yakuniy tenglamalar.
Daraxt bo'yicha chekli tenglamalarning tasnifini ko'rib chiqing:

Ushbu sxemaning birinchi qatori f(x) polinomining koeffitsientlarini o'z ichiga oladi va uchinchi qator a0 = b0 dan boshlanadi va keyin har bir bi koeffitsienti c ga ko'paytiriladi va keyingi ai+1 koeffitsienti ostida imzolanadi. Tegishli ustunning birinchi va ikkinchi qator raqamlari qo'shiladi va ustunning uchinchi qatoriga bi+1 natijasi yoziladi. Shunday qilib, uchinchi qatorda f(c) ko‘phadni binomiga (x-c) bo‘lish natijasida olingan qismning koeffitsientlari, qolgan qismi esa son jihatdan ushbu ko‘phadning x = cdagi qiymatiga teng, ya’ni. bn = f(c) = r.
Misol.
Xorner sxemasidan foydalanib, f(x) = x5 + 3x4 - 2x3 + x2 - x + 1 ko'phadni binomiga (x - 3) bo'ling. Yechim. Berilgan ko'phadning Gorner sxemasini tuzamiz.

	1	3	-2	1	-1	1
c = 3		3	18	48	147	438
	1	6	16	49	146	439

Demak: r = f(3) = 439, g(x) = x4 + 6x3 + 16x2 + 49x + 146 demak f(x) = (x – 3)( x4 + 6x3 + 16x2 + 49x + 146) + 439

Misol.
c = 1 tenglamaning ildizi x3 + 2x2 - 3 = 0 ekanligini aniqlang.
Yechim.
Agar c = 1 f(x) = x3 + 2x2 – 3 = 0 tenglamaning ildizi boʻlsa, x3 + 2x2 – 3 koʻphad koʻphadga (x - 1) qoldiqsiz boʻlinishi kerak. Biz Horner sxemasidan foydalanamiz.

	a0 = 1	a1 = 2	a2 = 0	a3 = -3
c = 1		1*1	1*3	3*1
	b0 = 1	b2 =3	b2 =3	r = b3 =0

Demak, f(1) = 0 (qoldiq r = 0) va demak, c = 1 berilgan tenglamaning ildizidir.
6-topshiriq

Bir o’lchamli butun sonlardan iborat massiv berilgan. Uning elementlar qiymatlari -10⁹ dan10⁹ gacha bo’lishi mumkin. Ma’lumki, undagi har xil sonlar soni uning elementlar soni n danoshmaydi. Massiv elementlarini qayta qiymatlash da quyidagi shartlar bajarilishi kerak:

1) Qayta qiymatlashda ishlatiladigan eng minimal son 1 bo’lishi kerak.
2) Qayta qiymatlashda ishlatiladigan maksimal son iloji boricha eng kichik bo’lishi kerak.
3) Bir xil qiymatli elementlarning qayta qiymatlangach ham qiymatlari bir xil bo’lishikerak.
4) Avvalgi qiymati katta bo’lgan songa kattaroq qiymat berilishi kerak.
Qayta qiymatlash orqali elementlarning asil qiymati yo’qoladi, lekin ularning tenglik, katta-kichiklik haqidagi ma’lumot saqlanib qoladi. Sizning vazifangiz yuqoridagi shartlarniqanoatlantiradigan tartibda berilgan bir o’lchamli massiv elementlarini qayta qiymatlabchiqishdan iborat. Lekin sizdan massivning barcha elementlarini chiqarish emas, faqat ba’zielementlarini chiqarish so’raladi.
Kiruvchi ma’lumotlar
Birinchi qatorda massiv elementlari soni n berilgan(1≤n≤10⁵). Ikkinchi qatorda n ta son−massiv elementlari bitta probel bilan ajratib berilgan. Massiv elementlari butun va moduljihatdan 10⁹ dan oshmaydi. Uchinchi qatorda so’rovlar soni m(1≤m≤300) beriladi. Keyingiqatorda m ta butun son k_i – qayta qiymatlangan massivdagi so’ralgan element indeksiberiladi(1≤ k_i ≤n).
Chiquvchi ma’lumotlar
Birinchi qatorda m ta sonni – har bir so’rovga javob sifatida qayta qiymatlangan massivdagik_i – indeksdagi qiymatini so’rovlar berilish tartibida bitta probel bilan ajratib chiqaring.
M isollar
х=-1, х=-2,х=3, .
Kod qismi:
n = int(input())
a = list(map(int, input().split()))
m = abs(a[-1])

for i in range(-m, m+1):

s = 0
for j in range(n):
s += i**(n-j)*a[j]
if s == 0:
print(i)

Yechim: