代码之家  ›  专栏  ›  技术社区  ›  DarkLeafyGreen

用递归求零点

  •  0
  • DarkLeafyGreen  · 技术社区  · 14 年前

    我想找出正弦函数的零点。参数是一个区间[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;
            }       
        }
    }
    

    它给了我很多错误 返回零点(中间,b);

    在第一步中,我只想找到区间中的第一个零点。

    有什么想法吗?

    8 回复  |  直到 14 年前
        1
  •  6
  •   JeremyP    14 年前

    每个人都忽视的基本问题:

    • 我们并不总是想要返回一个结果(假设在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)
        }
    } 
    
        2
  •  3
  •   MAK    14 年前

    简单地说“它给了我错误”并不是很有帮助。什么样的错误?在运行时编译错误或未捕获的异常?

    对于您的代码,有两个问题最突出:

    1. 变量 mitte 似乎没有在任何地方声明。
    2. 您正在使用>和<比较reals。虽然这本身是可以的,但最好使用公差检查0,而不是依赖于<和>,以避免由于浮点精度引起的问题。就所有实际用途而言-0.000000000001为0。

    可能还有其他问题,我刚刚写下了第一眼就跳出来的问题。

    编辑:

    显然 米特 是由于操作程序粘贴代码时出错(并已更正)。正如其他答案所指出的,代码属于无限递归。这是因为递归调用的间隔错误。

    需要注意的一点是,sin函数对于a和b的一个选择可以单调地递增,而在其他间隔可以单调地递减。例如,它在[0,pi/2]上增加,在[pi/2,3*pi/2]上减少。因此,递归调用需要根据进行搜索的原始间隔进行更改。对于一个间隔math.sin(middle)<0意味着math.sin(x)<0对于[a,middle]中的所有x,但对于其他间隔,则相反。这可能就是为什么对于您正在尝试的间隔,它会陷入无限递归的原因。我认为这在另一个区间内有效,在这个区间内,罪恶实际上在减少。尝试通过[pi/2,3*pi/2]调用函数。

        3
  •  3
  •   aepryus    14 年前

    我猜您在运行时会遇到堆栈溢出错误。<和>符号颠倒。另外,您应该使用.0001而不是0来进行比较。

    编辑1: 实际上,您的基本算法有问题。如果间隔中有一个以上的零会发生什么?如果罪(a)和罪(mitte)有相同的符号会发生什么?如果间隔中没有零会发生什么?

    编辑2: 好吧,所以我做了这个问题,从根本上说,你的解决方案是有问题的;我会重新开始思考如何解决它。

    主要的问题是间隔中可能有多个零,而您正试图找到它们中的每一个。创建返回类型double的函数只能返回一个解决方案。所以,与其创建一个返回double的函数,不如返回void,并在找到零时打印出来。

    另一个提示:您应该继续搜索,直到a和b在.0001范围内。您的最终解决方案不会以任何其他方式使用.0001。(也就是说,检查是否发现零不应使用.0001公差,也不应准确使用0。想一想,当abs(a-b)小于0.0001时,你将如何真正知道你是否找到了0。

        4
  •  2
  •   teukkam    14 年前

    你把作业读到最后了吗?上面写着:

    搜索间隔[下限,上限 限制]应该减半,直到降低 极限和上限小于 彼此相距0.0001。

    所以你不能期待 Math.sin(middle) 因为浮点精度问题返回零。相反,您需要在达到0.0001精度时停止递归。

        5
  •  2
  •   aioobe    14 年前

    我猜你会遇到 StackOverflowError . 这是因为在递归中永远不会达到基本情况。( Math.sin(middle) 可能永远不等于 确切地 0!)

    你的练习说

    […]直到下限和上限彼此之间的距离小于0.0001。

    所以,试着把这个放在方法的最前面:

    double middle = (a + b)/2;
    if (b - a < 0.0001)
        return middle;
    
        6
  •  1
  •   Josephine    14 年前

    除了其他提到的一些浮点问题外,您的算法似乎基于以下隐含假设:

    1. sin(a)为正
    2. sin(b)为负,并且
    3. sin(x)是区间上的递减函数[a,b]。

    我看不出这些假设的依据。当它们中的任何一个是错误的,我都不期望你的算法能工作。当a=5和b=8时,它们都是假的。

        7
  •  0
  •   Buhake Sindi Tesnep    14 年前
    if(Math.sin(mitte) < 0){
    

    在哪里 mitte 宣布?不是 米特 middle ?

        8
  •  0
  •   Vladimir Ivanov    14 年前
    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;   
    }
    

    我想是这样的-只是为了修正第一个错误