本文共 1266 字，大约阅读时间需要 4 分钟。
输入一个无符号整数n，用最少的步骤将该数变为1，当n为偶数时能够採取的步骤是除2的形式，当n为奇数的时候能够採取加1或者减1的操作。
#include#include using namespace std;int min(int a, int b) { if (a < b) return a; return b;}int get_pow(uint num) { if (num <= 1) return 0; int power = 0; while (0 == (num % 2)) { power++; num /= 2; } return power;}int get_step(uint num) { if (1 >= num) return 1; int step = 0; while (num > 1) { if (0 == (num % 2)) { step++; num /= 2; } else { int plus_pow = get_pow(num + 1); printf("num=%d, plus_pow=%d\n", num, plus_pow); int minus_pow = get_pow(num - 1); printf("num=%d, minus_pow=%d\n", num, minus_pow); if (1 == plus_pow && 1 == minus_pow) { step += 1 + min(get_step(num - 1), get_step(num + 1)); return step; } else if (plus_pow > minus_pow) { step += 1 + plus_pow; num = (num + 1) / ((int)pow(2.0, plus_pow)); } else if (plus_pow < minus_pow) { step += 1 + minus_pow; num = (num - 1) / ((int)pow(2.0, minus_pow)); } } if (3 == num) { step += 2; num = 1; } } if (0 == num) step += 1; return step;}int main(int argc, char* argv[]) { int num = 0; cin >> num; int step = get_step(num); cout << "step:" << step << endl; return 0;}