[アルゴリズム]奇妙な計算機

質問のタイプ

:最初はBFSを使おうとは思っていませんでしたが、BFSで簡単に解決できる問題です.

もんだいぶんせき

:まず,問題で要求されるのは,特定数Nを所定の条件での異常計算器とするために,何回ボタンを押す必要があるかである.この場合、計算機は*2と//3を選択できます.この2つの選択のみがNを作成する必要があり、開始値が1から始まります.問題では、作成できない値は入力値として与えられませんが、5桁を超える数値でNを作成しようとすると、計算機に障害が発生し、処理する必要があります.

問題を解く

:実は、この問題で、感覚のある部分は2つの選択地で、選択地の上で他の選択の方法をします.
1
*2 //3
= 2 = 0
*2 //3 *2 //3
=4 = 0 =0 =0
:上記のようにrootnodeを1とし、2^n個のルールを継続して持ち、ストレッチのバイナリツリーとなる.選択地は、各選択地の2つの選択地であるため、可能なツリーモデルである.したがって、この問題のポイントは、計算機の結果値には2つのオプション(*2,//3)があり、これらのオプションをグラフィック形式で表示できることです.これにより、BFSまたはDFSにかかわらず、可能なすべてのオプションの数を参照できます.BFSによる検索が最も効果的な方法であるため、BFSを選択して問題を解決する必要があります.問題の探索空間を考慮して、すべての選択を考慮すべきで、私は最初simplewhile文を通じてそれにアクセスしようとしました.しかし,グラフという資料構造を考えると,問題は非常に容易になる.まだ明確ではないが,このように問題に要求される論理と資料構造の特性を結びつけると,問題解決がより容易になる.

インプリメンテーション

depth = {} path = {} n = int(input()) if n == 1: print(0) else: path[1] = True depth[1] = 0 queue = [1] def get_two_choices(num) : return [num*2, num//3] flag = False while not flag: top = queue.pop(0) for el in get_two_choices(top): try: if path[el]: continue except: if el == n: flag = True print(depth[top] + 1) break path[el] = True if len(str(el)) > 5: continue depth[el] = depth[top] + 1 queue.append(el)