Cho một số nguyên Number làm đầu vào. Mục tiêu là tìm số bước hoặc phép toán tối thiểu để giảm Number về 1. Các phép toán được phép:
Nếu Number chẵn, chia cho 2.
Nếu Number lẻ, tăng hoặc giảm 1.
Ví dụ
Đầu vào - Number = 28
Đầu ra - Số bước tối thiểu giảm 28 về 1: 6
Giải thích -
28 chẵn - chia 2 = 14
14 chẵn - chia 2 = 7
7 lẻ - tăng 1 = 8
8 chẵn - chia 2 = 4
4 chẵn - chia 2 = 2
2 chẵn - chia 2 = 1
Đầu vào - Number = 9
Đầu ra - Số bước tối thiểu giảm 9 về 1: 4
Giải thích -
9 lẻ - giảm 1 = 8
8 chẵn - chia 2 = 4
4 chẵn - chia 2 = 2
2 chẵn - chia 2 = 1
Phương pháp sử dụng trong chương trình dưới đây
Sử dụng đệ quy để kiểm tra số phép toán tối thiểu giảm Number về 1. Nếu chẵn thì chia 2, nếu lẻ thì đệ quy kiểm tra Number+1 hoặc Number-1, lấy cái nhỏ hơn.
Nhập số nguyên Number.
Hàm minWays(int num) nhận num và trả về số phép toán tối thiểu giảm num về 1.
Khai báo biến tmp1, tmp2, min.
Nếu num = 1 trả về 0.
Nếu num%2==0 (chẵn) thì tmp1 = minWays(num/2), trả về 1 + tmp1.
Nếu lẻ thì tmp1 = minWays(num-1), tmp2 = minWays(num+1), min = min(tmp1, tmp2), trả về 1 + min.
In kết quả trong main.
Ví dụ mã
#include <iostream> using namespace std; int minWays(int num){ int tmp1,tmp2,min; if (num == 1){ return 0; } else if (num % 2 == 0){ tmp1=minWays(num/2); return (1 + tmp1); } else{ int tmp1=minWays(num - 1); int tmp2=minWays(num + 1); int min=tmp1<tmp2?tmp1:tmp2; return (1 + min); } } int main(){ int Number = 21; cout <<"Số bước tối thiểu giảm "<<Number<<" về 1: "<<minWays(Number); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Số bước tối thiểu giảm 21 về 1: 6