โปรแกรมหาจำนวนวิธีขึ้นชั้นถัดไปด้วยบันได ใน Python

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

เช่น N=10, k=2 ผลลัพธ์ 63 เพราะจำนวนวิธี S = wxyz ผลรวม wx + yz = 63

วิธีแก้ปัญหา

• N := N - 1
• c := 2 * ceil(k + log10(N))
• e := N, b := 2, s := 1
• while e > 0
  • ถ้า e คี่: s := p-c หลักแรกของ (s*b) โดย p คือจำนวนหลักของ s*b
  • e := floor(e/2)
  • b := p-c หลักแรกของ (b*b) โดย p คือจำนวนหลักของ b*b
• s := k หลักแรกของ s
• r := s + (2^N) mod 10^k
• คืนค่า r

ตัวอย่างโค้ด

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))

Input

10, 2

Output

63