暇なので
暇つぶしに数学オリンピックの
問題をプログラムで解いてみることにしました。
解説動画はこちら
さて今回はこんな問題です。
・・・
うーーーん
全然プログラムが終わりません。
10桁なので90億回近く計算する羽目になります。
これだと普通のPCではなかなか終わりません。
そこでもっと効率の良いコードを
考えてみることにします。
itertoolsを使うと
順列を求めることができます。
この場合全ての桁の数が違う数値10個を使った
順列を求めてあげれば
10桁全ての整数で判定しなくても良くなります。
答えはresultの個数を数えて
3456個になりました。
最後は
ある日数学者ハーディが入院中の
友人ラマヌジャンを見舞いに行ったとき
ここで XXXX はある 4 桁の正の整数を表している。
このとき次の問題に答えなさい。

さて、この数式を少し変えてみると

これならプログラムに組み込めますね。
早速mとnを求める感じにしてみましょう。
さて答えはmが12 , nが9です。
この二通りの組み合わせから求められる
4桁の整数は
1729
になります。
このような2つの立方数の和として
n 通りに表される最小の正の整数を
ラマヌジャンさんのタクシー数
と言っているそうです。
なかなか面白い数ですね。
タクシー数は他にもありますが
手計算するのはしんどいですねーーー
でもプログラムならすぐに求めることができるのが
プログラムのいいところです。
数学オリンピックの問題でさえも
整数問題なら、PCを持ち込めれば解ける!!!!!
(多分ダメだーー)
なので、答えだけは出せます。
手でやる解き方は知りません。
今回はここまでです
それでは。
暇つぶしに数学オリンピックの
問題をプログラムで解いてみることにしました。
解説動画はこちら
さて今回はこんな問題です。
引用:2016年ジュニア数学オリンピック予選
「各桁の数字が相異なるような37の倍数のうち
最大のものを求めよ。」
最大のものを求めよ。」
雑なコードで解いてみることにします。
各桁が異なる整数で最大になるのは・・・
9876543210
でしょうね。
でしょうね。
あとは37の倍数ならOKなので
この値から1ずつ引いて
37の倍数
かつ
各桁が異なる整数
になれば良いですね。
コードはこんな感じになりました。
答えは・・・
9876435012
各桁が異なる整数で37で割り切れますね。
コードでは判定する部分として
37で割りきれるかどうかは
37で割った余りが0になるということになります。
%で余を求められるので
計算できますね。
10桁の各桁が異なるは
いったん数字に直して
10個の数字をセットに入れ込みます。
そうすると各桁が違い場合は
長さが10
各桁で同じ数字が来た場合は
長さが10未満になるので弾けます。
この2つの判定を用いて
その最大値を求めました。
プログラムで解くと
早く終わりますねwww
では次
引用:平成26年度 京都数学オリンピック道場
これもさっきと同じ
各桁が違うがそのまま使えますね。
割る数を変えて11111にすれば
簡単に解けちゃいますね!!!!!
この値から1ずつ引いて
37の倍数
かつ
各桁が異なる整数
になれば良いですね。
コードはこんな感じになりました。
num = 9876543210 for i in range(num,0,-1): if i%37==0 and len({n for n in str(i)})==10: print(i) break
答えは・・・
9876435012
各桁が異なる整数で37で割り切れますね。
コードでは判定する部分として
37で割りきれるかどうかは
37で割った余りが0になるということになります。
%で余を求められるので
計算できますね。
10桁の各桁が異なるは
いったん数字に直して
10個の数字をセットに入れ込みます。
そうすると各桁が違い場合は
長さが10
各桁で同じ数字が来た場合は
長さが10未満になるので弾けます。
この2つの判定を用いて
その最大値を求めました。
プログラムで解くと
早く終わりますねwww
では次
引用:平成26年度 京都数学オリンピック道場
10 桁の正の整数の各桁に 0 以上 9 以下のすべての整数が現れ
かつ 11111 の倍数であるとき,
その整数を面白い整数と呼ぶことにする。
面白い整数は全部でいくつあるか。
面白い整数は全部でいくつあるか。
これもさっきと同じ
各桁が違うがそのまま使えますね。
割る数を変えて11111にすれば
簡単に解けちゃいますね!!!!!
num = 9876543210 result = [] for i in range(num,1023456789,-1): if i%11111==0 and len({n for n in str(i)})==10: result.append(i)
・・・
うーーーん
全然プログラムが終わりません。
10桁なので90億回近く計算する羽目になります。
これだと普通のPCではなかなか終わりません。
そこでもっと効率の良いコードを
考えてみることにします。
import itertools result = [] for nums in itertools.permutations([1,2,3,4,5,6,7,8,9,0],10): num = int(''.join([str(n) for n in nums])) if num<1000000000: break if num%11111==0: result.append(num) print(len(result))
itertoolsを使うと
順列を求めることができます。
この場合全ての桁の数が違う数値10個を使った
順列を求めてあげれば
10桁全ての整数で判定しなくても良くなります。
答えはresultの個数を数えて
3456個になりました。
最後は
引用:平成26年度 京都数学オリンピック道場
ある日数学者ハーディが入院中の
友人ラマヌジャンを見舞いに行ったとき
「乗ってきたタクシーのナンバーが XXXX だった。」
と言ったところ,これを聞いたラマヌジャンは
「とても興味深い数字です
XXXX は2つの立方数の和で 2 通りに表せる
最小の数なのです。」と答えた。
XXXX は2つの立方数の和で 2 通りに表せる
最小の数なのです。」と答えた。
ここで XXXX はある 4 桁の正の整数を表している。
このとき次の問題に答えなさい。

さて、この数式を少し変えてみると

これならプログラムに組み込めますね。
早速mとnを求める感じにしてみましょう。
for m in range(2,100): for n in range(2,100): if m**3-n**3 == 999: print('m:{0} , n:{1}'.format(m,n)) breakm:12 , n:9
さて答えはmが12 , nが9です。
この二通りの組み合わせから求められる
4桁の整数は
1729
になります。
このような2つの立方数の和として
n 通りに表される最小の正の整数を
ラマヌジャンさんのタクシー数
と言っているそうです。
なかなか面白い数ですね。
タクシー数は他にもありますが
手計算するのはしんどいですねーーー
でもプログラムならすぐに求めることができるのが
プログラムのいいところです。
数学オリンピックの問題でさえも
整数問題なら、PCを持ち込めれば解ける!!!!!
(多分ダメだーー)
手でやる解き方は知りません。
今回はここまでです
それでは。
コメントする