Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

目前能找到的测试数据都过了,但是还是WA。。。。。。求高手指点

Posted by lisanhu at 2016-07-24 18:13:13 on Problem 1001
思路跟常规有所不同,使用24个long 作为存储空间,模拟底层乘法器的计算方式,以超大整数进行计算,结果添加小数点再进行修正字符串

能找到的测试数据全都过了,但是依然WA,求高手指点错在哪里了

代码如下:
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

#define STORE 24

class LargeNumber;

LargeNumber operator*(const LargeNumber &lhs, const LargeNumber &rhs);

string trim(string &src);

class LargeNumber {
public:
    long bits[STORE];
    long carry, dot;

    LargeNumber(const char *str = "0") : carry(0), dot(0) {
        for (int i = 0; i < STORE; ++i) {
            bits[i] = 0;
        }
        size_t len = strlen(str);
        char buf[100];
        for (int i = 0; i < 7; ++i) {
            buf[i] = 0;
        }
        const char *pt = strchr(str, '.');
        if (NULL == pt) {
            dot = 0;
            strcpy(buf, str);
        } else {
            dot = (int) (len - (pt - str) / sizeof(char) - 1);
            strncpy(buf, str, pt - str);
            strncpy(buf + (pt - str), pt + 1, (size_t) dot);
        }
        bits[0] = (unsigned long) atol(buf);
    }

    LargeNumber(const LargeNumber &rhs) {
        memcpy(bits, rhs.bits, STORE * sizeof(long));
        carry = rhs.carry, dot = rhs.dot;
    }

    LargeNumber power(int n) {
        if (n == 0) {
            return LargeNumber("1");
        } else if (n > 1) {
            return power(n - 1) * *this;
        } else if (n == 1) {
            return *this;
        } else {
            throw 10;
        }
    }

    string to_string() {
        string result;
        const char *tpl = "%09ld";
        char buf[10];
        for (int i = 0; i < STORE; ++i) {
            sprintf(buf, tpl, bits[STORE - i - 1]);
            result.append(buf);
        }
        result.insert(result.length() - dot, ".");
        result = trim(result);
        return result;
    }
};

string trim(string &src) {
    string result;
    string::iterator end;
    int state = 0;
    for (size_t i = 0; i < src.length(); ++i) {
        if (src[i] == '0' && state == 0) {
            continue;
        }
        state = 1;
        result.push_back(src[i]);
    }

    size_t len = result.length();
    for (size_t i = 0; i < len; ++i) {
        size_t idx = len - i - 1;
        if (result[idx] == '0') {
            end = result.end() - 1;
            result.erase(end);
            continue;
        }
        break;
    }

    len = result.length();
    if (result[len - 1] == '.') {
        end = result.end() - 1;
        result.erase(end);
    }

    if (result == "") {
        result = "0";
    }
    return result;
}

LargeNumber operator*(const LargeNumber &lhs, const LargeNumber &rhs) {
    LargeNumber result;
    result.dot = lhs.dot + rhs.dot;
    result.carry = 0;
    long base = 1000000000L;
    long tmp;
    for (int i = 0; i < STORE; ++i) {
        for (int j = 0; j < STORE; ++j) {
            tmp = rhs.bits[i] * lhs.bits[j] + result.carry;

            if (tmp >= base) {
                result.carry = tmp / base;
                if (i + j < STORE) {
                    result.bits[i + j] += tmp - result.carry * base;
                }
            } else {
                result.carry = 0;
                if (i + j < STORE) {
                    result.bits[i + j] += tmp;
                }
            }
        }
    }
    return result;
}

/**
 * 95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12
 * @return
 */
int main() {
    string number;
    int power;
    LargeNumber num;
    while (cin >> number >> power) {
        num = number.c_str();
        cout << num.power(power).to_string() << endl;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator