"""BTVN CS11.1 Bài2. Các hàm số nhận n nguyên không âm; lũy thừa xét a khác0.

Mẫu chạy chọn n từ0 đến20. Tìm nhị phân cần A đã xếp không giảm.
"""


def tong(n):
    if n == 0:
        return 0
    return n + tong(n - 1)


def tong_le(n):
    if n <= 0:
        return 0
    if n % 2 == 1:
        return n + tong_le(n - 1)
    return tong_le(n - 1)


def giai_thua(n):
    if n == 0:
        return 1
    return n * giai_thua(n - 1)


def luy_thua(a, n):
    if n == 0:
        return 1
    return a * luy_thua(a, n - 1)


def tong_giai_thua(p, k, n):
    if k > n:
        return 0
    p = p * k
    return p + tong_giai_thua(p, k + 1, n)


def tim_nhi_phan(A, left, right, K):
    if left > right:
        return -1
    mid = (left + right) // 2
    if A[mid] == K:
        return mid
    if A[mid] < K:
        return tim_nhi_phan(
            A, mid + 1, right, K)
    return tim_nhi_phan(
        A, left, mid - 1, K)


def in_nguoc(A, k):
    if k < 0:
        return
    print(A[k], end=" ")
    in_nguoc(A, k - 1)


def sap_xep_chen(A, k):
    if k <= 0:
        return
    sap_xep_chen(A, k - 1)
    value = A[k]
    j = k - 1
    while j >= 0 and A[j] > value:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = value


def main():
    try:
        n = int(input("Nhập n từ 0 đến 20 trong mẫu thử: "))
    except ValueError:
        print("Cần nhập một số nguyên.")
        return
    if not 0 <= n <= 20:
        print("Mẫu thử chỉ nhận n từ 0 đến 20.")
        return
    print("S(n) =", tong(n))
    print("SL(n) =", tong_le(n))
    print("n! =", giai_thua(n))
    print("3^n =", luy_thua(3, n))
    print("Tổng giai thừa =", tong_giai_thua(1, 1, n))
    A = [9, 4, 7, 4]
    print("Dãy đảo:", end=" ")
    in_nguoc(A, len(A) - 1)
    print()
    sap_xep_chen(A, len(A) - 1)
    print("Dãy sau sắp xếp:", A)
    print("Chỉ số của 7:", tim_nhi_phan(A, 0, len(A) - 1, 7))


if __name__ == "__main__":
    main()