こんにちは。「Javaを復習する初心者」です。
Project Eulerという数学の問題サイトがあります。そのサイトのProblem 11から15を解いてみました。
Problem 11
自分なり直訳してみました。
以下の20×20格子の中で、斜めに4つの数が赤くマークされている。その積は26 × 63 × 78 × 14 = 1788696である。
～数字の格子～
それらの積は26 × 63 × 78 × 14 = 1788696である。
この20×20格子の中で同じ方向で4つ隣接する数（上、下、左、右、または斜め）の積で最大は何か？
ソース
private final int SIZE = 20;
private void test() {
String[] strs = {
"08", "02", "22", "97", "38", "15", "00", "40", "00", "75", "04", "05", "07", "78", "52", "12", "50", "77", "91", "08",
"49", "49", "99", "40", "17", "81", "18", "57", "60", "87", "17", "40", "98", "43", "69", "48", "04", "56", "62", "00",
"81", "49", "31", "73", "55", "79", "14", "29", "93", "71", "40", "67", "53", "88", "30", "03", "49", "13", "36", "65",
"52", "70", "95", "23", "04", "60", "11", "42", "69", "24", "68", "56", "01", "32", "56", "71", "37", "02", "36", "91",
"22", "31", "16", "71", "51", "67", "63", "89", "41", "92", "36", "54", "22", "40", "40", "28", "66", "33", "13", "80",
"24", "47", "32", "60", "99", "03", "45", "02", "44", "75", "33", "53", "78", "36", "84", "20", "35", "17", "12", "50",
"32", "98", "81", "28", "64", "23", "67", "10", "26", "38", "40", "67", "59", "54", "70", "66", "18", "38", "64", "70",
"67", "26", "20", "68", "02", "62", "12", "20", "95", "63", "94", "39", "63", "08", "40", "91", "66", "49", "94", "21",
"24", "55", "58", "05", "66", "73", "99", "26", "97", "17", "78", "78", "96", "83", "14", "88", "34", "89", "63", "72",
"21", "36", "23", "09", "75", "00", "76", "44", "20", "45", "35", "14", "00", "61", "33", "97", "34", "31", "33", "95",
"78", "17", "53", "28", "22", "75", "31", "67", "15", "94", "03", "80", "04", "62", "16", "14", "09", "53", "56", "92",
"16", "39", "05", "42", "96", "35", "31", "47", "55", "58", "88", "24", "00", "17", "54", "24", "36", "29", "85", "57",
"86", "56", "00", "48", "35", "71", "89", "07", "05", "44", "44", "37", "44", "60", "21", "58", "51", "54", "17", "58",
"19", "80", "81", "68", "05", "94", "47", "69", "28", "73", "92", "13", "86", "52", "17", "77", "04", "89", "55", "40",
"04", "52", "08", "83", "97", "35", "99", "16", "07", "97", "57", "32", "16", "26", "26", "79", "33", "27", "98", "66",
"88", "36", "68", "87", "57", "62", "20", "72", "03", "46", "33", "67", "46", "55", "12", "32", "63", "93", "53", "69",
"04", "42", "16", "73", "38", "25", "39", "11", "24", "94", "72", "18", "08", "46", "29", "32", "40", "62", "76", "36",
"20", "69", "36", "41", "72", "30", "23", "88", "34", "62", "99", "69", "82", "67", "59", "85", "74", "04", "36", "16",
"20", "73", "35", "29", "78", "31", "90", "01", "74", "31", "49", "71", "48", "86", "81", "16", "23", "57", "05", "54",
"01", "70", "54", "71", "83", "51", "54", "69", "16", "92", "33", "48", "61", "43", "52", "01", "89", "19", "67", "48",
};
int[][] nums = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
nums[i][j] = Integer.parseInt(strs[i + j * SIZE]);
}
}
long max, temp;
max = getGreatestInDownDirection(nums);
temp = getGreatestInRightDirection(nums);
max = Math.max(max, temp);
temp = getGreatestInRightDownDirection(nums);
max = Math.max(max, temp);
temp = getGreatestInLeftDownDirection(nums);
max = Math.max(max, temp);
System.out.println(max);
}
private long getGreatestInDownDirection(int nums[][]) {
long max = 0;
for (int i = 0; i <SIZE - 4; i++) {
for (int j = 0; j < SIZE; j++) {
long p = nums[i][j] * nums[i + 1][j] * nums[i + 2][j] * nums[i + 3][j];
max = Math.max(max, p);
}
}
return max;
}
private long getGreatestInRightDirection(int nums[][]) {
long max = 0;
for (int i = 0; i <SIZE; i++) {
for (int j = 0; j < SIZE - 4; j++) {
long p = nums[i][j] * nums[i][j + 1] * nums[i][j + 2] * nums[i][j + 3];
max = Math.max(max, p);
}
}
return max;
}
private long getGreatestInRightDownDirection(int nums[][]) {
long max = 0;
for (int i = 0; i <SIZE - 4; i++) {
for (int j = 0; j < SIZE - 4; j++) {
long p = nums[i][j] * nums[i + 1][j + 1] * nums[i + 2][j + 2] * nums[i + 3][j + 3];
max = Math.max(max, p);
}
}
return max;
}
private long getGreatestInLeftDownDirection(int nums[][]) {
long max = 0;
for (int i = 0; i <SIZE - 4; i++) {
for (int j = 3; j < SIZE; j++) {
long p = nums[i][j] * nums[i + 1][j - 1] * nums[i + 2][j - 2] * nums[i + 3][j - 3];
max = Math.max(max, p);
}
}
return max;
}問題文には20×20の格子状に数字が記載されています。この数字のは04など0で始まる数字があります。Javaでは0で始まる数値リテラルは8進数で扱われます。今回は2桁なので気になりませんが、3桁の場合は注意が必要です。例えば、数値リテラル011は10進数で9です。なので、一般的な方法として、Javaのソースには文字列リテラルとして記述して、int型に変換しています。
問題文には隣接する4つの数字を選ぶ方向は「上、下、左、右、または斜め」と記述されていますが、今回は「下、右、斜め右下、斜め左下」の積の最大を取得するメソッドを使いました。「斜め」という方法が実質2種類あるのがポイントだと思います。
最大値をmaxという変数に格納していますが、そこではMath#maxメソッドを使っています。そこの部分はif文でも問題ないです。
Problem 12
自分なり直訳してみました。
三角数は自然数を加算することで得られる。7番目の三角数は1 + 2 + 3 + 4 + 5 + 6 + 7 = 28となる。最初の10項は次である：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
最初の7個の三角数の約数を挙げると以下になる：
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
28は5個以上の約数を持つ最初の三角数であることが分かる。
500個以上の約数を持つ最初の三角数の値は何か？
ソース
private void test() {
long num = 0;
long triangleNumber = 0;
while (true) {
triangleNumber += ++num;
if (getCountOfDivisorsOf(triangleNumber) >= 500) {
break;
}
}
System.out.println(triangleNumber);
}
private int getCountOfDivisorsOf(long num) {
int count = 0;
double sqrtDouble = Math.sqrt(num);
int sqrtInt = (int)sqrtDouble;
for (long i = 1; i <= sqrtInt; i++) {
if (num % i == 0) {
count += 2;
}
}
if (sqrtDouble - sqrtInt == 0) {
count --;
}
return count;
}この問題をやって気づいたことは、約数を調べるのは時間がかかるということです。for文の条件式で「i <= sqrtInt」にして、iが約数ならばcountを「+2」しています。これは約数を並べたときに積の組合せが中央で左右対称の位置にあるという性質を考えるとわかります。numの平方根より小さい約数にはそれとペアになるnumの平方根より大きい約数があるということです。ただし、約数が元の数の平方根と等しい場合は2重にカウントしていることになるため、最後のif文で調整しています。for文の条件を単純に「i <= num」にしてしまうと大変時間がかかります。
Problem 13
自分なり直訳してみました。
以下50個の100桁の数字の合計の最初の10桁を求めよ。
～数字の表～
ソース
private void test() {
String[] strs = {
"37107287533902102798797998220837590246510135740250"
, "46376937677490009712648124896970078050417018260538"
, "74324986199524741059474233309513058123726617309629"
, "91942213363574161572522430563301811072406154908250"
, "23067588207539346171171980310421047513778063246676"
, "89261670696623633820136378418383684178734361726757"
, "28112879812849979408065481931592621691275889832738"
, "44274228917432520321923589422876796487670272189318"
, "47451445736001306439091167216856844588711603153276"
, "70386486105843025439939619828917593665686757934951"
, "62176457141856560629502157223196586755079324193331"
, "64906352462741904929101432445813822663347944758178"
, "92575867718337217661963751590579239728245598838407"
, "58203565325359399008402633568948830189458628227828"
, "80181199384826282014278194139940567587151170094390"
, "35398664372827112653829987240784473053190104293586"
, "86515506006295864861532075273371959191420517255829"
, "71693888707715466499115593487603532921714970056938"
, "54370070576826684624621495650076471787294438377604"
, "53282654108756828443191190634694037855217779295145"
, "36123272525000296071075082563815656710885258350721"
, "45876576172410976447339110607218265236877223636045"
, "17423706905851860660448207621209813287860733969412"
, "81142660418086830619328460811191061556940512689692"
, "51934325451728388641918047049293215058642563049483"
, "62467221648435076201727918039944693004732956340691"
, "15732444386908125794514089057706229429197107928209"
, "55037687525678773091862540744969844508330393682126"
, "18336384825330154686196124348767681297534375946515"
, "80386287592878490201521685554828717201219257766954"
, "78182833757993103614740356856449095527097864797581"
, "16726320100436897842553539920931837441497806860984"
, "48403098129077791799088218795327364475675590848030"
, "87086987551392711854517078544161852424320693150332"
, "59959406895756536782107074926966537676326235447210"
, "69793950679652694742597709739166693763042633987085"
, "41052684708299085211399427365734116182760315001271"
, "65378607361501080857009149939512557028198746004375"
, "35829035317434717326932123578154982629742552737307"
, "94953759765105305946966067683156574377167401875275"
, "88902802571733229619176668713819931811048770190271"
, "25267680276078003013678680992525463401061632866526"
, "36270218540497705585629946580636237993140746255962"
, "24074486908231174977792365466257246923322810917141"
, "91430288197103288597806669760892938638285025333403"
, "34413065578016127815921815005561868836468420090470"
, "23053081172816430487623791969842487255036638784583"
, "11487696932154902810424020138335124462181441773470"
, "63783299490636259666498587618221225225512486764533"
, "67720186971698544312419572409913959008952310058822"
, "95548255300263520781532296796249481641953868218774"
, "76085327132285723110424803456124867697064507995236"
, "37774242535411291684276865538926205024910326572967"
, "23701913275725675285653248258265463092207058596522"
, "29798860272258331913126375147341994889534765745501"
, "18495701454879288984856827726077713721403798879715"
, "38298203783031473527721580348144513491373226651381"
, "34829543829199918180278916522431027392251122869539"
, "40957953066405232632538044100059654939159879593635"
, "29746152185502371307642255121183693803580388584903"
, "41698116222072977186158236678424689157993532961922"
, "62467957194401269043877107275048102390895523597457"
, "23189706772547915061505504953922979530901129967519"
, "86188088225875314529584099251203829009407770775672"
, "11306739708304724483816533873502340845647058077308"
, "82959174767140363198008187129011875491310547126581"
, "97623331044818386269515456334926366572897563400500"
, "42846280183517070527831839425882145521227251250327"
, "55121603546981200581762165212827652751691296897789"
, "32238195734329339946437501907836945765883352399886"
, "75506164965184775180738168837861091527357929701337"
, "62177842752192623401942399639168044983993173312731"
, "32924185707147349566916674687634660915035914677504"
, "99518671430235219628894890102423325116913619626622"
, "73267460800591547471830798392868535206946944540724"
, "76841822524674417161514036427982273348055556214818"
, "97142617910342598647204516893989422179826088076852"
, "87783646182799346313767754307809363333018982642090"
, "10848802521674670883215120185883543223812876952786"
, "71329612474782464538636993009049310363619763878039"
, "62184073572399794223406235393808339651327408011116"
, "66627891981488087797941876876144230030984490851411"
, "60661826293682836764744779239180335110989069790714"
, "85786944089552990653640447425576083659976645795096"
, "66024396409905389607120198219976047599490197230297"
, "64913982680032973156037120041377903785566085089252"
, "16730939319872750275468906903707539413042652315011"
, "94809377245048795150954100921645863754710598436791"
, "78639167021187492431995700641917969777599028300699"
, "15368713711936614952811305876380278410754449733078"
, "40789923115535562561142322423255033685442488917353"
, "44889911501440648020369068063960672322193204149535"
, "41503128880339536053299340368006977710650566631954"
, "81234880673210146739058568557934581403627822703280"
, "82616570773948327592232845941706525094512325230608"
, "22918802058777319719839450180888072429661980811197"
, "77158542502016545090413245809786882778948721859617"
, "72107838435069186155435662884062257473692284509516"
, "20849603980134001723930671666823555245252804609722"
, "53503534226472524250874054075591789781264330331690" };
BigInteger bigInteger = new BigInteger("0");
for (String s : strs) {
bigInteger = bigInteger.add(new BigInteger(s));
}
System.out.print(bigInteger.toString().substring(0, 10));
}Javaには大きな数値を扱うためにはBigIntegerというクラスがあります。問題文の数字はString型の配列に格納しておき、String型からBigIntegerを生成して加算していくという方法にしました。加算の部分では、BigIntegerは変更が不可能なクラスであるため、「bigInteger = bigInteger.add(new BigInteger(s));」という記述をしています。合計の最初の10桁を求めるので、変数bigIntegerをString型に直してsubStringで最初の10桁を取り出しています。
Problem 14
自分なり直訳してみました。
反復列を次で定義する：
- n → n/2 (nが偶数)
- n → 3n + 1 (nが奇数)
上記の規則で13から開始すると次の列を得る。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
(13から始まり1で終わる)この列は10項を含む。全ての数で開始しても1で終わると考えられているが、証明はされていない（Collatz問題）。
100万未満の数で開始して最長の数列を得るのは何か？
注意：数列を開始すれば100万を超えても良い。
ソース
private void test() {
int max = 0;
long start = 0;
for (long i = 1; i < 1000000; i++) {
int length = 1;
long num = i;
do {
num = iter(num);
length ++;
} while (num != 1);
if (max < length) {
max = length;
start = i;
}
}
System.out.println(start);
}
private long iter(long n) {
if (n % 2 == 0) {
return n / 2;
} else {
return 3 * n + 1;
}
}Problem 15
自分なり直訳してみました。
2×2格子の左上の角から初めて、右か下だけに進むと、ちょうど6通りのルートががある。
20×20格子のではいくつのルートがあるか。
ソース
private final int SUM = 40;
private final int CHOICE = 20;
private void test() {
BigInteger bigInteger1 = iter(new BigInteger(String.valueOf(SUM)), SUM - 1, SUM - CHOICE + 1);
BigInteger bigInteger2 = iter(new BigInteger(String.valueOf(CHOICE)), CHOICE - 1, 1);
System.out.println(bigInteger1.divide(bigInteger2));
}
private BigInteger iter(BigInteger num, int mul, int min) {
if (mul >= min) {
return iter(num.multiply(new BigInteger(String.valueOf(mul))), mul - 1, min);
} else {
return num;
}
}組合せの公式で解きました。ただし、数値が大きいのでBigIntegerを使いました。