poj-1001

//384K  0MS G++#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAX 5200structruct BigNumber {char val[MAX]; // all chars are '0' or no char means '0'};typedef struct BigNumber BigNumber;void bigNumberAddZero(BigNumber * p1, int zeroNum) {    int length = strlen(p1->val);    int i = 0;    for (; i < zeroNum; i++) {        p1->val[i+length] = '0';    }    p1->val[i+length] = 0;}void bigNumberAdd(BigNumber * p1, BigNumber * p2, BigNumber * res) {    int p1L = strlen(p1->val);    int p2L = strlen(p2->val);// printf("bigNumberAdd %d %d\n", p1L, p2L);    int maxLength = p1L > p2L ? p1L : p2L;    if (p1L > p2L) {        bigNumberAddZero(p2, p1L - p2L);    } else if (p1L < p2L) {        bigNumberAddZero(p1, p2L - p1L);    }    int carryFlag = 0;    int i = 0;    for (i = 0; i < maxLength; i++) {        int v1 = (p1->val[i] - '0');        int v2 = (p2->val[i] - '0');        int sum = v1 + v2 + carryFlag;        if (sum >= 10) {            carryFlag = 1;            res->val[i] = sum - 10 + '0';        } else {            carryFlag = 0;            res->val[i] = sum + '0';        }    }    if (carryFlag == 1) {        res->val[maxLength] = '1';        carryFlag = 0;        res->val[maxLength+1] = 0;    } else {        res->val[maxLength] = 0;    }}void bigNumberMultiplyS(BigNumber * p1, int p2, BigNumber * res) {    int carryVal = 0;    int length = strlen(p1->val);    for (int i = 0; i < length; i++) {        int val = p1->val[i] - '0';        int result = val*p2 + carryVal;        carryVal = result/10;        res->val[i] = result%10 + '0';    }    if (carryVal > 0) {        res->val[length] = carryVal + '0';        res->val[length+1] = 0;    }}void bigNumberAppendZero(BigNumber * p1, int zeroNum) {    if (!zeroNum) {        return;    }    for (int i = strlen(p1->val); i >= 0; i--) {        p1->val[i+zeroNum] = p1->val[i];        p1->val[i] = '0';    }}BigNumber b1;BigNumber b2;BigNumber b3;BigNumber res;BigNumber tmp;BigNumber tmp2;void printBigNumber(BigNumber * p1) {    char beginPrint = 0;    if (strlen(p1->val) == 0) {        printf("0");    } else {        for (int i = strlen(p1->val)-1; i >= 0; i--) {            if (beginPrint) {                printf("%c", p1->val[i]);            } else {if (p1->val[i] != '0') { // first counter 1~9    beginPrint = 1;    printf("%c", p1->val[i]);}}}}printf("\n");}void bigNumberMultiply(BigNumber * p1, BigNumber * p2, BigNumber * res) {// printf("bigNumberMultiply\n");    int p1L = strlen(p1->val);    int p2L = strlen(p2->val);    BigNumber * big = p1L > p2L ? p1 : p2;    BigNumber * small = p1L <= p2L ? p1 : p2;    BigNumber * small = p1L <= p2L ? p1 : p2;    int length = p1L < p2L ? p1L : p2L;    for (int i = 0; i < length; i++) {// printf("bigNumberMultiply %c\n", small->val[i]);        int S = small->val[i] - '0';        memset(&tmp, 0, sizeof(BigNumber));if (S) { // this check better in bigNumberMultiplyS    bigNumberMultiplyS(big, S, &tmp);    bigNumberAppendZero(&tmp, i);    memcpy(&tmp2, res, sizeof(BigNumber));    bigNumberAdd(&tmp2, &tmp, res);}}}void reset() {    memset(&b1, 0, sizeof(BigNumber));    memset(&b2, 0, sizeof(BigNumber));    memset(&b3, 0, sizeof(BigNumber));    memset(&res, 0, sizeof(BigNumber));    memset(&tmp, 0, sizeof(BigNumber));    memset(&tmp2, 0, sizeof(BigNumber));}void bigNumberExp(BigNumber * p1, int N, BigNumber * res) {// printf("N %d\n", N);    if (N == 0) {        res->val[0] = '0';        res->val[1] = 0;        return;    }    memcpy(res, p1, sizeof(BigNumber));    int i = 2;// printf("%d %d\n", i, N);    for (; i <= N; i++) {// printf("%d\n", i);        bigNumberMultiply(p1, res, &tmp2);// printBigNumber(&tmp2);        memcpy(res, &tmp2, sizeof(BigNumber));        memset(&tmp2, 0, sizeof(BigNumber));    }// printf("END\n");}void printBigNumberWithPoint(BigNumber * p1, int smallNum) {    int length = strlen(p1->val);    if (!length) {        printf("0\n");        return;    }    for (int i = length - 1; i >= 0; i--) { // remove prefix 0; eg 004459900 -> 4459900        if (p1->val[i] != '0') {            p1->val[i+1] = 0;            break;        }    }    length = strlen(p1->val);    if (smallNum <= 0) { // no small number        for (int i = length-1; i >= 0; i--) {            printf("%c", p1->val[i]);        }        printf("\n");        return;    } else if (smallNum >= length) { // all small number, remove all after 0, eg 3343708000 -> 3343708        int i = 0;        for (; i <= length-1; i++) {            if (p1->val[i] != '0') {                break;            }        }        int printEnd = i;        int frontZeroNum = smallNum - length;        printf(".");        for (int i = 1; i <= frontZeroNum; i++) {            printf("0");        }        for (int i = length-1; i >= printEnd; i--) {            printf("%c", p1->val[i]);        }    } else { //bigNum.smallNumber        int printEnd = 0;        for (int i = 0; i < smallNum; i++) {            if (p1->val[i] != '0') {                printEnd = i;                break;            }        }        for (int i = length - 1; i >= printEnd; i--) {            printf("%c", p1->val[i]);            if (i == smallNum) {                printf(".");            }        }    }    printf("\n");}int main() {    int N;    reset();    while(scanf("%s %d", b1.val, &N) != EOF) {        int i;        int length = strlen(b1.val);                // for (int i = length - 1; i >= 0; i--) {        //     if (b1.val[i] == '.') {        //         break;        //     } else if (b1.val[i] != '0') {        //         b1.val[i+1] = 0;        //         break;        //     }        // }        // find the '.' location        for (i = 0; i < length; i++) {            if (b1.val[i] == '.') {                break;            }        }        // find the length of small number        int smallNumberLength;        if (i >= length) { // '.' do not exist, no small number            smallNumberLength = 0;        } else {    // get the length of small number, special case: 1.0000 -> 1            for (int j = length-1; j >= i; j--) {                if (b1.val[j] == '.') { // no small number. eg 1.0000                    b1.val[j] = 0;                    smallNumberLength = 0;                    break;                } else if (b1.val[j] != '0') {                    b1.val[j+1] = 0;                    smallNumberLength = j - i;                    break;                }            }        }        //remove '.'        if (smallNumberLength == 0) {        } else {            for (; i < length; i++) {                b1.val[i] = b1.val[i+1];            }        }        int noZeroBegin = 0;        int noZeroEnd = strlen(b1.val)-1;        //remove front 0, e.g, 0022343200 -> 22343200        for (; b1.val[noZeroBegin] == '0'; noZeroBegin++) {        }        // //remove append 0, e.g, 22343200 -> 223432        // for (; b1.val[noZeroEnd] == '0'; noZeroEnd--) {        // }        strncpy(b3.val, b1.val + noZeroBegin, noZeroEnd - noZeroBegin + 1);// printf("%s %d\n", b1.val, smallNumberLength);// printf("%s %d %d %d\n", b3.val, smallNumberLength, noZeroBegin, noZeroEnd);        length = strlen(b3.val);        for (i = 0; i <= (length/2)-1; i++) {            char tmp = b3.val[i];            b3.val[i] = b3.val[length - i-1];            b3.val[length - i-1] = tmp;        }// memcpy(&b2, &b1, sizeof(BigNumber));// bigNumberAppendZero(&b1, 4);// bigNumberAdd(&b1, &b2, &b3);// bigNumberAdd(&b3, &b2, &b1);// bigNumberMultiplyS(&b1, 5, &b2);// bigNumberMultiply(&b1, &b2, &b3);        smallNumberLength *= N;        bigNumberExp(&b3, N, &b2);        // printBigNumber(&b3);        // printBigNumber(&b2);        // printBigNumberWithPoint(&b3, smallNumberLength);        printBigNumberWithPoint(&b2, smallNumberLength);// printBigNumber(&b3);// printf("%s %d\n", b1.val, smallNumberLength);// printf("%s %d\n", b2.val, smallNumberLength);// printf("%s %d\n", b3.val, smallNumberLength);        reset();    }}

384K 0MS G++

本来想捏个软柿子，以为1001应该是个水题，谁想到竟然是我以前望而生畏的大数乘法(以前最多大数加减)，

这个问题是一个典型的思维方式，是水题(小学乘法)，但实现细节的绝对调查。

基本上大家都知道要用字符串来模拟求值，但脑子里有雏形和真实写作的差别并不是一点点。

而且题目的输出要求不能多余0等，也进一步增加了AC的难度，记录了思路：

首先，打开一个大字符串数组来存储大数(直接打开5000，反正内存够了)， 专门做了一个bignumber封装，只是一个皮肤。

输入也是字符串A，长度为L，首先要找到 ‘.’ 如果找不到位置，那么这个数字一定是整数，小数位长度是0.

如果找到了，就找到了。.'， 这意味着这是一个实数。我们应该先做一件事，那就是清除小数位后面的0，比如 1.01000 -> 1.01(似乎不会出现 0XX.XX 这种情况，但还是考虑了)， 只有这样做，我们才能找到真正的小数位长度。然后是把 '.' 去掉，得到一个整数，作为以后的操作，

这里为了方便操作，采用小端保存法(A前后颠倒)，即将整数的低位存储在数组前面的位置，如 1234 将其保存在数组C中 C[0] = 4 C[1] = 3 C[2] = 2 C[3] = 1、这样在以后的大整数加法中会很方便，否则每次都要考虑数位对齐，

要实现的大数操作包括：

1. 两个大数相加： 小学加法，做进位标记参与运算， 但是要扩大数位短的大数。

2. 一个大数和一个整数相乘；小学乘法 保存进位(0~9)进行进位变量。

3. 一个大数增加10的N这个方倍：向右平移N位，空出来补零。

4. 两个大数相乘： 以数位短的大数作为乘数，可以节省一些时间，其它操作是小学乘法步骤，用前三种操作组合实现， 单位数乘法每次进行一次，然后累积到

乘积和中，同时适当乘以10n次方。

4. 大数整数次方运算： 懒得做乘法优化(也就是说) ，若N为偶数， X的N次方 = （X的N/2次方平方)平方， 如果是奇数，再乘一次X，可以大大降低乘数)

直接乘，反正时间够了，次数最多25次.

在最终输出结果时，计算结果的小数位S应该是多少（即次数*X的原始小数位长度）。如果小数位为0，则直接输出整数。

如果小数位大于结果R的长度L(和只有小数)，则在前面添加一个 '.然后输出 S-L0，然后输出R，注意最终连续0不能输出 及0.0021212300 -> 0.0021212300

假如既有整数又有小数，那么也要考虑小数后面连续0的情况，输出时还要插入 '.'。

这个问题是一个非常经典的问题，比较测试基本技能和细节，当我想再次写正确的时候，估计细节是相似的（事实上，不现实，事实上，软件开发方法在很大程度上是一种试错方法，

这其实是由人的思维结构决定的，除非所有的code都在脑海中打磨出来).