华为"128为大整数相加"机试题
最近正直春招,偶尔接触到了华为的这道大整数相加的测试题,在网上找了一个算法,然后自己尝试进行了优化,最后也对memmove()函数效率有了进一步把握.
#include <time.h>
#include <iostream>
using namespace std;
#define MAX_LENGTH 128
void Add(const char *pszOperand1, const char *pszOperand2, char *pszResult); //互联网上原始代码
void Add2(const char *pszOperand1, const char *pszOperand2, char *pszResult, size_t len ); //优化后的代码
int main()
{
char szOperand1[MAX_LENGTH + 1], szOperand2[MAX_LENGTH + 1], szResult[MAX_LENGTH + 2];
cin >> szOperand1 >> szOperand2;
clock_t startTime = clock();
for ( int i = 0; i < 100000000; ++i ) //原始代码测试
{
Add(szOperand1, szOperand2, szResult);
}
clock_t endTime = clock();
cout << szOperand1 << " + " << szOperand2 << " = " << szResult << endl;
cout << "Total time = " << endTime - startTime << endl; //132725ms
startTime = clock();
for ( int i = 0; i < 100000000; ++i ) //优化后代码测试
{
Add2( szOperand1, szOperand2, szResult, MAX_LENGTH+2 );
}
endTime = clock();
cout << szOperand1 << " + " << szOperand2 << " = " << szResult << endl;
cout << "Total time = " << endTime - startTime << endl; //84287ms
//总结:Add2()函数比Add()函数在使用了memmove()优化后效率提升了36.28%,而空间节省了40%。
return 0;
}
void Add(const char *pszOperand1, const char *pszOperand2, char *pszResult)
{
short iResult[MAX_LENGTH + 1];
short iCarry = 0;
int i = (int) strlen(pszOperand1) - 1;
int j = (int) strlen(pszOperand2) - 1;
int k = MAX_LENGTH + 1;
while (i >= 0 || j >= 0)
{
k--;
iResult[k] = 0;
if (i >= 0)
iResult[k] += pszOperand1[i--] - '0';
if (j >= 0)
iResult[k] += pszOperand2[j--] - '0';
iResult[k] += iCarry;
if (iResult[k] >= 10)
{
iResult[k] -= 10;
iCarry = 1;
}
else
iCarry = 0;
}
if (iCarry == 1)
iResult[--k] = 1;
i = 0;
for (; k <= MAX_LENGTH; k++, i++)
pszResult[i] = iResult[k] + '0';
pszResult[i] = '\0';
}
void Add2(const char *pszOperand1, const char *pszOperand2, char *pszResult, size_t len )
{
size_t i = strlen( pszOperand1 );
size_t j = strlen( pszOperand2 );
if ( len < (max(i, j) +2 ) )
return;
size_t k = len;
pszResult[--k] = '\0';
short temp = 0;
short curso = 0;
while ( i > 0 || j > 0 )
{
temp = curso;
if ( i > 0 )
temp += pszOperand1[--i] - '0';
if ( j > 0 )
temp += pszOperand2[--j] - '0';
if ( temp > 10 )
{
pszResult[--k] = temp - 10 + '0';
curso = 1;
}
else
{
pszResult[--k] = temp + '0';
curso = 0;
}
}
memmove( pszResult, pszResult + k, len - k );
}
测试用例:被加数与加数都是下面的120位整数
123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
测试环境:
编译器 :vs 2005
操作系统:windows7 64 bit
处理器 :英特尔 Pentium(奔腾) G860 @ 3.00GHz 双核
内存 :4 GB ( 金士顿 DDR3 1600MHz )
总结:Add2()函数比Add()函数在使用了memmove()优化后效率提升了36.28%,而空间节省了40%。
最新文章
- oracle遍历表更新另一个表(一对多)
- 如何让你的App适配iOS7?
- 使用HtmlAgilityPack解析Html(非常好用)
- bootstrap按钮
- dp - 2015 Multi-University Training Contest 2 1004 Delicious Apples
- node socket onmessage
- 多线程基础及实例(java)
- mysql导出部分(指定)数据库表字段
- 修改MySQL的递增的起始值
- java selenium webdriver实战 应用小结
- mongodb更新数据
- TCP/IP详解 卷1 第二十章 TCP的成块数据流
- Oracle三层嵌套分页查询示例及rownum原理
- ip通信第七周
- Java虚拟机垃圾收集器
- 设计模式---状态变化模式之备忘录模式(Memento)
- vuejs中使用echarts
- cpu使用率低负载高,原因分析
- linux下vim的安装及其设置细节
- python 小程序,在列表中找到所有指定内容的位置
热门文章
- redhat enterprixe 5.0 NFS服务配置与管理
- <;构建之法>;之第一二三章的感悟
- TopCoder SRM 583 TurnOnLamps
- POJ 2886 Who Gets the Most Candies?
- wScratchPad 实现刮刮卡效果
- Python 条件判断 循环
- jQuery 自定义扩展,与$冲突处理
- 《JAVA学习笔记(14-1---14-7)》
- Android开发中的ANR问题如何避免?
- UIViewController添加子控制器(addChildViewController)