subject_32766.htm

vc

<p>
序号：32766 发表者：竹叶 发表日期：2003-03-14 16:51:49
<br>主题：任意数的阶乘
<br>内容：求一种算法：<BR>用整型数来完成求任意数的阶乘<BR>要求：<BR>1）程序中出现的所有数都必须只用整型表示<BR>2）输入：任意一个整数<BR>3）输出：该整数的阶乘<BR>
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：bird 回复日期：2003-03-14 17:16:36
<br>内容：一个解决这个问题的一个方法是：动态创建一个链表，使得链表中的每个元素代表计算结果中的一个数字，这样，理论上讲，计算结果的长度仅仅受到内存大小的制约!<BR><BR>//<BR><BR>#include "stdafx.h"<BR><BR>#include "iostream.h"<BR>#include "stdlib.h"<BR><BR><BR>//here is a dual link list<BR>class Node{<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR>private:<BR> int data;<BR> Node *next;<BR> Node *prev;<BR> Node *head;<BR> Node *rear;<BR>&nbsp;&nbsp;&nbsp;&nbsp;<BR><BR>public:<BR> Node(const int&amp; item)<BR> :data(item),prev(NULL),next(NULL),head(NULL),rear(NULL){};<BR><BR> //get next node<BR> Node* GetNextNode(){return next;};<BR> Node* GetPrevNode(){return prev;};<BR><BR> //insert after<BR> void InsertAfterMe(Node* p);<BR><BR> //Delete the appointed<BR> void DeleteMe(void);<BR><BR> int GetData(void){return data;};<BR> void SetData(int item){data = item;};<BR><BR> //reset<BR> Node* GoBacktoHead();<BR><BR> //go to the rear<BR> Node* GoForwardtoRear();<BR> //clear the whole<BR> void ClearAll(void);<BR><BR> //get the counts of the link<BR> int GetElementNum();<BR>};<BR><BR><BR>int Node::GetElementNum()<BR>{<BR> int count = 0;<BR> Node* p =GoBacktoHead();<BR> <BR> while(p-&gt;GetNextNode()!=NULL){ <BR>&nbsp;&nbsp;count++;<BR>&nbsp;&nbsp;p = p-&gt;GetNextNode();<BR> }<BR><BR> count++;<BR> return count;<BR>}<BR><BR>void Node::InsertAfterMe(Node* p)<BR>{<BR> //&nbsp;&nbsp;&nbsp;&nbsp;Node* p;<BR> if(prev == NULL) { head = this;}<BR> p-&gt;next = next;<BR> p-&gt;prev = this;<BR> next = p;<BR> if(p-&gt;next == NULL){rear = p;}<BR>};<BR><BR><BR>void Node::DeleteMe(void)<BR>{<BR> if(prev == NULL) { // if this node is the first one<BR>&nbsp;&nbsp;next-&gt;prev = NULL;<BR>&nbsp;&nbsp;head = next;&nbsp;&nbsp;// then the next one becomes the first one<BR>&nbsp;&nbsp;delete this;&nbsp;&nbsp;//delete this node<BR>&nbsp;&nbsp;return;<BR> }<BR><BR> if(next == NULL){&nbsp;&nbsp;//if this node is the last one<BR>&nbsp;&nbsp;prev-&gt;next = NULL;<BR>&nbsp;&nbsp;rear = prev; // then the previous one becomes the last one<BR>&nbsp;&nbsp;return;<BR> }<BR><BR> prev-&gt;next = next;<BR> delete this;<BR>};<BR><BR>Node* Node::GoBacktoHead()<BR>{<BR> if(head == this){ //this is the first node<BR>&nbsp;&nbsp;return this;<BR> }<BR><BR> Node *p = this;<BR> while(p-&gt;prev != NULL){<BR>&nbsp;&nbsp;p = p-&gt;prev;<BR> }<BR><BR> return p;<BR>}<BR><BR>Node* Node::GoForwardtoRear()<BR>{<BR> if(rear == this){<BR>&nbsp;&nbsp;return this;<BR> }<BR><BR> Node *p = this;<BR> while(p-&gt;next != NULL){<BR>&nbsp;&nbsp;p = p-&gt;next;<BR> }<BR><BR> return p;<BR>}<BR><BR>void Node::ClearAll(void)<BR>{<BR> Node* p = GoBacktoHead();<BR> Node* p2;<BR> while(p-&gt;GetNextNode() != NULL){<BR>&nbsp;&nbsp;p2 = p;<BR>&nbsp;&nbsp;p = p-&gt;GetNextNode();<BR>&nbsp;&nbsp;delete p2;<BR> }<BR><BR> delete p;<BR>};<BR><BR>int main(int argc, char* argv[])<BR>{<BR> int remain;<BR> int carry;<BR> int result;<BR> int N;<BR> Node* p = new Node(1);<BR><BR> cout&lt;&lt;"Pls input the number:";<BR> cin&gt;&gt;N;<BR> for(int n=1;n&lt;=N;n++)<BR> {<BR>&nbsp;&nbsp;remain = carry = 0;<BR>&nbsp;&nbsp;p = p-&gt;GoBacktoHead();<BR><BR>&nbsp;&nbsp;//while not the end of the list,process the element one by one<BR>&nbsp;&nbsp;while(p-&gt;GetNextNode() != NULL){<BR>&nbsp;&nbsp; result = p-&gt;GetData()*n+carry;<BR>&nbsp;&nbsp; if(result&gt;=10){<BR>&nbsp;&nbsp;&nbsp;&nbsp;remain = result%10;<BR>&nbsp;&nbsp;&nbsp;&nbsp;carry = result/10;<BR>&nbsp;&nbsp;&nbsp;&nbsp;p-&gt;SetData(remain);<BR>&nbsp;&nbsp; }<BR>&nbsp;&nbsp; else{p-&gt;SetData(result);}<BR><BR>&nbsp;&nbsp;p = p-&gt;GetNextNode();<BR>&nbsp;&nbsp;carry = result/10;<BR>&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;result = p-&gt;GetData()*n+carry;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<BR>&nbsp;&nbsp;//if carry occurs,process the carry and <BR>&nbsp;&nbsp;//store into the newly allocated space.<BR><BR>&nbsp;&nbsp;while(result &gt;= 10){<BR>&nbsp;&nbsp; Node * newNode = new Node(0);<BR>&nbsp;&nbsp; p-&gt;SetData(result%10);//remainder<BR>&nbsp;&nbsp; result = result/10;<BR>&nbsp;&nbsp; p-&gt;InsertAfterMe(newNode);<BR>&nbsp;&nbsp; p = p-&gt;GetNextNode();<BR>&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;p-&gt;SetData(result);<BR><BR> }//end of if<BR><BR> p = p-&gt;GoForwardtoRear();<BR><BR> while(p-&gt;GetPrevNode()!=NULL){<BR>&nbsp;&nbsp;cout&lt;&lt;p-&gt;GetData();<BR>&nbsp;&nbsp;p=p-&gt;GetPrevNode();<BR> }<BR><BR> cout&lt;&lt;p-&gt;GetData()&lt;&lt;endl;<BR> int num = p-&gt;GetElementNum();<BR> if(num &gt;=5){<BR>&nbsp;&nbsp;p = p-&gt;GoForwardtoRear();<BR><BR>&nbsp;&nbsp;cout&lt;&lt;endl&lt;&lt;"Or"&lt;&lt;endl&lt;&lt;endl;<BR><BR>&nbsp;&nbsp;cout&lt;&lt;p-&gt;GetData()&lt;&lt;".";<BR>&nbsp;&nbsp;p = p-&gt;GetPrevNode();<BR><BR>&nbsp;&nbsp;for(int i=1;i&lt;5;i++){<BR>&nbsp;&nbsp; cout&lt;&lt;p-&gt;GetData();<BR>&nbsp;&nbsp; p = p-&gt;GetPrevNode();<BR>&nbsp;&nbsp;}<BR><BR>&nbsp;&nbsp;cout&lt;&lt;"E"&lt;&lt;num-1&lt;&lt;endl;<BR> }<BR><BR> //clear the memory<BR> p-&gt;ClearAll();<BR><BR> return 0;<BR>}<BR>2003-3-14 17:18:20