首页
论坛
课程
招聘
[代码之美]题4
2008-9-28 00:32 4973

[代码之美]题4

2008-9-28 00:32
4973
哈哈我也来发一个。

/************************************************************************
Author: xiep
Date  : 2008-9-27
其实像大数乘法,加法,减法,阶乘问题常见算法是用数组或向量(vector)等模拟手算。
只考虑了非负数的情形。
测试用例考虑了大数乘大数,
              大数乘小数,
              小数乘大数,
              小数乘小数,
          以及0乘和乘0。
*************************************************************************/

#include <fstream>
#include <assert.h>
using namespace std;

#define	MAX_LEN	10000 + 1

void by(int res[],		//保存结果,顺序存储
		int num1[],		//被乘数,顺序存储
		int len1,		//被乘数位数
		int num2[],		//乘数,顺序存储
		int len2)		//乘数位数
{
	int i,j,k;			//循环变量
	int lenres=len1+len2;		//结果数组的长度

	//将结果数组初始化为0,这是必须的
	for(i=0; i<lenres; i++)
		res[i]=0;
	
	//构造一个大小等于被乘数的数组,用于保存中间结果
	int *temp = new int[len1];
	assert( NULL != temp );
	
	//关键代码
	int index=0;
	for(i=len2-1; i>=0; i--)		//乘数
	{
		index++;
		for(k=lenres-index,j=len1-1; j>=0; k--,j--)
		{
			temp[j] = num1[j]*num2[i];	//乘
			res[k] += temp[j];		//将中间结果加入结果数组
		}
	}
	delete[] temp;					//回收内存
	
	int tmp,carry=0;
	for (i=lenres-1; i>0; i--)
	{
		tmp = res[i]+carry;			//因为( (2^31-1) - (2^31-1)/10 ) / 81 = 50373073
		res[i] = tmp % 10;			//所以乘数最多可以是 50373073 位
		carry = tmp /10;            //被乘数位数不限,保证不溢出
	}
	res[0]=carry;
}


int main(void)
{
	fstream in( "in.txt" );
	fstream out( "out.txt" );

	char chNum1[MAX_LEN], chNum2[MAX_LEN];

	int testcaseNum;
	in>>testcaseNum;

	int i;
	while(testcaseNum--)
	{
		in>>chNum1>>chNum2;
		int len1 = strlen(chNum1);
		int len2 = strlen(chNum2);
		
		int intNum1[MAX_LEN],						//被乘数
			intNum2[MAX_LEN],						//乘数
			*result=new int[len1+len2];				//结果	
		assert( NULL != result);
		
		for(i=0; i<len1; i++)
			intNum1[i]=chNum1[i]-'0';

		for(i=0; i<len2; i++)
			intNum2[i]=chNum2[i]-'0';
		
		by(result,intNum1,len1,intNum2,len2);		//乘
		
		//输出结果
		bool remain0 = true;
		for(i=0; i<len2+len1; i++)
		{
			if( result[i] != 0 ) remain0 = false;
			if( !remain0 ) out<<result[i];
		}
		if( remain0 ) out<<"0";
		out<<endl;
		
		delete[] result;							//回收内存
	}
	
    return 0;
}

安卓应用层抓包通杀脚本发布!《高研班》2021年3月班开始招生!

上传的附件:
  • 4.rar (91.71kb,33次下载)
收藏
点赞0
打赏
分享
最新回复 (4)
雪    币: 1331
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Ivanov 活跃值 2008-9-28 10:31
2
0
鼓励~东西不错
雪    币: 765
活跃值: 活跃值 (125)
能力值: (RANK:730 )
在线值:
发帖
回帖
粉丝
海风月影 活跃值 17 2008-9-28 11:42
3
0
论坛已经看不到声望了
雪    币: 2025
活跃值: 活跃值 (15)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 活跃值 4 2008-9-28 11:45
4
0
听说你脚下的星星就是代表声望
雪    币: 509
活跃值: 活跃值 (10)
能力值: ( LV12,RANK:220 )
在线值:
发帖
回帖
粉丝
xiep 活跃值 5 2008-9-28 15:49
5
0
Yeah~~
游客
登录 | 注册 方可回帖
返回