文章/答案/技术大牛

发布

社区首页 >问答首页 >计算价值为$11^n$的`1‘位数

问计算价值为$11^n$的`1‘位数
EN

Code Review用户

提问于 2019-12-02 15:49:03

回答 4查看 1.1K关注 0票数 4

我在努力提高代码的效率，

问题是：

给定一个值n (其中n在[0 .. 500]范围内)，在数字11^n的十进制表示中返回与1相等的数字数。

当然，当处理更大的功率(其中n是一个很大的数字)，这大大降低了效率。

我设法提出了一个快速但效率低下的粗略解决方案，这似乎很有效，但我能做些什么来改进代码及其效率呢？

import java.util.ArrayList;

public class Solution {

private static int num = 11;

public static int solution(int n) {

    int counter = 0;
    String compare = "1";
    double answer = Math.round(Math.pow(num, n));
    System.out.println(answer);

    String s = String.valueOf(answer);
    String[] parts = s.split("");

    for (int i=0; i<parts.length; i++){
        if (parts[i].equals(compare)){
            counter++;
        }
    }
    System.out.println(counter);
    return counter;
}

public static void main(String[] args) {

    solution(8);
    solution(3);

    }
}

任何帮助提高我对编写更有效的代码的技术的理解，都将是非常感谢的，以及对上面的代码示例的改进。

java

performance

algorithm

array

回答 4

Code Review用户

发布于 2019-12-03 07:35:55

你应该把你的编程技巧放在一边，然后思考一下。从数学上想一想，它实际上意味着什么。

11^n = (10+1)^n

假设a=10，b=1 => (a+b)^n，这可以使用pascal三角展开：

我想每个人都知道这是怎么发生的..。

然后是这样的：

(a+b)^n = {n \choose 0} a^n b^0 + {n \choose 1} a^{n-1} b^1 + \dots + {n \choose n} a^0 b^n

您可以注意到，自b=1以来，我们可以删除所有这些术语b^x

我们只剩下

(a+b)^n = {n \choose 0} a^n + {n \choose 1} a^{n-1} + \dots + {n \choose n} a^0

从a=10开始，我们就知道a^n基本上是1，后面跟着n个零。

简单的系数的添加和携带现在应该显示数字是1和什么时候是其他任何东西。

票数 9

Code Review用户

发布于 2019-12-03 00:23:31

实现是错误的，一旦n超过15，将返回不正确的结果。

double使用53位尾数存储值，允许精确表示大约16位精度的值。当n \gt 16，然后是11^n \gt 10^{16}，以及double值时，将无法精确地表示该值。这种不准确意味着您无法计数结果中的1位数，而不希望返回正确的值。

不需要很长时间就可以说服自己，11^n总是以1数字结尾。现在，考虑一下，11^{16} = 45949729863572161，并与以下内容进行比较：

jshell> String.valueOf(Math.round(Math.pow(11, 16)))
$20 ==> "45949729863572160"

要精确计算1数字的数量，需要使用扩展精度整数(即，BigInteger)或以不同方式确定所需值的算法。

用正则表达式分割字符串可能是计数1数字的最不有效的方法。除了正则表达式之外，JVM还需要分配一个String[]，以及字符串中每个字符的一个String。计算1数字的一种更有效的方法是一次提取一个字符(而不是字符串)：

int counter = 0;
for(int i = 0; i < s.length; i++)
    if (s.charAt(i) == '1')
        counter++;

票数 8

Code Review用户

发布于 2019-12-03 09:02:01

和我之前的其他答案一样，问题是关于exp n的大值。如果你拿起笔和纸，试图把1331 (11^3)和11乘以14641 (11^4)，你就会这样做：

 1331 x 
   11
-------
 1331 +
1331
-------
14641

所以，基本上，如果你有11^n，你想要计算11^{n+1}，它可以用11^n和11^n * 10之和来计算。为了避免由于数字的尺寸而造成的问题，您可以用字符串编写数字。在1331的情况下，我们可以使用和字符串01331和13310，并计算字符串14641。

我定义了一个名为PowerOfEleven的类和一个包含以下测试的main方法：

public class PowerOfEleven {
    private static String ELEVEN = "11";
    private static String ZERO = "0";
    private static String ONE = "1";

    public static void main(String[] args) {
        assertEquals(calculatePower(0), "1");
        assertEquals(calculatePower(1), "11");
        assertEquals(calculatePower(2), "121");
        assertEquals(calculatePower(3), "1331");
        assertEquals(calculatePower(4), "14641");
        assertEquals(calculatePower(5), "161051");
        assertEquals(calculatePower(6), "1771561");
    }
}

calculatePower方法对每n个数字11^n使用字符串之和计算，就像使用钢笔和纸张时那样：

public static String calculatePower(int n) {
    if (n == 0) { return ONE; }
    String number = ELEVEN ;
    for (int i = 1; i < n; ++i) {
        String first = ZERO  + number;
        String second = number + ZERO;
        number = sum(first, second);
    }
    return number;
}

我正在添加字符串，在第一个字符串之前放置一个零，在第二个字符串之后添加另一个零，因此，例如，对于1331，您将获得字符串01331和13310。我为字符串的和定义了一个方法，如下所示：

private static String sum(String s1, String s2) {
    final int n = s1.length();
    char[] arr1 = s1.toCharArray();
    char[] arr2 = s2.toCharArray();

    StringBuilder result = new StringBuilder();
    int remainder = 0;
    for (int i = n - 1; i >= 0; --i) {
        int firstDigit = Character.getNumericValue(arr1[i]);
        int secondDigit = Character.getNumericValue(arr2[i]);
        int value = firstDigit + secondDigit + remainder;
        remainder = 0;
        if (value >= 10) {
            value = value - 10;
            remainder = 1;
        }
        result.append(Character.forDigit(value, 10));
    }
    if (remainder > 0) {
        result.append(remainder);
    }

    return result.reverse().toString();
}

该方法使用一个StringBuilder对象来存储结果:当您从末尾开始对两个字符串的数字进行求和时，您将得到一个新的数字和一个可以是0或1的余数。从和获得的新数字被附加在StringBuilder的后面，因此您必须反转StringBuilder结果才能获得实际值。

注意：@使用Pascal三角形(如果实现)的想法简化了我关于字符串和的概念，并且肯定提高了性能。

票数 3

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/233278

复制

相似问题

问计算价值为$11^n$的`1‘位数
EN

回答 4

Code Review用户

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算价值为$11^n$的`1‘位数EN

回答 4

Code Review用户

Code Review用户

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算价值为$11^n$的`1‘位数
EN