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

模範解答のミソ

  • 模範解答ではブーリアン型を使って解いている。
  • TrueとFalseの反転を利用している。
  • 正負の反転を使ったわたしの解答と、基本的な考え方は変わらない。

修正されたわたしの解答

cards = [True]*100
for n in range (2,101):
    k = n
    while k < 100:
        cards[k] = not cards[k]
        k = k + n
f = 0
while f < 100:
    try:
        f = cards.index(True,f)
        print f
        f += 1
    except:
        f += 1

気づき・反省点

  • 今回苦労したのは、解答を出力する部分。
  • Pythonのfind, indexメソッドは左端から検索して最初にヒットした箇所のindexを返す。
  • 網羅的に全ての検索結果を返すメソッドは探しえた限り見つからなかった。
  • 左端から検索し、ヒットしたら右隣から更に検索するプログラムを組んだ。
  • findメソッドだと、検索対象が見つからなかった時に-1を返すので無限ループに陥ってしまう。
  • indexメソッドは検索対象が見つからなかった時にエラーとなる。
  • try-exceptによる例外処理でエラーを回避した。

参考にしたサイト

Pythonを学ぼう 第19回 文字列の操作 - ほぷしぃ
Pythonの例外処理 - Life with Python