Advertisement
huutho_96

Thách thức BIGINT

May 27th, 2015
676
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <conio.h>
  3. #include <fstream>
  4. #include <string>
  5. #include <stack>
  6. using namespace std;
  7. struct Node
  8. {
  9. int x;
  10. Node *pNext;
  11. };
  12.  
  13. //List có contructor mặc định và contructor sao chép đề sử dụng trong trường hợp dùng stack
  14. struct List
  15. {
  16. Node *pHead, *pTail;
  17. int Dau;
  18. List()
  19. {
  20. Dau = 1;
  21. }
  22. List operator = (const List& L)
  23. {
  24. Node *p = L.pHead, *p1;
  25. this->pHead = NULL;
  26. this->pTail = NULL;
  27. this->Dau = L.Dau;
  28. while (p != NULL)
  29. {
  30. p1 = new Node;
  31. if (!p1)
  32. exit(1);
  33. p1->pNext = NULL;
  34. p1->x = p->x;
  35. if (pHead == NULL)
  36. {
  37. pHead = pTail = p1;
  38. }
  39. else
  40. {
  41. pTail->pNext = p1;
  42. pTail = p1;
  43. }
  44. p = p->pNext;
  45. }
  46. return *this;
  47. }
  48. };
  49. //tạo list
  50. void CreateList(List &L)
  51. {
  52. L.pHead = L.pTail = NULL;
  53. }
  54. //tạo node
  55. Node* CreateNode(int x)
  56. {
  57. Node *p = new Node;
  58. if (p == NULL) exit(1);
  59. p->x = x;
  60. p->pNext = NULL;
  61. return p;
  62. }
  63. //thêm đầu
  64. void AddHead(List &L, Node *p)
  65. {
  66. if (L.pHead == NULL)
  67. {
  68. L.pHead = L.pTail = p;
  69. }
  70. else
  71. {
  72. p->pNext = L.pHead;
  73. L.pHead = p;
  74. }
  75. }
  76. //xóa cuối
  77. void DelHead(List &L)
  78. {
  79. Node *p;
  80. if (L.pHead == NULL) return;
  81. p = L.pHead;
  82. L.pHead = p->pNext;
  83. delete p;
  84. if (L.pHead == NULL) L.pTail = NULL;
  85. }
  86. //xóa cuối
  87. void DelTail(List &L)
  88. {
  89. Node *p = L.pHead;
  90. Node *pBef = NULL;
  91. if (p == NULL) return;
  92. if (L.pHead == L.pTail)
  93. {
  94. L.pHead = L.pTail = NULL;
  95. delete p;
  96. return;
  97. }
  98. while (p != L.pTail)
  99. {
  100. pBef = p;
  101. p = p->pNext;
  102. }
  103. pBef->pNext = NULL;
  104. L.pTail = pBef;
  105. }
  106. //Nhập bằng tay
  107. void Input(List &L)
  108. {
  109. int x;
  110. Node *p = NULL;
  111. cout << endl;
  112. cout << "nhap so nguyen: ";
  113. do
  114. {
  115. x = getch();
  116. if (L.pHead == NULL && x == '-')
  117. {
  118. cout << "-";
  119. L.Dau = -1;
  120. }
  121. if (x >= 48 && x <= 57)
  122. {
  123. x = x - 48;
  124. cout << x;
  125. p = CreateNode(x);
  126. AddHead(L, p);
  127. }
  128. else
  129. {
  130. if (x == 8)
  131. {
  132. if (L.pHead != NULL || L.Dau == -1)
  133. {
  134. if (L.pHead == NULL)
  135. {
  136. putch(8);
  137. putch(' ');
  138. putch(8);
  139. L.Dau = 1;
  140. continue;
  141. }
  142. putch(8);
  143. putch(' ');
  144. putch(8);
  145. p = L.pHead;
  146. L.pHead = L.pHead->pNext;
  147. delete p;
  148. }
  149. }
  150. }
  151. } while (x != 13);
  152. }
  153. //Xuất
  154. void Output(List &L)
  155. {
  156. Node *p = L.pHead;
  157. if (L.Dau == -1) cout << "-";
  158. while (p != NULL)
  159. {
  160. cout << p->x;
  161. p = p->pNext;
  162. }
  163. }
  164. //thêm cuối
  165. void AddTail(List &L, Node *p)
  166. {
  167. if (L.pHead == NULL)
  168. {
  169. L.pHead = L.pTail = p;
  170. }
  171. else
  172. {
  173. L.pTail->pNext = p;
  174. L.pTail = p;
  175. }
  176. }
  177. //Lấy độ dài list
  178. int ListLen(List L)
  179. {
  180. int dem = 0;
  181. Node *p = L.pHead;
  182. while (p != NULL)
  183. {
  184. dem++;
  185. p = p->pNext;
  186. }
  187. return dem;
  188. }
  189. //Hủy List
  190. void HuyList(List &L1)
  191. {
  192. Node *p1 = L1.pHead;
  193. while (L1.pHead != NULL)
  194. {
  195. L1.pHead = L1.pHead->pNext;
  196. delete p1;
  197. p1 = L1.pHead;
  198. }
  199. L1.pTail = NULL;
  200. }
  201. //So sánh 2 số nguyên cùng độ dài, và là 2 sô nguyên bị đảo ngược
  202. int SoSanhListCungDoDai(Node *p1, Node *p2)
  203. {
  204. int t;
  205. if (p1->pNext != NULL && p2->pNext != NULL)
  206. {
  207. t = SoSanhListCungDoDai(p1->pNext, p2->pNext);
  208. if (t != 0) return t;
  209. }
  210. if ((p1->pNext == NULL && p2->pNext == NULL) || t == 0)
  211. {
  212. if (p1->x > p2->x) return 1;
  213. if (p1->x < p2->x) return -1;
  214. return 0;
  215. }
  216. }
  217. int SoSanhList(List L1, List L2)
  218. {
  219. int len1 = ListLen(L1), len2 = ListLen(L2);
  220. if (len1 > len2) return 1;
  221. if (len1 == len2) return SoSanhListCungDoDai(L1.pHead, L2.pHead);
  222. if (len1 < len2) return -1;
  223. }
  224.  
  225. //Cộng Trừ 2 BIGINT
  226. void CongList(List L1, List L2, List &L3)
  227. {
  228. Node *p1 = L1.pHead, *p2 = L2.pHead;
  229. Node *p3 = NULL;
  230. int r = 0;
  231. int x;
  232. while (p1 != NULL && p2 != NULL)
  233. {
  234. x = p1->x + p2->x + r;
  235. if (x >= 10)
  236. {
  237. r = 1;
  238. x = x - 10;
  239. }
  240. else
  241. r = 0;
  242. p3 = CreateNode(x);
  243. AddHead(L3, p3);
  244. p1 = p1->pNext;
  245. p2 = p2->pNext;
  246. }
  247. while (p1 != NULL)
  248. {
  249. x = p1->x + r;
  250. if (x >= 10)
  251. {
  252. r = 1;
  253. x = x - 10;
  254. }
  255. else
  256. r = 0;
  257. p3 = CreateNode(x);
  258. AddHead(L3, p3);
  259. p1 = p1->pNext;
  260. }
  261. while (p2 != NULL)
  262. {
  263. x = p2->x + r;
  264. if (x >= 10)
  265. {
  266. r = 1;
  267. x = x - 10;
  268. }
  269. else
  270. r = 0;
  271. p3 = CreateNode(x);
  272. AddHead(L3, p3);
  273. p2 = p2->pNext;
  274. }
  275. if (r == 1)
  276. {
  277. p3 = CreateNode(1);
  278. AddHead(L3, p3);
  279. }
  280. }
  281. void TruList(List L1, List L2, List &L3)
  282. {
  283. List L;
  284. int dau = 1;
  285. if (SoSanhList(L1, L2) == -1)
  286. {
  287. L.pHead = L1.pHead;
  288. L1.pHead = L2.pHead;
  289. L2.pHead = L.pHead;
  290. dau = -1;
  291.  
  292. }
  293. Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
  294. int r = 0, x;
  295. while (p1 != NULL && p2 != NULL)
  296. {
  297. x = p1->x - p2->x - r;
  298. if (x < 0)
  299. {
  300. r = 1;
  301. x = x + 10;
  302. }
  303. else
  304. r = 0;
  305. p3 = CreateNode(x);
  306. AddHead(L3, p3);
  307.  
  308. p1 = p1->pNext;
  309. p2 = p2->pNext;
  310. }
  311. while (p1 != NULL)
  312. {
  313. x = p1->x - r;
  314. if (x < 0)
  315. {
  316. r = 1;
  317. x = x + 10;
  318. }
  319. else
  320. r = 0;
  321. p3 = CreateNode(x);
  322. AddHead(L3, p3);
  323. p1 = p1->pNext;
  324. }
  325. p3 = L3.pHead;
  326. while (L3.pHead != NULL)
  327. {
  328. if (L3.pHead->x == 0)
  329. {
  330. p2 = L3.pHead;
  331. L3.pHead = L3.pHead->pNext;
  332. delete p2;
  333. if (ListLen(L3) == 1)
  334. {
  335. if (L3.pHead->x == 0) dau = 0;
  336. break;
  337. }
  338. }
  339. else
  340. break;
  341. }
  342. if (L3.pHead) L3.Dau = dau;
  343. else
  344. CreateList(L3);
  345. }
  346.  
  347. //các hàm phục vụ nhân chia bigint
  348. //Chèn số 0 vào đầu list
  349. void Chen(List &L)
  350. {
  351. AddHead(L, CreateNode(0));
  352. }
  353. //Sao chép bigint và đảo ngược chiều bigint lại
  354. void CopyList(List L, List &L1)
  355. {
  356.  
  357. Node *p = L.pHead;
  358. while (p != NULL)
  359. {
  360. AddHead(L1, CreateNode(p->x));
  361. p = p->pNext;
  362. }
  363. }
  364. //Nhân BIGINT với 1 số nguyên
  365. void NhanListVoiMotSo(List L, List &L1, int x)
  366. {
  367. Node *p = L.pHead;
  368. int r = 0;
  369. int n;
  370. while (p != NULL)
  371. {
  372. n = p->x * x + r;
  373. if (n >= 10)
  374. {
  375. r = n / 10;
  376. n %= 10;
  377. }
  378. else
  379. r = 0;
  380. AddTail(L1, CreateNode(n));
  381. p = p->pNext;
  382. }
  383.  
  384. if (r != 0)
  385. {
  386. AddTail(L1, CreateNode(r));
  387. }
  388. }
  389. //Đảo ngược list
  390. void DaoList(List &L)
  391. {
  392. Node *p1 = L.pHead;
  393. List L1;
  394. CreateList(L1);
  395. while (p1 != NULL)
  396. {
  397. AddHead(L1, CreateNode(p1->x));
  398. p1 = p1->pNext;
  399. }
  400. HuyList(L);
  401. L.pHead = L1.pHead;
  402. L.pTail = L1.pTail;
  403. CreateList(L1);
  404. }
  405. //Nhân 2 bigint
  406. void NhanList(List L1, List L2, List &L3)
  407. {
  408. if (L1.Dau * L2.Dau < 0) L3.Dau = -1;
  409. else L3.Dau = 1;
  410.  
  411.  
  412. Node *p1 = L1.pHead, *p2 = L2.pHead, *p3 = NULL;
  413. int x = 0;
  414. int r = 0;
  415. int dem = 0;
  416. List L, L4;
  417. CreateList(L);
  418. CreateList(L4);
  419. while (p2 != NULL)
  420. {
  421. NhanListVoiMotSo(L1, L, p2->x);
  422. for (int i = 0; i < dem; i++) Chen(L);
  423.  
  424. CongList(L, L3, L4);
  425. HuyList(L);
  426. HuyList(L3);
  427. CopyList(L4, L3);
  428. HuyList(L4);
  429. p2 = p2->pNext;
  430. dem++;
  431. }
  432. DaoList(L3);
  433. }
  434.  
  435. //Copy N Node từ node p trở đi. phục vụ hàm chia
  436. int CopyListNode(List &L, Node *&p, int n)
  437. {
  438. int i = 0;
  439. while (p && i < n)
  440. {
  441. AddHead(L, CreateNode(p->x));
  442. p = p->pNext;
  443. i++;
  444. }
  445. if (i < n) return 0;
  446. return 1;
  447. }
  448. //So sánh list theo
  449. int SoSanhListXuoi(List L1, List L2)
  450. {
  451. int len1 = ListLen(L1);
  452. int len2 = ListLen(L2);
  453. if (len1 > len2) return 1;
  454. if (len1 < len2) return -1;
  455. Node *p1 = L1.pHead;
  456. Node *p2 = L2.pHead;
  457. while (p1 && p2)
  458. {
  459. if (p1->x > p2->x) return 1;
  460. if (p1->x < p2->x) return -1;
  461. p1 = p1->pNext;
  462. p2 = p2->pNext;
  463. }
  464. if (p1 == NULL && p2) return -1;
  465. if (p1 && p2 == NULL) return 1;
  466. return 0;
  467. }
  468. //Chia list có độ dài chênh lệch 1 để lấy 1 số nguyên
  469. void ChiaListLay1So(List L1, List L2, int &KetQua)
  470. {
  471. //L1, L2 la list nguoc
  472. int t;
  473. List Tam;
  474. CreateList(Tam);
  475. List L;
  476. CreateList(L);
  477. CopyList(L2, L);
  478. List L3;
  479. CreateList(L3);
  480. CopyList(L1, L3);
  481. //Tam, L va L3 la list xuoi
  482. while (L3.pHead != NULL && L3.pHead->x == 0) DelHead(L3);
  483. DaoList(L);
  484. for (int i = 1; i <= 10; i++)
  485. {
  486. //dua vao list nguoc, tra ve list nguoc
  487. NhanListVoiMotSo(L, Tam, i);
  488. DaoList(Tam);
  489. t = SoSanhListXuoi(L3, Tam);
  490. if (t <= 0)
  491. {
  492. if (t == 0)
  493. {
  494. KetQua = i;
  495. }
  496. else
  497. KetQua = i - 1;
  498. return;
  499. }
  500. else
  501. HuyList(Tam);
  502. }
  503. }
  504. //chia 2 bigint
  505. void ChiaList(List L1, List &L2, List &L3)
  506. {
  507. if (L1.Dau * L2.Dau < 0) L3.Dau = -1;
  508. else L3.Dau = 1;
  509.  
  510. //L1, L2 list nguoc
  511. int len = ListLen(L2);
  512. List Tam;
  513. CreateList(Tam);
  514. List L4;
  515. CreateList(L4);
  516. List L5;
  517. CreateList(L5);
  518. DaoList(L1);//L1 list xuoi
  519. Node *p1 = L1.pHead;
  520. int t = CopyListNode(Tam, p1, len);//list xuoi
  521. if (t == 0)
  522. {
  523. AddHead(L3, CreateNode(0));
  524. return;
  525. }
  526. //l2 list nguoc
  527. //tam là list nguoc
  528. while (1)
  529. {
  530.  
  531. ChiaListLay1So(Tam, L2, t);
  532. NhanListVoiMotSo(L2, L4, t);//list cung chieu
  533. if (t)
  534. {
  535. while (L4.pHead != L4.pTail && L4.pTail->x == 0)
  536. DelTail(L4);
  537. TruList(Tam, L4, L5);
  538. //L5 xuoi
  539. if (L5.pHead && L5.pHead->x == 0)
  540. {
  541. HuyList(Tam);
  542. HuyList(L5);
  543. }
  544. else
  545. if (L5.pHead && L5.pHead->x > 0)
  546. {
  547. Tam.pHead = L5.pHead;
  548. Tam.pTail = L5.pTail;
  549. CreateList(L5);
  550. }
  551. DaoList(Tam);
  552. }
  553. HuyList(L4);
  554. AddTail(L3, CreateNode(t));
  555. if (p1 == NULL) break;
  556. AddHead(Tam, CreateNode(p1->x));
  557. p1 = p1->pNext;
  558. }
  559. DaoList(L2);
  560. if (L3.pHead->x == 0) DelHead(L3);
  561. }
  562. //đọc bigint
  563. void ReadFile(List &L, string path = "")
  564. {
  565. fstream f;
  566. f.open(path, ios::out | ios::in);
  567. char c;
  568. if (f)
  569. {
  570. while (!f.eof())
  571. {
  572. f >> c;
  573. if (f.eof()) break;
  574. AddHead(L, CreateNode(c - 48));
  575. }
  576. }
  577. else cout << "path error\n";
  578. f.close();
  579. }
  580. // đọc đa thức
  581. void DocDaThuc(string &DaThuc, string path = "")
  582. {
  583. fstream f;
  584. f.open(path, ios::in | ios::out);
  585. if (f)
  586. {
  587. while (!f.eof())
  588. getline(f, DaThuc);
  589. }
  590. f.close();
  591. }
  592. //Xét độ ưu tiên toán tử
  593. int UT(char c)
  594. {
  595. if (c == '+' || c == '-') return 1;
  596. if (c == '*' || c == '/') return 2;
  597. return 0;
  598. }
  599. //Xử lý trung tố sang hậu tố
  600. string XuLyDaThuc()
  601. {
  602. stack<char> s = {};
  603. string DaThuc = "";
  604. string HauTo = "";
  605. char a;
  606. DocDaThuc(DaThuc, "D:/DaThuc.txt");
  607. int len = DaThuc.size();
  608. for (int i = 0; i < len; i++)
  609. {
  610. if (DaThuc[i] >= '0' && DaThuc[i] <= '9')
  611. {
  612. while (DaThuc[i] >= '0' && DaThuc[i] <= '9')
  613. HauTo += DaThuc[i++];
  614. HauTo += ' ';
  615. }
  616.  
  617. if (DaThuc[i] == '(')
  618. s.push(DaThuc[i]);
  619.  
  620. if (DaThuc[i] == '+' || DaThuc[i] == '-' || DaThuc[i] == '*' || DaThuc[i] == '/')
  621. {
  622. while (!s.empty() && UT(s.top()) >= UT(DaThuc[i]))
  623. {
  624. HauTo += s.top();
  625. s.pop();
  626. }
  627. s.push(DaThuc[i]);
  628. }
  629.  
  630. if (DaThuc[i] == ')')
  631. {
  632. while (!s.empty() && s.top() != '(')
  633. {
  634. HauTo += s.top();
  635. s.pop();
  636. }
  637. s.pop();
  638. }
  639.  
  640. }
  641. while (!s.empty())
  642. {
  643. HauTo += s.top();
  644. s.pop();
  645. }
  646. return HauTo;
  647. }
  648. //Ghi kết quả vào file
  649. void GhiFile(List L)
  650. {
  651. fstream f;
  652. f.open("Output.txt", ios::out);
  653. if (L.pHead && L.Dau == -1) f << "-";
  654. Node *p = L.pHead;
  655. while (p)
  656. {
  657. f << p->x;
  658. p = p->pNext;
  659. }
  660. f.flush();
  661. f.close();
  662. system("Output.txt");
  663. }
  664. //Tính giá trị đa thức theo biểu thức hậu tố
  665. void TinhDaThuc(string DaThuc)
  666. {
  667. stack<List> SL;
  668. stack<char> s;
  669. List L;
  670. List a, b, c;
  671. CreateList(a);
  672. CreateList(b);
  673. CreateList(c);
  674. CreateList(L);
  675. int len = DaThuc.size();
  676. for (int i = 0; i < len; i++)
  677. {
  678. if (DaThuc[i] >= '0' && DaThuc[i] <= '9')
  679. {
  680. while (DaThuc[i] >= '0' && DaThuc[i] <= '9')
  681. {
  682. AddHead(L, CreateNode(DaThuc[i] - 48));
  683. i++;
  684. }
  685. SL.push(L);
  686. CreateList(L);
  687. }
  688. if (DaThuc[i] == '+' || DaThuc[i] == '-' || DaThuc[i] == '*' || DaThuc[i] == '/')
  689. {
  690. if (DaThuc[i] == '-')
  691. int a = 2;
  692. a = SL.top();
  693. SL.pop();
  694. b = SL.top();
  695. SL.pop();
  696. if (DaThuc[i] == '+')
  697. {
  698. if (b.Dau == -1 && a.Dau == -1)
  699. {
  700. CongList(b, a, c);
  701. c.Dau = -1;
  702. }
  703. if (b.Dau == 1 && a.Dau == -1)
  704. TruList(b, a, c);
  705. if (b.Dau == -1 && a.Dau == 1)
  706. TruList(a, b, c);
  707. if (b.Dau == 1 && a.Dau == 1)
  708. CongList(b, a, c);
  709. }
  710. if (DaThuc[i] == '-')
  711. {
  712. if (b.Dau == -1 && a.Dau == 1)
  713. {
  714. CongList(b, a, c);
  715. c.Dau = -1;
  716. }
  717. if (b.Dau == 1 && a.Dau == -1)
  718. CongList(b, a, c);
  719. if (b.Dau == -1 && a.Dau == -1)
  720. {
  721. TruList(a, b, c);
  722. }
  723. if (b.Dau == 1 && a.Dau == 1)
  724. TruList(b, a, c);
  725. }
  726. if (DaThuc[i] == '*')
  727. NhanList(b, a, c);
  728. if (DaThuc[i] == '/')
  729. ChiaList(b, a, c);
  730. DaoList(c);
  731. SL.push(c);
  732. CreateList(a);
  733. CreateList(b);
  734. CreateList(c);
  735. }
  736. }
  737. DaoList(SL.top());
  738. Output(SL.top());
  739. cout << endl;
  740. //GhiFile(SL.top());
  741. }
  742.  
  743.  
  744.  
  745. //Lưu ý các file test đặt đúng đường dẫn và đúng tên
  746.  
  747. //Hàm main1 kiểm tra phep + - * /
  748. void main1()
  749. {
  750. List L1, L2, L3, L4;
  751. ReadFile(L1, "D:/Update.txt");
  752. int dau;
  753. CreateList(L1);
  754. CreateList(L2);
  755. CreateList(L3);
  756. ReadFile(L1, "D:/SN1.txt");
  757. ReadFile(L2, "D:/SN2.txt");
  758. CongList(L1, L2, L3);
  759. cout << endl;
  760. cout << "Cong: ";
  761. Output(L3);
  762. HuyList(L3);
  763. TruList(L1, L2, L3);
  764. cout << endl;
  765. cout << "Tru: ";
  766. Output(L3);
  767. HuyList(L3);
  768. NhanList(L1, L2, L3);
  769. cout << endl;
  770. cout << "Nhan: ";
  771. Output(L3);
  772. HuyList(L3);
  773. ChiaList(L1, L2, L3);
  774. cout << endl;
  775. cout << "Chia: ";
  776. Output(L3);
  777. getchar();
  778. }
  779.  
  780. //main2 test việc xử lý số âm, việc nhập thủ công
  781. void main2()
  782. {
  783. List L;
  784. CreateList(L);
  785. List L1;
  786. CreateList(L1);
  787. List L2;
  788. CreateList(L2);
  789. Input(L);
  790. Input(L1);
  791. NhanList(L, L1, L2);
  792. cout << endl;
  793. Output(L2);
  794. }
  795.  
  796. //Tính giá trị đa thức. đa thức đặt trong ổ D tên file là DaThuc.txt
  797. void main3()
  798. {
  799. string HauTo = XuLyDaThuc();
  800. TinhDaThuc(HauTo);
  801. }
  802.  
  803. void main()
  804. {
  805. //main1();
  806. main2();
  807. //main3();
  808. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement