线上OJ:
洛谷:https://www.luogu.com.cn/problem/P7071 (opens in a new tab)
acwing:https://www.acwing.com/problem/content/2769/ (opens in a new tab)
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=2004 (opens in a new tab)
核心思想:
由题意可知,
1、如果 n 是奇数,则肯定不可能为 2 的幂次方和。因为 1 不是 2 的正整数次幂。
所以,如果 n 是奇数,直接输出 -1 即可。
2、如果 n 是偶数,则本题就变成了十进制转二进制,然后从高位起遇到1则输出。
关于十进制转二进制方法举例:
十进制的10能实现优秀的拆分 10 = 8+2,实际上对应着二进制后的 1010 ,即
10 / 2 = 5 … 0
5 / 2 = 2 … 1
2 / 2 = 1 … 0
1 / 2 = 0 … 1
先得到的余数是低位,后得到的是高位。按倒序取余数,得到 10 对应的二进制数字为1010
第一个1对应着 ,第二个1对应 。 所以,本题就变成了十进制转二进制,然后从高位起遇到1则输出
注意:最后输出时由于使用 pow() 函数,但 pow()的返回是 double型,故需强制加上 int() 转换
题解代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin >> n;
int num, a[100], i; //r:数字数组 ri:数组填充用下标
if(n % 2 == 1) cout << -1; // 如果是奇数,直接输出 -1
else
{ // 这个for实现 10进制转 2进制
for(i = 0; n > 0; i++) a[i] = n%2, n/=2; // 保留余数至a[i],然后n/2准备下一轮除余
for(int j = i - 1; j >= 0; j--) //倒序遍历数组
{
if(a[j] == 1)
cout << int(pow(2, j)) << " "; //注意:pow返回浮点型,且浮点型在很长时输出样式可能变为科学计数法,故此处必须加上强制转换 int()
}
}
return 0;
}