AcWing 1. 2的n次幂
原题链接
困难
作者:
男神
,
2024-03-04 18:42:48
,
所有人可见
,
阅读 22
//还是讲一下原理 假如一串数字 1358*2,这时候 我们储存到数组里面,得到的数字 是从个位开始的
//比如说他的结果是 2716 那么他在数组中的储存方式的就是6127;
//那么怎么实现2的n次幂呢 打个比方 2的4次幂 2*2*2*2* 这时候可以定义一个
//数 int x=1 让x*=2;经历四次循环 但是这样的结果最后变大了根本储存不了那么就只能
//将每次计算的结果储存到数组里面 ,那怎么实现呢;
//比如说 128 *2在这里128 相当于 在数组中 ,这时候遍历各个位数 也就是从索引0开始,i小于位数
//的循环 也就是说每运算一次 乘以2 的操作的需要循环遍历
//这时候 128*2 个位得到 6,还要进1 那么怎么实现 这个操作呢 a[0]*2%10,并把这个值存入索引0
//那么接下来 我们会遍历到下一位数 我们也要a[1]*2%10,然后要判断上一步是否进位了,也就是判断
//a[0]*2/10=0 //这时候你会发现就是这个数组的长度是渐变的,也就是从1开始递增
//你最终可以得知这个数组中实际有效位数递增到了几
//123217869 1 2
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
int m=1;//此时 数组有效长度为1
int a[3010]={1}//定义一个数组长度 并且他只有一个1 ,其他后面都是0;
for(int i=0;i<n;i++){
int t=0;//用来记录计算得到的结果
for(int j;j<m;j++)
{
t=a[j]*2;//这里必须是t+=a[j]*2; 因为t 定义在外面不会被刷新,而每次循环结束t的值都是是否进一位
a[j]=t%10;
t/=10;//用来判断是否有进位
}
if(t)a[m++]=1;//这句话的意思就是当循环结束后也就是所有位数遍历完成,看下一位(未生成位)是否需要打卡
//a[m-1]是最后一位 并且 需要遍历的位数需要加1 ;
}
for(int i=m-1;i>=0;i--)cout<<a[i];
return 0;}