1. C++ / Говнокод #19534

    +3

    1. 1
    2. 2
    3. 3
    int main() { 
    for (float n = 0, l = 0, q = scanf("%f", &n), r = n, m = (l + r) / 2; r - l > 0.00001 || 0 * printf("%f", l); m*m <= n ? l = m : r = m, m = (l + r) / 2); 
    }

    Просто бинпоиск в одну строчку)

    Запостил: AndreyZ, 25 Февраля 2016

    Комментарии (21) RSS

    • Этот код двоичным поиском ищет квадратный корень из числа с плавающей точкой.
      Ответить
      • for(float a=0,_=scanf("%f",&a),x=a,y=x+1;fabs(y-x)>0.00001||!printf("%f",x);y=x,x=(x+a/x)/2);
        А чё не ньютоном?
        Ответить
        • Потому что Ньютон на #CF байт старее Ломоносова.
          Ответить
          • Бля. На #44 же. Вот ведь блять перепил... Нахуй так жить?..
            Ответить
        • а у меня длиннее
          for (double a = Double.Parse(Console.ReadLine()), xp = a+1, x = a; Math.Abs(x - xp) > 0.000001 || new Func<bool>(() =>{Console.WriteLine(x);return false; }).Invoke(); xp = x, x = (x + a / x) / 2) ;
          Ответить
        • Цель была написать бинпоиск, а поиск корня был примером(вместо него может быть любая монотонная функция). А про метод ньютона не знал, спасибо.)
          Ответить
          • >> А про метод ньютона не знал, спасибо.)

            x = sqrt(a) -> x*x = a -> x = a/x -> x+x = x+ a/x -> x = (x+a/x)/2

            А хрень с сложением от того, что x = a/x очень фигово вычисляется итеративно
            Ответить
            • Где-то статья попадалась, где метод ньютона вывели из бинарного поиска...
              Ответить
              • Ну общая формула типа x = x - f(x)/f'(x), для х таких, что f(x) = 0

                у нас f(x) = x*x-a
                f'(x) = 2x

                откуда
                x = x - (x*x-a)/ 2x
                x = x-x/2 - a/2x
                x = (x - a/x)/2

                это все, что я знаю
                Ответить
                • Ты знак проебал:
                  x = x - (x*x-a)/ 2x
                  x = x-x/2 + a/2x
                  x = (x + a/x)/2
                  Ответить
                  • ну да, ночь была, спать хотел, все такое
                    Ответить
          • >А про метод ньютона не знал, спасибо.)
            Householder 1st order
            Ответить
    • r - l > что-то

      Вот так опасно проверять же. А вдруг там очень близкие большие числа (порядка FLOAT_MAX)
      Ответить
      • Да не надо там флоат макс... Это сравнение на числах порядка 1000 уже загнётся. У флоата же мантисса в районе 7 десятичных цифр.
        Ответить
        • А что не так с этим сравнением? Я не очень понял.
          Ответить
          • Ну для простоты покажу на десятичных числах. Ты считаешь корень от 1000003. Пусть у тебя флоат хранит ровно 7 значащих цифр и расчёт добрался до L = 1000.001, а R = 1000.002 (реальный ответ ~1000.0014999). Ты считаешь M = 1000.0015, но т.к. точность ограничена, оно округляется до 1000.002. Его квадрат 1000004 больше искомого, т.е. делаем R = M... Дальше понятно? :)
            Ответить
            • В бинпоиске похожая проблема возникает, когда диапазон сужается. Чтобы поиск завершался, пишут l = m + 1 и r = m - 1 (если r включается). И тут, видимо, надо эпсилон добавлять/вычитать.
              Ответить
              • Можно ограничить число итераций, но это костыль. И еще вроде можно смотреть изменилось-ли r-l.
                Ответить
                • > изменилось-ли r-l
                  Тогда уж просто перед присваиванием сравнить m и заменяемое им число. Если одинаковые - дальше крутить цикл смысла нету.
                  Ответить
                  • Простите, а не проще ли сконвертить float через union к инту и проверить равенство после & битовой маски (исключив младшие N бит. N выбрать по вкусу). Я даже в сраных жавах так делал. Брат жив.
                    Ответить
    • for (...; abs(a - sqrt(2)) < 0.00001 ;...);
      Ответить

    Добавить комментарий