1まで

2147 ワード
greedy algorithm algorithm テキストリンク
質問する
任意の数Nが1である前に、次の2つのプロセスのうちの1つを繰り返し選択して実行します.ただし,2番目の演算はNをKで割った場合にのみ選択できる.
  • Nから1を減算します.
  • NをKで割った.(ただしKはNの倍数である)
    • (例をスキップ)
    NとKが与えられると、Nが1になるまで1回または2回のプロセスを実行する最小回数を求めるプログラムを作成します.
    アイデア
    1までに最小回数を達成するには、もちろんより多くの数字を減らす必要があります.つまり、除算すればするほど有利になる.だから、分けられるなら分けて、分けられないなら1を抜く論理を作ったほうがいい.
    に答える
    n, k = map(int, input().split())
count = 0

while n != 1:
    if n % k == 0:
        n = n / k
        count = count + 1
    else:
        n = n - 1
        count = count + 1

print(count)
    アイデアをコードに変換するだけで簡単な問題です.
    フィードバック
  • の考え方に正当性を与えようとしたが、残念ながら数学的な証明はしていなかった…
  • を改善する方法もある.よく勉強しなさい.
    • その他
  • 時間:7分
    • Ruby開発用アルゴリズム
    vue javaバックグラウンドExcel互換ieのエクスポート