Pythonで解く数学パズル

「プログラマ脳を鍛える数学パズル」をPythonで解きます。

カードを裏返して!:「プログラマ脳を鍛える数学パズル」Q03の答え

問題

1~100までの番号が書かれた100枚のカードが順番に並べられています。
最初、すべてのカードは裏返しの状態で置かれています。

ある人が2番のカードから、1つおきにカードを裏返していきます。すると、2, 4, 6, … , 100番のカードが表を向いています。
次に、別の人が、3番のカードから2つおきにカードを裏返していきます。(裏向きのカードは表を向き、表向いているカードは裏返しされます。)
また、別の人が、4番のカードから3つおきに、カードを裏返してきます。

このようにn番目のカードからn-1つおきにカードを裏返す操作を、どのカードの向きも変わらなくなるまで続けたとします。

裏向きになっているカードの番号をすべて求めてください。

元ネタ:
第13回「今週のアルゴリズム:カードを裏返して!」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • 表と裏を判定するのに0か1かで2進数のビット演算子を使うことを当初考えたが、うまくいかずに断念した。
  • 次いで表と裏を正負の逆転で表すことを考えた。-1をかけることで正負が逆転する。
  • 1を100個並べたリストを作成し、裏返すカードにあたる数値に-1をかけることを繰り返せば良い。
  • n番目のカードからn-1つおきにカードを裏返す = インデックスnの値に-1をかける。インデックス2n, 3n, 4nと-1をかけて行く。

わたしのオリジナル解答

cards = [1]*100
for n in range (2,101):
    k = n
    while k < 100:
        cards[k] = cards[k] * -1
        k = k + n
f = 0
while f < 100:
    try:
        f = cards.index(1,f)
        print f
        f += 1
    except:
        f += 1
続きを読む

数列の四則演算:「プログラマ脳を鍛える数学パズル」Q02の答え

問題

数字を文字列として表し、各桁の間に四則演算の演算子を入れることを考えます。 (演算子は入れても入れなくても構いません。)

例)
1234 → 1 + 2 * 3 - 4 = 3
9876 → 9 * 87 + 6 = 789

でき上がった式を計算した結果、元の数の桁を逆から並べた数字と同じになるものを求めてください。
(式の計算は数学の順序で行います。※乗除が先、加減は後)

元ネタ:
第10回「今週のアルゴリズム:数列の四則演算」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • 回文を判定する関数を作る
  • 4桁の数字のそれぞれの間に四則演算記号をいれる組み合わせを考える。
  • 四則+何も入れないパターンで5通り。数字の間が3ヶ所なので53 = 125通りだが、全く何も入れないパターン(元の数字のまま)を除くと124通りある計算。

と、ここまでは考えてみたが、四則演算記号を挿入して計算結果を出す方法が考えられなかったのでちょっとだけカンニング

evalという組み込み関数を使えと言うアドバイスがあったので取り入れてプログラムを書いた。

わたしのオリジナル解答

def arepalinrome(x, y):
        return str(x) == str(y)[::-1]

op = ['+', '-', '*', '/','']
for num in range(1000,9999):
    for i in op:
        for j in op:
            for k in op:
                the_answer = eval(str(num)[0] + i + str(num)[1] + j +str(num)[2] + k + str(num)[3])
                if arepalinrome(num, the_answer):
                    print (str(num)[0] + i + str(num)[1] + j +str(num)[2] + k + str(num)[3] + "=" + str(the_answer))

ループを深く掘り下げるコードはなかなか難しい。

だが、実はこのコードはエラーが発生して解答が出ない。0で割ってしまうのと、「08」のような数字が生じてエラーが出るようだ。

続きを読む

10進数で回文:「プログラマ脳を鍛える数学パズル」Q01の答え

問題

10進数、2進数、8進数のいずれで表現しても回文数となる数のうち、 10進数の10以上で最小の値を求めてください。
回文数は逆から数字を読んでも同じ数になる数のことです。

元ネタ:
第4回「今週のアルゴリズム:10進数で回文」正解者発表|CodeIQ MAGAZINE

わたしの考え方

  • 回文を判定する関数を作る
  • 数値を文字列に変換>逆転し、元の文字列と等しいか判定する
  • 2進数、8進数への変換は組み込み関数bin(x), oct(x)を利用
  • 2進数、8進数はそれぞれアタマに0b, 0がつくのでそれらは取り除いて回文を判定しなければならない
  • 10以上で最小の答えをみつけるのは、変数iを用意して、i =10から初めてi += 1で一つずつ増やして行けばいいかと最初は思ったけど、うまく書けなかったのでrange(10, 1000)として答えを得た。

わたしのオリジナル解答

def ispalindrome(x):
    Dec_x = str(x)
    Bin_x = str(bin(x))[2:]
    Oct_x = str(oct(x))[1:]
    return Dec_x == Dec_x[::-1] and Bin_x == Bin_x[::-1] and Oct_x == Oct_x[::-1]

for i in range(10, 1000):
    if ispalindrome(i):
        print i
続きを読む

はじめに

さて

当ブログ、Pythonで解く数学パズルは私iGCNのPython学習の記録をつけて行くために開設しました。

今年の初めに2016年の目標としてプログラミングを勉強することを思い立ち、数ある言語の中からPythonを選んで学習を開始しました。

igcn.hateblo.jp

igcn.hateblo.jp

これまでにPythonスタートブックやドットインストール、Codecademyなどの教材で勉強してきました。Pythonの基礎は分かってきた気がしますが、自分でゼロからコーディングする能力はまだ身に付いていないと思います。

そこで、アルゴリズムを作る能力とコーディング力を鍛えるために次の教材としてプログラマ脳を鍛える数学パズル」Pythonで読み解くことを思い立ちました。

本書はCodeIQに掲載された数学アルゴリズム問題をまとめた本で、解説と解答サンプルコードが計70問分納められています。ただし、解答はRubyで書かれています。

それを敢えてPythonで解いてみようと思い立ったのでした。

これからの予定

計70問の問題を解きながら、その過程をこのブログに記録して行こうと思います。そんなに自由時間もないので、週に1ー2問ずつくらいのペースでボチボチ進めて行こうと思っています。

具体的には、

答えを導くためのアルゴリズムを考える

それを実現するためのPythonコードをまずは自力で書いてみる

解答を読んで、RubyをPythonで実装し直してみる

のような構成で、1問解くごとに解答をアップして行こうと思います。つまり70回分のネタが既にストックされていると言うことになりますね。

さいごに

頑張って年内に終わらせたいところですが、もしかして1回も記事がアップされないまま終わってしまったりして。と言うことがないように、皆様からのpeer pressureをお待ちしております。

間違っている点の指摘や、こうした方が良いよ等のアドバイスのコメントもお待ちしています。

では