Posted By

Veeggon on 02/23/12


Tagged


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

Veeggon


Factorials of (Almost) Any Size


 / Published in: C++
 

Limited by memory.

  1. //
  2. //
  3. // Nnn.cpp : Defines the entry point for the console application.
  4. // author : Hai Yi
  5. // review : V. Cortes / Feb,23,2012
  6. // date : Sept,11,2000
  7. //
  8. //
  9.  
  10. #include <iostream>
  11. #include <stdlib.h>
  12. using namespace std;
  13.  
  14. //here is a dual link list
  15. class Node{
  16.  
  17. private:
  18. int data;
  19. Node *next;
  20. Node *prev;
  21. Node *head;
  22. Node *rear;
  23.  
  24.  
  25. public:
  26. Node(const int& item)
  27. :data(item),prev(NULL),next(NULL),head(NULL),rear(NULL){}
  28.  
  29. //get next node
  30. Node* GetNextNode(){return next;}
  31. Node* GetPrevNode(){return prev;}
  32.  
  33. //insert after
  34. void InsertAfterMe(Node* p);
  35.  
  36. //Delete the appointed
  37. void DeleteMe();
  38.  
  39. int GetData(){return data;}
  40. void SetData(int item){data = item;}
  41.  
  42. //reset
  43. Node* GoBacktoHead();
  44.  
  45. //go to the rear
  46. Node* GoForwardtoRear();
  47. //clear the whole
  48. void ClearAll();
  49.  
  50. //get the counts of the link
  51. int GetElementNum();
  52. };
  53.  
  54.  
  55. int Node::GetElementNum()
  56. {
  57. int count = 0;
  58. Node* p =GoBacktoHead();
  59.  
  60. while(p->GetNextNode()!=NULL){
  61. count++;
  62. p = p->GetNextNode();
  63. }
  64.  
  65. count++;
  66. return count;
  67. }
  68.  
  69. void Node::InsertAfterMe(Node* p)
  70. {
  71. // Node* p;
  72. if(prev == NULL) { head = this;}
  73. p->next = next;
  74. p->prev = this;
  75.  
  76.  
  77. next = p;
  78. if(p->next == NULL) rear = p;
  79. else p->next->prev = p;
  80. }
  81.  
  82.  
  83. void Node::DeleteMe()
  84. {
  85. if(prev == NULL) { // if this node is the first one
  86. next->prev = NULL;
  87. head = next; // then the next one becomes the first one
  88. delete this; //delete this node
  89. return;
  90. }
  91.  
  92. if(next == NULL){ //if this node is the last one
  93. prev->next = NULL;
  94. rear = prev; // then the previous one becomes the last one
  95. delete this;
  96. return;
  97. }
  98.  
  99. prev->next = next;
  100. next->prev = prev;
  101. delete this;
  102. }
  103.  
  104. Node* Node::GoBacktoHead()
  105. {
  106. if(head == this){ //this is the first node
  107. return this;
  108. }
  109.  
  110. Node *p = this;
  111. while(p->prev != NULL){
  112. p = p->prev;
  113. }
  114.  
  115. return p;
  116. }
  117.  
  118. Node* Node::GoForwardtoRear()
  119. {
  120. if(rear == this){
  121. return this;
  122. }
  123.  
  124. Node *p = this;
  125. while(p->next != NULL){
  126. p = p->next;
  127. }
  128.  
  129. return p;
  130. }
  131.  
  132. void Node::ClearAll()
  133. {
  134. Node* p = GoBacktoHead();
  135. Node* p2;
  136. while(p->GetNextNode() != NULL){
  137. p2 = p;
  138. p = p->GetNextNode();
  139. delete p2;
  140. }
  141.  
  142. delete p;
  143. }
  144.  
  145. int main(int argc, char* argv[])
  146. {
  147. int remain;
  148. int carry;
  149. int result;
  150. int N;
  151. Node* p = new Node(1);
  152.  
  153. std::cout<<"Input the number: ";
  154. std::cin>>N;
  155. for(int n=1;n<=N;n++)
  156. {
  157. remain = carry = 0;
  158. p = p->GoBacktoHead();
  159.  
  160. //while not the end of the list,process the element one by one
  161. while(p->GetNextNode() != NULL){
  162. result = p->GetData()*n+carry;
  163. if(result>=10){
  164. remain = result%10;
  165. carry = result/10;
  166. p->SetData(remain);
  167. }
  168. else{
  169. p->SetData(result);
  170. carry = result/10;
  171. }
  172.  
  173. p = p->GetNextNode();
  174. }
  175.  
  176. result = p->GetData()*n+carry;
  177.  
  178. //if carry occurs,process the carry and
  179. //**store into the newly allocated space.**
  180.  
  181. while(result >= 10){
  182. p->SetData(result%10);//remainder
  183. Node * newNode = new Node(0); //create new node with data 0
  184. result = result/10; //cut last digit
  185. p->InsertAfterMe(newNode); //put new node in the rear
  186. p = p->GetNextNode(); //advance to this new node
  187. }
  188.  
  189. p->SetData(result); //when result < 10, put result in this new node
  190.  
  191. }//end of for
  192.  
  193.  
  194. p = p->GoForwardtoRear();
  195.  
  196. while(p->GetPrevNode()!=NULL){
  197. std::cout<<p->GetData();
  198. p=p->GetPrevNode();
  199. }
  200.  
  201. std::cout<<p->GetData()<<std::endl;
  202. int num = p->GetElementNum();
  203. if(num >=5){
  204. p = p->GoForwardtoRear();
  205.  
  206. std::cout<<std::endl<<"Or"<<std::endl<<std::endl;
  207.  
  208. std::cout<<p->GetData()<<".";
  209. p = p->GetPrevNode();
  210.  
  211. for(int i=1;i<10;i++){
  212. std::cout<<p->GetData();
  213. p = p->GetPrevNode();
  214. }
  215.  
  216. std::cout<<"e"<<num-1<<std::endl;
  217. }
  218.  
  219. //clear the memory
  220. p->ClearAll();
  221.  
  222. return 0;
  223. }

Report this snippet  

You need to login to post a comment.