大整数的排序算法-C++大整数运算 利用已有的大整数怎么实现三个运算

问题描述

C++大整数运算 利用已有的大整数怎么实现三个运算
我有以下的C++代码，请问我该如何实现以下三个运算？如果我在定义大整数的类中定义三个友元函数，能否直接使用我定义的“运算符重载”？
a) 求出100以内的数的阶乘；
b) 一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。当N=4时，1634满足条件，因为1^4 + 6^4 + 3^4 + 4^4 = 1634（其中“^”表示乘方），求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。
c) 实现N个大整数的排序算法；
代码如下：

#include

#include

#include

#include

using namespace std;

#define MAXN 9999

#define MAXSIZE 10

#define DLEN 4

class BigNum

{

private:

int a[500]; //可以控制大数的位数

int len; //大数长度

public:

BigNum(){ len = 1;memset(a0sizeof(a)); } //构造函数

BigNum(const int); //将一个int类型的变量转化为大数

BigNum(const char*); //将一个字符串类型的变量转化为大数

BigNum(const BigNum &); //拷贝构造函数

BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算

friend istream& operator>>(istream&  BigNum&);   //重载输入运算符   friend ostream& operator<<(ostream&  BigNum&);   //重载输出运算符   BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算    BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算    BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算    BigNum operator/(const int   &) const;    //重载除法运算符，大数对一个整数进行相除运算   BigNum operator^(const int  &) const;    //大数的n次方运算   int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算       bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较   bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较   void print();       //输出大数

};

BigNum::BigNum(const int b) //将一个int类型的变量转化为大数

{

int cd = b;

len = 0;

memset(a0sizeof(a));

while(d > MAXN)

{

c = d - (d / (MAXN + 1)) * (MAXN + 1);

d = d / (MAXN + 1);

a[len++] = c;

}

a[len++] = d;

}

BigNum::BigNum(const char*s) //将一个字符串类型的变量转化为大数

{

int tkindexli;

memset(a0sizeof(a));

l=strlen(s);

len=l/DLEN;

if(l%DLEN)

len++;

index=0;

for(i=l-1;i>=0;i-=DLEN)

{

t=0;

k=i-DLEN+1;

if(k k=0;
for(int j=k;j t=t*10+s[j]-'0';
a[index++]=t;
}
}
BigNum::BigNum(const BigNum & T) : len(T.len) //拷贝构造函数
{
int i;
memset(a0sizeof(a));
for(i = 0 ; i a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n) //重载赋值运算符，大数之间进行赋值运算
{
int i;
len = n.len;
memset(a0sizeof(a));
for(i = 0 ; i a[i] = n.a[i];
return *this;
}
istream& operator>>(istream & in BigNum & b) //重载输入运算符

{

char ch[MAXSIZE*4];

int i = -1;

in>>ch;

int l=strlen(ch);

int count=0sum=0;

for(i=l-1;i>=0;)

{

sum = 0;

int t=1;

for(int j=0;j=0;j++i--t*=10)

{

sum+=(ch[i]-'0')*t;

}

b.a[count]=sum;

count++;

}

b.len =count++;

return in;

}

ostream& operator<<(ostream& out BigNum& b) //重载输出运算符

{

int i;

cout << b.a[b.len - 1];

for(i = b.len - 2 ; i >= 0 ; i--)

{

cout.width(DLEN);

cout.fill('0');

cout << b.a[i];

}

return out;

}

BigNum BigNum::operator+(const BigNum & T) const //两个大数之间的相加运算

{

BigNum t(*this);

int ibig; //位数

big = T.len > len ? T.len : len;

for(i = 0 ; i < big ; i++)

{

t.a[i] +=T.a[i];

if(t.a[i] > MAXN)

{

t.a[i + 1]++;

t.a[i] -=MAXN+1;

}

}

if(t.a[big] != 0)

t.len = big + 1;

else

t.len = big;

return t;

}

BigNum BigNum::operator-(const BigNum & T) const //两个大数之间的相减运算

{

int ijbig;

bool flag;

BigNum t1t2;

if(*this>T)

{

t1=*this;

t2=T;

flag=0;

}

else

{

t1=T;

t2=*this;

flag=1;

}

big=t1.len;

for(i = 0 ; i < big ; i++)

{

if(t1.a[i] < t2.a[i])

{

j = i + 1;

while(t1.a[j] == 0)

j++;

t1.a[j--]--;

while(j > i)

t1.a[j--] += MAXN;

t1.a[i] += MAXN + 1 - t2.a[i];

}

else

t1.a[i] -= t2.a[i];

}

t1.len = big;

while(t1.a[len - 1] == 0 && t1.len > 1)

{

t1.len--;

big--;

}

if(flag)

t1.a[big-1]=0-t1.a[big-1];

return t1;

}

BigNum BigNum::operator*(const BigNum & T) const //两个大数之间的相乘运算

{

BigNum ret;

int ijup;

int temptemp1;

for(i = 0 ; i < len ; i++)

{

up = 0;

for(j = 0 ; j < T.len ; j++)

{

temp = a[i] * T.a[j] + ret.a[i + j] + up;

if(temp > MAXN)

{

temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);

up = temp / (MAXN + 1);

ret.a[i + j] = temp1;

}

else

{

up = 0;

ret.a[i + j] = temp;

}

}

if(up != 0)

ret.a[i + j] = up;

}

ret.len = i + j;

while(ret.a[ret.len - 1] == 0 && ret.len > 1)

ret.len--;

return ret;

}

BigNum BigNum::operator/(const int & b) const //大数对一个整数进行相除运算

{

BigNum ret;

int idown = 0;

for(i = len - 1 ; i >= 0 ; i--)

{

ret.a[i] = (a[i] + down * (MAXN + 1)) / b;

down = a[i] + down * (MAXN + 1) - ret.a[i] * b;

}

ret.len = len;

while(ret.a[ret.len - 1] == 0 && ret.len > 1)

ret.len--;

return ret;

}

int BigNum::operator %(const int & b) const //大数对一个int类型的变量进行取模运算

{

int id=0;

for (i = len-1; i>=0; i--)

{

d = ((d * (MAXN+1))% b + a[i])% b;

}

return d;

}

BigNum BigNum::operator^(const int & n) const //大数的n次方运算

{

BigNum tret(1);

int i;

if(n exit(-1);
if(n==0)
return 1;
if(n==1)
return *this;
int m=n;
while(m>1)

{

t=*this;

for( i=1;i< {
t=t*t;
}
m-=i;
ret=ret*t;
if(m==1)
ret=ret*(*this);
}
return ret;
}
bool BigNum::operator>(const BigNum & T) const //大数和另一个大数的大小比较

{

int ln;

if(len > T.len)

return true;

else if(len == T.len)

{

ln = len - 1;

while(a[ln] == T.a[ln] && ln >= 0)

ln--;

if(ln >= 0 && a[ln] > T.a[ln])

return true;

else

return false;

}

else

return false;

}

bool BigNum::operator >(const int & t) const //大数和一个int类型的变量的大小比较

{

BigNum b(t);

return *this>b;

}

void BigNum::print() //输出大数

{

int i;

cout << a[len - 1];

for(i = len - 2 ; i >= 0 ; i--)

{

cout.width(DLEN);

cout.fill('0');

cout << a[i];

}

cout << endl;

}

时间： 2024-09-12 21:47:11

大整数的排序算法-C++大整数运算 利用已有的大整数怎么实现三个运算的相关文章

数据结构实践——大数据集上排序算法性能的体验

本文是针对[数据结构基础系列(9):排序]的实践项目. [项目 - 大数据集上排序算法性能的体验] 设计一个函数,产生一个至少5万条记录的数据集合.在同一数据集上,用直接插入排序.冒泡排序.快速排序.直接选择排序.堆排序.归并排序.基数排序等算法进行排序,记录所需要的时间,经过对比,得到对复杂度不同的各种算法在运行时间方面的感性认识. 提示1:这一项目需要整合多种排序算法,可以考虑先建设排序算法库,作为我们这门课算法库的收官之作: 提示2:本项目旨在获得对于复杂度不同算法的感性认识,由于数据分布

算法学习入门之使用C语言实现各大基本的排序算法_C 语言

首先来看一下排序算法的一些相关概念:1.稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后,仍能保持它们在排序之前的相对次序,我们就说这种排序方法是稳定的.反之,就是非稳定的. 比如:一组数排序前是a1,a2,a3,a4,a5,其中a2=a4,经过某种排序后为a1,a2,a4,a3,a5,则我们说这种排序是稳定的,因为a2排序前在a4的前面,排序后它还是在a4的前面.假如变成a1,a4,a2,a3,a5就不是稳定的了. 2.内排序和外排序 在排序过程中,所有需要排序的数都在内存,并

排序算法（Java）——那些年面试常见的排序算法

前言 排序就是将一组对象按照某种逻辑顺序重新排列的过程.比如信用卡账单中的交易是按照日期排序的--这种排序很可能使用了某种排序算法.在计算时代早期,大家普遍认为30%的计算周期都用在了排序上,今天这个比例可能降低了,大概是因为现在的排序算法更加高效.现在这个时代数据可以说是无处不在,而整理数据的第一步往往就是进行排序.所有的计算机系统都实现了各种排序算法以供系统和用户使用. 即使你只是使用标准库中的排序函数,学习排序算法仍然有很大的实际意义: - 排序算法往往是我们解决其他问题的第一步 - 排序

js的各种排序算法实现(总结)_javascript技巧

如下所示: // ---------- 一些排序算法 var Sort = {} Sort.prototype = { // 利用sort进行排序 systemSort:function(array){ return array.sort(function(a, b){ return a - b; }); }, // 冒泡排序 bubbleSort:function(array){ var i = 0, len = array.length, j, d; for(; i<len; i++){ f

c语言-C填空题：键盘上输入10个整数，程序按降序完成从大到小排序

问题描述 C填空题:键盘上输入10个整数,程序按降序完成从大到小排序 #include void sort(int *p,int *q) { int *max,*s; if(p>q)return; max=p; __ for(s=p+1;s<=q;s++)__ if()max=s; swap(); sort((),q); } void swap(int *x,int *y) { int temp; temp=*x; *x=*y; *y=temp; } void main() { int i,a

九大排序算法总结

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 常见的内部排序算法有:插入排序.希尔排序.选择排序.冒泡排序.归并排序.快速排序.堆排序.基数排序等. 算法一:插入排序 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 算法步骤 1)将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当

《程序设计解题策略》——第1章　利用树型数据关系的解题策略　1.1　利用划分树求解整数区间内第k大的值

第1章 利用树型数据关系的解题策略 树是一个具有层次结构的集合,一种限制前件数且没有回路的连通图.在现实生活和程序设计的竞赛试题中,许多问题的数据关系呈树型结构,因此有关树的概念.原理.操作方法和一些由树的数据结构支持的算法,一直受到编程者的重视,被广泛应用于解题过程.在本章里,我们将介绍利用树型数据关系解题的七种策略: 1) 利用划分树求解整数区间内第k大值. 2) 利用最小生成树及其扩展形式(最优比率生成树.最小k度生成树.次小生成树)计算有权连通无向图中边权和满足限制条件的最优生成树. 3

十大经典排序算法的JS版

前言 读者自行尝试可以想看源码戳这(https://github.com/damonare/Sorts),博主在github建了个库,读者可以Clone下来本地尝试.此博文配合源码体验更棒哦 这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,小平和小平头,玛丽和马里奥,Java和javascript-.当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了.可如今,javascript来了个咸鱼翻身,几乎

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 常见的内部排序算法有:插入排序.希尔排序.选择排序.冒泡排序.归并排序.快速排序.堆排序.基数排序等. 本文将依次介绍上述八大排序算法. 算法一:插入排序 插入排序示意图 插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入. 算法步骤: 1)将第一待排序序列第一