Cho một số nguyên làm đầu vào. Mục tiêu là tìm số bước hoặc thao tác tối thiểu cần thiết để giảm Số đầu vào xuống 1. Các thao tác có thể được thực hiện sẽ là-:
-
Nếu Số là số chẵn thì Chia nó cho 2.
-
Nếu Số là số lẻ, thì hãy tăng hoặc giảm nó đi 1.
Ví dụ
Đầu vào - Số =28
Đầu ra - Các bước tối thiểu để giảm 28 xuống 1:6
Giải thích -
28 là số chẵn - chia cho 2 =14
14 là số chẵn - chia cho 2 =7
7 là số lẻ - tăng 1 =8
8 là số chẵn - chia cho 2 =4
4 là số chẵn - chia cho 2 =2
2 là số chẵn - chia cho 2 =1
Đầu vào - Số =9
Đầu ra - Các bước tối thiểu để giảm 9 thành 1:4
Giải thích -
9 là số lẻ - giảm 1 =8
8 là số chẵn - chia cho 2 =4
4 là số chẵn - chia cho 2 =2
2 là số chẵn - chia cho 2 =1
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, hãy sử dụng một cách tiếp cận đệ quy để kiểm tra các phép toán tối thiểu cần thiết để giảm Số xuống 1. Trong trường hợp nó thậm chí chỉ đơn giản là chia cho 2, hãy kiểm tra đệ quy để biết các cách tối thiểu cho Số + 1 hoặc Số-1, tùy theo giá trị nào nhỏ hơn.
-
Lấy Số đầu vào là số nguyên.
-
Hàm minWays (int num) nhận num làm đầu vào và trả về số lượng các phép toán tối thiểu cần thiết để giảm num xuống 1.
-
Lấy các biến tmp1, tmp2 và min làm số nguyên.
-
Nếu num bằng 0 thì trả về 1.
-
Nếu num% 2 ==0 thì nó là số chẵn thì đặt num =num / 2
-
Nếu num là lẻ thì đặt tmp1 =minWays (num-1) và tmp2 =minWays (num + 1).
-
Đặt tối thiểu là tối thiểu của tmp1 và tmp2.
-
Trả về 1 + phút.
-
Cuối cùng, chúng tôi sẽ nhận được kết quả mong muốn.
-
In kết quả trong main.
Ví dụ
#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 <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
Minimum steps to reduce 21 to 1: 6