PythonでN個のオレンジを食べる最小日数を見つけるプログラム

数nがあるとします。したがって、キッチンにn個のオレンジがあり、次のルールを維持しながら、これらのオレンジのいくつかを毎日食べていると考えてください。1.オレンジを1つ食べる。 2. nが偶数の場合は、n/2個のオレンジを食べます。 3. nが3で割り切れる場合、2 *（n / 3）個のオレンジを食べることができます。毎日1つのオプションしか選択できません。オレンジをn個食べるための最小日数を見つける必要があります。

したがって、入力がn =10の場合、出力は4になります。

• 1日目にオレンジを1つ、10-1=9を食べます。

• 2日目に6個のオレンジを食べます。9-2*（9/3）=9-6=3。

• 3日目にオレンジを2つ食べます。3-2*（3/3）=3-2=1です。

• 4日目に最後のオレンジを食べる1-1=0。

これを解決するには、次の手順に従います-

• 関数fun（）を定義します。これにはn

  かかります

• nがメモにある場合、

  • メモを返す[n]

• n <=2の場合、

  • nを返す

• memo [n]：=1 +最小値（n mod 2+ fun（n / 2の商））および（n mod 3 + fun（n / 3の商））

• メモを返す[n]

• メインの方法から、次のようにします

• memo：=新しい地図

• fun（n）を返す

例

理解を深めるために、次の実装を見てみましょう

def solve(n):
   def fun(n):
      if n in memo:
         return memo[n]
      if n<=2:
         return n
      memo[n]=1+min(n%2+fun(n//2),n%3+fun(n//3))
      return memo[n]
   memo={}
   return fun(n)

n = 12
print(solve(n))

入力

7, [5,1,4,3]

出力

4