C++’da Horner Kuralıyla Verimli Polinom Değerlendirmesi

Horner yöntemi, polinomları değerlendirmek için, gerekli çarpma işlemlerini en aza indirgeyerek verimli bir yol sunar. Bu, özellikle yüksek dereceli polinomlar için, basit yaklaşımla karşılaştırıldığında performansı önemli ölçüde iyileştirir. Bu makale, aşağıdaki formdaki bir polinomu değerlendirmek için Horner kuralının çeşitli C++ uygulamalarını ele almaktadır:

P(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀

İçerik Tablosu

• Yinelemeli Yaklaşım (Geriye Doğru Döngü)
• Yinelemeli Yaklaşım (İleriye Doğru Döngü)
• Özyinelemeli Yaklaşım
• Sonuç

Yinelemeli Yaklaşım (Geriye Doğru Döngü)

Bu uygulama, geriye doğru yineleyen bir döngü kullanarak Horner kuralının iç içe geçmiş çarpma yapısını doğrudan yansıtır.

#include <iostream>
#include <vector>

double hornerBackward(const std::vector<double>& coefficients, double x) {
  double result = coefficients.back(); 
  for (int i = coefficients.size() - 2; i >= 0; --i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerBackward(coefficients, x);
  std::cout << "Polinomun x = " << x << " değerindeki değeri: " << result << std::endl;
  return 0;
}

Yinelemeli Yaklaşım (İleriye Doğru Döngü)

Geriye doğru yineleme daha sezgisel olsa da, ileriye doğru döngü de aynı derecede verimlidir. Bu sürüm, sabit terimden başlayarak sonucu artımlı olarak oluşturur.

#include <iostream>
#include <vector>

double hornerForward(const std::vector<double>& coefficients, double x) {
  double result = coefficients[0];
  for (size_t i = 1; i < coefficients.size(); ++i) {
    result = result * x + coefficients[i];
  }
  return result;
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerForward(coefficients, x);
  std::cout << "Polinomun x = " << x << " değerindeki değeri: " << result << std::endl;
  return 0;
}

Özyinelemeli Yaklaşım

Horner kuralı, iç içe geçmiş çarpma yapısını doğrudan yansıtarak zarif bir şekilde özyinelemeli olarak uygulanabilir. Bununla birlikte, çok yüksek dereceli polinomlar için, fonksiyon çağırma yükü performansı etkileyebilir.

#include <iostream>
#include <vector>

double hornerRecursive(const std::vector<double>& coefficients, double x, int n) {
  if (n == 0) {
    return coefficients[0];
  } else {
    return x * hornerRecursive(coefficients, x, n - 1) + coefficients[n];
  }
}

int main() {
  std::vector<double> coefficients = {2, -6, 2, -1}; 
  double x = 3;
  double result = hornerRecursive(coefficients, x, coefficients.size() - 1);
  std::cout << "Polinomun x = " << x << " değerindeki değeri: " << result << std::endl;
  return 0;
}

Sonuç

Bu makale, Horner kuralının üç C++ uygulamasını sundu: yinelemeli (geriye ve ileriye doğru döngüler) ve özyinelemeli. Özyinelemeli yaklaşım zarafet sunarken, yinelemeli yöntemler, özellikle daha büyük polinomlar için, azaltılmış yük nedeniyle genellikle daha iyi performans sağlar. En uygun seçim, uygulamanızın belirli ihtiyaçlarına ve tercihlerine bağlıdır; ancak, Horner kuralını anlamak, verimli polinom değerlendirmesi için önemlidir.