0

したがって、問題なく動作します。必要な 2 つの主要な変更は、x の平方根までをチェックすることだけです (チェック ケースを余りのチェックインからべき乗のチェックに反転することも必要です)。もう 1 つの変更点は、数値が最大 double をはるかに超えるため、double の使用は明らかに無謀だったことです。

これは CodeEval からの挑戦です。Facebook から最初に尋ねられたと思います。これは私の脳が即座に吐き​​出したものです。すべての手動テスト ケース (例: 10-> 1、25->2、3-> 0) に合格します。私は自分の考えでどのようにしたかを最初に確認したいので、他の解決策は見ていません。私がベースから外れていて、これがうまくいかない場合は、誰かがそう言ってくれるとありがたいです:P. これがうまくいかず、新しい方法を考え出さなければならない場合、私はこれにもっと時間を費やします。

満足できないケースはすぐにはわかりません..しかし、それは問題ではありません。私は実行時の複雑さを計算するのが得意ではありませんでしたが、ネストが多すぎると思います。

左右からチェックすることで（これはコードでもう少し明確です）、実行時間を大幅に短縮できると思いました。それが思ったほど効果的でないだけなのか、それとも他のループがまだ多すぎるのか、それともその両方なのかはわかりません。

何かご意見は？これは回収可能ですか、それとも破棄して新しい方法で考える必要がありますか?

質問とコードが続きます。ご覧いただきありがとうございます:-)

クレジット: この課題は、Facebook Hacker Cup 2011 で登場しました
。2 乗数は、2 つの完全な 2 乗の和として表すことができる整数 X です。たとえば、10 = 3^2 + 1^2 であるため、10 は二重平方です。この問題でのあなたの仕事は、X が与えられたとき、それを 2 つの平方和として書ける方法の数を決定することです。たとえば、10 は 3^2 + 1^2 としてのみ記述できます (1^2 + 3^2 は異なるものとして数えません)。一方、25 は 5^2 + 0^2 または 4^2 + 3^2 と書くことができます。
注: ブルート フォース アプローチを試みないでください。効果がないでしょう。次の制約が保持されます:
0 <= X <= 2147483647
1 <= N <= 100

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class DoubleSquares {
    public static void main(String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader in = new BufferedReader(new FileReader(file));
        String line;
        while ((line = in.readLine()) != null) {
            int total = 0;
            String[] lineArray = line.split("\\s");
            if (lineArray.length > 0) {
                double x = (double) Integer.parseInt(lineArray[0]);
                if (x == 0){total++;} //special case if input is 0
                double sLeft = 0.00;  //left boundary to indicate where to stop (so we dont repeat e.g. 4+1 and 1+4)
                for(double sRight = x; sRight > sLeft; sRight--){
                    if (Math.sqrt(sRight) % 1 == 0){//has no remainder then it's a candidate..
                        double needed = x-sRight;
                        if (Math.sqrt(needed) % 1 == 0){//check of solution to what makes sRight == x is a perfect square.
                            total++; //increment if so.
                        }
                        sLeft = needed;
                    }
                }
            }
            System.out.println(total);
        }
    }
}

もう少し明確にするために、これは問題なく動作しているように見えますが、CodeEval 自動グレーダーに送信すると、10 秒の実行後に終了します。遅すぎるか、大きな入力でスタックしていることは間違いありません。

4

3 に答える 3

5

この問題は、Edsgar Dijkstra が 1976 年の著書The Discipline of Programmingで論じています。ダイクストラは、 xがnの整数平方根から下向きにスイープし、yがゼロから上向きにスイープするときに、1 回のパスですべてのペアを見つけます。次の 3 つの再帰規則と再帰ベースによって導かれる、xとyB(x, y)の間のすべての適切なペアを返す関数を考えてみましょう。

  • x² + y² < n の場合、B(x, y) = B(x, y+1) となります。これは、x ≥ u の解 (u, v) が存在しないためです。これは、u² + v² < n を意味するためです。
  • x² + y² = n の場合、ペア (x, y) は解であり、B(x, y) = (x, y) ⋃ B(x-1, y+1) であり、スイープが続行されます。
  • x² + y² > n の場合、x には可能な解がないため、B(x, y) = B(x-1, y) となります。
  • 最後に、x < y の場合、B(x, y) は null セットであり、再帰は停止します。

私のブログでSchemeでソリューションを書いた方法は次のとおりです。Javaに翻訳するのはあなたに任せます：

(define (squares n)
  (let loop ((x (isqrt n)) (y 0) (zs '()))
    (cond ((< x y) zs)
          ((< (+ (* x x) (* y y)) n) (loop x (+ y 1) zs))
          ((< n (+ (* x x) (* y y))) (loop (- x 1) y zs))
          (else (loop (- x 1) (+ y 1) (cons (list x y) zs))))))

テストケースとして役立つと思われるいくつかの例を次に示します。

> (squares 50)
((5 5) (7 1))
> (squares 48612265)
((5008 4851) (5139 4712) (5179 4668) (5243 4596) (5432 4371)
 (5613 4136) (5656 4077) (5691 4028) (5832 3821) (5907 3704)
 (6048 3469) (6124 3333) (6213 3164) (6259 3072) (6384 2803)
 (6404 2757) (6413 2736) (6556 2373) (6576 2317) (6637 2136)
 (6651 2092) (6756 1723) (6772 1659) (6789 1588) (6853 1284)
 (6899 1008) (6917 876) (6944 627) (6948 581) (6952 531)
 (6971 132) (6972 59))
> (squares 999)
()
于 2013-10-12T23:26:20.507 に答える
0

私の考えは：

  • 可能な最大の a または b を見つけます :int x1 = int(Math.sqrt(x))
  • 配列内の 0 から x1 までのすべての正方形をリストしますlong[] squares = new long[50000];
  • 今このループ：

int right = binarySearch(squares, math.sqrt(x1));

int count = 0;

for(int i = 0 ; i < right; i++){

   if(Math.sqrt(x-squares[i]) == int(Math.sqrt(x-squares[i]))){

      count++;

   } else if(int(Math.sqrt(x-squares[i])) < squares[i]) {

      break;

   }

}

System.out.println(x);

したがって、square 配列の要素と X の差が完全な正方形かどうかを確認するたびに、

これは私の考えですので、コメントするときはよろしくお願いします!!

于 2013-10-13T00:38:42.510 に答える