пятница, 14 сентября 2012 г.

Деление многочлена на многочлен

Вот здесь, на форуме MSDN. Задали вопрос, есть ли на C# библиотека умеющая делить многочлен на многочлен. Началось обсуждение. Т.к. сходу готовой библиотеки, удовлетворяющей требованиям нет, то пусть она теперь будет.

Ок, деление многочлена на многочлен, весьма просто, поэтому я решил и накропать соответствующую библиотечку.
Класс реализующий логику деления получился вот такой:

///
/// Класс, для реализации метода деления многочлена на многочлен
///
public static class MyMath
{
    ///
    /// Метод деления многочлена на многочлен
    ///
    /// Коэффициенты многочлена делимого, индекс в массиве - степень элемента многочлена
    /// Коэффициенты многочлена делителя, индекс в массиве - степень элемента многочлена
    /// Коэффициенты многочлена частного, индекс в массиве - степень элемента многочлена
    /// Коэффициенты многочлена остатка, индекс в массиве - степень элемента многочлена
    public static void Deconv(double[] dividend, double[] divisor, out double[] quotient, out double[] remainder)
    {
        if (dividend.Last() == 0)
        {
            throw new ArithmeticException("Старший член многочлена делимого не может быть 0");
        }
        if (divisor.Last() == 0)
        {
            throw new ArithmeticException("Старший член многочлена делителя не может быть 0");
        }
        remainder = (double[])dividend.Clone();
        quotient = new double[remainder.Length - divisor.Length + 1];
        for (int i = 0; i < quotient.Length; i++)
        {
            double coeff = remainder[remainder.Length - i - 1] / divisor.Last();
            quotient[quotient.Length - i - 1] = coeff;
            for (int j = 0; j < divisor.Length; j++)
            {
                remainder[remainder.Length - i - j - 1] -= coeff * divisor[divisor.Length - j - 1];
            }
        }
    }
}


Как можно этим воспользоваться:

static void Main(string[] args)
{
    // 2*x^2+4*x+3
    double[] dividend = { 3, 4, 2};
    // 2*x+1
    double[] divisor = { 1, 2 };
    double[] quotient;
    double[] remainder;

    MyMath.Deconv(dividend, divisor, out quotient, out remainder);
    Console.WriteLine("Частное:");
    for (int i = 0; i < quotient.Length; i++)
    {
        if (quotient[quotient.Length - i - 1] != 0)
        {
            Console.Write("{0}{1}*x^{2}", quotient[quotient.Length - i - 1] >= 0 ? "+" : "", quotient[quotient.Length - i - 1], quotient.Length - i - 1);
        }
    }
    Console.WriteLine();
    Console.WriteLine("Остаток:");
    for (int i = 0; i < remainder.Length; i++)
    {
        if (remainder[remainder.Length - i - 1] != 0)
        {
            Console.WriteLine("{0}{1}*x^{2}", remainder[remainder.Length - i - 1] >= 0 ? "+" : "", remainder[remainder.Length - i - 1], remainder.Length - i - 1);
        }
    }
    Console.ReadKey();
}
Поделив многочлен на многочлен в блокнотике и запустив программу, я получил правильный результат:
Вот и отвлекся на 20 минут от работы ))
Пошел дальше дела делать.

4 комментария:

  1. Подскажите, если в текстбокс выводить значения эти. как лучше сделать?
    textbox += не подходит ведь

    ОтветитьУдалить
    Ответы
    1. Подходит, просто вместо:
      Console.WriteLine("{0}{1}*x^{2}", remainder[remainder.Length - i - 1] >= 0 ? "+" : "", remainder[remainder.Length - i - 1], remainder.Length - i - 1);
      Надо писать:
      textbox += string.Format("{0}{1}*x^{2}", remainder[remainder.Length - i - 1] >= 0 ? "+" : "", remainder[remainder.Length - i - 1], remainder.Length - i - 1);

      Удалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить
  3. Подскажите, такой вопрос: есть два операнда. Double x=a+b. С какой точностью будет посчитан результат? В IEEE 754 пишут про 1.11е-16. На сайте о двоичной арифметике есть кое-что поясняющее, но здесь не до конца понятно. Якобы это зависит от типа операций.
    Т.е. мы получаем результат, а вот насколько он точен? Как посчитать возможную погрешность?

    ОтветитьУдалить