P1010 [NOIP1998 普及组] 幂次方（十进制转二进制）（递归）

P1010 [NOIP1998 普及组] 幂次方

个人感想

终于能真正自主解决一道纯递归题目了，完成前面那次P1928 外星密码的遗憾了
十进制转化二进制再处理也顺利搞定（之前洛谷月赛就有相似题目，当时觉得很难就没写，太亏了）

十进制转二进制

样例：

int a[]
while (n != 0) {
		if (n % 2 == 1) {
			a[num] = 1;
		} else {
			a[num] = 0;
		}
		num++;
		n /= 2;
	}

用一个数组来存储二进制数的每一位，就可以很方便的对二进制数做处理（位运算还不懂）

题目思路

跟之前那道题一样，对一个括号内包含括号直接做递归处理，这里要注意一下在2[0],2[1]，还有对+号的特判就ok了。

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
int a[100];

void check(int n) {

	int b[16];
	for (int i = 0; i <= 15; i++) {
		b[i] = 0;
	}
	int num = 0;
	while (n != 0) {
		if (n % 2 == 1) {
			b[num] = 1;
		} else {
			b[num] = 0;
		}
		num++;
		n /= 2;
	}
	for (int i = num; i >= 0 ; i--) {
		if (b[i] != 0) {
			if (i == 1) {
				cout << 2;
				if (b[0] == 1) {
					cout << "+";
				}
			} else if (i == 0) {
				cout << "2(0)";
			} else {
				cout << 2 << "(";
				check(i);
				cout << ")";
				for (int j  = i - 1; j >= 0; j--) {
					if (b[j] == 1) {
						cout << "+";
						break;
					}
				}
			}

		}
	}
}

int main() {
	int n;
	cin >> n;
	int num = 0;
	while (n != 0) {
		if (n % 2 == 1) {
			a[num] = 1;
		} else {
			a[num] = 0;
		}
		num++;
		n /= 2;
	}
	for (int i = num; i >= 0 ; i--) {
		if (a[i] != 0) {
			if (i == 1) {
				cout << 2;
				if (a[0] == 1) {
					cout << "+";
				}
			} else if (i == 0) {
				cout << "2(0)";
			} else {
				cout << 2 << "(";
				check(i);
				cout << ")";
				for (int j = i - 1; j >= 0; j--) {
					if (a[j] == 1) {
						cout << "+";
						break;
					}
				}
			}

		}
	}

	return 0;
}