تقييم كثيرات الحدود بكفاءة باستخدام قاعدة هورنر في C++

توفر طريقة هورنر طريقة فعالة لتقييم كثيرات الحدود، مع تقليل عدد عمليات الضرب المطلوبة. وهذا يحسن الأداء بشكل كبير مقارنة بالطريقة البسيطة، خاصةً بالنسبة لكثيرات الحدود ذات الدرجات العالية. تستعرض هذه المقالة عدة تنفيذات بلغة C++ لقاعدة هورنر لتقييم كثيرة حدود بالشكل:

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

محتويات

• الطريقة التكرارية (حلقة عكسية)
• الطريقة التكرارية (حلقة أمامية)
• الطريقة التراجعية
• الخلاصة

الطريقة التكرارية (حلقة عكسية)

يعكس هذا التنفيذ مباشرةً بنية الضرب المتداخلة لقاعدة هورنر باستخدام حلقة تكرارية عكسية.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

الطريقة التكرارية (حلقة أمامية)

في حين أن التكرار العكسي أكثر وضوحًا، إلا أن الحلقة الأمامية بنفس الكفاءة. يبدأ هذا الإصدار من الحد الثابت، ويبني النتيجة بشكل تدريجي.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

الطريقة التراجعية

يمكن تنفيذ قاعدة هورنر بشكل أنيق تراجعيًا، مما يعكس مباشرةً بنية الضرب المتداخلة. ومع ذلك، بالنسبة لكثيرات الحدود ذات الدرجات العالية جدًا، قد يؤثر عبء استدعاء الدالة على الأداء.

#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 << "The value of the polynomial at x = " << x << " is: " << result << std::endl;
  return 0;
}

الخلاصة

قدمت هذه المقالة ثلاثة تنفيذات بلغة C++ لقاعدة هورنر: تكرارية (حلقات أمامية وعكسية) وتراجعية. في حين أن النهج التراجعي يوفر أناقة، فإن الأساليب التكرارية توفر بشكل عام أداءً أفضل، خاصةً بالنسبة لكثيرات الحدود الأكبر، نظرًا لانخفاض العبء الإضافي. يعتمد الخيار الأمثل على احتياجات وتفضيلات تطبيقك المحددة؛ ومع ذلك، فإن فهم قاعدة هورنر أمر أساسي لتقييم كثيرات الحدود بكفاءة.