浙江龙网

  1. 首页 > 生活百科 > >

幂次方表达:p1010

生活百科

1 题目ID：
P1010 [NOIP1998 普及组] 幂次方
2 题目描述：
任何一个正整数都可以用 22 的幂次方表示 。例如 137=2^7+2^3+2^0137=27+23+20 。
同时约定方次用括号来表示，即 a^bab 可表示为 a(b)a(b) 。
【幂次方表达:p1010】由此可知 ， 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 表示（在表示中不能有空格） 。
输入输出样例
输入 #1复制
1315输出 #1复制
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"); doif(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;}

    推荐阅读


    上一篇：Java安全之动态加载字节码

    下一篇：R数据分析：孟德尔随机化实操