洛谷：P1010幂次方

思路

递归加条件判断,递归时主要遍历 2^i 次方判断 其值是否大于输入的值，如果大于则2^(i-1)为小于输入的数，i-1为当前幂次项的值。

代码

#include <stdio.h>
#include <iostream>
#include <sstream> 
#include <vector>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <bitset>
using namespace std;string s;
void dfs(int x)//递归得到输出字符串
{int ans = 0;if (x <= 0)return;//递归终止条件，n减去之前已表达出的数小于等于0for (int i = 0; i<x; i++)//遍历2^i次方 {ans = pow(2, i);if (ans>x) //当2^i大于当前数 ，则2^(i-1)小于等于此数 {if (i>3)//当i大于3时需要重新将i-1拆分 {s += "2(";dfs(i - 1);//s += "+";}else//小于3时直接将该部分输出保存在字符串中 {if (i - 1 == 1)//判断i-1是否为1，为1时需要将其特殊输出 {s += "2";}else{s += "2(";s += to_string(i - 1);}}if (i - 1 != 1)s += ')';//判断i是-1否为1，为1时不输出右括号 s += "+";ans = pow(2, i - 1);//将2^(i-1)保存到ans中 ，用于后面计算剩余数 break;}else if (ans == x)//当2^i等于当前数 {if (i>2)//当i大于2时需要重新将i拆分 {s += "2(";dfs(i);//重新拆分i }else{if (i == 1)//判断i是否为1，为1时需要将其特殊输出 {s += "2";}else{s += "2(";s += to_string(i);}}if (i != 1)s += ')';//判断i是否为1，为1时不输出右括号 break;}}dfs(x - ans);//递归剩余未计算数字 return;
}int main()
{int n;cin >> n;dfs(n);cout << s;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！