こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 16から20を解いてみました。
Problem 16
自分なり直訳してみました。
2^15 = 32768であり各桁の合計は3 + 2 + 7 + 6 + 8 = 26である。
2^1000の各桁の合計は何か？
ソース
BigInteger bigInteger1 = new BigInteger("1");
BigInteger bigInteger2 = new BigInteger("2");
for (int i = 1; i <= 1000; i++) {
bigInteger1 = bigInteger1.multiply(bigInteger2);
}
String s = bigInteger1.toString();
int sum = 0;
for (int i = 0; i < s.length(); i++) {
sum += s.charAt(i) - '0';
}
System.out.println(sum);2のべき乗を1000回も計算する問題なのでBigIntegerクラスを使いました。for文はiが1から1000にして、2のi乗がbigInteger1に格納されるようにしています。String#charAtメソッドは文字コードを取得するため、’0’との差を使ってます。
Problem 17
自分なり直訳してみました。
1から5の数字を英語で書くと、one, two, three, four, fiveであり、合計で3 + 3 + 5 + 4 + 4 = 19文字使われている。
1から1000の数字を英語で書くと、何文字使われているか。
注意：空白またはハイフンはカウントしない。例えば、342 (three hundred and forty-two)は23文字で、115 (one hundred and fifteen)は20文字である。”and”を使うのはBritishの慣習である。
ソース
private final String[] GROUP1_9 = {
"one",
"two",
"three",
"four",
"five",
"six",
"seven",
"eight",
"nine"
};
private final String[] GROUP10_19 = {
"ten",
"eleven",
"twelve",
"thirteen",
"fourteen",
"fifteen",
"sixteen",
"seventeen",
"eighteen",
"nineteen",
};
private final String[] PREFIX_DIGIT_2 = {
"twenty",
"thirty",
"forty",
"fifty",
"sixty",
"seventy",
"eighty",
"ninety"
};
private final String HUNDRED = "hundred";
private final String THOUSAND = "thousand";
private final String AND = "and";
private void test() {
int sum = 0;
for (int i = 1; i < 1000; i++) {
if (i < 100) {
sum += getSumOfDigit1_2(i);
} else {
sum += getSumOfDigit3(i);
}
}
sum += GROUP1_9[0].length() + THOUSAND.length();
System.out.println(sum);
}
private int getSumOfDigit1_2(int num) {
int sum = 0;
if (1 <= num && num <= 9) {
sum = GROUP1_9[num -1].length();
} else if (10 <= num && num <= 19) {
sum = GROUP10_19[num - 10].length();
} else {
// 20から99
int digit1 = num % 10;
int digit2 = num / 10;
// 2桁目
sum += PREFIX_DIGIT_2[digit2 - 2].length();
// 1桁目
if (digit1 != 0) {
sum += GROUP1_9[digit1 - 1].length();
}
}
return sum;
}
private int getSumOfDigit3(int num) {
int sum = 0;
int digit3 = num / 100;
// "XXX hundred and"
sum += GROUP1_9[digit3 - 1].length() + HUNDRED.length();
// 1-2桁目
int digit1_2 = num % 100;
if (digit1_2 != 0) {
sum += AND.length() + getSumOfDigit1_2(digit1_2);
}
return sum;
}10から19までは例外的に個別にString配列に定義しました。その他の場合は「one」から「nine」、「twenty」から「ninety」を使う考え方です。スペースとハイフンはカウントしないため、元からString型変数に追加していません。また4桁の数は1000のみなのでそれは個別にカウントしています。
Problem 18
自分なり直訳してみました。
以下の三角形を頂点から下の行における隣接する数へ移動するとき、頂点から下部までの最大値は23である。
3 7 4 2 4 6 8 5 9 3
つまり、3 + 7 + 4 + 9 = 23。
以下の三角形で頂点から下部までの最大を求めよ。
～数字の三角形～
注意：16384通りあるが、すべての通りを試すことで解決できる。しかし、 Problem 67では100行の三角形なので総当たりでは解けない。賢い方法が必要である。
ソース
private final String[][] ROWS_STR = {
{ "75" },
{ "95", "64" },
{ "17", "47", "82" },
{ "18", "35", "87", "10" },
{ "20", "04", "82", "47", "65" },
{ "19", "01", "23", "75", "03", "34" },
{ "88", "02", "77", "73", "07", "63", "67" },
{ "99", "65", "04", "28", "06", "16", "70", "92" },
{ "41", "41", "26", "56", "83", "40", "80", "70", "33" },
{ "41", "48", "72", "33", "47", "32", "37", "16", "94", "29" },
{ "53", "71", "44", "65", "25", "43", "91", "52", "97", "51", "14" },
{ "70", "11", "33", "28", "77", "73", "17", "78", "39", "68", "17", "57" },
{ "91", "71", "52", "38", "17", "14", "91", "43", "58", "50", "27", "29", "48" },
{ "63", "66", "04", "68", "89", "53", "67", "30", "73", "16", "69", "87", "40", "31" },
{ "04", "62", "98", "27", "23", "09", "70", "98", "73", "93", "38", "53", "60", "04", "23" }
};
private int[][] rows_int;
private int max = 0;
private void test() {
rows_int = new int[ROWS_STR.length][];
for (int i = 0; i < ROWS_STR.length; i++) {
rows_int[i] = new int[ROWS_STR[i].length];
for (int j = 0; j < ROWS_STR[i].length; j++) {
rows_int[i][j] = Integer.parseInt(ROWS_STR[i][j]);
}
}
move(0, 0, 0);
System.out.println(max);
}
private void move(int i, int j, int num) {
int sum = num + rows_int[i][j];
if (i == ROWS_STR.length - 1) {
max = Math.max(max, sum);
return ;
}
// 左下
move(i + 1, j, sum);
// 右下
move(i + 1, j + 1, sum);
}フィールドに合計の最大値を格納するための変数maxを用意しました。再帰呼び出し用のmoveメソッドを定義して、呼び出しの末端でmaxに最大値を格納するという考え方で作りました。
与えらて数字の三角形は文字列として2次元配列に格納しました。これは数値リテラルで09が範囲外になるためです。0で始まる場合、8進数扱いになります。ただし、09を9を書き換えるだけで良かった気がします。
Problem 19
自分なり直訳してみました。
以下の情報が与えられている。
- 1 Jan 1900はMonday。
- September, April, JuneそしてNovemberに30日ある。2月を除いて他は31日ある。2月は28日で、うるう年は29日。
- うるう年は4年で割れる年だが、400で割れないかつ100で割れないのはうるう年ではない。
1 Jan 1901から31 Dec 2000で月のはじめが日曜日であるのは何回か。
ソース
LocalDate localDate = LocalDate.of(1901, 1, 1);
int count = 0;
while (localDate.getYear() <= 2000) {
if (localDate.getDayOfWeek() == DayOfWeek.SUNDAY) {
count ++;
}
localDate = localDate.plusMonths(1);
}
System.out.println(count);Java8からLocalDateクラスがあります。年月日を扱うクラスです。plusMonthsメソッドで1か月加算することができます。getDayOfWeekメソッドで曜日を取得することができます。これを使うと簡単に問題を解くことができました。
Problem 20
自分なり直訳してみました。
n!はn × (n − 1) × … × 3 × 2 × 1を表す。
例えば、10! = 10 × 9 × … × 3 × 2 × 1 = 3628800であり、その数10!の各桁の合計は3 + 6 + 2 + 8 + 8 + 0 + 0 = 27である。
100!の各桁の合計を求めよ。
ソース
private void test() {
BigInteger bigInteger = cal(new BigInteger("1"), 100);
String s = bigInteger.toString();
int sum = 0;
for (int i = 0; i < s.length(); i++) {
sum += s.charAt(i) - '0';
}
System.out.println(sum);
}
private BigInteger cal(BigInteger bigInteger, int num) {
if (num == 1) {
return bigInteger;
} else {
return cal(bigInteger.multiply(new BigInteger(String.valueOf(num))), num - 1);
}
}階乗の計算なので、BigIntegerを使いました。再帰呼び出しでmultiplyメソッドを使って積を計算しています。各桁の合計は一度String型に直して、charAtメソッドを使ってます。ただし、文字コードが取得されてるので’0’との差を加算するようにしています。