Obliczanie wartości wielomianu- schemat Hornera
Schemat Hornera ma zastosowanie na przykład w algorytmie szybkiego potęgowania jak i w algorytmie obliczania wartości wielomianu. Wielomian stopni an można zapisać w ogólnej postaci:
Chcąc obliczyć wartość (y) wielomianu dla podanego x i znanych współczynników a(i) według schematu Hornera stosujemy poniższe podejście
Powyższą zależność można zrealizować na dwa sposoby przez zastosowanie iteracji oraz przez zastosowanie rekurencji. W obu algorytmach zastosowano listę do przechowywania kolejnych współczynników. Stopień wielomianu ustalany jest w kodzie programu poprzez odczytanie rozmiaru listy (ilości elementów). Oznacza to, że przy braku i-tego współczynnika należy podać zero.
Schemat algorytmu obliczania wartości wielomianu (metoda iteracyjna)
Kod funkcji realizujący obliczanie wartości wielomianu w sposób iteracyjny zapisany w języku C#
Wskazówka:
int wieIte(int x,List<int> w)
{
int y = w[0];
for(int i=1; i<w.Count;i++)
y=y*x+w[i];
return y;
}
Schemat algorytmu obliczania wartości wielomianu (metoda rekurencyjna)
Kod funkcji realizujący obliczanie wartości wielomianu w sposób rekurencyjny zapisany w języku C#
Wskazówka:
int wieRek(int x,int i,List<int> w)
{
if (i > 0) { return wieRek(x, i - 1, w) * x + w[i]; }
return w[0];
}
Przykładowa aplikacja wykorzystująca oba rozwiązania
Pełny kod klasy Form formatki utworzonej aplikacji
Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _17AlgWspWielomianu
{
public partial class Form1 : Form
{
int x;//wartość argumentu wielomianu
int n = 0;//stopień wielomianu
//lista współczynników wielomianu
List<int> wsp = new List<int>();
int wieIte(int x,List<int> w)
{
int y = w[0];
for(int i=1; i<w.Count;i++)
y=y*x+w[i];
return y;
}
int wieRek(int x,int i,List<int> w)
{
if (i > 0) { return wieRek(x, i - 1, w) * x + w[i]; }
return w[0];
}
public Form1()
{
InitializeComponent();
}
void wczytajWspolczynniki(List<int> w,TextBox tb,Label lb)
{
if (tb.Text.Length < 1) return;
//czyść listę
w.Clear();
lb.Text = null;
//ustal stopien wielomianu przez zliczenie linii
//domyslni ezakładamy, że nie ma pustych linii
n = tb.Lines.Count() - 1;
//ładuje nowe współczynniki
for (int i = 0; i < tb.Lines.Count(); i++)
{
String s = tb.Lines[i].ToString();
if (Int32.TryParse(s,out int j))
{
w.Add(j);
string plus = "+";
if (i == n) plus = " ";
lb.Text += w[w.Count-1].ToString() + "x^" + (n - i).ToString() + plus;
}
}
}
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{ //wyskocz na BackSpcae, Enter lub minus
if (e.KeyChar == 8 || e.KeyChar == 13 || e.KeyChar=='-') return;
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled=true;//blokuj nienumeryczne
}
private void textBox1_KeyUp(object sender, KeyEventArgs e)
{
if (e.KeyValue == 8 || e.KeyValue == 13 || e.KeyValue == '-') return;
wczytajWspolczynniki(wsp, textBox1, label3);
}
private void button1_Click(object sender, EventArgs e)
{
if (textBox2.Text.Length < 1) return;
x = int.Parse(textBox2.Text);
MessageBox.Show(
wieIte(x, wsp).ToString(),
"Wartość wielomianu",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
private void button2_Click(object sender, EventArgs e)
{
if (textBox2.Text.Length < 1) return;
x = int.Parse(textBox2.Text);
MessageBox.Show(
wieRek(x,wsp.Count-1,wsp).ToString(),
"Wartość wielomianu",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
}
}
