Chương trình tìm số cách chúng ta có thể lên tầng tiếp theo bằng cầu thang trong Python

Giả sử có một trường hợp cầu thang có N bậc. Người ta có thể đi từng bước hoặc ở mỗi bước, người ta có thể nhảy nhiều nhất N bước. Chúng ta phải tìm ra số cách mà chúng ta có thể lên đến tầng cao nhất. Giá trị N có thể lớn, chúng tôi chỉ quan tâm đến K chữ số đầu tiên và K chữ số cuối cùng của số cách.

Vì vậy, nếu đầu vào là N =10 k =2, thì đầu ra sẽ là 63 vì có 10 bước, nếu có S số cách mà chúng ta có thể đi đến đỉnh, thì coi S có dạng wxyz Vì vậy, tổng wx + yz là 63.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=N - 1
• c:=2 * trần của (k + log (N); base10)
• e:=N, b:=2, s:=1
• while e> 0, do
  • nếu e là số lẻ, thì
    • s:=các số p-c đầu tiên của (s * b) trong đó p là số các chữ số trong s * b
  • e:=tầng của e / 2
  • b:=các số p-c đầu tiên của (b * b) trong đó p là số các chữ số trong b * b
• s:=p - k chữ số đầu tiên của s, trong đó p là số chữ số trong s
• r:=s + (2 ^ N) mod 10 ^ k
• trả về r

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

10, 2

Đầu ra

63