[Icarus]北大《C++程序设计》week4编程代码_#include

本周的课程作业量有点儿大，比较不好写的是后两题。倒数第二题参考了网上很多人的代码，最后选了一个我觉得比较好的写法，即用指针的指针（而不是仅仅用指针）来实现这个二维数组，这样写下来逻辑就顺畅多了。。。同理，也可以使用指针的指针的指针来实现三维数组，不过构造析构会比较麻烦。

此次交作业，同样要注意的是本周的填空代码如果在Coursera上提交的话只需提交空缺部分即可，不然会通不过。

最后的这个大整数类折磨了我好几天（是我基础比较薄弱），刚开始的时候看别人的代码没看懂，然后果断找来晴神宝典细细研读了大整数（又称高精度整数）运算的内容（《算法笔记》第5章-数学问题-5.6），无奈乘除法部分只介绍了高精度与低精度的乘除，上面的原话是“至于高精度与高精度的乘法和除法，考试一般不会涉及，因此留给有兴趣的读者自行了解。”再去翻王道的机试指南，比较郁闷的是发现情况也是一样的，都是高精度整数与普通整数的乘除。

太TM应试了。

不过想到了自己也是因为应试的原因才做的这个作业，我缓缓地放下了想要摔书的手。

只能自己想办法解决了。看了好几个大神的代码，虽然没太看懂，但是大概掌握了一点儿解决乘除法的思想，试着自己写了代码。说白了原理其实挺简单，乘法就是一个数不断累加，除法就是一个数能被除数减掉多少次那个次数就是商。当然，具体解决的算法不是这样，这个需要自己动手演算一下才能明白。

上代码：

编程题 ＃1

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

下面程序的输出是：

3+4i

5+6i

请补足Complex类的成员函数。不能加成员变量。

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
class Complex {
private:    
    double r,i;
public:    
    void Print() {
        cout << r << "+" << i << "i" << endl;
    }
// 在此处补充你的代码
};
int main() {
    Complex a;
    a = "3+4i"; a.Print();
    a = "5+6i"; a.Print();
    return 0;
}

输入

无

输出

3+4i

5+6i

样例输入

无

样例输出

3+4i
5+6i

参考代码：

/*
 * week4 part1.cpp
 *
 *  Created on: 2018年3月5日
 *      Author: Arno
 */
 
 
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
 
class Complex {
private:
    double r,i;
public:
    void Print() {
        cout << r << "+" << i << "i" << endl;
    }
    //此处为补充代码
    Complex & operator=(const char* str){
    	string s=str;
    	int pos=s.find("+",0);//查找加号的位置
    	string sTmp=s.substr(0,pos);//分离出代表实部的字符串
    	r=atof(sTmp.c_str());//atof库函数能将const char*指针指向的内容转换成float
    	sTmp=s.substr(pos+1,s.length()-pos-2);//分离出代表虚部的字符串
    	i=atof(sTmp.c_str());
    	return *this;
    }
};
int main() {
    Complex a;
    a = "3+4i"; a.Print();
    a = "5+6i"; a.Print();
    return 0;
}

编程题 ＃2

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

下面的MyInt类只有一个成员变量。MyInt类内部的部分代码被隐藏了。假设下面的程序能编译通过，且输出结果是:

4,1

请写出被隐藏的部分。（您写的内容必须是能全部放进 MyInt类内部的，MyInt的成员函数里不允许使用静态变量）。

#include <iostream>
using namespace std;
class MyInt {
    int nVal;
    public:
        MyInt(int n) { nVal = n; }
        int ReturnVal() { return nVal; }
// 在此处补充你的代码
};
int main () {
    MyInt objInt(10);
    objInt-2-1-3;
    cout << objInt.ReturnVal();
    cout <<",";
    objInt-2-1;
    cout << objInt.ReturnVal();
    return 0;
}

输入

无

输出

4,1

样例输入

无

样例输出

4,1

参考代码：

/*
 * week4 part2.cpp
 *
 *  Created on: 2018年3月5日
 *      Author: Arno
 */
 
#include <iostream>
using namespace std;
 
class MyInt  {
    int nVal;
    public:
        MyInt(int n) { nVal = n; }
        int ReturnVal() { return nVal; }
        //在此处补充你的代码
        MyInt & operator-(const int n){
        	nVal-=n;
        	return *this;
        }
};
int main ()  {
    MyInt objInt(10);
    objInt-2-1-3;
    cout << objInt.ReturnVal();
    cout <<",";
    objInt-2-1;
    cout << objInt.ReturnVal();
    return 0;
}

编程题 ＃3

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

写一个二维数组类 Array2,使得下面程序的输出结果是：

0,1,2,3,

4,5,6,7,

8,9,10,11,

next

0,1,2,3,

4,5,6,7,

8,9,10,11,

程序：

#include <iostream>
#include <cstring>
using namespace std;
// 在此处补充你的代码
int main() {
    Array2 a(3,4);
    int i,j;
    for( i = 0;i < 3; ++i )
        for( j = 0; j < 4; j ++ )
            a[i][j] = i * 4 + j;
    for( i = 0;i < 3; ++i ) {
        for( j = 0; j < 4; j ++ ) {
            cout << a(i,j) << ",";
        }
        cout << endl;
    }
    cout << "next" << endl;
    Array2 b; b = a;
    for( i = 0;i < 3; ++i ) {
        for( j = 0; j < 4; j ++ ) {
            cout << b[i][j] << ",";
        }
        cout << endl;
    }
    return 0;
}

输入

无

输出

0,1,2,3,

4,5,6,7,

8,9,10,11,

next

0,1,2,3,

4,5,6,7,

8,9,10,11,

样例输入

无

样例输出

0,1,2,3,
4,5,6,7,
8,9,10,11,
next
0,1,2,3,
4,5,6,7,
8,9,10,11,

参考代码：

/*
 * week4 part3.cpp
 *
 *  Created on: 2018年3月5日
 *      Author: Arno
 */
 
#include <iostream>
#include <cstring>
using namespace std;
//在此处补充你的代码
class Array2	{
	int row,column;
	int **ptr;//因为是二维数组，所以定义一个指向指针的指针
public:
	Array2(int i=0,int j=0);//构造函数
	Array2(Array2 & a);//复制构造函数
	~Array2();//析构函数
	Array2 & operator=(const Array2 & a);//用于数组对象间的赋值
	int *& operator[](int i){
		return ptr[i];
	}//相当于只重载了第一个[]，返回了（行）指针
	int & operator()(int i,int j){
		return ptr[i][j];//（行）指针再加上[]，就可以直接定位数据了
	}//用于支持根据下标访问数组
};
Array2::Array2(int i,int j):row(i),column(j){
	if(i==0||j==0)
		ptr=NULL;//若行列中有一个为0，则置指针的指针为空
	else{
		ptr=new int*[i];//分配指向每行的指针，注意左右两边都是int**
		for(int k=0;k<i;++k){
			ptr[k]=new int[j];//给每个行指针分配对应的列空间
		}
	}
}
Array2::Array2(Array2 & a){
	row=a.row;
	column=a.column;//行和列的参数先拷贝一下
	if(!a.ptr){
		ptr=NULL;
		return;
	}
	ptr=new int*[a.row];//深拷贝
	for(int k=0;k<a.row;++k){
		ptr[k]=new int[a.column];
		memcpy(ptr[k],a.ptr[k],sizeof(int)*a.column);
	}
}
Array2::~Array2(){
	if(ptr){
		for(int k=0;k<row;++k){
			delete [] ptr[k];
		}
		delete [] ptr;//先释放列空间再释放行指针数组
	}
}
Array2 & Array2::operator=(const Array2 & a){
	if(ptr==a.ptr)//防止a=a这样的赋值导致错误
		return *this;
	row=a.row;
	column=a.column;//先拷贝行列数据
	if(ptr){
		for(int k=0;k<row;++k){
			delete [] ptr[k];
		}
		delete [] ptr;
	}//若ptr存在则先将其占用的所有内存空间释放掉
	if(a.ptr==NULL){
		ptr=NULL;
		return *this;//若a指针为空，则现在对象的指针也置为NULL
	}
	ptr=new int*[a.row];//分配行指针
	for(int k=0;k<a.row;++k){
		ptr[k]=new int[a.column];
		memcpy(ptr[k],a.ptr[k],sizeof(int)*a.column);//给每一行分配空间并拷贝
	}
	return *this;
}
 
int main() {
    Array2 a(3,4);
    int i,j;
    for(  i = 0;i < 3; ++i )
        for(  j = 0; j < 4; j ++ )
            a[i][j] = i * 4 + j;
    for(  i = 0;i < 3; ++i ) {
        for(  j = 0; j < 4; j ++ ) {
            cout << a(i,j) << ",";
        }
        cout << endl;
    }
    cout << "next" << endl;
    Array2 b;
    b = a;
    for(  i = 0;i < 3; ++i ) {
        for(  j = 0; j < 4; j ++ ) {
            cout << b[i][j] << ",";
        }
        cout << endl;
    }
    return 0;
}

编程题＃4：大整数的加减乘除

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

给出两个正整数以及四则运算操作符（+ - * /），求运算结果。

输入

第一行：正整数a，长度不超过100

第二行：四则运算符o，o是“+”，“-”，“*”，“/”中的某一个

第三行：正整数b，长度不超过100

保证输入不含多余的空格或其它字符

输出

一行：表达式“a o b”的值。

补充说明：

1. 减法结果有可能为负数

2. 除法结果向下取整

3. 输出符合日常书写习惯，不能有多余的0、空格或其它字符

样例输入

9876543210
+
9876543210

样例输出

19753086420

参考代码：

/*
 * BigInt Calculation.cpp
 *
 *  Created on: 2018年3月14日
 *      Author: Arno
 */
 
#include<cstdio>
#include<cstring>
using namespace std;
 
class BigInt{
	int d[1000];//用作存储大整数的每一位数
	bool flag;//用作正负号
	int len;//大整数的数位长度
public:
	BigInt(){
		memset(d,0,sizeof(d));
		flag=true;
		len=0;
	}//无参数时的构造函数
	BigInt(const char str[]);//有字符串参数的构造函数
	bool operator<(const BigInt & operand2);
	bool operator>(const BigInt & operand2);
	bool operator==(const BigInt & operand2);
	BigInt & operator=(const BigInt & operand);
	BigInt operator+(const BigInt & operand2);
	BigInt operator-(const BigInt & operand2);
	BigInt operator*(const BigInt & multiplier);
	BigInt operator/(const BigInt & divisor);
	void printBigInt();//打印大整数
};
 
BigInt::BigInt(const char str[]){
	flag=true;//由于输入的数据为正数，所以置为真
	len=strlen(str);//字符串长度即为数位长度
	for(int i=0;i<len;++i){
		d[i]=str[len-1-i]-'0';//逆着赋值，这样整数的低位存储在数组的低位
	}
}
 
bool BigInt::operator <(const BigInt & operand2){
	if(len<operand2.len)
		return true;//数的长度比后者小，则数小
	else if(len==operand2.len){
		for(int i=len-1;i>=0;--i){
			if(d[i]<operand2.d[i])
				return true;//从高位往低位比较，只要有一位小，则数小
			else if(d[i]>operand2.d[i])
				return false;
		}
		return false;//两数相等
	}else
		return false;//前面的数大
}
 
bool BigInt::operator >(const BigInt & operand2){
	if(len>operand2.len)
		return true;//数的长度比后者大，则数大
	else if(len==operand2.len){
		for(int i=len-1;i>=0;--i){
			if(d[i]>operand2.d[i])
				return true;//从高位往低位比较，只要有一位大，则数大
			else if(d[i]<operand2.d[i])
				return false;
		}
		return false;//两数相等
	}else
		return false;//前面的数小
}
 
bool BigInt::operator ==(const BigInt & operand2){
	if(len==operand2.len){
		for(int i=len-1;i>=0;--i){
			if(d[i]!=operand2.d[i])
				return false;//从高位往低位比较，只要有一位不等，则数不等
		}
		return true;//两数相等
	}else
		return false;
}
 
BigInt & BigInt::operator =(const BigInt & operand){
	if(operand.d==this->d)
		return *this;//防止a=a这样的情况
	this->len=operand.len;
	this->flag=operand.flag;
	for(int i=0;i<operand.len;++i){
		this->d[i]=operand.d[i];
	}
	return *this;
}
 
BigInt BigInt::operator +(const BigInt & operand2){
	BigInt result;
	int carry=0;//carry是进位
	for(int i=0;i<len||i<operand2.len;++i){//以较长的为界限
		int temp=carry+d[i]+operand2.d[i];//两个对应位与进位相加
		carry=temp/10;//去掉最后一位之后就是新的进位
		result.d[result.len++]=temp%10;//留下最后一位作为该位的结果
	}
	if(carry!=0)//若最后进位不为0，则直接赋给结果的最高位
		result.d[result.len++]=carry;
	return result;
}
 
BigInt BigInt::operator -(const BigInt & operand2){
	BigInt result;
	BigInt minuend;//被减数
	BigInt subtrahend;//减数
	if(*this<operand2){
		result.flag=false;
		minuend=operand2;
		subtrahend=*this;//如果被减数小于减数，则将结果置负并将两数对换
	}else{
		minuend=*this;
		subtrahend=operand2;
	}
	for(int i=0;i<minuend.len||i<subtrahend.len;++i){//以较长的为界限
		if(minuend.d[i]<subtrahend.d[i]){//如果不够减
			minuend.d[i+1]--;//向高位借位
			minuend.d[i]+=10;//当前位加10
		}
		result.d[result.len++]=minuend.d[i]-subtrahend.d[i];//减法结果为当前位结果
	}
	while(result.len-1>=1&&result.d[result.len-1]==0){
		result.len--;//去除高位的0，同时至少保留一位最低位
	}
	return result;
}
 
BigInt BigInt::operator *(const BigInt & multiplier){
	BigInt result;
	result.len=this->len+multiplier.len;//两数相乘乘积位数最大为两数位数之和
	for(int i=0;i<this->len;++i){
		for(int j=0;j<multiplier.len;++j){
			result.d[i+j]+=this->d[i]*multiplier.d[j];//关键算法，需要自己手动模拟一下
			result.d[i+j+1]+=result.d[i+j]/10;
			result.d[i+j]=result.d[i+j]%10;//简单来说就是a[i]*b[j]保存在c[i+j]上
		}
	}
	if(result.d[result.len-1]==0)
		result.len--;//两数相乘乘积位数最小为两数位数之和减掉1
	return result;
}
 
BigInt BigInt::operator /(const BigInt & divisor){
	BigInt quotient;//商
	BigInt remainder;//余数
	if(divisor.len==1&&divisor.d[0]==0){
		printf("除数不能为0！");
		return quotient;
	}
	if(*this<divisor){
		quotient.len=1;
		quotient.d[0]=0;//若除数比被除数大，则商为零
	}else{
		quotient.len=this->len-divisor.len +1;//商的位数最多为被除数位数减除数位数加1
		remainder.len=divisor.len-1;//给余数赋初值，取被除数的前“除数位数-1”位的数作为余数
		for(int i=remainder.len-1;i>=0;--i){
			remainder.d[i]=this->d[i+quotient.len];
		}//每一轮用余数去除除数，在该位上上一个商的值
		for(int i=quotient.len-1;i>=0;--i){//从商的高位开始
			remainder.len++;
			for(int j=remainder.len-1;j>0;--j){
				remainder.d[j]=remainder.d[j-1];
			}
			remainder.d[0]=this->d[i];//被除数当前的这位数和上一次遗留的余数组合
			if(remainder<divisor)
				quotient.d[i]=0;//若不够除，该位为0
			else{//够除
				int cnt=0;
				while(remainder>divisor||remainder==divisor){
					remainder=remainder-divisor;
					cnt++;
				}//够减几次，该位上商就是几，跳出循环时获得新的余数
				quotient.d[i]=cnt;
			}
		}
		if(quotient.d[quotient.len-1]==0)
			quotient.len--;//商的最高位若为0，则去掉
	}
	return quotient;
}
 
void BigInt::printBigInt(){
	if(flag==false)
		printf("-");
	for(int i=len-1;i>=0;--i){
		printf("%d",d[i]);
	}
}
 
int main(){
	char str1[1000];
	char op;
	char str2[1000];
	gets(str1);
	op=getchar();
	getchar();//吞掉回车符
	gets(str2);
	BigInt a(str1);
	BigInt b(str2);
	BigInt c;
	switch(op){
		case '+':c=a+b;break;
		case '-':c=a-b;break;
		case '*':c=a*b;break;
		case '/':c=a/b;break;
		default:break;
	}
	c.printBigInt();
	return 0;
}

大整数我没用iostream，因为晴神宝典说cin和cout消耗的时间比scanf和printf多得多，为了效率我决定用C的输入输出试试手。在这里不得不吐槽一下，scanf果然不是那么好用的，主函数部分不知道为什么输入老是出问题，debug数次未果之后我给换成了gets和getchar才正常。还有一个收获就是，不断的WA之后浏览课程讨论区发现有人说POJ上可以看未通过的测试用例，更好地知道是哪里出了问题，于是去注册了一个，果然。这样以后debug的时候就会方便很多了。