Sicily 1028. Hanoi Tower Sequence【高精度取余和除法】

题目链接在此

这道题目有点意思。渣渣我从这位大神这里得到了解题奥妙。

找某个数的二进制从右边数第一个“1”是第几位即可。

由于这题的数可能很大，那么就要使用高精度除法和取余了=。=

思路就是模仿手算除法。1020就是道高精度取余的题，与这道题可以互相借鉴。

源代码如下：

#include<iostream>
#include<string>

using namespace std;

int charToInt(char a) {
return a - '0';
}

char intToChar(int n) {
return n + '0';
}

int main() {
int caseNum;
string num;
int modResult;  //  记录除法过程中的余数
bool isFirst = true;

cin >> caseNum;
for (int t = 1; t <= caseNum; t++) {
if (isFirst)
isFirst = false;
else
cout << endl;

cin >> num;

int FirstOneInBinary = 0;  //  记录从右边数第一个“1”出现在第几位。
while (true) {
FirstOneInBinary++;
modResult = charToInt(num[0]) % 2;
num[0] = intToChar(charToInt(num[0]) / 2);

for (int i = 1; i < num.length(); i++) {
//  每次做除法时，逐位更新num的值
char originalNum = num[i];
num[i] = intToChar((modResult * 10 + charToInt(originalNum)) / 2);
modResult = (modResult * 10 + charToInt(originalNum)) % 2;
}

if (modResult == 1)
break;
}

cout << "Case " << t << ": " << FirstOneInBinary << endl;
}

return 0;
}