CTDL và giải thuật - phép biến đổi số
Hải vừa nghĩ ra một phép biến đổi số, cụ thể như sau:
Với số tự nhiên n
nếu:
n
là số chẵn thì biến đổi n thànhn/2.
n
là số lẽ thì biến đổi n thành3*n+1.
Hiện tại Hải đang có hai số tự nhiên n
và k
, Hải muốn biết số lượng số mà khi số đó biến đổi k
lần liên tiếp thì biến đổi thành số n
.
Ví dụ:
- Test mẫu 1:
Input Output 10 3 3
Vớin = 10
,k = 3
, thì kết quả mong muốn là3
.
Giải thích: 3 số đó là12, 13, 80
.12
biến đổi3
lần:12->6->3->10.
13
biến đổi3
lần:13->40->20->10.
80
biến đổi3
lần:80->40->20->10.
- Test mẫu 2:
Input Output 5 2 2
Vớin = 5
,k = 2
, thì kết quả mong muốn là2
.
Giải thích: 2 số đó là3, 20
.3
biến đổi2
lần:3->10->5.
20
biến đổi2
lần:20->10->5.
Hướng dẫn bài tập.
Ý tưởng:
Thay vì kiểm tra các số nào có thể biến đổi k lần thành số n
, thì hay lần lượt kiểm tra các số nào có thể biến đổi 1
lần thành số n
ví dụ là x
và y
, sau đó tiếp tục gọi hàm xem số nào có thể biến đổi k-1
lần thành số x
và y
. Nếu k = 0
thì trả về 1
.
Code mẫu:
Ngôn ngữ C++:
#include<iostream>
using namespace std;
int count = 0;
void convert(int n, int k){
if (k == 0){
count ++;
}
else{
convert(2*n, k-1);
if ((n-1)%3 == 0 && ((n-1)/3)%2 == 1){
convert((n-1)/3, k-1);
}
}
}
int main(){
int n, k;
cin >> n >> k;
convert(n, k);
cout << count;
return 0;
}