Квадратное уравнение? Да раз плюнуть!

    Бытует мнение, что только 10% программистов способны написать двоичный поиск. Это мнение мы испытывать не будем, но что насчёт квадратного уравнения?

    Поставим задачу конкретнее: решение квадратного уравнения вида ax2+bx+c=0 с целочисленными коэффициентами. На вход подаются три целых числа в рамках int (коэффициенты a, b и c). Программа должна всегда выдавать результат.
    Казалось бы, плёвое дело: пять минут и готово! И вот спустя те самые пять минут имеем на выходе следующий код:
    Код
    int a, b, c;
    std::cin >> a >> b >> c;
    
    long long discriminant = b*b - 4*a*c;
    
    if (discriminant > 0)
      std::cout << "D > 0; 2 корня:\n"
                << "x1 = " << (-b + sqrt(discriminant))/(2*a) << "\n"
                << "x2 = " << (-b - sqrt(discriminant))/(2*a) << std::endl;
    else if (discriminant == 0)
      std::cout << "D = 0; 1 корень:\n"
                << "x = " << -1.*b/(2*a) << std::endl;
    else if (discriminant < 0)
      std::cout << "D < 0; нет корней." << std::endl;
    
    Всё здорово? Как бы не так. «Заказчик», пятиклассник Петя, недоволен: на его ввод программа выдала какие-то «nan» и «inf».
    0 -1 -1
    D > 0; 2 корня:
    x1 = inf
    x2 = nan
    

    Пожимаем плечами, добавляем условие для вырожденного случая:
    Код
    if (a == 0)
    {
      if (b != 0)
        std::cout << "a = 0; уравнение вырождается в линейное:\n"
                  << "x = " << -1.*c/b << std::endl;
      else if (c == 0)
        std::cout << "Все коэффициенты равны нулю; x - любое число." << std::endl;
      else
        std::cout << "Нет решений." << std::endl;
    }
    else
    {
      // Предыдущий код, начиная с дискриминанта.
    }
    
    Стало лучше? А вот и нет.
    1 0 -2
    D > 0; 2 корня:
    x1 = 1.41421
    x2 = -1.41421
    
    49 7 -2
    D > 0; 2 корня:
    x1 = 0.142857
    x2 = -0.285714
    
    За такие ответы Петю в школе отругали: корень должен оставаться корнем, дробь — дробью. Чешем в затылке, вздыхаем и берёмся за код; структура за структурой, функция за функцией он распухает раз в десять, но основная функция при этом остаётся относительно неизменной, хотя и сильно прибавила в весе.
    Код
    Весь код этого этапа.
    if (a == 0)
    {
      if (b != 0)
        std::cout << "a = 0; уравнение вырождается в линейное:\n"
                  << "x = " << fraction(-c,b).toString() << std::endl;
      else if (c == 0)
        std::cout << "Все коэффициенты равны нулю; x - любое число." << std::endl;
      else
        std::cout << "Нет решений." << std::endl;
    }
    else
    {
      long long discriminant = b*b - 4*a*c;
    
      if (discriminant > 0)
      {
        std::cout << "D > 0; 2 корня:\n";
    
        radical dRoot (discriminant);
    
        if (dRoot.isInteger())
        {
          std::cout << "x1 = " << fraction(-b + sqrt(discriminant), 2*a).toString() << "\n"
                    << "x2 = " << fraction(-b - sqrt(discriminant), 2*a).toString() << std::endl;
        }
        else
        {
          std::string rational = fraction(-b, 2*a).toString(),
                      irrational = fraction(radical(discriminant), 2*a).toString();
          if (rational == "0")
            std::cout << "x1 = " << irrational << "\n"
                      << "x2 = " << "- " << irrational << std::endl;
          else
            std::cout << "x1 = " << rational << " + " << irrational << "\n"
                      << "x2 = " << rational << " - " << irrational << std::endl;
        }
      }
      else if (discriminant == 0)
        std::cout << "D = 0; 1 корень:\n"
                  << "x = " << fraction(-b, 2*a).toString() << std::endl;
      else if (discriminant < 0)
        std::cout << "D < 0; нет корней." << std::endl;
    }
    
    1 0 -2
    D > 0; 2 корня:
    x1 = ┐/2
    x2 = - ┐/2
    
    49 7 -2
    D > 0; 2 корня:
    x1 = 1/7
    x2 = -2/7
    
    Петя доволен, Петя принёс из школы пятёрку по математике родителям и шоколадку нам.
    Прошло пять лет. Пётр перешёл в десятый класс. Там на уроке алгебры ему поведали о мнимых и комплексных числах. Откопав где-то на диске нашу программу, он пытается с её помощью — негодяй! — сделать домашнее задание. Но что это?
    1 0 25
    D < 0; нет корней.
    
    Негодующий Пётр приносит нам программу на доделку. Спустя пару часов чтения старого кода понимаем, что проблема решается… добавлением пары строк (честно говоря, я сам не ожидал).
    Код
    if (discriminant != 0)
    {
      std::cout << "D != 0; 2 корня:\n";
    
      radical dRoot (discriminant);
    
      if (dRoot.isInteger())
      {
        std::cout << "x1 = " << fraction(-b + sqrt(discriminant), 2*a).toString() << "\n"
                  << "x2 = " << fraction(-b - sqrt(discriminant), 2*a).toString() << std::endl;
      }
      else
      {
        std::string rational = fraction(-b, 2*a).toString(),
                    irrational = fraction(radical(discriminant), 2*a).toString();
        if (rational == "0")
          std::cout << "x1 = " << irrational << "\n"
                    << "x2 = " << "- " << irrational << std::endl;
        else
          std::cout << "x1 = " << rational << " + " << irrational << "\n"
                    << "x2 = " << rational << " - " << irrational << std::endl;
      }
    }
    else if (discriminant == 0)
      std::cout << "D = 0; 1 корень:\n"
                << "x = " << fraction(-b, 2*a).toString() << std::endl;
    

    1 0 25
    D != 0; 2 корня:
    x1 = i*5
    x2 = - i*5
    
    1 2 53
    D != 0; 2 корня:
    x1 = -1 + i*2┐/13
    x2 = -1 - i*2┐/13
    

    Петя заканчивает школу с пятёркой в аттестате, поступает в престижный университет и вылетает после первой же сессии.
    Конец.
    Итоговый код.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 61

      +25
      Если дискриминант равен 0, то у уравнения 2 корня, но одинаковых. Будем учить хорошему=)
        0
        Таки да. С этим промашка вышла :)
          –6
          Если учить хорошему, то если дискриминант меньше 0, то нету корней только области вещественных чисел, в области комплексных чисел существуют корни.
            +11
            Или можно было дочитать пост до конца.
              +11
              Это конечно проблема, да.
            +2
            То есть, другими словами, график соответствующей функции пересекает ось абсцисс в одной и той же точке два раза? О_о
              +6
              Это называется не так: количество корней многочлена степени n равна n (учитывая кратность). То бишь корень один, а вот кратность у него 2.
            +6
            Эх… а нам в школе в десятом классе не рассказывали о комплексных числах
              +2
              В седьмом классе в учебнике был параграф со звёздочкой, где рассказали что такое и как обращаться. Школьнику вполне достаточно.
              +2
              А почему коэффициенты int? Чтобы дискриминант влез в long long и не заморачиваться с длинной арифметикой?
              А почему коэффициенты целочисленные? Почему не вещественные. Там ведь такой простор для ошибок. Сравнение с нулем, потеря точности при вычислении дискриминанта и т.д.
                +1
                С вещественными коэффициентами всё очень и очень плохо: в условии могут быть и дроби, и корни самых разных степеней, и мнимые числа, и прочая, и прочая, и прочая. Заморачиваться с парсингом и длинной арифметикой? Зачем?
                  +1
                  А то. Добавить погрешности при работе с вещественными… и задача превращается в огромного, злобного монстра…
                +10
                По следам Итхеппенса?
                  +4
                  Здесь специально для не читавших ITHappens поясню, что речь идёт об истории http://ithappens.ru/story/10776 на ITHappens.
                    0
                    Хм. А я ведь её читал. Видно, отложилось где-то в памяти :)
                  0
                  Ох, помню тоже писал подобное…
                  Только на скриптовом языке для AVZ, когда на virusinfo проходил обучение :)
                    +2
                    Сегодня преподу как раз сдавал лабу, там в одном месте надо было решить квадратное уравнение с комплексными корнями. Решил в Wolfram Mathematica, показал ему. Он спрашивает: «А вы вручную считать умеете? А то большинство ваших коллег уже забыли, как такое на листике считать». Стало обидно за даржаву — написал ему решение на листочке :)
                      0
                      А вы квадратный корень в столбик считать умеете? :D Студенты очень удивились, когда я показал, как это делается…
                        0
                        Я по мотивам этого пытаюсь в уме научиться извлекать, но дальше трёх значащих цифр не идёт особо.
                          0
                          В уме лучше работает просто метод Ньютона: меньше информации приходится запоминать одновременно (только исходное число и текущее приближение корня), соответственно, меньше опасность ошибиться (и больше шансов ошибку исправить). С одной стороны, получается дольше, каждый раз приходится возводить в квадрат заново, с другой — можно получить больше дополнительных цифр. Тем более, что дальше пяти цифр результата пройти сложно :)
                          +1
                          Честно признаюсь: в школе умел, но сейчас уже забыл )
                            0
                            Для этого есть логарифмическая линейка.
                              +1
                              На ней даже три знака получить трудно — максимум, два с половиной. А от студентов требовалась тысяча — вот они и интересовались, как её лучше посчитать. Без использования чужой длинной арифметики.
                                0
                                Так для этого и калькулятор подойдёт, причём любой.
                                  0
                                  Вот я вроде старше вас лет на десяток, но никто никогда не учил меня пользоваться логарифмической линейкой… Я о ней читал и даже на бумаге рисовал (был у меня бзик рисовать на бумаге программы для различных средств ВТ), но логарифмы считал либо на электронном калькуляторе, либо по таблицам синусов и косинусов. В любом случае результатом были десятичные дроби ограниченной разряда этак до четвертого после запятой точности.
                                    0
                                    Я линейкой пользоваться сам учился. Было очень интересно, и на физике помогало. А калькулятора тогда у нас не было.
                                      0
                                      Я тоже же сам учился по картинкам — у нас в учебнике алгебре главы были… Но нам линейки не давали, а «давали» только калькуляторы,.
                                      0
                                      А мне логарифмическая линейка случайно в руки попалась (дома лежала где-то), вместе с книжкой где полностью описывались правила всяких действий на ней, вплоть до самых продвинутых. Хотя особой нужды в этом не было, но пользоваться ей научился =) Основные действия и сейчас помню. Вот таблицы различных функций уже, можно сказать, не застал (младше вас почти на 20 лет).
                                        0
                                        Я из школы выпустился два года назад, но таблицы Брадиса у нас там были, и нас учили ими пользоваться.
                                        Ой, так мы ж с вами одногодки практически.
                                          0
                                          Увы, мой отец был юристом, а мать сетевязом…
                                          0
                                          Нас учили в школе, как и таблицам и всем возможным столбикам, класс математический был. Калькулятором на математиках пользоваться не поощрялось.
                                          Но с линейкой я гораздо раньше познакомился, дед научил. И еще многому другому.
                                  • UFO just landed and posted this here
                                      –2
                                      Вариант с целочисленными коэффициентами значительно проще. Я думаю, что написать корректную программу для нахождения вещественных корней квадратного уравнения с вещественными коэффициентами сможет менее 1% программистов. Если считать, что программа, рашающая такую простую задачу, должна давать ответ с полной доступной точностью.
                                        0
                                        Что вы имеете в виду под полной доступной точностью? Я даже с ограниченной стандартными типами точностью не знаю как подойти к вводу (хотя бы) вещественных чисел — как минимум это калькулятор (с функциями, пределами и интегралами) нужно писать, но далеко не уверен, что это покроет все множество иррациональных чисел. Вы же не рассматриваете в рамках такой простой задачи вещественные коэффициенты только как рациональные и пару-тройку популярных иррациональных констант?
                                          +1
                                          Если числа вводятся как десятичные дроби, то проще всего работать с ними как с десятично-рациональными и написать небольшую длинную арифметику (или использовать существующую). А вот если это числа double, возникшие в программе (что более вероятно), то становится интересно: как проверить условие b^2>=4*a*c для 53-битных чисел? Я бы, наверное, представил каждое вещественное число в виде суммы чисел, в которых только по 24 ненулевых бита, написал для них аккуратную операцию нормализации такой суммы, после чего арифметика (без деления) работала бы без потерь точности. А после того, как у нас есть дискриминант, можно вернуться в double, найти больший по модулю корень, а меньший посчитать по теореме Виета (как c/a/x1). Непросто, но если про программу известно, что ей нужно работать вблизи вырожденных случаев, то такое может понадобиться.
                                            0
                                            Если вводятся как десятичные (небесконечные) или рациональные дроби, то если разрешно учетверить разрядность большего знаменателя, ничего особо сложного не вижу — обычные школьные правила сравнения дробей и библиотека длинной арифметики (без деления, да). А вот нормализация (как вынос множителей из под радикала, так и сокращение дробей) могут вызвать задержки ощутимые даже для одноразового расчета.
                                              0
                                              нормализация (как вынос множителей из под радикала, так и сокращение дробей) могут вызвать задержки ощутимые даже для одноразового расчета


                                              Это же разве задержки? Вот Вы сравните на досуге время работы стандартной функции hypot() и прямого вычисления по соответствующей формуле. Будете неприятно удивлены. А дело в том, что hypot() полностью реализует специальную вещественную магию (tm) и обеспечивает максимальное количество верных разрядов в ответе.
                                                0
                                                Вынос множителя из-под радикала (при решении в алгебраических числах) — это действительно задержка. Так же, как и работа с десятичными числами без перевода их в double.
                                                А гипотенузу уже обсуждали. Правда, проверить скорость и точность разных подходов так никто и не взялся.
                                                  0
                                                  Да, это я читал. Корректно проверить точность довольно хлопотно, поскольку там основные отличия между полноценной hypot() и версией с простым делением на максимум проявляются (насколько я помню свои старые эксперименты) для денормализованных чисел. А оценки скорости хорошо известны всем, кто занимается численными приложениями — версия с делением на максимум примерно вдвое, а полноценный hypot() примерно на порядок медленнее бесхитростной реализации (кстати, в обсуждении по ссылке примерно такие же оценки тоже назывались). Именно это я имел в виду, когда сказал «Это же разве задержки?» — по сравнению с hypot() вынос множителя изменяет производительность не очень сильно (коэффициент 2 против 10-15).
                                                  0
                                                  Максимальное не обеспечивает. Я проверял лет 10 назад. Обусловлено было тем, что, грубо говоря, что корень из 4/9 никак не считался как 2/3… Числа были не равны. Поэтому я вспомнил программирование для КР580ВМ80А и реализовал свою арифметику…
                                                    0
                                                    Ну, Вы наверно сами понимаете, что «проверял лет 10 назад» — это вообще ни о чем не говорит. Какой компилятор? Какие библиотеки? Корректно ли проверяли? Кроме того, один знак последнего двоичного разряда — это в общем случае теоретический минимум погрешности для чисел с плавающей точкой. Так что даже точный смысл Ваших слов остался неясным.
                                                      0
                                                      Какой компилятор? PHP ни разу не был компилятором. Библиотек никаких, кроме стандартной и собственной.

                                                      Я проверял числа не с плавающей точкой, использовал целочисленную рациональную арифметику на уровне, кажется, 4-го класса (по исчислению СССР).
                                                        +1
                                                        Вы в исходном сообщении где-то между строк написали про то, что тестировали в PHP? Или в исходном посте что-то говорилось про PHP? Или все на свете пишут на PHP? И вообще, я подозреваю, что в PHP результат будет зависеть от того, каким компилятором и с какой libc был собран сам этот интерпретатор.

                                                        Я проверял числа не с плавающей точкой, использовал целочисленную рациональную арифметику


                                                        Тогда какую ценность имеет вот это Ваше высказывание:

                                                        Максимальное не обеспечивает.


                                                        если речь шла о свойствах именно функции hypot() из libc?
                                                          0
                                                          Сорри. Я просто зациклился на PHP в какой-то момент, начиная представлять конкретный код. Дает себе знать востребованность языка за последние 10 лет…
                                            0
                                            Имеется в виду, конечно, машинная вещественная арифметика. Под полной точностью понимают максимальное возможное количество верных двоичных разрядов. Например, в случае кратных корней, ожидаемое количество верных двоичных разрядов будет вдвое меньше общего количества разрядов в вещественном числе (вывод, кажущийся неожиданным, если просто смотреть на формулы). На самом деле корректная программа решения квадратного уравнения оказывается довольно сложной и ее написание практически недоступно среднему программисту без специальной подготовки.
                                              0
                                              Например, в случае кратных корней, ожидаемое количество верных двоичных разрядов будет вдвое меньше общего количества разрядов в вещественном числе
                                              Это зависит от интерпретации исходных данных — считаем ли мы, что исходные коэффициенты заданы с точностью плюс-минус младший бит, и мы имеем право выдать решение любого уравнения с коэффициентами в этих пределах — или мы должны считать, что коэффициенты — именно такие двоично-рациональные числа, и от нас ожидают решения именно этого уравнения, с максимально возможной точностью? Конечно, первая постановка встречается намного чаще. Но и вторая имеет право на существование.
                                                0
                                                Да, это верно, но во второй постановке промежуточные вычисления потребуют использования чисел как минимум вдвое большей разрядности в случае корней кратности 2. И я, конечно, имел в виду именно первую постановку задачи.
                                            0
                                            1) решение квадратного уравнения вида ax2+bx+c=0 с целочисленными коэффициентами.
                                            При a = 0 уравнение не квадратное. Так что либо говорим, что решаем уравнение (без слова квадратное), либо не выпендриваемся добавляя исключительные случаи.

                                            2) Программа должна всегда выдавать результат.
                                            Опять таки, программа выдаёт результат. Причём, даже правильный.
                                            Зачем пытаться усложнить себе жизнь, если этого не было в задании?
                                              0
                                              Задание «написать программу решения квадратного уравнения» каждый понимает в меру своей испорченности образованности и эрудиции. И три разных человека могут счесть одну и ту же программу как неработающей («комплексные корни есть, а пишет, что корней нет»), так и работающей как надо, а равно как «мою задачу выполняет, но столько лишнего». Просто такое задание не техническое.
                                                0
                                                1) Напоминаю, в определении в учебнике написано:
                                                Уравнение вида ax2+bx+c=0, где a≠0.

                                                Здесь этого условия в задании нет, так что этот случай тоже рассматривается.

                                                2) Программа и вначале выдавала результат, но не тот, который был нужен.
                                                +2
                                                Это моя любимая задача! Она отлично показывает как надо подходить к анализу формулировки задачи заказчиком и как все неоднозначно в этом плане.

                                                Я эту задачу всегда первой давал студентам, когда начинал рассказывать про проектирование новой системы и первичный анализ требований заказчика. Большинство студентов ее решают как описано в самом первом варианте, а задумываться начинают только после наводящих вопросов про комплексные числа, вырожденные случаи и т.д.
                                                  +6
                                                  Что-то я не понял.

                                                  long long discriminant = b*b - 4*a*c;
                                                  

                                                  Без преобразования b к long long мы начнём получать неверный результат уже начиная с b=50000 (даже чуть раньше). Если преобразуем — то на числах, близких к границе int, получим переполнение, когда 4*a*c окажется больше 2^63. Я в этом месте написал
                                                  		__int64 ac=(__int64)a*c;
                                                  		__int64 b2=(__int64)b*b;
                                                  		__int64 D=b2/4-ac;
                                                  		if(b%2==0 && D==0) printf("One root: %lg\n",-(double)b/2.0/a);
                                                  		else{
                                                  			if(D<0) printf("No roots\n");
                                                  			else{
                                                  				double v=sqrt((double)D+(b%2==0 ? 0 : 0.25));
                                                  				printf("Two roots: %lg and %lg\n",(-b/2.0-v)/a,(-b/2.0+v)/a);
                                                  			}
                                                  		}
                                                  

                                                  По идее, сравнение дискриминанта с нулём будет работать всегда корректно, даже когда double для этого бы не хватило. Но вот с выводом в алгебраическом виде возникает проблема: при нечётных b дискриминант может выйти за пределы 2^64 и тут уж без длинной арифметики не обойтись.
                                                  Кстати, как устроен класс radical? Он должен выносить полный квадрат за пределы корня (иначе пятёрку не поставят — sqrt(18) не понравится ни одному учителю). Удалось ли там обойтись без полного разложения 19-значных чисел на множители?
                                                    –1
                                                    Полное там не нужно, сложность тупого перебора не sqrt(N), а sqrt(sqrt(N)).
                                                      0
                                                      В лучшем случае, N^(1/3)/log(N): для числа p^2*q, где p и q — близкие простые, никакого способа лучше, чем перебирать все простые до min(p,q) не видно (если не переходить к продвинутым теоретико-числовым алгоритмам).
                                                      0
                                                      Насчёт дискриминанта — не знал, по наивности решил, что такого будет достаточно.
                                                      Да, radical выносит за пределы без разложения, в общем-то, но в не слишком оптимальном цикле (для оптимального стоило заиметь массив простых чисел:
                                                      int radical::getPerfectSquare()
                                                      {
                                                        long long a = abs(radicand);
                                                        int square = 1;
                                                        int maxDiv = floor(sqrt(a));  // делители, большие корня из подкоренного выражения, нас не интересуют: их всегда будет меньше двух
                                                      
                                                        for (int i = 2; i <= maxDiv; i++)
                                                        {
                                                          while (a % (i*i) == 0)
                                                          {
                                                            a /= i*i;
                                                            square *= i;
                                                          }
                                                          maxDiv = floor(sqrt(a));
                                                        }
                                                      
                                                        return square;
                                                      }
                                                      

                                                      Вот и корень из 18, например:
                                                      1 0 -18
                                                      D != 0; 2 корня:
                                                      x1 = 3┐/2
                                                      x2 = - 3┐/2
                                                      
                                                    • UFO just landed and posted this here
                                                        –1
                                                        Мой первый курсовик в техническом вузе: аналитическое решение всех видов квадратных и биквадратных уравнений с учётом комплексных корней — сделан за вечер:
                                                        image
                                                          +1
                                                          Честно говоря, не вижу здесь ничего особенно сложного. Может, поясните, в чём «фишка»? Какие были подводные камни? На чём написано?
                                                            –1
                                                            В том то и дело что ничего сложного нет в этой задаче — решается в один присест даже без подготовки.
                                                              –1
                                                              Ну так не интересно.
                                                              Написание поста, параллельно с кодом и чаями, заняло у меня от силы полтора часа + полчаса на вычитку.
                                                                0
                                                                А смысл имело? Мне кажется тут не совсем та аудитория, которая не сможет алгоритмически решить ту задачу, которую каждый школьник решит на бумажке. Тем более что там всё линейно и без подводных камней.

                                                        Only users with full accounts can post comments. Log in, please.