piatok, 17 apríl 2015 08:00 Written by 3126 times
Rate this item
(2 votes)

C# - Hornerova schéma

V numerickej matematike je Hornerova schéma ( tiež Hornerov algoritmus či Hornerova metóda ) názov algoritmu pre efektívne vyhodnocovanie polynómov. V tomto článku sa pokúsime vytvorit program, ktorý vypočíta korene polynómu n-tého rádu pomocou Hornerovej schémy.

Ako funguje Hornerová schéma si môžeme pozrieť na videu :

K vysvetleniu videa vyššie, majme polynom n-tého radu :

f(x0) = a0 + a1x0 + a2x02 + ... + anx0n

ktorý prepíšeme na tvar :

f(x0) = a0 + x0(a1 + x0(a2 + x0(a3 + ... + (an-1 + anx0)....)

Prepišme si do tabuľky polynom 5 rádu :

K 5 4 3 2 1 0
  b5 = a5 b4 = a4 + x0b5 b3 = a3 + x0b4 b2 = a2 + x0b3 b1 = a1 + x0b2 b0 = a0 + x0b1

Príklad :

f(x) = x4 + 3x3 + 5x2 + 7x + 9 pre x = 2

Riešenie :

K 4 3 2 1 0
Step b4 = 1 b3 = 3 + 2 * 1 b2 = 5 + 2 * 5 b1 = 7 + 2 * 15 b0 = 9 + 2 * 37
Result 1 5 15 37 83

Výsledok polynomu pre x =2 je  f(2) = 83. Ak by bol vysledok pre x = 2 rovný 0 , tak sme našli koreň polynomu.

Príklad z videa :

f(x) = x3 - 6x2 + 11x - 6


Možné korene polynomu su delitele císla -6 , čiže (+/-6), (+/-3),(+/-2),(+/-1)

Spravme si teda metódu na výpočet deliteľov celého čísla v c# :

private IEnumerable<int> getDivisors(int n)
{
	if (n == 0)
		return (IEnumerable<int>)new int[] { 0 };
	else
		return Enumerable.Range(-Math.Abs(n), 2 * Math.Abs(n) + 1)
			.Where(a => a != 0)
			.Where(a => (n % a) == 0);
}

 Overíme všetky možné korene pomocou Hornerovej schémy. Na to použijeme nasledujúci kód :

private bool findRootWithHornerScheme(int[] coefficientsA, int x, out int[] coefficientsB)
{
	var lenght = coefficientsA.Length;
	var tmpB = new int[lenght];
	coefficientsB = new int[lenght - 1];
	tmpB[0] = coefficientsA[0];
	for (int i = 1; i < lenght; i++)
	{
		tmpB[i] = tmpB[i - 1] * x + coefficientsA[i];
	}
	//ak je posledny koefiecient B == 0 ,tak zadane x je korenom polynomu
	if (tmpB[lenght - 1] == 0)
	{
		Array.Copy(tmpB, coefficientsB, lenght - 1);
		return true;//bol najdeny koren
	}
	//nebol najdeny koren a metoda vrati false
	return false;
}

Ak je posledný koefiecient B == 0 ,tak zadané x je koreňom polynomu. Nové koeficienty B použije na výpočet ďalšieho koreňa. Výsledný program by mohol vyzerať nejak takto:

horner

 

 Kompletné zdrojové kódy si môžete stiahnuť v prílohe.

Last modified on piatok, 17 apríl 2015 09:40
Ing.Jaroslav Vadel

Som zakladateľom www.projectik.eu.

Hram sa na programatora, ktory ovlada c#,cpp,java,unity3d,php,html,NI testand... ..."Naprogramovat program,ktory funguje vie kazdy. Ale to,ze program funguje este neznamena,ze je napisany spravne "..

Website: www.projectik.eu