[問題解決]Baek Jun-16953 A->B(dfs&bfs)

8167 ワード
ProblemSolving テキストリンク

提问链接


問題の説明


整数AをBに変えたいです.可能な演算は次の2つです.
2を掛ける.
数の一番右に1を追加します.
AからBまでの演算の最大値を求める.

入力


第1行は、A、B(1≦A

しゅつりょく


AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.

入力例1


2 162

サンプル出力1


5

入力例2


4 42

サンプル出力2


-1

入力例3


100 40021

サンプル出力3


5

私の答え


ナビゲートする頂点(ノード)ごとに、ブランチを2回(*2または右側に1回)貼り付けます.
bfsで問題を解決する.
探索深さが深まるとdfsは非常に非効率になる.
AがBより大きいと探索を行う必要がないので,不適切な探索方法である.

コード1

  • 私のコード
    • from collections import deque

a, b = map(int, input().split())

answer = -1

queue = deque([(a,1)])
while queue:
    v, i = queue.popleft()
    if v==b:
        answer = i
        break
    if v*2 <= b:
        queue.append((v*2, i+1))
    if int(str(v)+ str(1)) <= b:
            queue.append((int(str(v)+ str(1)), i+1))
print(answer)

    その他の解釈。


    優先度キューは、まず優先度が最も高いデータ(小さなデータ)を抽出します.
    優先キューを使用して問題を解決する理由は、次のとおりです.
    a−>bを用いて2つの演算を同時に行うことができる.
    2つの演算の結果を要素のサイズ順にソートできるからです.

  • 優先キューの作成
    que = PriorityQueue()

  • 要素の追加
    que.put(4)

  • 要素の削除
    que.get()#小さい要素から削除

  • キューサイズ
    que.qsize()

    • コード2

  • その他のコード
    • from queue import PriorityQueue

a, b = map(int, input().split())
queue = PriorityQueue()
queue.put((a, 1))

while queue.qsize() > 0:
    c, n = queue.get()
    if c==b : 
        print(n)
        break
    elif c> b:
        print(-1)
        break
    else:
        queue.put((int(str(c)+"1"), n+1))
        queue.put((c*2, n+1))
    開放閉鎖原則のモデルの黄金法則
    ルーティーンを極める