poj-1001
发布时间：2023-05-24 09:25:11
//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都在脑海中打磨出来).
