project Euler 021
環境
問題
d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.
例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.
それでは10000未満の友愛数の和を求めよ.
考え方
- 1から10000までの数を数え上げる。
- その数の約数の和を計算する
- 2.の和からさらに約数の和を計算する
- 数え上げの数字と3.の約数の和が等しい時、それらの数字を友愛数とし、配列に格納しておく
- 数え上げが終了した後、配列内の友愛数の和を計算する
コード
let limit = 10000;
let yuaisuList: number[] = [];
for (let a = 2; a < limit; a++) {
let yakusuAList = [1];
let yakusuBList = [1];
for (let i = 2; i < a; i++) {
if (a % i === 0) {
yakusuAList.push(i);
}
}
let sumA = yakusuAList.reduce((a, b) => a + b);
for (let i = 2; i < sumA; i++) {
if (sumA % i === 0) {
yakusuBList.push(i);
}
}
let sumB = yakusuBList.reduce((a, b) => a + b);
if (
a === sumB &&
!yuaisuList.find(yuaisu => yuaisu === a) &&
sumA !== sumB
) {
yuaisuList.push(a);
yuaisuList.push(sumA);
}
}
return yuaisuList.reduce((a, b) => a + b);
説明
project Euler 020
環境
問題
n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.
例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる.この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.
では, 100! の各位の数字の和を求めよ.
注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。
考え方
- 100!を計算する（bigint型）。
- 計算結果の各位の数字を取り出す
- 和を計算する
コード
let n = BigInt(100);
let sum = BigInt(1);
for (let i = n; n > BigInt(0); n--) {
sum = sum * n;
}
let array = [];
for (let j = 0; j <= String(sum).length; j++) {
array.push(String(sum).charAt(j));
}
return array.reduce((a, b) => {
return String(Number(a) + Number(b));
});
説明
- 100!を計算する（number型では計算できないため、bigint型を使う）
- 計算結果を文字列に変換し、各位の数を取り出す
- 取り出した文字を数字に再変換し、和を計算する
project Euler 019
環境
問題
次の情報が与えられている.
- 1900年1月1日は月曜日である.
- 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.
- 2月は28日まであるが, うるう年のときは29日である.
- うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.
20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?
考え方
- 変数に西暦年、月、日を設定する
- 日は「9月, 4月, 6月, 11月は30日, 2月を除く他の月は31日。」「2月は28日まであるが, うるう年のときは29日」「うるう年は西暦が4で割り切れる年に起こる。しかし、西暦が400で割り切れず100で割り切れる年はうるう年でない」条件を満たしつつ、for文で回す。
コード
// 0 = 日、1 = 月、2 = 火、3 = 水、4 = 木、5 = 金、6 = 土
let date = 1;
let limitDay = 31;
let sum = 0;
for (let year = 1900; year < 2001; year++) {
for (let month = 1; month < 13; month++) {
if (month === 9 || month === 4 || month === 6 || month === 11) {
limitDay = 30;
} else if (
month === 1 ||
month === 3 ||
month === 5 ||
month === 7 ||
month === 8 ||
month === 10 ||
month === 12
) {
limitDay = 31;
} else if (month === 2) {
if (year % 400 !== 0 && year % 100 === 0) {
limitDay = 28;
} else if (year % 4 === 0) {
limitDay = 29;
} else {
limitDay = 28;
}
}
for (let day = 1; day <= limitDay; day++) {
if (year > 1900 && day === 1 && date === 0) {
sum = sum + 1;
}
date = date + 1;
// 曜日計算
if (date === 7) {
date = 0;
}
}
}
}
return sum;
説明
- 曜日、月によって変化する日、月の初めが日曜日になる回数を変数に設定する。
- for 文で1900年から2000年までループする。
- その中で、for 文で1月から12月まで回す。
- この時、月によって変わる最後の日を条件分岐で設定する。
- さらにその中で、for 文で1日〜28 or 29 or 30 or 31日を回す。
- 日の for 文内で、月の初めが日曜日になる時かつ1901年以上の時、数える。
- さらに、曜日計算をする
project Euler 018 ❌
解けなかったよ。。
時間が出来たら、解答を見て理解する。
project Euler 017
環境
問題
1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.
注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.
考え方
- 1(one) ~ 10(ten), eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, and を文字数化する
- 1から1000までを数え上げる
- 数え上げ数を分解して、英単語で表す
- 英単語を文字数に変換する
- 合計値を計算する
コード
let eitangoList = [
{
number: 0,
eitango: ""
},
{
number: 1,
eitango: "one"
},
{
number: 2,
eitango: "two"
},
{
number: 3,
eitango: "three"
},
{
number: 4,
eitango: "four"
},
{
number: 5,
eitango: "five"
},
{
number: 6,
eitango: "six"
},
{
number: 7,
eitango: "seven"
},
{
number: 8,
eitango: "eight"
},
{
number: 9,
eitango: "nine"
},
{
number: 10,
eitango: "ten"
},
{
number: 11,
eitango: "eleven"
},
{
number: 12,
eitango: "twelve"
},
{
number: 13,
eitango: "thirteen"
},
{
number: 14,
eitango: "fourteen"
},
{
number: 15,
eitango: "fifteen"
},
{
number: 16,
eitango: "sixteen"
},
{
number: 17,
eitango: "seventeen"
},
{
number: 18,
eitango: "eighteen"
},
{
number: 19,
eitango: "nineteen"
},
{
number: 20,
eitango: "twenty"
},
{
number: 30,
eitango: "thirty"
},
{
number: 40,
eitango: "forty"
},
{
number: 50,
eitango: "fifty"
},
{
number: 60,
eitango: "sixty"
},
{
number: 70,
eitango: "seventy"
},
{
number: 80,
eitango: "eighty"
},
{
number: 90,
eitango: "ninety"
},
{
number: 100,
eitango: "hundred"
},
{
number: 1000,
eitango: "thousand"
}
];
let sum = 0;
for (let i = 1; i <= 1000; i++) {
let eitangosu: number | undefined = 0;
let iStr = String(i);
let niketa = String(i).substring(-2);
let sanketa = String(i).substring(-3);
// 一桁
if (iStr.length === 1) {
eitangosu = eitangoList.find(eigo => {
return i === eigo.number;
})?.eitango.length;
if (eitangosu) {
sum = sum + eitangosu;
}
}
// 二桁
if (iStr.length === 2) {
if (i < 21) {
eitangosu = eitangoList.find(eigo => {
return i === eigo.number;
})?.eitango.length;
if (eitangosu) {
sum = sum + eitangosu;
}
} else {
let niketame = niketa.charAt(0);
let hitoketame = niketa.charAt(1);
let ninokurai = niketame + "0";
let niketameeitango = eitangoList.find(eigo => {
return eigo.number === Number.parseInt(ninokurai);
});
let hitoketameeitango = eitangoList.find(eigo => {
return eigo.number === Number.parseInt(hitoketame);
});
if (!niketameeitango || !hitoketameeitango) return;
sum =
sum +
niketameeitango.eitango.length +
hitoketameeitango?.eitango.length;
}
}
// 三桁
if (iStr.length === 3) {
let sanketame = sanketa.charAt(0);
let niketame = niketa.charAt(1);
let hitoketame = niketa.charAt(2);
let sannokurai = sanketame;
let ninokurai = niketame + "0";
let sanketameeitango =
eitangoList.find(eigo => {
return eigo.number === Number.parseInt(sannokurai);
})?.eitango + "hundredand";
let niketameeitango = eitangoList.find(eigo => {
return eigo.number === Number.parseInt(ninokurai);
});
let hitoketameeitango = eitangoList.find(eigo => {
return eigo.number === Number.parseInt(hitoketame);
});
if (!niketameeitango || !hitoketameeitango) return;
sum =
sum +
sanketameeitango.length +
niketameeitango.eitango.length +
hitoketameeitango?.eitango.length;
}
if (iStr.length === 4) {
let yonnokurai = "onethousand";
sum = sum + yonnokurai.length;
}
}
return sum;
説明
- 英単語に対応する数を連想配列として設定する。
- 数え上げ数の1桁目、2桁目、3桁目の数字を文字に変換し、それぞれの長さを算出して、和を計算する
project Euler 016
環境
問題
215 = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる. 同様にして, 21000 の各位の数字の和を求めよ.
考え方
- 21000を計算する（bigint型）。
- 計算結果の各位の数字を取り出す
- 和を計算する
コード
let two = BigInt(2);
let ruijousu = 1000;
let result = BigInt(1);
for (let i = 1; i <= ruijousu; i++) {
result = result * two;
}
let resultStr = String(result);
let resultList = [];
for (let j = 0; j < resultStr.length; j++) {
resultList.push(resultStr.charAt(j));
}
let sum = 0;
resultList.forEach(result => {
sum = sum + Number.parseInt(result);
});
return sum;
説明
- 21000を計算する（number型では計算できないため、bigint型を使う）
- 計算結果を文字列に変換し、各位の数を取り出す
- 取り出した文字を数字に再変換し、和を計算する
project Euler 015
環境
問題
2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.
考え方
- 最短経路の算出の仕方は、例の場合は、4C2 = (4 * 3) / (2 * 1)
- 20×20の場合は、40C20
コード
const tate = 20;
const yoko = 20;
let bunbo = 1;
let bunshi = 1;
for (let i = tate + yoko; i > tate; i--) {
bunbo = bunbo * i;
}
for (let i = tate; i > 0; i--) {
bunshi = bunshi * i;
}
return Math.floor(bunbo / bunshi);
説明
組み合わせの計算をコードで書く
$$nCr = ( (n + r) * (n + r - 1) * (n + r - 2) * ( ... ) * n ) / ( r * (r - 1) * (r - 2) * ( ... ) * 1 )$$
最後に小数点を丸めて計算する
