1 题目ID:
P1010 [NOIP1998 普及组] 幂次方
2 题目描述:
任何一个正整数都可以用 22 的幂次方表示。例如 137=2^7+2^3+2^0137=27+23+20。
同时约定方次用括号来表示,即 a^bab 可表示为 a(b)a(b)。
由此可知,137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步:7= 2^2+2+2^07=22+2+20 ( 2^121 用 22 表示),并且 3=2+2^03=2+20。
所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)2(2(2)+2+2(0))+2(2+2(0))+2(0)。
又如 1315=2^{10} +2^8 +2^5 +2+11315=210+28+25+2+1。
所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。
输入格式
一行一个正整数 nn。
输出格式
符合约定的 nn 的 0, 20,2 表示(在表示中不能有空格)。
输入输出样例
1315
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
说明/提示
【数据范围】
对于 100\%100% 的数据,1 \le n \le 2 \times {10}^41≤n≤2×104。
3 题目分析:
输入一个数字,必然能用 2 的n元次幂和表示(除了0),这是毫无疑问的。但是如何表达?
首先考虑到每一个数在计算机里都是按二进制存储的,如果将这个数右移一位,这个数就相当于除了2,同时最高位向右移了一位,其位置,相当于最大的2次幂数。
由此,我们可以得出一个解决方法,对输入的数进行移位,每移位依次,就输入对应的状态的符号,例如输入7,存储为 0000 1011。向右移位,得 0000 0101。输出”2(“,
再移位,得 0000 0010。输出 "2)",再移位,得 0000 0001。输出 "+2" ,再移位,得 0000 0000。输出 "+2(0)"。以上由递归完成。
3.1 数据结构描述:
已知输入为一位 int 的数据,则为其 二进制最高位 配置一个 int 类型的状态位。同时配置一个 string 类型变量,作为输出。
3.2 算法描述:
设置变量 (int) n,作为输入,设置递归函数 op(int x,int i = 0, string s = string("") ) 返回类型为string。x 作为主参数,决定输出内容。i 作为辅助参数,default为0,用来判断当前输出什么内容,s作为返回参数,default为""。
将n作为参数输入op(),进入函数后,首先判断参数 x 是否为0,若为0,则表明此时当前输入只能输出"2(0)"。
若不为1,判断是否为0,为0则返回无内容。若不为0,则进入循环,若 x 不为 0 ,则往 s 中填内容,若 i 为 1,则表示,此时函数已经递归过了,正在判断是否需要填充2。不为 1,则有两种可能,一是刚进入函数,二是已多次进入递归,之后将 i 作为参数传入函数op(),进行递归。按结果分别往s中填充内容。若 s 填充之前为空,则次数不需要填充"+",因为无内容填充"+",会导致 "(+2"或者"2+)"的情况出现。
递归返回string,输出函数返回值。
例如 7 (4 + 2 + 1),7 进入后先表达4,即 2(2)+,2表达为 +2,1表达为 2(0)。最终返回的就是 2(2) + 2 + 2(0)。
4 具体代码
#include<iostream> using namespace std; string op(int x,int i = 0,string s = string("")){ if(!x)return string("0"); do if(x&1) s = (i == 1 ? "2" : "2(" + op(i) + ")") + (s == "" ? "":"+") + s; while(++i,x>>=1); return s; } int main(){ int n; cin>>n; cout<<op(n)<<endl; return 0; }