สมมติว่าเรามีตัวเลข A และ B สองตัว เราต้องหาจำนวนบวกขั้นต่ำ M เพื่อให้ M หารด้วย A ลงตัว และผลรวมของหลัก M เท่ากับ B ดังนั้นหากไม่มีผลลัพธ์ดังกล่าว ให้ส่งคืน - 1.
ดังนั้น หากอินพุตเป็น A =50, B =2 ผลลัพธ์จะเป็น 200 เนื่องจากหารด้วย 50 ลงตัว และผลรวมของหลัก =2 + 0 + 0 =2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดคอนเทนเนอร์ประเภทองค์ประกอบหนึ่งรายการ ที่มีสองตัวเลข a และ b และหนึ่งสตริง
-
que :=รายการใหม่
-
elem :=องค์ประกอบใหม่ที่มี (0, 0, สตริงว่าง)
-
เข้าชมแล้ว[0, 0] :=1
-
แทรกองค์ประกอบที่ส่วนท้ายของ que
-
ในขณะที่ขนาดของ que> 0 ทำ
-
temp_elem :=ลบองค์ประกอบแรกออกจาก que
-
ถ้า temp_elem.a เป็น 0 และ temp_elem.b คือ b แล้ว
-
คืนค่าจำนวนเต็มของ temp_elem.string
-
-
สำหรับผมอยู่ในช่วง 0 ถึง 9 ทำ
-
x :=(temp_elem.a * 10 + i) mod a
-
y :=temp_elem.b + i
-
ถ้า y <=b และเข้าชม[x, y] เป็นเท็จ แล้ว
-
เยี่ยมชม[x, y] :=1
-
แทรกองค์ประกอบใหม่ด้วย x, y และ temp_elem.string เชื่อมเข้าด้วยกัน
-
-
-
-
กลับ -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
visited = [[0 for x in range(501)] for y in range(5001)] class Element: def __init__(self, a, b, string): self.a = a self.b = b self.string = string def get_number(a, b): que = [] elem = Element(0, 0, "") visited[0][0] = 1 que.append(elem) while len(que) > 0: temp_elem = que.pop(0) if temp_elem.a == 0 and temp_elem.b == b: return int(temp_elem.string) for i in range(0, 10): x = (temp_elem.a * 10 + i) % a y = temp_elem.b + i if y <= b and visited[x][y] == False: visited[x][y] = 1 que.append(Element(x, y, temp_elem.string + str(i))) return -1 a, b = 50, 2 print(get_number(a, b))
อินพุต
50, 2
ผลลัพธ์
200
