পাইথনে সিঁড়ি ব্যবহার করে পরবর্তী ফ্লোরে পৌঁছানোর উপায় সংখ্যা বের করার প্রোগ্রাম

ধরুন, একটি সিঁড়ি আছে যাতে N ধাপ (steps) আছে। কেউ ধাপে ধাপে যেতে পারে, অথবা প্রতিটি ধাপে, কেউ সর্বোচ্চ N ধাপের লাফ (jump) নিতে পারে। আমাদের সéon উপায় সংখ্যা বের করতে হবে যাতে আমরা উপরের ফ্লোরে যেতে পারি। N মান বড় হতে পারে, আমরা কেবল উপায় সংখ্যার প্রথম এবং শেষ K অঙ্কে আগ্রহী।

সুতরাং, যদি ইনপুট হয় N = 10, k = 2, তবে আউটপুট হবে 63 কারণ ১০ ধাপ আছে, যদি উপরে যাওয়ার S সংখ্যক উপায় থাকে, তবে S-কে wxyz রূপে বিবেচনা করুন। সুতরাং, wx + yz যোগফল হল 63।

এটি সমাধান করার জন্য, আমরা নিচের ধাপগুলো অনুসরণ করব:

N := N - 1
c := 2 * ceiling(k + log(N); base 10)
e := N, b := 2, s := 1
যখন e > 0, করুন:
- যদি e বিজোড় (odd) হয়, তবে:
  - s := (s*b)-এর প্রথম p-c অঙ্কের সংখ্যা, যেখানে p হল s*b-র অঙ্ক সংখ্যা
- e := floor(e/2)
- b := (b*b)-এর প্রথম p-c অঙ্কের সংখ্যা, যেখানে p হল b*b-র অঙ্ক সংখ্যা
s := s-এর প্রথম p - k অঙ্কের সংখ্যা, যেখানে p হল 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))

ইনপুট

10, 2