給定 N 作為自然數，我們可以和他一起做這 3 個操作。
1) 從 N 中減去 1
2）如果是偶數，除以2
3）如果它除以3，那么除以3
當 N 變為 1 時，我們停止此操作。我們需要找到最小的操作，使 N 變為 1
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'count' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER num as parameter.
#
def count(num):
count = 0
while num != 1:
if (num % 3 ==0 ):
count = 1
num = num / 3
elif((num -1) % 3 == 0):
count = 2
num = (num - 1) / 3
elif (num % 2 ==0):
count = 1
num = num / 2
else:
num = num - 1
count = 1
return count
這是我的代碼。從 11 個測驗用例中，它通過了 9 個并給出了 2 個錯誤答案。我不知道我的代碼針對哪些測驗用例給出了錯誤的答案。您能幫助了解問題出在哪里嗎？
uj5u.com熱心網友回復：
您假設最好先減去 1 然后除以 3，但這并不總是正確的。
考慮 16
您的解決方案是 16-15-5-4-3-1 = 5 個步驟
更好的解決方案：16-8-4-2-1 = 4 步
uj5u.com熱心網友回復：
可能不是最有效的解決方案，但是：
def count(num):
count1, count2 = float('inf'), float('inf')
if num == 1:
return 0
if num % 3 == 0:
count1 = 1 count(num // 3)
if num % 2 == 0:
count2 = 1 count(num // 2)
count3 = 1 count(num - 1)
return min(count1, count2, count3)
uj5u.com熱心網友回復：
這些型別的問題通常有一小部分規則可以產生最佳答案。
但是，您的基本問題是您假設您的規則集是最佳的，沒有任何證據。你真的沒有理由相信它會產生正確的計數。
不幸的是，這些關于 SO 的問題的答案有時會提供正確的規則集，但似乎總是忽略任何證明規則集是最優的。
你必須做一些保證有效的事情，所以除非你有那種證據，否則你應該求助于 A* 搜索或類似的搜索。
uj5u.com熱心網友回復：
您可以使用非遞回廣度優先策略。
假設有一個佇列持有數字串列。最初，將僅包含 N 的串列輸入到佇列中。然后重復以下操作，直到佇列為空：
- 選擇佇列中的第一個串列。
- 對所有三個操作重復 3。
- 選擇一個操作。如果可能，將其應用于最后一個串列編號并將結果添加到串列末尾。如果串列是一個解決方案，請將其存盤在某個地方。如果沒有，請將其添加到佇列的末尾。
該策略是詳盡無遺的，可以找到所有解決方案。由于只對最小值感興趣，因此我們引入了限制界限。一旦解決方案串列可用，我們不會將比該串列更長的串列輸入到佇列中，如果它們已經在佇列中，我們也不會考慮它們。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492025.html
標籤：Python python-3.x 算法
上一篇：排序保留2個專案在頂部