项目欧拉＃119做出更快

试图解决项目欧拉问题119：项目欧拉＃119做出更快

数512是有趣的，因为它等于升高到一些功率的其数字的总和：5 + 1 + 2 = 8 ，并且8^3 = 512。具有这个属性的数字的另一个例子是614656 = 28^4。

我们将定义一个这个序列的第n项，并坚持一个数字必须包含至少两个数字才能有一个和。

您将得到的是A2 = 512和A10 = 614656.

查找A30。

问：有没有找到答案不仅仅是检查每一个数字，直到A30更有效的方法是发现了什么？

我的代码

int currentNum = 0; 
    long value = 0; 
    for (long a = 11; currentNum != 30; a++){ //maybe a++ is inefficient 
     int test = Util.sumDigits(a); 
     if (isPower(a, test)) { 
      currentNum++; 
      value = a; 
      System.out.println(value + ":" + currentNum); 
     } 
    } 
    System.out.println(value);

isPower检查是否是测试的功率。 Util.sumDigits：

public static int sumDigits(long n){ 
     int sum = 0; 
     String s = "" + n; 
     while (!s.equals("")){ 
      sum += Integer.parseInt("" + s.charAt(0)); 
      s = s.substring(1); 
     } 
     return sum; 
    }

程序已运行约30分钟（可能溢出很长）。输出（到目前为止）：

81：1

512：2

2401：3

4913：4

5832：5

17576：6

19683：7

234256：8

390625：9

614656：10

1679616：11

17210368：12

34012224：13

52521875：14

60466176：15

205962976：16

612220032：17

来源

2012-12-12 Justin

子串部分必须是一个杀手... – assylias

可能有更高效的算法，但所有int /字符串转换可能是昂贵的。你可以分开一些数字，有些数学可能更快。这里％是mod运算符。 '512％10 = 2; 512-2 = 510; 510％100/10 = 1; 510 - 10 = 500; 500％1000/100 = 5; 500 - 500 = 0' – Schwern

@assylias Util.sumDigits运行得非常快，我认为它可能是主体for循环中的迭代。 – Justin

的解决方案是一个15位数字。祝你好运，优化总和足以使运行足够快，检查每一个数字。

转过头来问题。数字总和是一个相对较低的数字（数字中最多9位数字），并且功率也会相对较低（即使是小数字也不需要很大的功率就可以达到15位数）。

因此，循环总和和权力，计算总数（你可以保持在一个乘法的内部循环中运行总数，甚至不需要功率计算），然后总结这些数字，看看它是否与你的循环变量。

数字将不会按顺序排列，因此计算得比您需要的还多，并对结果进行排序。

应该在约一秒钟内运行。

来源

2012-12-12 22:35:11 JasonD

有关数字和...这里是一些铁的事实：

0% Scenario{vm=java, trial=0, benchmark=NaiveDigitSum} 542.90 ns; σ=11.00 ns @ 10 trials 
50% Scenario{vm=java, trial=0, benchmark=BetterDigitSum} 42.13 ns; σ=1.42 ns @ 10 trials 

    benchmark ns linear runtime 
NaiveDigitSum 542.9 ============================== 
BetterDigitSum 42.1 ==

测试代码：

import com.google.caliper.Runner; 
import com.google.caliper.SimpleBenchmark; 

public class Performance extends SimpleBenchmark { 
    public void timeNaiveDigitSum(int reps) { 
    for (int r = 0; r < reps; r++) sumDigits(r + 1_000_000); 
    } 
    public void timeBetterDigitSum(int reps) { 
    for (int r = 0; r < reps; r++) sumDigitsBetter(r + 1_000_000); 
    } 
    public static int sumDigits(long n){ 
    int sum = 0; 
    String s = "" + n; 
    while (!s.equals("")){ 
     sum += Integer.parseInt("" + s.charAt(0)); 
     s = s.substring(1); 
    } 
    return sum; 
    } 
    static int sumDigitsBetter(long n) { 
    int sum = 0; 
    for (; n != 0; sum += n % 10, n /= 10); 
    return sum; 
    } 
    public static void main(String... args) { 
    Runner.main(Performance.class, args); 
    } 
}

（扰流溶液中取出，可通过编辑历史）

来源

2012-12-12 21:57:13

+1你一直很忙;-) – assylias

@assylias无法帮助它，这是一种内疚的享受:) –

@MarkoTopolnik删除扰流板，请。 – Justin

项目欧拉＃119做出更快

回答

相关问题