注册 登录
编程论坛 → C++教室

有些诡异的问题，求帮忙

八画小子 发布于 2011-08-17 22:56， 504 次点击
ValueNode.h
程序代码：
#ifndef VALUE_NODE_H_
#define VALUE_NODE_H_

#include <iostream>

const unsigned long long ZERO = 0;

class ValueNode
{
private:
    unsigned long long    capacity;        // 数值字符串中包含无效的0后的字符个数，即当前能够储存的最大位数，容量
    unsigned long long    length;            // 数值字符串除去无效的0后的位数，即当前所表示的数的实际有效位数，数值有效位数。
    char *                value;            // 数值字符串，以小数点开始，存储实际值。
private:
    bool expand();
public:
    ValueNode();
    ValueNode(const char * v);
    ValueNode(const unsigned long long x);
    ValueNode(const ValueNode & x);
    ~ValueNode();
    unsigned long long Length() const;
    ValueNode & Add(const char * v);
    ValueNode & Add(const ValueNode & x);
    ValueNode & operator+=(const char * v);
    ValueNode & operator+=(const ValueNode & x);
    ValueNode & operator+(const char * v);
    ValueNode & Sub(const ValueNode & x);
    ValueNode & Mul(const ValueNode & x);
    ValueNode & operator=(const char * v);
    ValueNode & operator=(const unsigned long long x);
    ValueNode & operator=(const ValueNode & x);

    friend ValueNode & operator+(const ValueNode & x, const ValueNode & y);
    friend bool operator==(const ValueNode & x, const ValueNode & y);
    friend bool operator!=(const ValueNode & x, const ValueNode & y);
    friend bool operator>=(const ValueNode & x, const ValueNode & y);
    friend bool operator>=(const ValueNode & x, const ValueNode & y);
    friend bool operator>(const ValueNode & x, const ValueNode & y);
    friend bool operator<(const ValueNode & x, const ValueNode & y);
    friend std::ostream & operator<<(std::ostream & os, const ValueNode & x);
};
#endif
ValueNode.cpp
程序代码：
#include "ValueNode.h"

// 私有成员函数
bool ValueNode::expand()
{
    char * temp    = new char[this->capacity * 2];
    if (temp == 0)
        return false;

    this->capacity *= 2;
    for(int i = 0; i < this->length; ++i)
        temp[i] = this->value[i];
    memset(temp + this->length, '\0', this->capacity - this->length);
    delete [] this->value;
    this->value = temp;
    return true;
}

// 共有成员函数
ValueNode::ValueNode()
{
    this->capacity    = 2;
    this->length    = 1;
    this->value        = new char[capacity];
    this->value[length - 1] = '0';
    memset(this->value + this->length, '\0', this->capacity - this->length);
}

ValueNode::ValueNode(const char * v)
{
    unsigned long long n = strlen(v);
    if(n == 0)
    {
        this->capacity    = 2;
        this->length    = 1;
        this->value        = new char[capacity];
        this->value[length - 1] = '0';
        memset(this->value + this->length, '\0', this->capacity - this->length);
    }
    else
    {
        unsigned long long p;
        for(p = 0; (v[p] == '0') && (p < n); ++p);
        if(p == n)
        {
            this->capacity    = 2;
            this->length    = 1;
            this->value        = new char[capacity];
            this->value[length - 1] = '0';
            memset(this->value + this->length, '\0', this->capacity - this->length);
        }
        else
        {
            this->capacity    = 2;
            this->length    = 0;
            this->value        = new char[capacity];

            for(unsigned long long i = 0; i < n - p; ++i)
            {
                this->value[i] = v[n - i - 1];
                this->length += 1;
                if(this->length == this->capacity)
                    this->expand();
            }
            memset(this->value + this->length, '\0', this->capacity - this->length);
        }
    }
}

ValueNode::ValueNode(const unsigned long long x)
{
    this->capacity    = 2;
    this->length    = 0;
    this->value        = new char[this->capacity];

    unsigned long long i = 0;
    unsigned long long temp = x;
    do
    {
        this->value[i] = temp % 10 + '0';
        this->length += 1;
        ++i;
        if(this->length == this->capacity)
            this->expand();
        temp /= 10;
    }while(temp);
    memset(this->value + this->length, '\0', this->capacity - this->length);
}

ValueNode::ValueNode(const ValueNode & x)
{
    this->capacity        = x.capacity;
    this->length        = x.length;
    this->value            = new char[this->capacity];
    memcpy(this->value, x.value, this->length);
}

ValueNode::~ValueNode()
{
    delete [] value;
}

unsigned long long ValueNode::Length() const
{
    if(this->value[0] == '0' && this->value[1] == '\0')
        return 0;
    return length;
}

ValueNode & ValueNode::Add(const ValueNode & x)
{
    unsigned long long max_length = (this->length >= x.length) ? this->length : x.length;   

    ValueNode result;
    result.length = 0;

    int carry_out    = 0;
    int carry_in    = 0;
    bool is_zero = true;   
    for(unsigned long long i = 0; i < max_length; ++i)
    {
        carry_in = carry_out;
        carry_out = 0;
        result.value[i] = this->value[i] + x.value[i]  + carry_in;
        if(this->value[i] != '\0')
            result.value[i] -= '0';
        if(x.value[i] != '\0')
            result.value[i] -= '0';
        result.length += 1;
        if(result.value[i] > 9)
        {
            carry_out = 1;
            result.value[i] -= 10;
        }
        if(result.value[i] != 0)
            is_zero = false;
        result.value[i] += '0';
        if(result.length == result.capacity)
            result.expand();
    }
    if(carry_out != 0)
    {
        result.value[result.length] = '1';
        is_zero = false;
        result.length += 1;
        if(result.length == result.capacity)
            result.expand();
        carry_out = 0;
    }

    if(is_zero)
    {
        result.capacity                    = 1;
        result.length                    = 0;
        result.value                    = new char[result.capacity];
        result.value[result.capacity]    = '0';
    }

    *this = result;

    return *this;
}

ValueNode & ValueNode::operator=(const char * v)
{
    unsigned long long n = strlen(v);
    unsigned long long p;
    for(p = 0; (v[p] == '0') && (p < n); ++p);
    if(p == n)
    {
        this->capacity    = 2;
        this->length    = 1;
        this->value        = new char[capacity];
        this->value[length - 1] = '0';
        memset(this->value + this->length, '\0', this->capacity - this->length);
    }
    else
    {
        this->capacity    = 2;
        this->length    = 0;
        this->value        = new char[capacity];

        for(unsigned long long i = 0; i < n - p; ++i)
        {
            this->value[i] = v[n - i - 1];
            this->length += 1;
            if(this->length == this->capacity)
                this->expand();
        }
        memset(this->value + this->length, '\0', this->capacity - this->length);
    }

    return *this;
}

ValueNode & ValueNode::operator=(const unsigned long long x)
{
    this->capacity    = 1;
    this->length    = 0;
    this->value        = new char[this->capacity];

    unsigned long long i = 0;
    unsigned long long temp = x;
    do
    {
        this->value[i] = temp % 10 + '0';
        this->length += 1;
        ++i;
        if(this->length == this->capacity)
            this->expand();
        temp /= 10;
    }while(temp);
    memset(this->value + this->length, '\0', this->capacity - this->length);

    return *this;
}

ValueNode & ValueNode::operator=(const ValueNode & x)
{
    this->capacity        = x.capacity;
    this->length        = x.length;
    this->value            = new char[this->capacity];
    memcpy(this->value, x.value, this->length);

    return *this;
}



// 友元函数
std::ostream & operator<<(std::ostream & os, const ValueNode & x)
{
    char * temp = new char[x.length + 1];
    for(unsigned long long i = 0; i < x.length; ++i)
        temp[x.length - 1 - i] = x.value[i];
    temp[x.length] = '\0';

    os << temp;
    return os;
}
test.cpp
程序代码：
#include <ctime>
#include "ValueNode.h"

using std::cin;
using std::cout;
using std::endl;

int main()
{
    unsigned long long times = 50;
    ValueNode a = "1";
    ValueNode b = "1";
    ValueNode temp;
    unsigned int i = 2;
    cout << "1.\t" << a << "\t\t\t\t" << a.Length() << endl << "2.\t" << b << "\t\t\t\t" << b.Length() << "\n";
    do
    {
        temp = b;
        b.Add(a);
        a = temp;
        cout << i++ << ".\t";
        cout << b << "\t\t\t\t";
        cout << b.Length() << endl;
    }while(i <= times);

    cin.get();
    return 0;
}


我的问题是：在计算斐波那契数列的第12个时出现了错误。看了所有的数据，发现如果前两个数的位数不一致就会出现问题，而其他的数只是因为前一钟情况而出问题。想问到底是为什么？如果单独计算没问题，比如89+144就没有问题。

6 回复
#2
stophin2011-08-18 00:17
add函数的问题，你是在8+13时用this[0]和x[0]加起来，相当于是8和1加起来，但事实是8和3加起来哦，请修改下自己的程序吧，为什么一定要用字符串来表示数字呢，斐波那契数列应该都是整数啊，把value定义成整数就省去了-'0'再+‘0’的麻烦了
#3
八画小子2011-08-18 00:58
8+13是没问题的
#4
naruto012011-08-18 01:14
程序代码：
ValueNode & ValueNode::Add(const ValueNode & x)
{
    unsigned long long max_length = (this->length >= x.length) ? this->length : x.length;   

    ValueNode result;

...    //省略

}
根据你的构造函数
程序代码：
ValueNode::ValueNode()
{
    this->capacity    = 2;
    this->length    = 1;
    this->value        = new char[capacity];
    this->value[length - 1] = '0';
    memset(this->value + this->length, '\0', this->capacity - this->length);
}
result对象至多只能存储2位有效数字吧？
到第12项(144)自然也就超出了存储范围。
#5
八画小子2011-08-18 01:20
我的电脑是4GB的，可使用3G左右的内存。在我的电脑上result最多可以储存65560位左右的十进制数
#6
八画小子2011-08-18 23:01
希望帮忙
#7
stophin2011-08-19 23:54
回复 6楼 八画小子
楼主你好，我帮你找了一下，发现只有第12个里面有错误，后面连累着错了。第12个里面是这样加的：前面的数是89和144,分别存放在x.value和this->value中，并且是倒序存储的，即:x.value中是'9''8',this->value中是'4''4''1'。取得max_length=3。
i=0,carry_in=0,this->value[0]+x.value[0],4+9+0=3,carry_out=1;
i=1,carry_in=1,this->value[1]+x.value[0],4+8+1=3,carry_out=1;
i=2,carry_in=1,this->value[2]+x.value[2],1+1+1=3,carry_out=0;
最终结果333，可以发现1+1+1=3这里x.value数组越界了，且它的取值为'1'，原本应该是1+0+1=2,结果233。楼主应该庆幸其他数组越界以后都取得了'0'或者'\0'，不然错误会更多。
解决的方法如下：
由于x.length和this->length在50个数的范围内只可能相差1(50个数以外的大数有没有诸如n位数+(n+1)位数=(n+3)位数的?可以验证一下，有的话差值为2，这种方法就不适用了)，而且max_length确定一定以及肯定会取this->length，这样在运行的过程中i一定会取到x.length(==max_length-1),这样x.value一定会越界，而且肯定是在边界上，这个地方本来是结束符'\0'的，但是楼主的程序中并没有给每个value加'\0',导致越界后取'1'(看个人系统了，不一定总是'1')。可以在add函数的for循环前面任意位置加上这句:
x.value[x.length]='\0';
或者
x.value[x.length]='0';

[ 本帖最后由 stophin 于 2011-8-19 23:56 编辑 ]
1
©2025, BC-CN.NET
电脑版