java - 使用递归的幂函数

coder 2024-03-08 原文

我必须用 Java 编写一个强大的方法。它接收两个整数，它们是正数还是负数都没有关系。它的复杂度应该是 O(logN) .它还必须使用递归。我当前的代码有两个数字，但我一直输出的结果为零，我不知道为什么。

import java.util.Scanner;

public class Powers {

    public static void main(String[] args) {
        float a;
        float n;
        float res;

        Scanner in = new Scanner(System.in);
        System.out.print("Enter int a ");
        a = in.nextFloat();

        System.out.print("Enter int n ");
        n = in.nextFloat();

        res = powers.pow(a, n);

        System.out.print(res);
    }

    public static float pow(float a, float n) {
        float result = 0;

        if (n == 0) {
            return 1;
        } else if (n < 0) {
            result = result * pow(a, n + 1);
        } else if (n > 0) {
            result = result * pow(a, n - 1);
        }

        return result;
    }
}

最佳答案

让我们从一些数学事实开始:

对于正 n，aⁿ = a⨯a⨯…⨯a n 次

对于负数 n，aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a)。这意味着 a 不能为零。

对于 n = 0，aⁿ = 1，即使 a 为零或负数。

所以让我们从正 n 的情况开始，然后从那里开始工作。

由于我们希望我们的解决方案是递归的，我们必须找到一种方法来基于较小的 n 定义 aⁿ，并从那里开始工作。人们通常认为递归的方式是尝试找到 n-1 的解决方案，然后从那里开始工作。

事实上，由于 aⁿ = a⨯(aⁿ⁻¹) 在数学上是正确的，所以天真的方法与您创建的方法非常相似:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    return ( a * pow(a,n-1));
}

然而，这的复杂度是 O(n)。为什么？因为对于 n=0 它不做任何乘法运算。对于 n=1，它进行一次乘法运算。对于 n=2，它调用 pow(a,1) ，我们知道它是一次乘法，然后乘以一次，所以我们有两次乘法。每个递归步骤有一个乘法，有n个步骤。所以是 O(n)。

为了使这个 O(log n)，我们需要将每一步都应用于分数 n 而不仅仅是 n-1。同样，有一个数学事实可以帮助我们:an₁+n₂ = an₁⨯an₂。

这意味着我们可以将 aⁿ 计算为 an/2⨯an/2。

但是如果 n 是奇数会发生什么？像 a⁹ 这样的东西将是 a4.5⨯a4.5。但我们在这里谈论的是整数幂。处理分数是完全不同的事情。幸运的是，我们可以将其表述为 a⨯a⁴⨯a⁴。

因此，对于偶数使用 an/2⨯an/2，对于奇数使用 a⨯ an/2⨯an/2(整数除法，给我们 9/2 = 4)。

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    if ( n % 2 == 1 ) {
        // Odd n
        return a * pow( a, n/2 ) * pow(a, n/2 );
    } else {
        // Even n
        return pow( a, n/2 ) * pow( a, n/2 );
    }
}

这实际上为我们提供了正确的结果(即对于正 n)。但实际上，这里的复杂性再次是 O(n) 而不是 O(log n)。为什么？因为我们要计算两次幂。这意味着我们实际上在下一级别调用它 4 次，在下一级别调用 8 次，依此类推。递归步骤的数量是指数级的，因此这与我们通过将 n 除以 2 所做的假设节省相抵消。

但实际上，只需要一个小小的修正:

public static int pow( int a, int n) {
    if ( n == 0 ) {
        return 1;
    }
    int powerOfHalfN = pow( a, n/2 );
    if ( n % 2 == 1 ) {
        // Odd n
        return a * powerOfHalfN * powerOfHalfN;
    } else {
        // Even n
        return powerOfHalfN * powerOfHalfN;
    }
}

在这个版本中，我们只调用一次递归。所以我们从 64 的幂中得到，非常快地通过 32、16、8、4、2、1 并完成。每一步只有一两次乘法，而且只有六步。这是 O(log n)。

这一切的结论是:

为了获得 O(log n)，我们需要在每一步处理 n 的一小部分的递归，而不仅仅是 n - 1 或 n - 任何东西。

但分数只是故事的一部分。我们需要注意不要多次调用递归，因为在一个步骤中使用多个递归调用会产生指数复杂性，而使用 n 的一小部分会抵消这种复杂性。

最后，我们准备好处理负数。我们只需要得到倒数 ⅟a⁻ⁿ。有两个重要的事情需要注意:

不允许除以零。也就是说，如果您得到 a=0，则不应执行计算。在 Java 中，我们会在这种情况下抛出异常。最合适的现成异常是 IllegalArgumentException。这是一个 RuntimeException，所以你不需要添加 throws子句到你的方法。如果您在 main 中发现它或阻止这种情况发生，那就太好了。读入参数时的方法。

你不能再返回一个整数(事实上，我们应该使用 long ，因为我们遇到了整数溢出，因为 int 非常低) - 因为结果可能是小数。

所以我们定义了这个方法，让它返回 double 值。这意味着我们还必须修复 powerOfHalfN 的类型.结果如下:

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power

        double powerOfHalfN = pow(a, n / 2);
        if (n % 2 == 1) {
            // Odd n
            return a * powerOfHalfN * powerOfHalfN;
        } else {
            // Even n
            return powerOfHalfN * powerOfHalfN;
        }
    }
}

请注意，处理负 n 的部分仅用于递归的顶层。一旦我们调用 pow()递归地，它总是带有正数，并且符号在达到 0 之前不会改变。

这应该是您锻炼的适当解决方案。但是，我个人不喜欢 if最后，所以这是另一个版本。你能说出为什么这样做吗？

public static double pow(int a, int n) {
    if (n == 0) {
        return 1.0;
    }
    if (n < 0) {
        // Negative power.
        if (a == 0) {
            throw new IllegalArgumentException(
                    "It's impossible to raise 0 to the power of a negative number");
        }
        return 1 / pow(a, -n);
    } else {
        // Positive power
        double powerOfHalfN = pow(a, n / 2);
        double[] factor = { 1, a };
        return factor[n % 2] * powerOfHalfN * powerOfHalfN;
    }
}

关于java - 使用递归的幂函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26689929/

java 使用 code powerOfHalfN return recursion pow

有关java - 使用递归的幂函数的更多相关文章

ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2
我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div
ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2
我有一个Ruby程序，它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重，我想提高压缩级别，因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗？是否有另一个允许指定压缩级别的Ruby库？最佳答案这是我通过查看rubyzip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d
ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2
很好奇，就使用rubyonrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？最佳答案不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提
ruby - 在 Ruby 中使用匿名模块 - 2
假设我做了一个模块如下:m=Module.newdoclassCendend三个问题:除了对m的引用之外，还有什么方法可以访问C和m中的其他内容？我可以在创建匿名模块后为其命名吗(就像我输入“module...”一样)？如何在使用完匿名模块后将其删除，使其定义的常量不再存在？最佳答案三个答案:是的，使用ObjectSpace.此代码使c引用你的类(class)C不引用m:c=nilObjectSpace.each_object{|obj|c=objif(Class===objandobj.name=~/::C$/)}当然这取决于
ruby - 使用 ruby 和 savon 的 SOAP 服务 - 2
我正在尝试使用ruby和Savon来使用网络服务。测试服务为http://www.webservicex.net/WS/WSDetails.aspx?WSID=9&CATID=2require'rubygems'require'savon'client=Savon::Client.new"http://www.webservicex.net/stockquote.asmx?WSDL"client.get_quotedo|soap|soap.body={:symbol=>"AAPL"}end返回SOAP异常。检查soap信封，在我看来soap请求没有正确的命名空间。任何人都可以建议我
python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。
ruby-on-rails - 'compass watch' 是如何工作的/它是如何与 rails 一起使用的 - 2
我在我的项目目录中完成了compasscreate.和compassinitrails。几个问题:我已将我的.sass文件放在public/stylesheets中。这是放置它们的正确位置吗？当我运行compasswatch时，它不会自动编译这些.sass文件。我必须手动指定文件:compasswatchpublic/stylesheets/myfile.sass等。如何让它自动运行？文件ie.css、print.css和screen.css已放在stylesheets/compiled。如何在编译后不让它们重新出现的情况下删除它们？我自己编译的.sass文件编译成compiled/t
ruby - 使用 ruby 将 HTML 转换为纯文本并维护结构/格式 - 2
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。最佳答案首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2
我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

java - 使用递归的幂函数

有关java - 使用递归的幂函数的更多相关文章

随机推荐