2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。2369人阅读
数学和算法（2）
题目：输入一序列的正实数和幂次（正整数）对，然后打印结果（具体的比这个精细）
这道题是关于大数计算的（大数求幂），从开始建立思路，到写代码、调式到最后被AC以及最终的优化，总共用了差不多一天的时间。开始AC时使用空间500K，时间37MS，最后一次AC空间400K，时间0MS，有很大提高。这主要归功于加大了每次的数据处理量，减少了重计算次数以及降低循环代码量。还有就是在使用了二分递归,避免了重复计算。不好的一点是代码量太大，并且使用了太多的变量。
不管怎么样，为这道题付出了很多想法，后来的一些大的优化主要来自对底层的深入理解，代码的整体实现粒度是很细的，阅读起来可能会有些困难，但很是值得推敲的，具体实现代码如下：
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
void add(char *s1, char *s2);
char *multi(char *s1, char *s2);
char *result(char *s, int n);
int main(void) {
char ch[100];
char tem, *temp1, *temp2;
while ( scanf(&%s%d&, ch, &num) != EOF ) {
chp = ch + strspn(ch, &0&);
// 去掉前导0
temp1 = &ch[strlen(ch)-1];
if ( (temp2 = strchr(ch, '.')) != NULL ) {
// 如果有小数点
while ( *temp1 == '0' )
// 去掉小数末尾的0
*temp1-- = 0;
= strlen(temp2) - 1;
// 小数位的num倍是最终结果的小数位数
memmove(temp2, temp2+1, strlen(temp2));
// 去掉小数点
= result(chp, num);
printf(&res: %s\n&, res);
temp1 = res + strspn(res, &0&);
temp2 = &res[strlen(res) - np];
// 定位小数点
if ( temp1 &= temp2 && np != 0 )
// 如果结果小于1
printf(&%c%s\n&, '.', temp2);
else if ( np == 0 )
// 如果是整数
printf(&%s\n&, temp1 == temp2 ? 0 : temp1);
// 将该放小数点位置的源字符保存
*temp2++ = 0;
// 这里将源结果字符串断开，块式输出效率高
printf(&%s%c%c%s\n&, temp1,
*temp2 == 0 ? && : temp2);
free(res);
char *result(char *s, int n) {
char *res, *ch1, *ch2;
if ( n == 1 )
return multi(s, &1&);
// 返回统一类型的可被free掉的数据空间
else if ( n == 2 )
return multi(s, s);
else if ( n & 2 ) {
ch1 = result(s, n && 1);
// 二分递归计算
if ( n % 2 != 0 ) {
ch2 = result(s, n - (n && 1));
res = multi(ch1, ch2);
free(ch2);
// result函数返回值得释放掉
// 如果n是偶数，可避免重复计算
res = multi(ch1, ch1);
free(ch1);
char *multi(char *s1, char *s2) {
char *ch1, *ch2, *cp1, *cp2, *cp3;
char chp[18];
i, j, num,
long long j1, j2, j3; // 加大每次计算量
i1 = strlen(s1);
i2 = strlen(s2);
ch1 = (char *)malloc(i1 + i2 + 2);
// 1 bit '\0', 1 carry bit(reserved for)
if ( strncmp(s2, &1&, 1) == 0 && i2 == 1 ) {
memcpy(ch1, s1, i1+1);
return ch1;
ch2 = (char *)malloc(i1 + i2 + 1);
// 1 bit '\0'
memset(ch1, '0', i1 + i2 + 2);
ch1[i1+i2+1] = 0;
while ( i & 0 ) {
if ( i &= 8 )
// 和j，每次各可处理8位
memset(ch2, '0', i1 + i2 + 1);
// ch2每次循环都可能被修改
ch2[i1+i2] = 0;
cp1 = &s1[i1];
cp2 = &s2[i2];
cp3 = &ch2[i1 + i];
i1+i2-(i2-i)=i1+i, 每次循环往左移动dis位，表示和记录进位
memcpy(chp, cp2 - i2 + i, dis);
chp[dis] = 0;
= atoi(chp);
while ( j & 0 ) {
if ( j &= 8 )
// 最多8位迭代处理与j2相乘
memcpy(chp, cp1, num);
chp[num] = 0;
= atoi(chp);
memcpy(chp, cp3, dis);
// cp3记录进位，最多有dis位
chp[dis] = 0;
= atoi(chp);
snprintf(chp, 18, &%lld&, j1 * j2 + j3);
j1 = strlen(chp);
memcpy(cp3 -j1 + dis, chp, j1);
// 数据向右对齐
// 定位到下次计算进位可能占据空间的开头地址
add(ch1, ch2);
// 将新的计算结果与前面的相加，最后可获得最后结果
free(ch2);
return ch1;
void add(char *s1, char *s2) {
char *cp1, *cp2, *cp3, *
char chp[18];
num, n1, n2;
long long i, j,
s2 += strspn(s2, &0&);
= strlen(s1);
// make sure n1 & n2
= strlen(s2)) == 0 )
= (char *)malloc(n1+1);
memset(ch, '0', n1);
ch[n1] = 0;
cp1 = &s1[n1];
cp2 = &s2[n2];
cp3 = &ch[n1 - 1];
while ( n2 & 0 ) {
// must validate enough memory
if ( n2 &= 16 )
memcpy(chp, cp1, num);
chp[num] = 0;
= atoll(chp);
memcpy(chp, cp2, num);
chp[num] = 0;
= atoll(chp);
memcpy(chp, cp3, 1);
chp[1] = 0;
= atoll(chp);
snprintf(chp, 18, &%lld&, i + j + k);
i = strlen(chp);
cp3 -= i - 1;
memcpy(cp3, chp, i);
cp3 += i - 1 -
memcpy(s1, ch, n1);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：23000次
排名：千里之外
原创：10篇