この電脳クラブは、私では解けなかった。問題は次の通り。
相異なる7数(すべて正数)がある。そのうちの6数を選んで掛け合わせ、 それに残りの1数を足すと素数になる。これはどの6数を選んでも成立している。 このような7数の組み合わせのうち、その7数の和が最小のものを見つけよ。
こたえは次の2組。
1 3 5 7 17 22 23
1 3 8 11 13 17 25
今になったら解けるかもしれない。錆びついた頭を少しでも滑らかにしたいと思い、 2019 年に再挑戦することにした。ただし、C 言語はもう使いこなせないから、 JavaScript で対応しよう。
まず、相異なる正の数7数を作ることを考えよう。 これらを小さい順から n1, n2, n3, n4, n5, n6, n7 とする。 式で書けば次のようになる。
0 < n1 < n2 < n3 < n4 < n5 < n6 < n7
問題は、条件を満たす数の組み合わせのなかで、その総和が最小となるものを求めている。 したがって、総和の小さい順から列挙する必要がある。 n1 + n2 + n3 + n4 + n5 + n6 + n7 の総和を n とするとき、 n を固定したときの (n1, n2, n3, n4, n5, n6, n7) の組み合わせすべてを求める方法を考えなければならない。
まず考えやすいように、数の組み合わせが2つだけの場合からいく。 仮に n = 12 としよう。(2023-01-18, var を let に直した。以下も同様)
let n = 12;
for (n1 = 1; n1 < n / 2; n1++) {
alert(n1 + "," + (n - n1) );
}
まずはこうすれば 1,11 から始まって 5,7 までを出力してくれる。 次に、数の組み合わせが3つになった場合を考えよう。
let n = 12;
for (n1 = 1; n1 < n / 3; n1++) {
for (n2 = n1 + 1; n2 < (n - n1) / 2; n2++) {
alert(n1 + "," + n2 + "," + (n - n1 - n2) );
}
}
一番小さい n1 がとりうる値は、1 以上 12 / 3 未満である。 12 / 3 以下ではない理由は、仮に等号が成立すると すべての組み合わせが同じになってしまうからである。 同じように、n2 がとりうる値は、n1 + 1 以上、(12 - n1) / 2 未満である。
以下同じ要領で、組を構成する数だけループを多重にしていけばよい。
次に、題意の積和が素数か否か判定するプログラムを作る。 エラトステネスのふるいをはじめいろいろな方法はあるが、 素朴なプログラムで判定することにした。 特に説明の要はないと思う。
function isprime(p)
{
let rootmax = Math.sqrt(p);
if (p % 2 == 0) return false;
if (p % 3 == 0) return false;
for (let i = 6; i < rootmax; i += 6) {
if (p % (i - 1) == 0) return false;
if (p % (i + 1) == 0) return false;
}
return true;
}
買ってすぐのときやった結果が残っている。結果は60点ぐらいだった。 情けない。
最初の3問で正解がゼロで、既に躓いてしまった。もうだめだ。
最初の3問こそ正答だったが、その次の問題が3問誤答続きで、以降問題を解くのを諦めた。 さて、問題のコードを見てみると、こんな固有名詞があった。
出題者はクラシック音楽が好きなのかな。 次の問題はどうだろう?
カクテルのようだが、Shanghai はわからなかった。次の問題をみると、 Mateus や Zubrowka まである。
最初の数問に挑戦して、できは6割だった。全問をもしやったら、 もっとできは悪いだろう。
問1の最初10問に挑戦して、できは6割だった。全問をもしやったら、 もっとできは悪いだろう(Perlに同じ)。 もっと Ruby を応援したいのになあ。
まりんきょ学問所 > C言語手習い > C マガジンを読む (2001年3月号)