4

Project Eulerの問題119を解決しようとしています:

数字 512 が興味深いのは、5 + 1 + 2 = 8 と 8^3 = 512 という数字の累乗の合計に等しいからです。このプロパティを持つ数字の別の例は、614656 = 28^4 です。

an をこの数列の n 番目の項と定義し、合計を得るには少なくとも 2 桁の数字が含まれている必要があると主張します。

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 は、a が検定の検出力かどうかをチェックします。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

4

2 に答える 2

8

解決策は15桁の数字です。合計を最適化して、すべての数値をチェックするのに十分な速度で実行できるように頑張ってください。

問題を頭に置いてください。桁の合計は比較的少ない数（最大9 x数の桁数）であり、累乗も比較的低くなります（小さい数でも15桁に上げるのに大きな累乗は必要ありません） 。

したがって、合計と累乗をループし、合計を計算し（乗算を使用して、内側のループで現在の合計を維持できます。累乗の計算は必要ありません）、その桁を合計して、ループ変数と一致するかどうかを確認します。

数字は順番に並んでいないので、必要以上に計算して結果を並べ替えます。

約1秒で実行されます。

于 2012-12-12T22:35:11.710 に答える
5

その数字の合計について...ここにいくつかの確かな事実があります：

 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-12T21:57:13.517 に答える