Найти ноль очков с рекурсией

Question

Я хочу найти нулевые точки функции синуса. Параметр представляет собой интервал [a, b]. Я должен к этому похож на бинарный поиск.

Реализация функции, которая ищет нулевые точки в функции синуса в интервале между a и b. Интервал поиска [нижний предел, верхний предел] должен быть уменьшен вдвое до тех пор, пока нижний предел и верхний предел не окажутся менее чем на 0,0001. Вот мой код:

public class Aufg3 {
    public static void main(String[] args) {

        System.out.println(zeropoint(5,8));
    }

    private static double zeropoint(double a, double b){
        double middle = (a + b)/2;

        if(Math.sin(middle) < 0){
            return zeropoint(a,middle);
        }else if(Math.sin(middle) > 0){
            return zeropoint(middle,b);
        }else{
            return middle;
        }       
    }
}

Это дает мне много ошибок в строке с return zeropoint (middle, b);

На первом шаге я хочу найти только первую нулевую точку в интервале.

Есть идеи?

Answer 1

Фундаментальные проблемы, которые все упустили из виду:

• мы не всегда хотим возвращать результат (представьте, что мы находим нулевые точки функции синуса между pi / 4 и 3pi / 4, их нет).
• в любом произвольном диапазоне может быть несколько нулей.

Очевидно, что необходим (возможно пустой) набор значений.

Итак, псевдокод функции действительно запрашивается (без использования Java, поскольку это домашняя работа):

Set zeropoint(double a, double b)
{
    double middle = mid point of a and b;
    if a and be less than 0.0001 apart
    {
        if (sin(a) and sin(b) are on opposite sides of 0)
        { 
            return set containing middle
        }
        else
        {
            return empty set
        }
    }
    else
    {
        return union of zeropoint(a, middle) and zeropoint(middle, b)
    }
} 

Answer 2

Я предполагаю, что вы получаете ошибки переполнения стека во время выполнения. Знаки <и> поменялись местами. Кроме того, вы должны использовать .0001, а не 0 для сравнения.

Редактировать 1: На самом деле, ваш основной алгоритм имеет проблемы. Что произойдет, если в интервале будет более одного нуля? Что произойдет, если грех (а) и грех (митта) имеют один и тот же знак? Что произойдет, если в интервале нет нулей?

Редактировать 2: Итак, я сделал проблему, и, по сути, ваше решение проблематично; Я попытался бы начать с размышлений, как решить эту проблему.

Основная проблема в том, что в интервале может быть несколько нулей, и вы пытаетесь найти каждый из них. Создание функции, которая возвращает тип double, может вернуть только одно решение. Поэтому вместо создания функции, возвращающей значение double, просто верните void и распечатайте нули по мере их нахождения.

Еще один совет: вы должны продолжать поиск, пока a и b не окажутся в пределах .0001 друг от друга. Ваше окончательное решение не будет использовать .0001 любым другим способом. (То есть, ваша проверка, чтобы увидеть, нашли ли вы ноль, не должна использовать допуск .0001, и при этом он не будет использовать точно 0. Подумайте, как вы действительно узнаете, если вы нашли ноль, когда abs (ab) меньше, чем .0001 .

Answer 3

Просто сказать «это дает мне ошибки» не очень полезно.Что за ошибки?Ошибки компиляции или неперехваченные исключения во время выполнения?

Для вашего кода в качестве возможных проблем выделяются две вещи:

1. переменная mitte нигде не объявлена.
2. вы используете> и <для сравнения реалов.Хотя это само по себе нормально, лучше проверять на 0, используя допуск, а не полагаться на <и>, чтобы избежать проблем из-за точности с плавающей запятой.Для всех практических целей -0,000000000001 равно 0.

Могут быть и другие проблемы, я просто записал те, которые выпрыгнули на первый взгляд.

Редактировать:

Видимо, mitte произошла из-за ошибки при вставке кода OP (и с тех пор была исправлена).Как указывали другие ответы, код попадает в бесконечную рекурсию.Это связано с тем, что рекурсивные вызовы находятся на неправильных интервалах.

Следует отметить, что функция sin может монотонно увеличиваться для одного выбора a и b и монотонно уменьшаться на некотором другом интервале.Например, оно увеличивается в течение [0, pi / 2] и уменьшается в течение [pi / 2,3 * pi / 2].Таким образом, рекурсивные вызовы должны быть изменены в соответствии с исходным интервалом, в котором выполняется поиск. Для одного интервала Math.sin (middle) <0 подразумевает, что Math.sin (x) <0 для всех x в [a, middle],но для некоторого другого интервала верно обратное.Это, вероятно, почему это попадает в бесконечную рекурсию для интервала, который вы пытаетесь.Я думаю, что это работает в некотором другом интервале, где грех фактически уменьшается.Попробуйте вызвать вашу функцию через [pi / 2,3 * pi / 2]. </p>

Answer 4

Я предполагаю, что вы столкнулись с StackOverflowError.Это связано с тем, что вы никогда не достигнете базового варианта в своей рекурсии.(Math.sin(middle) может никогда не равняться точно 0!)

Ваше упражнение говорит

[...], пока нижний предел и верхний предел не будутна расстоянии менее 0,0001 друг от друга.

Итак, попробуйте поставить это в верхней части вашего метода:

double middle = (a + b)/2;
if (b - a < 0.0001)
    return middle;

Answer 5

Вы прочитали задание до конца?В нем говорится:

Интервал поиска [нижний предел, верхний предел] должен быть уменьшен вдвое, пока нижний предел и верхний предел не будут меньше 0,0001 друг от друга.Поэтому вы не можете ожидать, что Math.sin(middle) вернет ровно ноль из-за проблем точности с плавающей точкой.Вместо этого вам нужно остановить рекурсию, когда вы достигнете 0,0001 точности.

Answer 6

Помимо некоторых проблем с плавающей запятой, о которых упоминали другие, ваш алгоритм, похоже, основан на неявных предположениях:

1. грех (а) положительный
2. грех (б) отрицательный, а
3. sin (x) - убывающая функция на интервале [a, b].

Я не вижу оснований для этих предположений. Когда любой из них ложен, я не ожидаю, что ваш алгоритм будет работать. Все они ложны, когда а = 5 и б = 8.

Answer 7

private static double zeropoint(double a, double b){
    double middle = (a + b)/2;
    double result = middle;

    if (Math.abs(a - b) > 0.0001) {
        double sin = Math.sin(middle);
        if (Math.abs(sin) < 0.0001) {
           result = middle;
        } else if (sin > 0) {
           result = zeropoint(a, middle);
        } else {
           result = zeropoint(middle, b);
        }
    }
    return result;   
}

как-то так, я думаю - просто исправить первые ошибки

Answer 8

if(Math.sin(mitte) < 0){

Где объявлено mitte? Разве mitte middle?