大数阶乘实习报告
- 格式：docx
- 大小：221.29 KB
- 文档页数：7
大数的阶乘【1】问题的描述：对于一个数的阶乘算法应该是有好多中算法，运用递归调用函数、指针等都可以实现，但是对于运算结果的存储是一个问题，对于一个数比较小，我们可以用数组或者字符串来存储该结果，但是如果对于一个大数的运算时，那么则不仅仅是一个数组可以解决的，为了储存的方便，可以运用单链表来解决相应的存储问题。
【2】求解思路：首先定义一个单链表，用来存储数的结果。
在计算的大数的阶乘时运用递归调用的方法来实现，在运算较大的数时，其中间变量也是存在该链表中，即在运算的同时完成存贮的过程，但是在存一个较大数的同时，考虑到位和进位的问题，在链表中定义了相应的函数来实现，即find和search和change函数。
【3】采用的数据结构：采用的数据结构为单链表。
【4】程序实现说明：class ChainNode //结点类的定义class Chain //链表类的定义boolIsEmpty() const {return first == 0;} //判断是否为空链表int Length() const; //计算链表的长度bool Find(int k, int& x); //取出第k个元素int Search(constint& x) const; //寻找数据为x的元素Chain& Change(int k, int x); //修改第k个元素的值Chain& Delete(int k, int& x); //删除第k个元素Chain& Insert(int k, constint& x); //在第k个元素后插入一个元素x void Output(); //输出//改为递归，才能先输出高位后输出低位void Chain::OutputOne(constChainNode* current)//先做乘法for(j = 0; j <j_end;j++){c.Find(j,k);k = i * k;c.Change(j,k);}//然后处理进位for(j = 0; j <j_end;j++){c.Find(j,k);if(k >= 1000){if (j <j_end -1)c.Find(j+1,l);else{c.Insert(j+1, 0); //增加高位l = 0;}l += k/1000;c.Change(j+1,l);k = k % 1000;c.Change(j,k);【5】程序清单：// cpp.cpp : 定义控制台应用程序的入口点。
//单链表的运用来实现大数的阶乘！！！！#include "stdafx.h"#include<iostream>#include <stdio.h>using namespace std;class ChainNode //结点类的定义{friend class Chain;private:int data; //数据元素域ChainNode* link; //链指针域};class Chain //链表类的定义{public:Chain(){first = 0;} //构造函数对头指针初始化为0~Chain();boolIsEmpty() const {return first == 0;} //判断是否为空链表int Length() const; //计算链表的长度bool Find(int k, int& x); //取出第k个元素int Search(constint& x) const; //寻找数据为x的元素Chain& Change(int k, int x); //修改第k个元素的值Chain& Delete(int k, int& x); //删除第k个元素Chain& Insert(int k, constint& x); //在第k个元素后插入一个元素x void Output(); //输出void OutputOne(constChainNode* current);private:ChainNode* first; //私有数据为头指针};Chain::~Chain() //链表的析构函数{ChainNode * next; //定义一个临时指针来在删除first指针时防止后续结点的丢失while(first){next = first->link;delete first;first = next;}}int Chain::Length() const{ChainNode* current = first;//这个由于是定义的常成员函数，因此在访问时不能通过该函数来改变私有数据first的值，故定义一个与first功能相同的current的指针intlen = 0;while(current){len++;current = current->link;}return len;}bool Chain::Find(intk,int& x){ChainNode* current = first;int index = 0;while(index < k && current ){current = current->link;index++;}if(current){x = current->data;return true;}return false;}int Chain::Search(constint& x) const{ChainNode* current = first;int index = 1;while(current && current->data != x){current = current->link;index++;}if(current)return index;return 0;}//改为递归，才能先输出高位后输出低位void Chain::OutputOne(constChainNode* current) {if (current){OutputOne(current->link);if (current->link)printf("%03d", current->data); //必须输出3位elseprintf("%d", current->data); //输出最高位时不能用%03d}}void Chain::Output(){OutputOne(this->first);cout<<endl;}Chain& Chain::Change(int k, int x){ChainNode* p = first;for(int index = 0; index < k && p; index++) p = p->link;if(p)p->data = x;return *this;}Chain& Chain::Delete(int k, int& x){ChainNode* p = first;if(k == 0)first = first->link;else{ChainNode* q = first;for(int index = 0; index < k-1 && q; index++) q = q->link;p = q->link;q->link = p->link;}x = p->data;delete p;return *this;}Chain& Chain::Insert(int k, constint& x){ChainNode* p = first;for(int index = 0; index < k-1 && p; index++) //for(int index = 0; index < k && p; index++)p = p->link;ChainNode* y=new ChainNode;y->data = x;if(k){y->link = p->link;p->link = y;}else{first = y;y->link = 0;}return *this;}int main(intargc, char* argv[]){Chain c;intn,i,j,k,l(0);c.Insert(0,1); //c.Insert(0,2);cout<<"请输入一个数：";cin>>n;for(i = 1; i<= n; i++){intj_end = c.Length();//先做乘法for(j = 0; j <j_end;j++){c.Find(j,k);k = i * k;c.Change(j,k);}//然后处理进位for(j = 0; j <j_end;j++){c.Find(j,k);if(k >= 1000){if (j <j_end -1)c.Find(j+1,l);else{c.Insert(j+1, 0); //增加高位l = 0;}l += k/1000;c.Change(j+1,l);k = k % 1000;c.Change(j,k);}}}cout<<c.Length()<<endl;cout<<endl<<n<<"的阶乘结果为：";c.Output();getchar();return 0;}【6】运行结果：。
