โปรแกรมหาทางไปชั้นถัดไปโดยใช้บันไดในภาษา Python

สมมติว่ามีบันไดแบบ N ขั้น หนึ่งสามารถไปทีละขั้นตอนหรือในแต่ละขั้นตอนสามารถกระโดดได้มากที่สุด N ขั้นตอน เราต้องหาหลายวิธีที่จะขึ้นไปชั้นบนสุดได้ ค่า N อาจมาก เราสนใจเฉพาะตัวเลข K ตัวแรกและตัวสุดท้ายของจำนวนวิธีเท่านั้น

ดังนั้นหากอินพุตเป็น N =10 k =2 เอาต์พุตจะเป็น 63 เพราะมี 10 ขั้นตอน หากมีหลายวิธีที่เราสามารถขึ้นไปบนได้ S ให้ถือว่า S อยู่ในรูปแบบ wxyz .ดังนั้น การรวม wx + yz เท่ากับ 63

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=N - 1
• c :=2 * เพดานของ (k + log(N);base10)
• e :=N, b :=2, s :=1
• ในขณะที่ e> 0, ทำ
  • ถ้า e เป็นเลขคี่
    • s :=หมายเลขหลัก p-c แรกของ (s*b) โดยที่ p คือจำนวนหลักใน s*b
  • e :=ชั้นของ e/2
  • b :=หมายเลขหลัก p-c แรกของ (b*b) โดยที่ p คือจำนวนหลักใน b*b
• s :=ตัวเลข p - k ตัวแรกของ s โดยที่ p คือจำนวนหลักใน s
• r :=s + (2^N) mod 10^k
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from math import log10,ceil

def solve(N,k):
   N -= 1
   c = 2*ceil(k + log10(N))
   e = N
   b = 2
   s = 1
   while e > 0:
      if e % 2 == 1:
         s = int(str(s*b)[:c])
      e //=2
      b = int(str(b*b)[:c])
   s = str(s)[:k]
   r = int(s) + pow(2, N, 10**k)
   return r

N = 10
k = 2
print(solve(N,k))

อินพุต

10, 2

ผลลัพธ์

63