每日一题——预言家(高精度)

学习目标:

在c语言中,我们的数字类型是有范围的,int,long。当我们数字规模特别大时,这些基本的数字类型已经无法存储了。那么我们就要想办法,怎么存储这些数字?

字符串?数组?这些都可以,我们就来看一下比较常用的数组是怎么存储的。


学习内容:

首先,我们用数组存放一个数字,原理就是将每一位数,放在数组的一个位上。

eg:123,存放在数组a[3]中,就是a[0]=1,a[1]=2,a[2]=3。输出时再按位输出即可。

然后是对这些数字要进行运算。+-*/。加法和减法好说,只要对他们进行按位相加,逢十进一即可。减法同理。乘法的话,就用其中一个数组的每一位分别与另一个数组的每一位相乘,并且每一次都要控制进位,而除法相对复杂,且应用较少,就不在此进行讲解,感兴趣的朋友可以自行了解。


看一下今天的题目:

 2^{15} = 32768215 =32768,他的各位和是3 + 2 + 7 + 6 + 8 = 263+2+7+6+8=26。

输入nn,求2^{n}2n的各位和。

输入

第一行输入组数T, 接下来T行,每行一个整数n。(1 <= T <= 1000,1 <= N <= 1000)

输出

对于每组数据,输出一个数,表示2的n次方的各位和。

样本

输入 输出
4
3
4
7
1000
8
7
11
1366

看到题目,2的1000次幂显然已经远远地超过了我们的数据范围,所以我们就要采用数组的方法进行求解。

其中主要包括的就是对数组进行相乘的系列操作,并对其以结构体的形式进行运算。

#include<bits/stdc++.h>
#define ll long long
#define N 50001
using namespace std;
struct node {
	int n;//代表数组长度也是数字的位数
	int a[N];//存储每一位
	node() {//对结构体的数据进行初始化
		n=0;
		int i;
		for(i=0; i<N; i++) a[i]=0;
	}
};
int main() {
	int t,i;
	scanf("%d",&t);
	while(t--) {
		int n,ans=0;
		scanf("%d",&n);
		node y;
		y.a[0]=1;
		y.n=1;
		while(n--) {
			for(i=0; i<y.n; i++) y.a[i]*=2;//每一位*2
			for(i=0; i<y.n; i++) {//逢十进一
				y.a[i+1]+=y.a[i]/10;
				y.a[i]=y.a[i]%10;
			}
			while(y.a[y.n]) {//对最高位进行逢十进一操作,直到为0
				y.a[y.n+1]+=y.a[y.n]/10;
				y.a[y.n]%=10;
				y.n++;
			}
		}
		for(int i=0; i<y.n; i++) ans+=y.a[i];//ans记录各位的相加和
		printf("%d\n",ans);
	}
	return 0;
}

 


每天坚持是一件很累的事,即使很慢,但也不要停止。由于过年,小编停更了几天,从今天开始,小编继续每日一题。欢迎大家及时督促,大家一起加油! 


大家记得点赞收藏,防止找不到哦。


欢迎大家订阅小编的每日一题专栏,会每天更新,都是用心准备的哦!

若有不同思路,欢迎评论区留言,看到必回,Goodnight!

上一篇:Linux模式设计--数据大小,对齐函数相关【转】


下一篇:P4588 [TJOI2018]数学计算