#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// -------------------------- 高精度工具函数 --------------------------

// 高精度判断是否为 1
bool isOne(string s) {
	return s == "1";
}

// 高精度判断奇偶
bool isEven(string s) {
	int last = s.back() - '0';
	return last % 2 == 0;
}

// 高精度除以 2
string div2(string s) {
	string res;
	int rem = 0;
	for (char c : s) {
		int num = rem * 10 + (c - '0');
		res.push_back(num / 2 + '0');
		rem = num % 2;
	}
	// 去掉前导 0
	while (res.size() > 1 && res[0] == '0')
		res.erase(res.begin());
	return res;
}

// 高精度乘 3 + 1
string mul3Add1(string s) {
	reverse(s.begin(), s.end());
	string res;
	int carry = 1;  // 直接 +1
	for (char c : s) {
		int num = (c - '0') * 3 + carry;
		res.push_back(num % 10 + '0');
		carry = num / 10;
	}
	while (carry) {
		res.push_back(carry % 10 + '0');
		carry /= 10;
	}
	reverse(res.begin(), res.end());
	return res;
}

// -------------------------- 主逻辑 --------------------------
int main() {
	string num;
	cout << " 请输入一个超大正整数（高精度无溢出）：";
	cin >> num;
	
	int step = 0;
	while (!isOne(num)) {
		cout << " 第 " << step << " 步：" << num << endl;
		if (isEven(num)) {
			num = div2(num);
		} else {
			num = mul3Add1(num);
		}
		step++;
	}
	
	cout << " 第 " << step << " 步：" << num << endl;
	cout << "\n 最终变成 1，共执行 " << step << " 步！" << endl;
	return 0;
}