Pythonで数値の複合被加数の最大数を見つける

指定された数Nがあり、範囲（1 <=N <=10 ^ 9）の場合、Nを可能な最大数の複合被加数の合計として表す必要があります。この最大数を返します。それ以外の場合、分割が見つからない場合は、-1を返します。

したがって、入力が16の場合、出力は4になります。16は4 + 4 + 4+4または8+8と書くことができますが、（4 + 4 + 4 + 4）には最大の被加数があります。

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

• max_val：=16

• 関数pre_calc（）を定義します。これには時間がかかります

• table：=サイズmax_valのリスト、各位置に-1を格納

• table [0]：=0

• v：=[4、6、9]

• 1からmax_valの範囲のiの場合、1ずつ増やします。

  • 0から2の範囲のkの場合、実行

    • j：=v [k]

    • i> =jであり、table [i --j]が-1でない場合、

      • table [i]：=table [i]の最大値、table [i --j] + 1

• リターンテーブル

• 関数max_summ（）を定義します。これはテーブルを取ります、n

• n

  • リターンテーブル[n]

• それ以外の場合

  • t：=整数（（n-max_val）/ 4）+ 1

  • t+テーブルを返す[n-4* t]

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

• テーブル：=pre_calc（）

• max_summ（table、n）

  を表示します

例

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

global max_val
max_val = 16
def pre_calc():
   table = [-1 for i in range(max_val)]
   table[0] = 0
   v = [4, 6, 9]
   for i in range(1, max_val, 1):
      for k in range(3):
         j = v[k]
         if (i >= j and table[i - j] != -1):
            table[i] = max(table[i], table[i - j] + 1)
   return table
def max_summ(table, n):
   if (n < max_val):
      return table[n]
   else:
      t = int((n - max_val) / 4)+ 1
      return t + table[n - 4 * t]
n = 16
table = pre_calc()
print(max_summ(table, n))

入力

16

出力

4