Horner算法

Question

我對我的控制檯程序有疑問。 它必須使用Horner算法來計數。沒有異常拋出，但是，它並沒有給出正確的結果。

如果有人可以幫助我，我將非常感激，因爲我不知道該怎麼辦......

這裏是我的程序的代碼：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Consola_Horner_Rekurencyjnie 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int n; 

      Console.WriteLine("Podaj stopień wielomioanu: "); 
      n = Convert.ToInt32(Console.ReadLine()); 

      int[] a = new int[++n]; 

      Console.WriteLine("Podaj wartosc a: "); 

      for (int i = 0; i < n; i++) 
      { 
       Console.WriteLine("a [" + i + "] = "); 
       a[i] = Convert.ToInt32(Console.ReadLine()); 
      } 

      int x; 

      Console.WriteLine("Podaj x:"); 
      x = Convert.ToInt32(Console.ReadLine()); 

      int Horner; 
      Horner = a[0]; 

      for (int i = 1; i < n; i++) 
      { 
       Horner = Horner * (i - 1) * x + a[i]; 
      } 

      Console.WriteLine("Wynik to:" + Horner); 
      Console.ReadLine(); 
     } 
    } 
} 

這是第二個選項計算代碼，但數都是錯誤的：

Func<int, int> Horner = null; 
Horner = (i) => (i == 0) ? a[0] : Horner(i - 1) * x + a[i]; 

Console.WriteLine("Wynik to:" + Horner(x)); 
Console.ReadLine(); 

我想重寫從C + +（在遞歸算法的形式）的原代碼。

原來的代碼如下所示：

int Horner; 
int n; 
int *a = new int[n]; 
int x; 


int main() 
{ 

     cout <<"Podaj stopień wielomianu: "; 
     cin >> n; 
     cin.ignore(); 


     cout << "Podaj wartość a: \n"; 
     for (int i = 0; i <= n; i++) 
     { 
      cout <<"a[" <<i<<"] = "; 
      cin >> a[i]; 
      cin.ignore(); 
     } 

     cout <<"Podaj x: "; 
     cin >> x; 
     cin.ignore(); 

     cout <<"Wynik to: " << Horner(n); 

     getchar(); 
     return 0; 
} 

int Horner (int i) 
{ 
     if (i == 0) 
      return a[0]; 
     else 
      return Horner (i - 1) * x + a[i]; 
} 

我已經不知道該怎麼辦呢？仍然徘徊在同一個地方......

Answer 1

你unnecesarily通過(i-1)在乘以你的循環。

將其更改爲：

 int Horner; 
     Horner = a[0]; 


     for (int i = 1; i < n; i++) 
     { 
      Horner = Horner * x + a[i]; 
     } 

甚至更​​好：

 int Horner = 0; 

     foreach (int wspolczynnik in a) 
     { 
      Horner = Horner * x + wspolczynnik; 
     } 

你可能看到一些實現，有Horner(i-1) * x + a(i)，但(i-1)在這種情況下數組索引，而不是一個乘數。

編輯：

在另一方面你的遞歸版本需要一個參數 - 多項式的程度，而你試圖用X來調用它。用n做！

int result = Horner(n); 

IMO這將是如果它花了2個參數更加清晰 - 多項式的程度，以及x：

Func<int, int, int> Horner = null; 
Horner = (i, x) => (i == 0) ? a[0] : Horner(i - 1, x) * x + a[i]; 

int result = Horner(n, x); 

Answer 2

我發現這裏在C＃中 「好」 的源代碼Horner scheme：

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