こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 57から58を解いてみました。
Problem 57
自分なりに直訳してみました。
- √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…
最初の4つの繰り返しに対してこの展開をすることにより、以下を得る:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…
その次の3つの項は99/70、239/169、そして577/408であるが、第8項は1393/985であり、分子の桁数が分母の桁数を超える最初の例である。
最初の1000項で、分子の桁数が分母の桁数より大きいような分数はいくつあるか?
連分数の計算を既存のライブラリでやってみたのですが、第50項でオーバーフローしました。なので、自前のクラスを作りました。
ソース
package problem00057;
import java.math.BigInteger;
public class MyFraction {
private static final BigInteger ZERO = new BigInteger("0");
private static final BigInteger ONE = new BigInteger("1");
/** 分子 */
private BigInteger numerator;
/** 分母 */
private BigInteger denominator;
MyFraction (BigInteger bigInteger) {
numerator = bigInteger;
denominator = ONE;
}
public MyFraction(BigInteger p ,BigInteger q) {
if (q.equals(ZERO)) {
throw new RuntimeException("分母を0に指定できません。");
}
numerator = p;
denominator = q;
BigInteger gcd = p.gcd(q);
numerator = numerator.divide(gcd);
denominator = denominator.divide(gcd);
}
public MyFraction add(MyFraction n) {
BigInteger p1 = n.getNumerator();
BigInteger q1 = n.getDenominator();
BigInteger p2 = numerator;
BigInteger q2 = denominator;
MyFraction f = new MyFraction(
p1.multiply(q2).add(p2.multiply(q1)),
q1.multiply(q2));
return f;
}
public MyFraction reverse() {
return new MyFraction(denominator, numerator);
}
@Override
public String toString() {
if (denominator.equals(new BigInteger("1"))) {
return numerator.toString();
}
return numerator + "/" + denominator;
}
/**
* @return 分子
*/
public BigInteger getNumerator() {
return numerator;
}
/**
* @return 分母
*/
public BigInteger getDenominator() {
return denominator;
}
}上記クラスは分母と分子をフィールドに持つMyFractionクラスです。分数の足し算と逆数を求めるというメソッドのみ実装しています。約分するには最小公倍数を求める必要がありますが、BigIntegerクラスにはgcd()メソッドが用意されていたので、それを使いました。
上記クラスを使って以下のようにプログラミングしました。
ソース
package problem00057;
import java.math.BigInteger;
public class Test {
public static void main(String[] args) {
new Test().test();
}
private void test() {
int count = 0;
for (int i = 1; i <= 1000; i++) {
MyFraction f = calc(i);
String p = f.getNumerator().toString();
String q = f.getDenominator().toString();
if (p.length() > q.length()) {
count ++;
}
}
System.out.println(count);
}
private MyFraction ZERO = new MyFraction(new BigInteger("0"));
private MyFraction ONE = new MyFraction(new BigInteger("1"));
private MyFraction TWO = new MyFraction(new BigInteger("2"));
private MyFraction calc(int numberOfIteration) {
MyFraction r = ZERO;
for (int i = 0; i < numberOfIteration; i++) {
r = r.add(TWO);
r = r.reverse();
}
r = r.add(ONE);
return r;
}
}calc()メソッドが第n項の計算をするメソッドです。連分数を最初から計算しなおすやり方なので、もっと工夫できるかもしれません。
Problem 58
自分なりに直訳してみました。
37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 41 20 7 8 9 10 27 42 21 22 23 24 25 26 43 44 45 46 47 48 49
興味深いことは、奇数の平方数が右下の対角線上にあることであるが、より興味深いことは、両方の対角線にある13個の数字のうち8個が素数である; 比率は8/13で約62%である。
渦巻に新しい層を計算し、長さ9の螺旋渦巻が形成される。この操作を続けていくと、対角線上の素数の割合が10%未満になるような最初の辺の長さを求めよ。
渦巻状の点を表すクラスSpiralPointを作りました。
ソース
package problem00058;
public class SpiralPoint {
private int x;
private int y;
private int number;
SpiralPoint() {
x = 0;
y = 0;
number = 1;
}
public void moveRight() {
x += 1;
number ++;
}
public void moveLeft() {
x -= 1;
number ++;
}
public void moveTop() {
y += 1;
number ++;
}
public void moveBottom() {
y -= 1;
number ++;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getNumber() {
return number;
}
@Override
public String toString() {
return "SpiralPoint [x=" + x + ", y=" + y + ", number=" + number + "]";
}
}移動した方向でフィールドx、yどちらかを変化させ、フィールドnumberの値が加算されます。フィールドx、yはデバッグで使いました。
このクラスを使い、以下のプログラムを書きました。
ソース
private void test() {
SpiralPoint spiralPoint = new SpiralPoint();
int total = 1;
int countOfPrimes = 0;
for (int i = 0; i < 10000000; i++) {
// 右に移動
spiralPoint.moveRight();
// 上に移動
int step = 2 * i + 1;
for (int j = 0; j < step; j++) {
spiralPoint.moveTop();
}
total ++;
if (check(spiralPoint.getNumber())) {
countOfPrimes++;
}
// 左に移動
step ++;
for (int j = 0; j < step; j++) {
spiralPoint.moveLeft();
}
total ++;
if (check(spiralPoint.getNumber())) {
countOfPrimes++;
}
// 下に移動
for (int j = 0; j < step; j++) {
spiralPoint.moveBottom();
}
total ++;
if (check(spiralPoint.getNumber())) {
countOfPrimes++;
}
// 右に移動
for (int j = 0; j < step; j++) {
spiralPoint.moveRight();
}
total ++;
if (check(spiralPoint.getNumber())) {
countOfPrimes++;
}
if ((double)countOfPrimes / total < 0.1) {
System.out.println(2 * i + 3);
break;
}
}
}
private boolean check(int n) {
for (int i = 2; i <= (int)Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}check()メソッドは素数判定です。対角線上の数を素数判定して、素数ならば素数の個数用の変数countOfPrimesを加算します。
「new SpiralPoint()」を宣言した時点で、点は中央の「1」の位置にある想定です。変数totalの初期値が1なのは、「1」が対角線上にあるからです。
for文のループ内の処理は以下のようになってます。
- 右に移動（1回）
- 上に移動（iに依存する回数）
- 左に移動（iに依存する回数）
- 下に移動（iに依存する回数）
- 右に移動（iに依存する回数）
これで渦巻を一回り大きくする処理になってます。右に1回移動した後は、上、左、下、右に規定回数移動したときにSpiralPointが対角線上の数になります。それぞれでtotalを加算し、素数判定をしています。ループの最後で比率を計算して、題意を満たすなら、辺の長さを出力するということをしています。