首页 > 试题广场 >

2的幂次方

[编程题]2的幂次方
  • 热度指数:7934 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    Every positive number can be presented by the exponential form.For example, 137 = 2^7 + 2^3 + 2^0。     Let's present a^b by the form a(b).Then 137 is presented by 2(7)+2(3)+2(0). Since 7 = 2^2 + 2 + 2^0 and 3 = 2 + 2^0 , 137 is finally presented by 2(2(2)+2 +2(0))+2(2+2(0))+2(0).        Given a positive number n,your task is to present n with the exponential form which only contains the digits 0 and 2.

输入描述:
    For each case, the input file contains a positive integer n (n<=20000).


输出描述:
    For each case, you should output the exponential form of n an a single line.Note that,there should not be any additional white spaces in the line.
示例1

输入

1315

输出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
#include <stdio.h>
(737)#include <stdint.h>
#include <string.h>

void GetNumber(int n)
{
    int res[15] = {0}, index = 0, count = 0;
    // 先转换为2进制
    while (n != 0)
    {
        if(n % 2 == 1) count++;
        res[index++] = n % 2;
        n /= 2;
    }
    // 遍历每一位
    for (int i = index - 1; i >= 0; i--)
    {
        if (res[i] != 0)
        {
            count--;
            printf("2");
            if(i == 1) {
                
            }else if(i == 0) {
                printf("(0)");
            }else {
                printf("(");
                GetNumber(i);
                printf(")");
            }
            if(count > 0) {
                    printf("+");
                }
        }
    }
}

int main()
{
    // freopen("data.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF)
    {
        GetNumber(n);
        printf("\n");
    }

    return 0;
}

发表于 2020-02-25 15:35:57 回复(0)
运用递归(C++)。
用到了<biset>,求出n的二进制表示
#include<iostream>
(720)#include<cstdio>
#include<bitset>

using namespace std;

string cf(int n){
	bitset<32> b(n);
	string str;
	int flag = 0;
	for(int i=31;i>=0;i--){
		if(b.test(i)){
			if(flag) str += "+";
			if(i==2) str += "2(2)";
			else if(i==1) str += "2";
			else if(i==0) str += "2(0)";
			else{
				str = str + "2(" + cf(i) + ")";	
			}
			flag = 1;	
		}	
	}
	return str;
	
}

int main(){
	int n;
	while(cin>>n){
		cout<<cf(n)<<endl;
	}
	return 0;
}



发表于 2020-05-09 15:02:55 回复(0)
Java  递归解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        System.out.println(fun(new Scanner(System.in).nextInt()));
    }

    static String fun(int i) {
        char[] array = Integer.toBinaryString(i).toCharArray();
        int count =0;
        for (char c : array) {
            if (c == '1') count++;
        }
        StringBuilder builder = new StringBuilder();
        for (int j = 0; j < array.length; j++) {
            if (array[j] == '1') {
                count--;
                int index = array.length - j;
                if (index == 1) {
                    builder.append("2(0)");
                } else if (index == 2) {
                    builder.append("2");
                } else {
                    builder.append("2(").append(fun(index-1)).append(")");
                }
                if (count>0)
                    builder.append("+");
            }
        }
        return builder.toString();
    }
}



编辑于 2020-03-06 19:23:49 回复(0)
自我感觉良好,写的也挺简单的,可以给大家参考一下。
#include<iostream>
#
include<string>
#include<stack>

using namespace std;

string F(int n){
    if (n == 2){
        return  "2(2)";
    }
    else if (n == 0)
        return "2(0)";
    else if (n == 1)
        return "2";
    else{
        string res = "";
        stack<int>s;
        int i = 0;
        while (n != 0){
            if (n % 2 == 1){
                s.push(i);
            }
            i += 1;
            n /= 2;
        }
        while (!s.empty()){
            if (s.top() > 2)
                res += "2(" + F(s.top()) + ')';
            else
                res += F(s.top());
            s.pop();
            if (!s.empty())
                res += '+';
        }
        return res;
    }
}

int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        cout << F(n) << endl;
    }
    return 0;
}

发表于 2020-03-03 12:16:58 回复(0)
#include<iostream>
#include<string>
using namespace std;

string dfs(int n) {
    string s;
    if (n == 2) return "2";
    if (n == 0) return "0"; //递归出口
    int i=20;
    while (i--) {
        if ((n >> i) & 1) {
            if (i == 1) s += "2+";  //防止2被解析成2(0)
            else {
                s += "2(";
                s += dfs(i); //递归
                s += ")";
                s += "+";
            }
        }
    }
    s = s.substr(0, s.size() - 1);
    return s;
}
int main() {
    int n;
    string r;
    while (cin >> n) {
        r = dfs(n);
        cout << r << endl;
    }
    return 0;
}
发表于 2018-08-21 00:00:08 回复(0)
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int mi[20];

void ten2two(int n);

int main(int argc, char** argv) {
    mi[0] = 1;
    for(int i=1;i<20;i++){
        mi[i] = 2*mi[i-1];
    
    int n;
    cin >> n;
    ten2two(n);
    return 0;
}

void ten2two(int n){
    if(n==1) cout << "2(0)";
    else if(n==2) cout << "2";
    else {
        bool flag = false;
        for (int i=19;i>=0;i--){
            if(mi[i] <= n){
                if(flag) cout << "+";
                n-=mi[i];
                if(i==0) cout << "2(0)";
                else if(i==1) cout << "2";
                else{
                    cout << "2(";
                    ten2two(i);
                    cout << ")";    
                }
                flag = true;    
            }
        }
    }
}
发表于 2021-01-28 15:20:23 回复(0)
#include<iostream>
using namespace std;
#include<string>
string trans(int n)
{
	if (n == 0 || n == 2)
		return to_string(n);
	else if (n == 1)
		return "2";
	else
	{
		int x = 0;//记录模2的次数
		string ans = "";
		while (n != 0)
		{
			if (n % 2 == 1)
			{	
				if (x != 1)
					ans.insert(0, ")");

				ans.insert(0, trans(x));
				
				if (x != 1)
					ans.insert(0, "2(");
				if (n != 1)
					ans.insert(0, "+");
			}
			x++;
			n /= 2;
		}
		return ans;
	}
}
int main()
{
	int n;
	while (cin>>n)
	    cout << trans(n) << endl;
	return 0;
}

快速幂 + 递归,应该写的比较清晰了
编辑于 2020-06-16 22:10:47 回复(1)
#include <bits/stdc++.h>

using namespace std;

vector<int> v;

string gcg(int m) {
    string str;
    int idx = 0;
    if (m == 0) return "0";
    if (m == 2) return "2";
    while (m != 0) {
        if (m >= v[idx]) {
            m -= v[idx];
            if (idx == 13) {
                str += "+2";
            } else {
                str += "+2(" + gcg(14 - idx) + ")";
            }
        }
        idx++;
    }
    return str.substr(1);
}

int main() {
    v.clear();
    for (int i = 0; i <= 14; ++i) {
        v.push_back(pow(2, 14 - i));
        //cout<< v[i] << " ";
    }
    //cout << endl;
    int m;
    while (cin >> m) {
        cout << gcg(m) << endl;
    }
    return 0;
}
递归
发表于 2020-03-04 10:48:09 回复(0)
//直接穷举
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    int a=pow(2,15);
    int n;
    cin>>n;
    string r="";
    
    for(int i=15;i>=0;i--)
    {
        if(n>=a)
        {
            n-=a;
            switch(i)
            {
                case 15:r+="2(2(2+2(0))+2(2)+2+2(0))+";break;
                case 14:r+="2(2(2+2(0))+2(2)+2)+";break;
                case 13:r+="2(2(2+2(0))+2(2)+2(0))+";break;
                case 12:r+="2(2(2+2(0))+2(2))+";break;
                case 11:r+="2(2(2+2(0))+2+2(0))+";break;
                case 10:r+="2(2(2+2(0))+2)+";break;
                case 9:r+="2(2(2+2(0))+2(0))+";break;
                case 8:r+="2(2(2+2(0)))+";break;
                case 7:r+="2(2(2)+2+2(0))+";break;
                case 6:r+="2(2(2)+2)+";break;
                case 5:r+="2(2(2)+2(0))+";break;
                case 4:r+="2(2(2))+";break;
                case 3:r+="2(2+2(0))+";break;
                case 2:r+="2(2)+";break;
                case 1:r+="2+";break;
                case 0:r+="2(0)+";break;
            }
        }
        a/=2;
    }
    
    r=r.substr(0,r.length()-1);
    cout<<r;
    return 0;
}

发表于 2019-06-30 16:53:24 回复(1)
  • 字符串嵌套:
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
string dtob(int n){
    int sum=0;
    vector<int> v;
    if(n==0) return "0";
    for(int i=18;i>=0;i--){
        int t = pow(2,i);
        if(sum+t<=n){
            v.push_back(i);
            if(sum+t==n) break;
            sum+=t;
        }
    }
    string s;
    for(int i=0;i<v.size();i++){
        string t ;
        if(v[i]==1) t = "2";
        else t = "2("+dtob(v[i])+")";
        s.append(t);
        if(i!=v.size()-1){
            s.push_back('+');
        }
    }
    return s;
}
int main(){
    int n;
    while(cin>>n){
        cout<<dtob(n)<<endl;
    }
    return 0;
}

发表于 2019-01-22 22:53:00 回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

//返回n的2^m表达形式的m序列,由大到小
vector<int> exp(int n)
{
    vector<int> m;
    while(n>0)
    {
        int t = 2;
        int k=0;
        while(pow(t, k)<=n)
        {
            k++;
        }
        m.push_back(k-1);
        n -= pow(t, k-1);
    }
    return m;
}


string expression(vector<int> m)
{
    string str;
    for(int i=0;i<m.size();i++)
    {
        if(m[i] == 0)  str += "2(0)";
        else if(m[i] == 1)
        {
            if(i == m.size()-1) str += "2";
            else str += "2+";
        }
        else
        {
            vector<int> tmp;
            tmp = exp(m[i]);
            if(i == m.size()-1) str += "2(" + expression(tmp) + ")";
            else str += "2(" + expression(tmp) + ")+";
        }
    }
    return str;
}

int main()
{
    int n;
    cin>>n;
    vector<int> m;
    m = exp(n);
    string str;
    str = expression(m);
    cout<<str<<endl;
    return 0;
}



编辑于 2019-01-04 19:18:34 回复(0)
#include<iostream>
using namespace std;
int pos[32];
inline int GetBit(int n,int i){
 return (n>>i)&1;
}
void print(int n){
 bool first=true;
 for(int i=15;i>=0;--i){
  if(GetBit(n,i)){
   if(!first)cout<<"+";
   else first=false;
   if(!i)cout<<"2(0)";
   else if(i==1)cout<<"2";
   else{
    cout<<"2(";
    print(i);
    cout<<")";
   }
  }
 }
}
int main(){
 int n;
 while(cin>>n){
  print(n);
        cout<<endl;
    }
 return 0;
}

发表于 2017-08-16 16:01:09 回复(14)
J1_头像 J1_
看完我的注释你就懂了
#include <bits/stdc++.h>
using namespace std;

/*  
例子:{129}
129 = 2({7}) + 2(0)
7   = 2({2}) + 2 + 2(0)
2   = 2
汇总 129 = 2( 2(2) + 2 + 2(0) ) + 2(0) 

如何得到的?
1, 129 -> 1   0 0 0 0 0 0  1
		 {7}  6 5 4 3 2 1  0  (2^n 的指数 n)
2, 7   -> 1  1 1
         {2} 1 0
3, 2   -> 1  0
          1  0
将一个数转换为二进制数,对于有"1"的位,考虑它是"二的几次方":
	如果是1或0不用处理(直接输出),
	如果是其他数则继续转二进制数如此循环。
处理 "+",对每一个二进制数,若不止一位有 "1",除第一个 "1" 外都要添上 "+" 
*/

void dfs(int n) {
	//1.先转成二进制数(逆序存放的) 
	vector<int> bin;
	while(n) {
		bin.push_back(n % 2);
		n /= 2;
	}
	//2. 逐位处理,如果有 "1",且下标不是 1 或 0,递归调用 
	bool first = true;
	for(int i = bin.size() - 1; i >= 0; i--) {
		if(bin[i] == 1) {
			//3. 处理加号 
			if(!first) {
				cout << "+";
			}
			first = false;
			
			//4. 直接输出 或 递归调用
			if(i == 0) {
				cout << "2(0)";
			}	
			else if(i == 1) {
				cout << "2";
			}
			else {
				cout << "2(";
				dfs(i);
				cout << ")";
			}
		}
	} 
}

int main() {
	int n;
	while(cin >> n) {
		dfs(n);
		cout << "\n";
	}
}


发表于 2020-04-11 16:18:17 回复(4)
#include <iostream>
using namespace std;

void ten_to_two(int n){
    char a[100];
    int ind=0,i,num=-1;
    while(n){
        a[ind] = n%2+'0';
        if(a[ind]=='1'){
            num++;
        }
        ind++;
        n/=2;
    }
    for(i=ind-1;i>=0;i--){
        if(i>1&&a[i]=='1'){ 
            cout << "2(";
            ten_to_two(i);  //大于2的时候
            cout << ")";
        }else if(i==1&&a[i]=='1'){
            cout << "2";    //等于2 的时候
        }else if(i==0&&a[i]=='1'){
            cout << "2(0)";  //等于1的时候
        }
        if(a[i]=='1'&&num-->0){
            cout << "+";
        }
    }
}

int main(){
    int n;
    while(cin >> n){
        /*
            把n变成二进制 从而输出
        */
        ten_to_two(n);
        cout << endl;
    }
    return 0;
}


靠模拟 .......计算二进制1的个数 从而确定有多少个加号。
其实就三种情况,大于2,等于2 以及 1
编辑于 2019-03-15 22:21:37 回复(1)
/*
    因为题目只说用0,2来表示数
    所以递归的最底层问题就是1和2这两个数可以直接表示
    思路:
    例如 11 = 1011(2)
    逆序 1101 (逆序非常容易求得)
         0123
         所以 11 = 2^0 + 2^1 + 2^3 (用数组下标来标识指数)
    那么如果下标大于等于2则可以继续分解-->> 递归
    题目中是按照下标从高位到低位,那么我们从后面逆序判断
    
*/
#include <bits/stdc++.h>
using namespace std;
void print(int n){
	bool first = true;
	vector<int> res;
	while(n){ // 求二进制逆序
		res.push_back(n%2);
		n>>=1;
	}
	for(int i=res.size()-1;i>=0;i--){
		if(res[i]==1){
			if(first==true){ 
				first = false;
			}else{
				cout<<"+";
			}
			if(i==0){
                cout<<"2(0)";
            }else if(i==1){
                cout<<"2";  
            }else{ // 如果下标大于2,可以继续分解成2的幂次的形式
				cout<<"2(";
				print(i);
				cout<<")";
			}
		}
	}
}
int main(){
	int n;
	while(cin>>n){
		print(n);
		cout<<endl;
	}
	return 0;
}

发表于 2020-03-10 11:45:08 回复(0)
#include <stdio.h>

void trans(int a){
    if(a==0){
        printf("2(0)");
        return;
    }
    if(a==1){
        printf("2");
        return;
    }
    int stack[15],top=-1,i=0;
    while(a!=0){
        stack[++top]=a%2;
        if(stack[top]!=0) i++;
        a=a/2;
    }
    while(top>-1){
        if(stack[top]!=0){
            i--;
           if(top==0) trans(0);
           else if(top==1) trans(1);
           else{
               printf("2(");
               trans(top);
               printf(")");
            }
            if(i>0) printf("+");
        }
        top--;
    }
}

int main(){
    int a;
    scanf("%d",&a);
    if(a==1) printf("2(0)");
    else if(a==0) printf(0);
    else trans(a);
}
发表于 2022-01-08 23:01:59 回复(0)
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
// 题目: 2的幂次方
// “安排”比较复杂
// 注意到题目中已经交代结果中只会出现2和0这两个数字
// 所以在递归函数的设计中大局上要考虑到“输出语句必须有且只有两种:输出0和输出2”
// 据此为指导有助于理清思路
void f(unsigned short n) {
    if (n == 0) { cout << "0"; return;}
    bitset<16> t(n); // 借助bitset这个容器n转为二进制字符串
    string s = t.to_string();
    bool flag = true; // 标志第一个有效数字
    for (int i = 0; i < 16; i ++) {
        if (s[i] == '1') {
            if (flag) {cout << "2"; flag = false;} // 如果是第一个有效数字
            else cout << "+2"; // 这是一个常见的问题,保证不产生“多余”
            if ((15-i) != 1) {
                cout << "(";// 括号位置的设置比较繁琐
                f(15-i);
                cout << ")";
            }
        }
    }
    return ;
}
int main(void)
{
    unsigned short n;
    cin >> n;
    f(n);
    return 0;
}

编辑于 2019-01-07 10:19:38 回复(0)

简单易懂,最简洁实现。一个转换函数,递归实现

def convenBin(num):
    numBin = bin(num).replace('0b','')        #转换成2进制
    numPower = len(numBin)-1                  #对应长度的2进制次幂
    result = []                           
    while numBin:
        if numBin[0] == '1':                  #如果该二进制位为1我们才加入结果
            if numPower >= 2:                 #次幂大于等于2我们要递归它
                result.append('2(%s)'% convenBin(numPower))
            elif numPower == 1:               #1和0不能通用解决,就单独列出来
                result.append('2')
            else:
                result.append('2(0)')
        numPower -= 1
        numBin = numBin[1:]
    return '+'.join(result)                   #返回用+相接的结果
while True:
    try:
        print(convenBin(int(input)))
    except Exception:
        break
编辑于 2018-10-14 10:19:46 回复(0)
#include <bits/stdc++.h>
using namespace std;

string slove(int n ) {
    if (n == 0) return "0";
    if (n == 1) return "";
    int index = 0;
    vector<int> nums;
    string ans;
    //求n的二级制
    while(n) {
        if (n & 1) {
            nums.push_back(index);
        }
        n >>= 1;
        index++;
    }
    //下面就是递归了,就是2( slove(这里放二级制的幂数例子的7,3,0) ),递归不理解的话就想想二叉树的前序中序后序遍历的树形结构
    for(int i = nums.size() - 1; i >=0; i--) {
        if (nums[i] == 1) {
            if (i == 0) ans += "2";
            else ans += "2+";
            continue;
        }
        ans += "2(";
        ans += slove(nums[i]);
        if (i == 0 ) ans += ")";
        else ans += ")+";
    }
    return ans;
}
int main() {
    int n;
    while(cin >> n) {
        cout << slove(n) << endl;
    }
}
// 64 位输出请用 printf("%lld")
编辑于 2024-03-26 14:57:29 回复(0)
#include <iostream>
#include <string>
using namespace std;
string toD(int num){//将数字转换成二进制字符串
    string re="";
    while(num>0){
        re=to_string(num%2)+re;
        num/=2;
    }
    return re;
}

void func(int n){//递归函数
    string s;
    if(n==2||n==0){//如果是0、2则直接输出
        cout<<n;
    }
    else{
        s=toD(n);//先转换成二进制
        bool tag=true;//tag用于控制第一个输出,之后的输出还有加上“+”
        for(int i=0;i<s.size();i++){
            if(s[i]=='1'){//二进制该位置为1
                if(!tag){
                    cout<<"+";
                }
                else{
                    tag=false;
                }

                if(s.size()-1-i!=1){//如果是2(1),则直接输出2,否则递归
                    cout<<"2(";
                    func(s.size()-1-i);
                    cout<<")";
                }
                else{
                    cout<<"2";
                }
                
            }
        }
    }

}
int main() {
    int num;
    string nstr;
    while(cin>>num){
        func(num);
    }
    return 0;
}

发表于 2023-03-17 16:10:21 回复(0)