259 lines
20 KiB
Plaintext
259 lines
20 KiB
Plaintext
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "systematic-dining",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"# Schemat Hornera"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "fatal-canon",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Schemat Hornera jest metodą obliczania wartości wielomianu dla danej wartości argumentu. Ilość mnożeń jest zredukowana do minimum. Jest to również algorytm dzielenia wielomianu W(x) przez dwumian x - c. Schemat ten powiązany jest z nazwiskiem brytyjskiego matematyka Hornera żyjącego na przełomie XVIII i XIX wieku, który w 1819 roku podał sposób obliczania wartości wielomianu. 150 lat wcześniej Newton wykorzystał podobny sposób dla zmniejszenia liczby operacji fizycznych."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "returning-paradise",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Klasyczne podejście"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "noticed-biotechnology",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Spójrzmy najpierw na tradycyjny sposób obliczania wartości wielomianu:"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 65,
|
||
|
|
"id": "martial-belle",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"source": [
|
||
|
|
"def oblicz_wartosc_wielomianu(wspolczynniki, x):\n",
|
||
|
|
" stopien = len(wspolczynniki) - 1\n",
|
||
|
|
" operacje = 0\n",
|
||
|
|
" wartosc = 0\n",
|
||
|
|
" \n",
|
||
|
|
" #do wyniku dodajemy kolejno obliczone ze współczynników wartości\n",
|
||
|
|
" for aktualny_stopien in range(stopien + 1):\n",
|
||
|
|
" wartosc += wspolczynniki[aktualny_stopien] * (x ** aktualny_stopien)\n",
|
||
|
|
" operacje += aktualny_stopien\n",
|
||
|
|
" if aktualny_stopien != 0:\n",
|
||
|
|
" #Po pierwszej iteracji współczynników, kolejne wymagają dodatkowej jednej operacji.\n",
|
||
|
|
" operacje += 1\n",
|
||
|
|
"\n",
|
||
|
|
" return f\"Wartość wielomianu dla argumentu {x} wynosi {wartosc}. Do obliczenia tej wartości, potrzebne było {operacje} operacji.\""
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "studied-cosmetic",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Powyższa funkcja oprócz wartości wielomianu liczy także ilość wykonanych operacji mnożenia. Możemy potem porównać, jak ta wartość wypada w porównaniu do schematu Hornera."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 85,
|
||
|
|
"id": "daily-radius",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"name": "stdout",
|
||
|
|
"output_type": "stream",
|
||
|
|
"text": [
|
||
|
|
"Wartość wielomianu dla argumentu 10 wynosi 4841. Do obliczenia tej wartości, potrzebne było 9 operacji.\n"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"#W(x) = 5x^3 - 2x^2 + 3x + 11\n",
|
||
|
|
"wspolczynniki = [11, 3, -2, 5] #w odwrotnej kolejności (zaczynając od najniższego stopnia)\n",
|
||
|
|
"x = 10\n",
|
||
|
|
"\n",
|
||
|
|
"print(oblicz_wartosc_wielomianu(wspolczynniki, x))"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "proprietary-brighton",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Schemat Hornera"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "widespread-hawaiian",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Zobaczmy teraz, jak schemat Hornera radzi sobie z tym samym zadaniem:"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 57,
|
||
|
|
"id": "infectious-example",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"source": [
|
||
|
|
"def oblicz_wartosc_wielomianu_horner(wspolczynniki, x):\n",
|
||
|
|
" stopien = len(wspolczynniki) - 1\n",
|
||
|
|
" wartosc = wspolczynniki[stopien]\n",
|
||
|
|
" operacje = 0\n",
|
||
|
|
" \n",
|
||
|
|
" while stopien > 0:\n",
|
||
|
|
" stopien = stopien - 1\n",
|
||
|
|
" wartosc = wartosc * x + wspolczynniki[stopien]\n",
|
||
|
|
" \n",
|
||
|
|
" #wykonywana jest jedna operacja mnożenia\n",
|
||
|
|
" operacje += 1\n",
|
||
|
|
" \n",
|
||
|
|
" return f\"Wartość wielomianu dla argumentu {x} wynosi {wartosc}. Potrzebne było {operacje} operacji.\""
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "dutch-trading",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"W tym przypadku, również zaczynając od najwyższego stopnia po kolei mnożymy wartość wielominu przez x, a następnie dodajemy ten współczynnik."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 63,
|
||
|
|
"id": "deluxe-evolution",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"name": "stdout",
|
||
|
|
"output_type": "stream",
|
||
|
|
"text": [
|
||
|
|
"Wartość wielomianu dla argumentu 10 wynosi 4841. Potrzebne było 3 operacji.\n"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"#W(x) = 5x^3 - 2x^2 + 3x + 11\n",
|
||
|
|
"wspolczynniki = [11, 3, -2, 5]\n",
|
||
|
|
"x = 10\n",
|
||
|
|
" \n",
|
||
|
|
"print(oblicz_wartosc_wielomianu_horner(wspolczynniki, x))"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "useful-documentation",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Jak widać na powyższym przykładzie, schemat Hornera potrzebuje mniej operacji mnożenia, żeby obliczyć tą samą wartość wielomianu. Jest to szczególnie przydatne podczas optymalizowania aplikacji wykorzystujących wielomiany."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "linear-intensity",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"### Porównanie"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "tutorial-brush",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Przy zastosowaniu schematu Hornera, liczba wymaganych operacji mnożenia jest taka sama, jak stopień wielomianu, podczas gdy klasyczne wyliczanie wartości wymaga ich znacznie więcej:"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"execution_count": 105,
|
||
|
|
"id": "genetic-freeware",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"text/plain": [
|
||
|
|
"[<matplotlib.lines.Line2D at 0x2bc1ba20820>]"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
"execution_count": 105,
|
||
|
|
"metadata": {},
|
||
|
|
"output_type": "execute_result"
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"data": {
|
||
|
|
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAlRklEQVR4nO3deXSU5fnG8e8dCEuABISAkJAEFVQEFYgKgtqCKKIiuIJotVKxrbVC8Vgqtj1WsbZalWpbxV0bsW6odauAC6WINQiIiLhQCIQt4QcECISEPL8/niEQSCAkM/POJNfnnJxk3sxkblq5eHK/z2LOOUREJP4kBF2AiIjUjgJcRCROKcBFROKUAlxEJE4pwEVE4lTjaL5Zu3btXFZWVjTfUkQk7s2fP7/QOZe6//WoBnhWVha5ubnRfEsRkbhnZiuruq4WiohInFKAi4jEKQW4iEicUoCLiMQpBbiISJxSgIuIREpODmRlQUKC/5yTE9YfH9VphCIiDUZODowdC8XF/vHKlf4xwOjRYXkLjcBFRCJh0qS94b1HcbG/HiYKcBGRSMjLO7zrtaAAFxGJhI4dq76ekRG2t1CAi4iE29KlB7ZPAJKSYPLksL2NAlxEJJwWLIAzz4RmzeCeeyAzE8z856lTw3YDEzQLRUQkfJyDG27wI+1Zs+CYY+CXv4zY2ynARUTCxQxeftkHeWZmxN9OLRQRkbp66y0YMwZ27/Y3KaMQ3qAAFxGpm5deguHD4fPPYdu2qL61AlxEpLaefhpGjoS+fWHmTEhJierbK8BFRGrj0Ufhhz+EQYPg3XejHt6gABcRqZ3jjoMrroA33oAWLQIpQQEuIlJTzsHcuf7rs86CF17w870DogAXEakJ52D8eOjfH2bPDroaQPPARUQObfduv0DniSdg3Dg444ygKwI0AhcRObjSUrjqKh/ev/413H+/X7ATA2oc4GbWyMwWmNmbocddzOwTM/vWzP5hZk0iV6aISED+9S/f6/7DH+B3v4uZ8IbDG4HfDCzd5/EfgAecc8cAm4Ax4SxMRCQmXHABzJ8Pt94adCUHqFGAm1k6cD7weOixAQOBl0NPeQYYHoH6RESib8sWOO88+Phj/7h372DrqUZNR+APArcC5aHHbYHNzrmy0OPVQFp4SxMRCUBhoV+cM3MmrF0bdDUHdcgAN7MLgA3Oufm1eQMzG2tmuWaWW1BQUJsfISISHWvX+vndX3wBr70GF18cdEUHVZNphP2BYWY2FGgGJANTgNZm1jg0Ck8H8qt6sXNuKjAVIDs724WlahGRcFu3zk8PXLcO3nkHvv/9oCs6pEOOwJ1zv3LOpTvnsoCRwPvOudHAB8CloaddA7wesSpFRCKtXTt/ks6MGXER3lC3eeC/BH5hZt/ie+JPhKckEZEoWrLEt04aN4Ynn4R+/YKuqMYOayWmc+5D4MPQ18uBU8NfkohIlOTmwrnnQp8+8N57QVdz2LQSU0QapjlzYOBASE6GRx4JuppaUYCLSMMzYwaccw506gT//jccdVTQFdWKAlxEGpbycpg4Ebp29bsKpqcHXVGtaTdCEWk4nIOEBHjzTWjaFI44IuiK6kQjcBFpGB5/3J+gU1YGHTvGfXiDAlxEGoIHH4Trr/enxpeWBl1N2CjARaT+cg7uusufpHPJJX55fPPmQVcVNgpwEam/7rzTH8Lwgx/4Pb2b1K9jC3QTU0Tqr3PO8VvD3nuvv3lZz9S/P5GINGxlZfDWW/7rvn3hT3+ql+ENCnARqU927YJRo/wpOv/9b9DVRJxaKCJSP+zYAZdeCm+/7Ufdp9b/rZoU4CIS/7ZuhYsugg8/hEcfhbFjg64oKhTgIhL/Zs3ye5o89xyMHh10NVGjABeR+FVe7m9QDh8Oy5bF7aZUtaWbmCISX3JyICvLB3ezZnD77f56AwtvUICLSDzJyfH97ZUr/SrL0lK47z5/vQFSgItI/Jg0CYqLK18rKfHXGyAFuIjEj7y8w7tezynARSR+dO5c9fWMjOjWESMU4CIS20pKYNw43/e++25ISqr8/aQkmDw5kNKCpmmEIhK7Cgvh4ov9HO/u3fcu0Jk0ybdNMjJ8eDegud/7UoCLSGz66iu/p8nq1TBtGowc6a+PHt1gA3t/CnARiT3z58PZZ/v9uz/80O8qKAdQD1xEYs+xx8J558Ennyi8D0IBLiKxYfdueOAB2L4dWraE55/3Ky6lWmqhiEjwtm3zfe033oCUFLjuuqArigsKcBEJ1qpVcOGFsHgxPPSQwvswKMBFJDgLFsDQoX55/FtvwZAhQVcUV9QDF5HgtG7t53LPnavwrgUFuIhEl3Mwfbrfy7tLF5g3D044Ieiq4pICXESip6QErr3Wr6585RV/zSzQkuKZeuAiEh2FhTBiBMyZA3fc4Q8gljpRgItI5C1d6pfF5+dXXhYvdaIAF5HIW78edu3SsvgwUw9cRCJnwQL/+Xvfg2++UXiHmQJcRMJv924YPx569/ajbvAHEEtYHTLAzayZmf3XzBaZ2RIzuyN0vYuZfWJm35rZP8ysSeTLFZGYt3UrDB8ODz4IP/85DBgQdEX1Vk1G4CXAQOfcScDJwBAz6wv8AXjAOXcMsAkYE7EqRSQ+rFrlA/udd+Avf4EpU6CxbrVFyiED3HnbQg8TQx8OGAi8HLr+DDA8EgWKSBx57z1YscIvi//pT4Oupt6rUQ/czBqZ2UJgAzAD+A7Y7JwrCz1lNZAWkQpFJPatX+8/jxkDy5bBuecGW08DUaMAd87tds6dDKQDpwLH1fQNzGysmeWaWW5BQUHtqhSR2OScP5PymGNgyRJ/7cgjg62pATmsWSjOuc3AB0A/oLWZ7WlupQP51bxmqnMu2zmXnZqaWpdaRSSWlJTANdfA7bfDRRfB0UcHXVGDU5NZKKlm1jr0dXNgMLAUH+R71sJeA7weoRpFJNYUFvozK597Dn73O/9Z0wSjria3hzsCz5hZI3zgv+ice9PMvgReMLO7gAXAExGsU0RiyZ//DLm58MILcMUVQVfTYJlzLmpvlp2d7XJzc6P2fiISZiUl0LQplJbCV19Bz55BV9QgmNl851z2/te1ElNEauaRR6BHD9iwARITFd4xQAEuIge3Z1n8T34C3bqp1x1DtERKRKq3dSuMGuUX5tx8M/zpT9CoUdBVSYgCXESqd8st8O678Ne/+hG4xBQFuIgcyDl/1NnkyX6WycCBQVckVVAPXKShy8mBrCxISPCfb7oJhg71BzC0a6fwjmEagYs0ZDk5MHYsFBf7xytXwsMPQ9eusH07NNEu0bFMI3CRhmzSpL3hva+SEmjTJvr1yGFRgIs0ZHl5VV9ftSq6dUitKMBFGrLOnau+npER3TqkVhTgIg3Rtm1w7bV+B8GkpMrfS0rys08k5inARRqazz+HU06BZ5+FM86AqVMhM9NPG8zM9I9Hjw66SqkBzUIRaSicg0cfhXHj/A3KmTP3ThFUYMcljcBFGoq1a+HWW+Gss2DRIs3vrgc0Ahep777+2s/r7tQJ5s2D447zi3Yk7un/RZH6yjm4/36/BexTT/lr3bsrvOsRjcBF6qPCQj/L5K23YPhw/yH1jv4pFqlv5syBk0+GGTP80WevvgpHHBF0VRIBGoGL1DfbtkGLFvDGG9C7d9DVSARpBC5SH6xb5w8YBhgyBL74QuHdACjAReLdjBlw0kl+V8GNG/21xMRga5KoUICLxKuyMrjtNjj3XL9v98cfQ9u2QVclUaQeuEg82r0bzj4bPvoIfvQjmDLlwD1NpN5TgIvEo0aNYMQIuOEGf+iwNEgKcJF4UVICEyfCoEFwwQX+lHhp0NQDF4kH330H/fvDgw/Cp58GXY3ECI3ARWLdCy/4GSaNG8P06VpVKRU0AheJZbNn+x53jx6wcKHCWypRgIvEoj0HDZ9xhj85/qOPdMyZHEABLhJLnIMnn4QuXWDZMn9KzpVXamGOVEkBLhIrtm6Fq6+GMWN8yyQ5OeiKJMYpwEViwcKF0KcPTJsGd94J770HHTsGXZXEOM1CEYkFTz7p+94ffABnnhl0NRInNAIXCcqmTfDVV/7rP/7
|
||
|
|
"text/plain": [
|
||
|
|
"<Figure size 432x288 with 1 Axes>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
"metadata": {
|
||
|
|
"needs_background": "light"
|
||
|
|
},
|
||
|
|
"output_type": "display_data"
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"source": [
|
||
|
|
"import matplotlib.pyplot as plt\n",
|
||
|
|
"x = [1, 2, 3, 4, 5, 6, 7, 8]\n",
|
||
|
|
"y1 = [2, 5, 9, 14, 20, 27, 35, 44]\n",
|
||
|
|
"y2 = [1, 2, 3, 4, 5, 6, 7, 8]\n",
|
||
|
|
"\n",
|
||
|
|
"plt.plot(x, y1, color='red', marker='o', linestyle='dashed')\n",
|
||
|
|
"plt.plot(x, y2, color='green', marker='o', linestyle='dashed')"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "monthly-instrument",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Na powyższym wykresie widać zależność pomiędzy stopniem wielomianu (oś x), a liczbą wymaganych do obliczenia jego wartości operacji mnożenia (oś y)."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"id": "published-developer",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"czerwony - Tradycyjna metoda \n",
|
||
|
|
"zielony - schemat Hornera"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {
|
||
|
|
"kernelspec": {
|
||
|
|
"display_name": "Python 3",
|
||
|
|
"language": "python",
|
||
|
|
"name": "python3"
|
||
|
|
},
|
||
|
|
"language_info": {
|
||
|
|
"codemirror_mode": {
|
||
|
|
"name": "ipython",
|
||
|
|
"version": 3
|
||
|
|
},
|
||
|
|
"file_extension": ".py",
|
||
|
|
"mimetype": "text/x-python",
|
||
|
|
"name": "python",
|
||
|
|
"nbconvert_exporter": "python",
|
||
|
|
"pygments_lexer": "ipython3",
|
||
|
|
"version": "3.9.2"
|
||
|
|
}
|
||
|
|
},
|
||
|
|
"nbformat": 4,
|
||
|
|
"nbformat_minor": 5
|
||
|
|
}
|