こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 36から40を解いてみました。
Problem 36
自分なり直訳してみました。
100万未満で10進数と2進数で回文数になる数の和を求めよ。
（回文数は、両方の基数で、先頭に0を含めないことに注意）
ソース
private void test() {
int sum = 0;
for (int i = 1; i < 1000000; i++) {
if (i % 10 != 0 && i % 10 != 2
&& check(String.valueOf(i))
&& check(String.valueOf(Integer.toBinaryString(i)))) {
sum += i;
}
}
System.out.println(sum);
}
private boolean check(String s) {
return s.equals(new StringBuilder(s).reverse().toString());
}checkメソッドを作って回文数かを判定しています。文字列の反転はStringBuilder#reverse()メソッドで可能です。反転後のString型オブジェクトはnew StringBuilder(s).reverse().toString()になります。最後のtoString()を忘れると、コンパイルエラーにはなりませんが結果が期待通りになりません。このcheckメソッド自体は任意の文字列に対して、回文かどうかを判定する作りになっています。
このメソッドに自然数iとその2進数表示を渡せばよいのですが、2進数表記はJavaにはInteger#toBinaryString()メソッドがあります。先頭が0で始まるものを含めないという問題なので、回文の先頭が0になるパターンを除いています。その条件は、10進数の場合が「i % 10 != 0」で2進数の場合が「i % 10 != 2」です。後半の条件は2進数表示で1桁目が0にならないということです。
Problem 37
自分なり直訳してみました。
左から右と右から左両方で縮められるのは11個の素数のみで、その和を求めよ。
注意：2、3、5、7は縮められる素数とは考えない。
ソース
private void test() {
int sum = 0;
for (int i = 10; i < 1000000; i++) {
if (checkTruncatableOf(i)) {
sum += i;
}
}
System.out.println(sum);
}
private boolean checkPrimaricityOf(int n) {
if (n == 1) {
return false;
}
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
private boolean checkTruncatableOf(int n) {
if (!checkPrimaricityOf(n)) {
return false;
}
String s = String.valueOf(n);
for (int i = 1; i < s.length(); i++) {
if (!checkPrimaricityOf(Integer.parseInt(s.substring(i)))
|| !checkPrimaricityOf(Integer.parseInt(s.substring(0, i)))) {
return false;
}
}
return true;
}まず素数か判定する必要があるため、checkPrimaricityOf()メソッドを作りました。1は素数ではないので、その場合は最初のif文でfalseを返却するようにしています。
縮められる素数かどうかを判定するため、checkTruncatableOf()メソッドを作りました。まず、自身が素数であるか判定しています。String型変数sに格納し、縮めた数をString#substring()メソッドで求めました。ちょうど、s.substring(i)、s.substring(0, i)で求めることができました。あとはそれぞれが素数かを判定するのみです。String#substring()メソッドの戻り値はString型なのでint型に直す必要がありますが、それはInteger#parseInt()メソッドで出来ます。
問題文では縮められる素数は11個だけあると書いてあります。なのでfor文の上限は実行しながら適当に決めました。while文でも良かったのかもしれません。また、一桁の素数は縮められる素数とは考えないという記述があるため、for文の最初を10にしています。
Problem 38
自分なり直訳してみました。
- 192 × 1 = 192
- 192 × 2 = 384
- 192 × 3 = 576
各積を連結することにより、1から9のpandigital 192384576が得られる。192384576を192と(1,2,3)の連結積と呼ぶ。
同様に、9で1、2、3、4、5を積を連結すると、pandigital 918273645が得られ、これは9と(1,2,3,4,5)の連結積である。
n > 1で、(1,2, … , n)との連結積を形成する1から9のpandigitalである9桁の数で最大のものは何か？
ソース
private void test() {
int max = 0;
for (int i = 1; i < 10000; i++) {
String s = createConcatenatedProductNear9DigitFrom(i);
if (checkPandigitalityOf(s)) {
max = Math.max(max, Integer.valueOf(s));
}
}
System.out.println(max);
}
private String createConcatenatedProductNear9DigitFrom(int n) {
StringBuilder sb = new StringBuilder(String.valueOf(n));
int multiplier = 1;
while (sb.length() < 9) {
sb.append(String.valueOf(n * (++ multiplier)));
}
return sb.toString();
}
private boolean checkPandigitalityOf(String s) {
if (s.length() != 9) {
return false;
}
int[] counts = new int[10];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - '0'] ++;
}
if (counts[0] > 0) {
return false;
}
for (int i = 1; i < counts.length; i++) {
if (counts[i] != 1) {
return false;
}
}
return true;
}createConcatenatedProductNear9DigitFromという長い名前のメソッドを定義しました。与えられた自然数から9桁に近い連結積を作るメソッドです。順番に積を連結していますが、連結回数が複数のため、StringBuilderを使っています。実際はwhile文の条件により、返却値は9桁以上になります。メソッド名は少々良くないかもしれませんが、他に思い浮かびませんでした。
checkPandigitalityOfメソッドを定義しました。これは与えられた自然数の文字列が1から9のpandigitalであるかどうかを判定するメソッドです。最初に9桁でない場合はfalseを返却しています。あとは各桁に1から9が1度だけ登場するということを調べています。注意としては0が登場してはならないということです。
for文によって問題文の条件を満たす最大の数を計算していますが、for文の終わりは適当です。実行しながら決めました。連結積によってはcreateConcatenatedProductNear9DigitFromメソッドの返却値はint型に収まらないかもしれませんが、checkPandigitalityOfメソッドで9桁である連結積のみを扱うことになるため、Integer.valueOf(s)の箇所ではエラーはでません。
Problem 39
自分なり直訳してみました。
{20,48,52}, {24,45,51}, {30,40,50}
p ≤ 1000に対して、解の数の最大となるpは何か？
ソース
private void test() {
int max = 0;
int p = 0;
for (int i = 1; i <= 1000; i++) {
int sumOfSolutions = numOfRightAngleTriangleWithPerimeter(i);
if (max < sumOfSolutions) {
max = sumOfSolutions;
p = i;
}
}
System.out.println(p);
}
private int numOfRightAngleTriangleWithPerimeter(int p) {
int sum = 0;
for (int i = 1; i < p; i++) {
for (int j = i; j < p; j++) {
int hypotence = p - i - j;
if (hypotence * hypotence == i * i + j * j) {
sum ++;
}
}
}
return sum;
}numOfRightAngleTriangleWithPerimeterというメソッドを作りました。直角三角形の周の長さを引数にしています。for文の2重ループで直角三角形を形成する辺の長さの組み合わせをカウントしています。斜辺以外の辺の長さをi、jとしています。辺の長さの組合せとして{ i, j, p-i-j }を考えます。直角三角形の場合、三平方の定理が成り立つ必要があるということです。つまり、斜辺の2乗が残りの2辺の2乗の和に等しいことを判定しています。
辺の長さの組み合わせのみをカウントするので、for文の2重ループでjの開始はiからにしています。それぞれp未満までとしていますが、斜辺が一番長いことを考えるともう少し条件を小さくできるかもしれません。
Problem 40
0.123456789101112131415161718192021…
小数部分の12桁目は1である。
d_nで小数部分のn桁目表すとき、次の展開の値を求めよ。
d_1 × d_10 × d_100 × d_1000 × d_10000 × d_100000 × d_1000000
ソース
private void test() {
StringBuilder sb = new StringBuilder();
int n = 1;
int nth = 1;
int value = 1;
do {
sb.append(String.valueOf(n++));
int length = sb.length();
if (length == 1 || length > nth) {
value *= Integer.valueOf(sb.charAt(nth - 1) - '0');
nth *= 10;
}
} while (sb.length() < 1000000);
System.out.println(value);
}問題文の無理数は、小数第1位から順番に1, 2, 3, …を順番に後ろに連結した数です。小数部分の並びをStringBuilder型変数に格納することにしました。文字列の連結を繰り返すからString型ではなく、StringBuilder型を使います。StringBuilder#charAtがあるので、これで小数部分のn番目を取り出します。ただし、charAtでは要素番号を指定するのでnth – 1が指定する引数になります。また、文字コードが取得されるので’0’との差を取っています。そのあとvalueに掛け算をしています。
問題文で求める数は1桁の自然数7個の積なので変数valueはint型にしました。
小数部分の長さが1000000を超えたら終わりです。なのでdo-while文の条件はsb.length() < 1000000です。