当前位置：首页 > 题解目录 > 正文内容

2的幂次方表示

亿万年的星光4年前 (2021-01-28)题解目录1320

【题目描述】

任何一个正整数都可以用2的幂次方表示。例如：
137=27+23+20

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：
2(7)+2(3)+2(0)
进一步：7=22+2+20（21用2表示）
3=2+20
所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如：
1315=210+28+25+2+1
所以1315最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

【输入描述】

一个正整数n（n≤20000）。

【输出描述】

一行，符合约定的n的0，2表示（在表示中不能有空格）。

【输入样例】

137

【输出样例】

2(2(2)+2+2(0))+2(2+2(0))+2(0)

【分析】

（1）21不能写成21，只能写成2
（2）最后分解的结果只有2和0，没有分解的继续分解
（3）最后的结果是一堆字符串的形式

【思路1】: 递归模式

//2的幂次方表示
#include<iostream>
#include<string>
using namespace std;
string cf(int n) {
   if(n==1) return "2(0)";   //递归结束情况
   if(n==2) return "2";     //递归结束情况
   int l=1,c=0;   //初值和次数
   while(l*2<=n) {  
       l*=2; // l是比n小的可以表示成2的c次方的最小数
       c++; //结束之后c值会保留最高次数 ，
   }
   string h; //用h表示最终的结果
   if(l==2)
       h+="2";
   else
       h+="2("+cf(c)+")"; //继续递归，直到结束    
   if(l==n)
       return h;    
   h+="+" + cf(n-l); //n-l表示剩余部分，继续递归
   return h;
}
int main() {
   int n;
   cin>>n;
   cout<<cf(n);
   return 0;
}

【思路2】：模拟和枚举

在初赛部分讲过进制转换，枚举到2的10次方，然后这个题的数据范围是20000，可以通过枚举的方式进行。先去定义一个数组

1
2
int num[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
// 最后一个32768是2的16次方

然后在计算中先找出最大的那个数，减去最大那个数之后就继续。

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int num[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
void digui(int x)
{
   if(x==0) //0的情况
   {
       printf("0");
       return ;
   }
   if(x==1) //1的情况
   {
       printf("2(0)");
       return ;
   }
   if(x==2) //2的情况
   {
       printf("2");
       return ;
   }
   
   for(int i=14;i>=0;i--)
   {
       if(x>=num[i]) //从最大数开始找
       {
           x-=num[i]; //减去最大的那个
           printf("2");
           if(i!=1)
           {
               printf("(");
               digui(i);
               printf(")");
           }
           if(x!=0)   // 如果没有分解完，就输出+号
               printf("+");
       }
   }
}
int main()
{
   int i,j;
   int n;
   scanf("%d",&n);
   digui(n);
   printf("\n");
   return 0;
}

补充：对于此题，不同数值表示方式

   s[1]="2(0)";           //1=2^0
   s[2]="2";             //2=2^1
   s[3]="2(2)";       //4=2^2
   s[4]="2(2+2(0))";   //8=2^3=2^(2+1)=2^2+2^1
   s[5]="2(2(2))";     //16=2^4,4="2(2)"  ,4前面出现过，直接使用
   s[6]="2(2(2)+2(0))";//32=2^5=2^(4+1) =2^4+2^1
   s[7]="2(2(2)+2)";     //64=2^6=2^(4+2) =2^4+2^2
   s[8]="2(2(2)+2+2(0))";             //128=2^7=2^(4+2+1)=2^4+2^2+2^1
   s[9]="2(2(2+2(0)))"    ;           //256=2^8, 8前面出现过，直接用
   s[10]="2(2(2+2(0))+2(0))";       //512=2^9=2^(8+1)=2^8+2^1
   s[11]="2(2(2+2(0))+2)";           //1024=2^10=2^(8+2)=2^8+2^2
   s[12]="2(2(2+2(0))+2+2(0))";   //2048=2^11=2^(8+2+1)=2^8+2^2+2^1
   s[13]="2(2(2+2(0))+2(2))";       //4096=2^12=2^(8+4)=2^8+2^4
   s[14]="2(2(2+2(0))+2(2)+2(0))";   //8192=2^13=2^(8+4+1)=2^8+2^4+2^1
   s[15]="2(2(2+2(0))+2(2)+2)";//16384=2^14=2^(8+4+2)=2^8+2^4+2^2
   s[16]="2(2(2+2(0))+2(2)+2+2(0))";//32768=2^15=2^(8+4+2+1)=2^8+2^4+2^2+2^1


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：学生分组

下一篇：分数求和

相关文章

【题解】周末舞会

【题目描述】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等...

【题解】完全背包问题

【题目描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和...

【题解】加密（2019青岛市程序设计竞赛）

【问题描述】文件加密最简单的方法是把文件的原文中的每个字母用另一个字母来代替。假设原文中只包括26个英文字母（有大写和小写），没有其他符号，且长度不超过100，加密规则如下：原文abcdefghijk...

单词提取

【题目描述】毛毛是个粗心的孩子，有一天在写英语作文时，不小心把不属于英文的字符混了进去。现在请帮他筛选出正常的英语单词。【输入描述】一行英语句子,大小写不定。以英文句点结尾。【输出描述】 删...

【题解】直方图

直方图（histogram.cpp）【题目描述】给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里面最大的数。假设Fmax(Fmax<10000)是数组里最大的数，那么我们只统...

【题解】转换的问题

【题目描述】那么，问题来了：输入一个十进制数N，将它转换成R进制数输出。【输入描述】输入数据包含多个测试实例，每个测试实例包含两个整数N(32位整数)和R（2<=R<=16, R<&...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.