1.2 编程实现大数加法，乘法，和指数操作
乘法采用了快速乘法的算法
#include<iostream>
#include<string>
#include<iterator>
#define Abs(x) ((x)>0?(x):-(x))
#define Min(x,y) ((x)>(y)?(y):(x))
using namespace std;
//以下大数运算都不涉及小数，大数指数操作的底数和指数都是正整数。
string pluss(string x, string y); //大数加法
string subtra(string x, string y); //大数减法
string inverse(string str); //把数字反转，比如123变成321，这是因为数组存储的第一位是数字最高位的原因
string multiply(string x, string y);//大数乘法
int transferr(string& str);
string transferr(int num);
string Pow(string x, int n); //大数指数
//const double eps = 1e-10;
//const double e = 2.718281828459;
int main() {
string x = "", y = "";
int yy = 0;
cout << "数字a:";
cin >> x;
cout << "数字b:";
cin >> yy;
cout << "a^b结果是:"<<Pow(x,yy) << endl;
}
string inverse(string str){
string ret = "";
string::reverse_iterator it=str.rbegin();
for (; it != str.rend(); ++it) {
ret += *it;
}
return ret;
}
string multiply(string x,string y) {
int len1 = x.size();
int len2 = y.size();
int len = Min(len1,len2);
string ret = "0";
if (len1 <= 1 || len2 <= 1) { //临界条件
if (len1 <= 1) {
int num = x[0] - '0';
while (num--) {
ret=pluss(ret, y);
}
}
else {
int num = y[0] - '0';
while (num--) {
ret = pluss(ret, x);
}
}
return ret;
}
string a = x.substr(0, len1 - len / 2);
string b = x.substr(len1 - len / 2, len / 2);
//a和b把x分成了两个部分（比如12345可以分成12和345）
string c = y.substr(0, len2 - len / 2);
string d = y.substr(len2 - len / 2, len / 2);
//c和d把y分成了两个部分（比如12345可以分成12和345）
string num1 = pluss(a, b);
string num2 = pluss(c, d);
string p1 = multiply(a, c);
string p2 = multiply(b, d);
string p3 = multiply(num1, num2);
string zeros1 = "", zeros2 = "";
for (int i = 0; i < len/2*2; ++i) {
zeros1 += '0';
}
for (int i = 0; i < len / 2; ++i) {
zeros2 += '0';
}
string num3 = pluss(p1, p2);
string num4 = pluss(p1.append(zeros1),
subtra(p3, num3).append(zeros2));
return pluss(num4, p2);
}
int transferr(string& str) {
int len = str.size();
int ret=0;
for (int i = 0; i < len; ++i) {
ret += (str[i] - '0') * (int)((1e-10)+pow(10, len - 1 - i));
}
return ret;
}
string pluss(string x, string y) { //传进来的参数逆序，返回值也是逆序
x = inverse(x);
y = inverse(y);
int carry = 0;
string ret = "";
int len1 = x.size();
int len2 = y.size();
if (len1 < len2){
for (int i = len1; i < len2; ++i){
x += '0';
}
}
else{
for (int i = len2; i < len1; ++i) {
y += '0';
}
}
int len = x.size();
for (int i = 0; i < len; ++i) {
ret+=(( (x[i]-'0') + (y[i]-'0') +carry ) %10 +'0');
carry =( (x[i] - '0') + (y[i] - '0') + carry ) / 10;
}
if (carry != 0) {
ret += '1';
}
return inverse(ret);
}
string transferr(int num) //返回值是逆序
{
string ret = "";
while (num != 0){
ret += (num%10 + '0');
num /= 10;
}
return inverse(ret);
}
string subtra(string x, string y) {
x = inverse(x);
y = inverse(y);
int carry = 0;
string ret = "";
int len1 = x.size();
int len2 = y.size();
if (len1 < len2) {
for (int i = len1; i < len2; ++i) {
x += '0';
}
}
else {
for (int i = len2; i < len1; ++i) {
y += '0';
}
}
int len = x.size();
string num1, num2;
int flag = 0;
for (int i = len - 1; i >= 0; --i) {
if (x[i] != y[i]) {
if (x[i] < y[i])
flag = 1;
break;
}
}
if (flag == 1)
return "-"+subtra(y, x);
for (int i = 0; i < len; ++i) {
int a= (((x[i] - '0') - (y[i] - '0') + carry) % 10);
if (a < 0) {
carry = -1;
a = 10 + a;
ret += (a + '0');
}
else {
carry = 0;
ret += (a + '0');
}
}
return inverse(ret);
}
string Pow(string x, int n) {
string res = "1";
while (n--) {
res=multiply(res, x);
}
return res;
}
1.6 稀疏矩阵（含0元素很多的矩阵mat[100][100]）
思路是先创建一个结构体doub，这个结构体用来存储矩阵中一个有效的数字和数字所在的位置（如果把0看成无效的），这个结构体是最基本的元素(相当于一个mat[0][0])
再创建一个结构体onerow，这个结构体用来存储有效行的下标（因为有很多行全部是0），和有效行中有效数字的个数（相当于一个mat[0]）
最后创建一个结构体sparsemat,这个结构体用来存储矩阵总行数，总列数，还有有效行的个数（相当于mat）
（这里实现复杂化了，我是想要方便更改稀疏矩阵内部元素，如果不需要更改的话，最开始mat[0][0]可以用三元组表示，即横坐标，纵坐标，元素值，然后sparsemat包含一个三元组的数组就行）
#include<iostream>
#include<iomanip>
#include"OutOfBounds.h"
using namespace std;
const int Maxsize = 100;
struct doub
{
int pos; //数据所在位置
double a; //数据
};
struct onerow {
int len=0;
int index; //行的编号
int cols; //总列数
doub data[Maxsize];
double& operator[](int y) {
if (y<0 || y>=cols) {
throw OutOfBounds(y); //异常处理，在另外一个类里面有定义
}
double ret = 0;
for (int i = 0; i < len; ++i) {
if (data[i].pos == y)
return data[i].a;
}
return ret;
}
};
//稀疏矩阵
struct sparsemat{
int rows, cols; //总行数，总列数
int count=0; //有效数据的行数
onerow data[Maxsize];
onerow& operator[](int x) {
if (x < 0 || x >= rows)
throw OutOfBounds(x);
onerow ret;
ret.cols = cols;
int j = 0;
for (int i = 0; i < count; ++i) {
if (data[i].index == x) {
return data[i];
}
}
return ret;
}
};
void printmat(sparsemat& mat);
int main()
{
sparsemat mat;
mat.cols = mat.rows = 10;
mat.count = 3;
mat.data[0].cols = 10;
mat.data[0].index = 2;
mat.data[0].len = 2;
mat.data[0].data[0].pos = 3;
mat.data[0].data[0].a = 4.2;
mat.data[0].data[1].pos = 6;
mat.data[0].data[1].a = 6;
mat.data[1].cols = 10;
mat.data[1].index = 4;
mat.data[1].len = 2;
mat.data[1].data[0].pos = 3;
mat.data[1].data[0].a = 57;
mat.data[1].data[1].pos = 7;
mat.data[1].data[1].a = 55.4;
mat.data[2].cols = 10;
mat.data[2].index = 7;
mat.data[2].len = 1;
mat.data[2].data[0].pos = 4;
mat.data[2].data[0].a = 10.2;
printmat(mat);
mat[2][3]=2;
cout << "-----------------更改后--------------------" << endl;
printmat(mat);
}
void printmat(sparsemat& mat)
{
int q = 0;
for (int i = 0; i < mat.rows; ++i) {
int p = 0;
if (i == mat.data[q].index) {
for (int j = 0; j < mat.cols; ++j) {
if (j == mat.data[q].data[p].pos) {
cout << setw(5) << mat.data[q].data[p].a;
++p;
}
else
cout << setw(5) << 0;
}
cout << endl;
++q;
}
else {
for (int k = 0; k < mat.cols; ++k) {
cout << setw(5) << 0;
}
cout << endl;
}
}
}
3.14
3.1
访问布尔型的变量（1个字节）比访问整型变量，字符型变量的时间要长，因为字节是寻址的最小单位，单独访问字节里的一个位需要更长的时间（大概...）
网友评论