תכנות — שיעור 134 10/January/2011    

פולינומים — כלל Horner

בעזרת כלל Horner, נִתן לחשב ערך של פולינום בנקודה במספר כְּפַלִים כמעלת הפולינום. לדוגמא, במקום החישוב התמים
lteq1.png
שבו יש לכאורה 15 הכפלות, אפשר לחשב את הבטוי
lteq2.png
עם 5 הכפלות בלבד.

פולינומים — חלוק ארוך

בדומה לחִלוק ארוך עם שארית של מספרים שלמים:
lteq3.png
שבו מקבלים
lteq4.png
נתן לחלק פולינומים
lteq5.png
ולקבל מנה Q ושארית R כך ש-
lteq6.png

השיטה

החישוב נעשה בשלבים. בכל שלב אנו דואגים "לסלק" את המקדם העליון של ה"שארית" הנוכחית באופן הבא. נסמן את השארית ההתחלתית:
lteq7.png
כשיש לנו
lteq8.png
בקלות אפשר לחשב
lteq9.png
ואז
lteq10.png
עכשיו ממשיכים באופן דומה ומקדמים את האינדקסים עד ש
lteq11.png
ולבסוף
lteq12.png

דוגמא

יהיו
lteq13.png
ואז בלולאות, הראשונה
lteq14.png
השניה
lteq15.png
השלישית
lteq16.png
ולבסוף:
lteq17.png

תרגילים

  1. השלם תרגילים קודמים
  2. מַמֵש את הפונקציה polynom_evaluate() בעזרת כלל Horner.
  3. הורד גירסא polynom-v4.tar.gz

חזרה לעמוד האם