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:

postać wielomianu wzór ogólny Visual studio C#

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

postać wielomianu schemat Hornera Visual studio C#

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

aplikacja obliczajaca wartośc wielomianu schemat hornera Visual studio C#

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
            );
        }
    }
}