Pythonでfind(x, y)の値が偶数か奇数かを判定するプログラム

配列 nums とインデックスのペア (x, y) が与えられ、再帰関数 find(x, y) の計算結果が偶数か奇数かを判定したい場面を考えてみましょう。find() 関数は次のように定義されています。

• x > y の場合：find(x, y) = 1
• それ以外の場合：find(x, y) = nums[x] ^ find(x+1, y)

なお、ここでの「^」はビット演算ではなく累乗（べき乗）を表すことに注意してください。

計算例

入力が nums = [3, 2, 7]、(x, y) = (1, 2) の場合、出力は「偶数（Even）」になります。その理由は以下の通りです。

• find(1, 2) = nums[1] ^ find(2, 2)
• find(2, 2) = nums[2] ^ find(3, 2)
• find(3, 2) = 1（3 > 2 が成立するため）
• よって find(2, 2) = 7 ^ 1 = 7、find(1, 2) = 2 ^ 7 = 128 となり、128 は偶数です

解法の考え方

再帰をそのまま計算すると、累乗によって値が爆発的に大きくなる可能性があります。そこで、結果の偶奇だけに着目することで、再帰を展開せずに効率的に判定できます。手順は以下の通りです。

• 変数 even を True で初期化します
• x > y の場合は find(x, y) = 1 となり必ず奇数なので、even を False にします
• nums[x] が奇数の場合、奇数を累乗しても結果は必ず奇数になるため、even を False にします
• x が配列の末尾より前であり、x < y かつ nums[x+1] が 0 の場合、find(x+1, y) が 0 になり、nums[x] ^ 0 = 1 という奇数になるため、even を False にします
• 最終的に even が True なら「Even」を、False なら「Odd」を返します

Pythonでの実装例

以下の実装を見ると、理解が深まります。

def solve(nums, x, y):
   even = True
   if x > y or (nums[x] % 2 == 1):
      even = False
   if x < len(nums) - 1 and x < y and nums[x+1] == 0:
      even = False
   if even:
      return 'Even'
   else:
      return 'Odd'

nums = [3,2,7]
(x, y) = 1,2
print(solve(nums, x, y))

入力

[3,2,7], 1, 2

出力

Even

このように、実際に大きな累乗を計算することなく、条件分岐だけで偶奇を判定できるのがこの手法のポイントです。