horner數據結構

Question

嗨 我有一個問題，我們如何使用Horner數據結構來顯示一個多項式，就像「x^100+1」？

例如用於上述多項式我們 需要尺寸101的陣列，其它的索引 示出了該多項式的功率 例如用於陣列[100] = 1和陣列[0] = 1，不幸的是所有的其他指標是0！但有另一種 的方式，這是不同的， 有助於顯示在一個小的 陣列的多項式！我想知道，這樣

感謝

Answer 1

霍納方案（HTTP： //en.wikipedia.org/wiki/Horner_scheme）是表示多項式的另一種方式，但由於信息內容相同，所以需要相同數量的信息（相同的數組大小）。唯一的區別是我們計算多項式時的排序。

p(x) = (...((a[n] * x + a[n-1]) * x + a[n-2]) ...) * x + a[0] 

在你的例子中，我們將再次有一個[100] = 1，a [0] = 1，其餘爲零。

在這種情況下，計算多項式的代碼將

result = a[n]; 
for(int i=n-1;i>=0;i--) { 
    result = result * x + a[i]; 
} 

Answer 2

一般的形式

A * x^n + B * x^n-1 + .... 

的多項式你只需要知道n和商店（A，B，...）爲你可以使用數組或列表。爲了表示，所有你需要的是n和這個列表。 我不知道，如果你有興趣的評價，但它會是這樣的

ArrayList<int> list = new ArrayList<int>(); 

填充列表與A，B，...

int result; 

for(int i=0; i<n; i++) 
    result+= list.get(i) * Math.pow(valueOfX, n-i);