Đưa về 0
Xem PDF
Điểm:
500 (p)
Thời gian:
1.0s
Bộ nhớ:
128M
Input:
bàn phím
Output:
màn hình
Cho một số nguyên dương \(N\). Thực hiện các thao tác sau để đưa \(N\) về \(0\) với số bước ít nhất:
- Nếu \(N\) là số chẵn, thực hiện \(N\) = \(\frac{N}{2}\).
- Nếu \(N\) là số lẻ, thực hiện \(N\) = \(N - 1\).
Hãy viết một chương trình:
- Nhập vào một số nguyên dương \(N (1 ≤ N ≤ 10^{18})\).
- In ra số bước ít nhất để đưa \(N\) về 0.
Ví dụ
Input
15
Ouput
7
Note
Bước 1: 15 (lẻ) -> 14
Bước 2: 14 (chẵn) -> 7
Bước 3: 7 (lẻ) -> 6
Bước 4: 6 (chẵn) -> 3
Bước 5: 3 (lẻ) -> 2
Bước 6: 2 (chẵn) -> 1
Bước 7: 1 (lẻ) -> 0
Tổng số bước: 7
Bình luận
n=int(input())
d=0
while n>0:
if n%2==0:
n//=2
else:
n-=1
d+=1
print(d)
ez