API tools faq
paste
Advertisement
Ikmik

poly.py

Ikmik
Jun 7th, 2015
333
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 15.30 KB | None | 0 0
raw download clone embed print report
  1. #!/usr/bin/python3
  2. # file: poly.py
  3.  
  4. import sys
  5. from fractions import gcd
  6.  
  7.  
  8. class Fraction:
  9.     def reduce(self):
  10.         g = gcd(self.a, self.b)
  11.         self.a //= g
  12.         self.b //= g
  13.  
  14.     def __init__(self, a = None, b = None):
  15.         if b is not None:
  16.             self.a = a
  17.             self.b = b
  18.         else:
  19.             if a is None:
  20.                 self.a = 0
  21.                 self.b = 1
  22.             if type(a) == Fraction:
  23.                 self.a = a.a
  24.                 self.b = a.b
  25.             if type(a) == int:
  26.                 self.a = a
  27.                 self.b = 1
  28.             if type(a) == str:
  29.                 a = a.rstrip()
  30.                 if a.find("/") != -1:
  31.                     lst = a.split("/")
  32.                 else:
  33.                     lst = a.split(" ")
  34.                 if len(lst) == 2:
  35.                     self.a, self.b = map(int, lst)
  36.                 else:
  37.                     self.a = int(lst[0])
  38.                     self.b = 1
  39.         self.reduce()
  40.    
  41.     def __str__(self):
  42.         if self.b == 1:
  43.             return str(self.a)
  44.         else:
  45.             return "/".join(map(str, (self.a, self.b)))
  46.  
  47.     def __lt__(self, other):
  48.         if type(other) == int:
  49.             return self < Fraction(other)
  50.         elif type(other) == float:
  51.             return float(self.a) < float(self.b) * other
  52.         elif type(other) == Fraction:
  53.             return self.a * other.b < other.a * self.b
  54.         else:
  55.             return NotImplemented
  56.  
  57.     def __gt__(self, other):
  58.         if type(other) == int:
  59.             return self > Fraction(other)
  60.         elif type(other) == float:
  61.             return float(self.a) > float(self.b) * other
  62.         elif type(other) == Fraction:
  63.             return self.a * other.b > other.a * self.b
  64.         else:
  65.             return NotImplemented
  66.  
  67.     def __eq__(self, other):
  68.         return not (self < other) and not(self > other)
  69.  
  70.     def __le__(self, other):
  71.         return self < other or self == other
  72.  
  73.     def __ge__(self, other):
  74.         return self > other or self == other
  75.  
  76.     def __ne__(self, other):
  77.         return not self == other
  78.  
  79.     def __mul__(self, other):
  80.         if type(other) == Fraction:
  81.             return Fraction(self.a * other.a, self.b * other.b)
  82.         elif type(other) == int:
  83.             return Fraction(self.a * other, self.b)
  84.         elif type(other) == float:
  85.             return self.a * other / self.b
  86.         else:
  87.             return NotImplemented
  88.  
  89.     def __rmul__(self, other):
  90.         return self * other
  91.  
  92.     def __imul__(self, other):
  93.         self = self * other
  94.         return self
  95.  
  96.     def __truediv__(self, other):
  97.         if self == 0:
  98.             return Fraction()
  99.         elif type(other) == Fraction:
  100.             return Fraction(self.a * other.b, self.b * other.a)
  101.         elif type(other) == int:
  102.             return self / Fraction(other)
  103.         elif type(other) == float:
  104.             return (self.a / self.b) / other
  105.         else:
  106.             return NotImplemented
  107.  
  108.     def __rtruediv__(self, other):
  109.         return Fraction(1) / (self / other)
  110.  
  111.     def __itruediv__(self, other):
  112.         self = self / other
  113.         return self
  114.  
  115.     def __pow__(self, other):
  116.         if type(other) == int:
  117.             if other < 0:
  118.                 return 1 / (self ** (-other))
  119.             else:
  120.                 res = Fraction()
  121.                 res.a = self.a ** other
  122.                 res.b = self.b ** other
  123.                 return res
  124.         elif type(other) == Fraction:
  125.             return (self.a / self.b) ** (other.a / other.b)
  126.         else:
  127.             return (self.a / self.b) ** other
  128.  
  129.     def __rpow__(self, other):
  130.         return other ** (self.a / self.b)
  131.  
  132.     def __ipow__(self, other):
  133.         self = self ** other
  134.         return self
  135.  
  136.     def __add__(self, other):
  137.         if type(other) == float:
  138.             return (self.a / self.b) + other
  139.         elif type(other) == Fraction:
  140.             return Fraction(self.a * other.b + other.a * self.b, self.b * other.b)
  141.         elif type(other) == int:
  142.             return self + Fraction(other)
  143.         else:
  144.             return NotImplemented
  145.  
  146.     def __radd__(self, other):
  147.         return self + other
  148.  
  149.     def __iadd__(self, other):
  150.         self = self + other
  151.         return self
  152.  
  153.     def __sub__(self, other):
  154.         return self + (-1) * other
  155.  
  156.     def __rsub__(self, other):
  157.         return other + (-1) * self
  158.  
  159.     def __isub__(self, other):
  160.         self += (-1) * other
  161.         return self
  162.  
  163.     def __pos__(self):
  164.         return self
  165.  
  166.     def __neg__(self):
  167.         return (-1) * self
  168.  
  169.     def __abs__(self):
  170.         if self.a < 0:
  171.             res = Fraction()
  172.             res.a = -self.a
  173.             res.b = self.b
  174.             return res
  175.         else:
  176.             return self
  177.  
  178.     def __int__(self):
  179.         return self.a // self.b
  180.  
  181.     def __float__(self):
  182.         return self.a / self.b
  183.  
  184.     def __round__(self, a = 0):
  185.         return round(float(self), a)
  186.  
  187.  
  188. class Poly:
  189.     def __reduce(self):
  190.         i = len(self) - 1
  191.         while i > 0 and self.__coef[i] == 0:
  192.             i -= 1
  193.         self.__coef = self.__coef[:i + 1]
  194.  
  195.     def __init__(self, arg=None, should_copy=True):
  196.         self.__symbol_string = "".join(map(chr, [8304, 185, 178, 179, 8308, 8309, 8310, 8311, 8312, 8313]))
  197.         if arg is None:
  198.             self.__coef = [0]
  199.         elif type(arg) in [int, float, Fraction]:
  200.             self.__coef = [arg]
  201.         elif type(arg) == list:
  202.             if should_copy:
  203.                 self.__coef = arg[:]
  204.             else:
  205.                 self.__coef = arg
  206.         elif type(arg) == tuple:
  207.             self.__coef = list(arg)
  208.         elif type(arg) == str:
  209.             self.__coef = list(map(eval, arg.split()))
  210.         elif type(arg) == Poly:
  211.             self.__coef = arg.__coef[:]
  212.         self.__reduce()
  213.        
  214.     def __int2upper_str(self, n):
  215.         return "".join(map(lambda c: self.__symbol_string[ord(c) - ord('0')], str(n)))
  216.  
  217.     def __monomial2str(self, i):
  218.         res = ""
  219.  
  220.         if i == 0:
  221.             if type(self.__coef[i]) == float:
  222.                 if self.__coef[i] < 0:
  223.                     if 1 == len(self.__coef):
  224.                         return str(round(self.__coef[i], 3))
  225.                     else:
  226.                         return "- " + str(-round(self.__coef[i], 3))
  227.                 else:
  228.                     if 1 == len(self.__coef):
  229.                         return str(round(self.__coef[i], 3))
  230.                     else:
  231.                         return "+ " + str(round(self.__coef[i], 3))
  232.             elif type(self.__coef[i]) == Fraction and self.__coef[i].b != 1:
  233.                 if self.__coef[i] < 0:
  234.                     if 1 == len(self.__coef):
  235.                         return "-(" + str(-self.__coef[i]) + ")"
  236.                     else:
  237.                         return "- (" + str(-self.__coef[i]) + ")"
  238.                 else:
  239.                     if 1 == len(self.__coef):
  240.                         return "(" + str(self.__coef[i]) + ")"
  241.                     else:
  242.                         return "+ (" + str(self.__coef[i]) + ")"
  243.             else:
  244.                 if 1 == len(self.__coef):
  245.                     return str(self.__coef[i])
  246.                 else:
  247.                     if self.__coef[i] < 0:
  248.                         return "- " + str(-self.__coef[i])
  249.                     else:
  250.                         return "+ " + str(self.__coef[i])
  251.  
  252.         if self.__coef[i] < 0:
  253.             res += "-"
  254.         elif i < len(self.__coef) - 1:
  255.             res += "+"
  256.         if i < len(self.__coef) - 1:
  257.             res += " "
  258.  
  259.         if type(self.__coef[i]) == Fraction:
  260.             if self.__coef[i].b != 1:
  261.                 res += "(" + str(abs(self.__coef[i])) + ")"
  262.             elif self.__coef[i].b == 1:
  263.                 if abs(self.__coef[i].a) != 1:
  264.                     res += str(abs(self.__coef[i].a))
  265.         elif type(self.__coef[i]) == int:
  266.             if abs(self.__coef[i]) != 1:
  267.                 res += str(abs(self.__coef[i]))
  268.         else:
  269.             k = abs(round(self.__coef[i], 3))
  270.             if k != 1:
  271.                 res += str(k)
  272.  
  273.         if i == 0:
  274.             return res
  275.         elif i == 1:
  276.             res += "x"
  277.         else:
  278.             res += "x" + self.__int2upper_str(i)
  279.         return res
  280.            
  281.     def __str__(self):
  282.         if self.__coef == [0]:
  283.             return "0"
  284.         res = []
  285.         for i in range(len(self.__coef) - 1, -1, -1):
  286.             if self.__coef[i] != 0:
  287.                 res.append(self.__monomial2str(i))
  288.         return " ".join(res)
  289.  
  290.     def __len__(self):
  291.         return len(self.__coef)
  292.  
  293.     def __add__(self, other):
  294.         if isinstance(other, Poly):
  295.             a = len(self)
  296.             b = len(other)
  297.             l = max(a, b)
  298.             res = [0 for i in range(l)]
  299.             for i in range(l):
  300.                 if i < a:
  301.                     res[i] += self.__coef[i]
  302.                 if i < b:
  303.                     res[i] += other.__coef[i]
  304.             return Poly(res, False)
  305.         else:
  306.             res = self.__coef[:]
  307.             res[0] = res[0] + other
  308.             return Poly(res)
  309.  
  310.     def __radd__(self, other):
  311.         return self + other
  312.  
  313.     def __iadd__(self, other):
  314.         self.__coef = (self + other).__coef
  315.         return self
  316.  
  317.  
  318. import random
  319.  
  320. random.seed(837283918)
  321. __count = 0
  322.  
  323. def TEST(title = ''):
  324.     global __count
  325.     __count += 1
  326.     print()
  327.     print('=====================================')
  328.     print('Подтест ', __count, ':', title)
  329.  
  330. def randInt():
  331.     return random.randint(-1000, 1000)
  332.  
  333. def randFloat():
  334.     return random.random() * 2000 - 1000
  335.  
  336. def randFraction():
  337.     a = random.randint(-1000, 1000)
  338.     b = random.randint(-1000, 1000)
  339.     while b == 0:
  340.         b = random.randint(-1000, 1000)
  341.     return Fraction(a, b)
  342.  
  343. def randZero():
  344.     return random.choice([0, 0.0, Fraction(0)])
  345.  
  346. def Zero():
  347.     return 0
  348.  
  349. def randCoeff(genFunc = [randInt, randFloat, randFraction, randZero]):
  350.     return random.choice(genFunc)()
  351.  
  352. def randIntPoly(n=100):
  353.     L = [randInt() for j in range(random.randint(1, n))]
  354.     while L[-1] == 0:
  355.         L[-1] = randInt()
  356.     return Poly(L)
  357.  
  358. def randFractionPoly(n=100):
  359.     L = [randFraction() for j in range(random.randint(1, n))]
  360.     while L[-1] == 0:
  361.         L[-1] = randFraction()
  362.     return Poly(L)
  363.  
  364. def randFloatPoly(n=100):
  365.     L = [randFloat() for j in range(random.randint(1, n))]
  366.     while L[-1] == 0:
  367.         L[-1] = randFloat()
  368.     return Poly(L)
  369.  
  370. def randPoly(n=100):
  371.     L = [randCoeff() for j in range(random.randint(1, n))]
  372.     while L[-1] == 0:
  373.         L[-1] = randCoeff()
  374.     return Poly(L)
  375.  
  376. print('Тестируются сложение многочленов')
  377. TEST('Метод __add__ для Poly + Poly')
  378. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  379. _B = Poly([1, 5, 7, 1, 2])
  380. _C = _A + _B
  381. print(_C)
  382. _A = Poly([-2, 3, -1, -5, 1, -2])
  383. _B = Poly([1, -5, -7, 1, -2, 3, -3, -1, 2])
  384. _C = _A + _B
  385. print(_C)
  386. _A = Poly([1, 2, 3])
  387. _B = Poly([1, 2, -3])
  388. _C = _A + _B
  389. print(_C)
  390.  
  391. TEST('Метод __add__ для Poly + int')
  392. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  393. _B = -7
  394. _C = _A + _B
  395. print(_C)
  396. _A = Poly([2, 0, 1])
  397. _B = -2
  398. _C = _A + _B
  399. print(_C)
  400. _A = Poly([Fraction(12, 7), 0, 1])
  401. _B = 1
  402. _C = _A + _B
  403. print(_C)
  404. _A = Poly([1.5, 0, 1])
  405. _B = 1
  406. _C = _A + _B
  407. print(_C)
  408.  
  409. TEST('Метод __add__ для Poly + Fraction')
  410. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  411. _B = Fraction(19, 4)
  412. _C = _A + _B
  413. print(_C)
  414. _A = Poly([2, 0, 1])
  415. _B = Fraction(-6, 3)
  416. _C = _A + _B
  417. print(_C)
  418. _A = Poly([Fraction(12, 7), 0, 1])
  419. _B = Fraction(-18, 5)
  420. _C = _A + _B
  421. print(_C)
  422. _A = Poly([1.5, 0, 1])
  423. _B = Fraction(14, 9)
  424. _C = _A + _B
  425. print(_C)
  426.  
  427. TEST('Метод __add__ для Poly + float')
  428. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  429. _B = 12.35
  430. _C = _A + _B
  431. print(_C)
  432. _A = Poly([2, 0, 1])
  433. _B = -2.0
  434. _C = _A + _B
  435. print(_C)
  436. _A = Poly([Fraction(12, 7), 0, 1])
  437. _B = 13.24
  438. _C = _A + _B
  439. print(_C)
  440. _A = Poly([1.5, 0, 1])
  441. _B = 17.81
  442. _C = _A + _B
  443. print(_C)
  444.  
  445. TEST('Метод __iadd__ для Poly + Poly')
  446. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  447. _B = Poly([1, 5, 7, 1, 2])
  448. _A += _B
  449. print(_A)
  450. _A = Poly([-2, 3, -1, -5, 1, -2])
  451. _B = Poly([1, -5, -7, 1, -2, 3, -3, -1, 2])
  452. _A += _B
  453. print(_A)
  454. _A = Poly([1, 2, 3])
  455. _B = Poly([1, 2, -3])
  456. _A += _B
  457. print(_A)
  458.  
  459. TEST('Метод __iadd__ для Poly + int')
  460. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  461. _B = -7
  462. _A += _B
  463. print(_A)
  464. _A = Poly([2, 0, 1])
  465. _B = -2
  466. _A += _B
  467. print(_A)
  468. _A = Poly([Fraction(12, 7), 0, 1])
  469. _B = 1
  470. _A += _B
  471. print(_A)
  472. _A = Poly([1.5, 0, 1])
  473. _B = 1
  474. _A += _B
  475. print(_A)
  476.  
  477. TEST('Метод __iadd__ для Poly + Fraction')
  478. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  479. _B = Fraction(19, 4)
  480. _A += _B
  481. print(_A)
  482. _A = Poly([2, 0, 1])
  483. _B = Fraction(-6, 3)
  484. _A += _B
  485. print(_A)
  486. _A = Poly([Fraction(12, 7), 0, 1])
  487. _B = Fraction(-18, 5)
  488. _A += _B
  489. print(_A)
  490. _A = Poly([1.5, 0, 1])
  491. _B = Fraction(14, 9)
  492. _A += _B
  493. print(_A)
  494.  
  495. TEST('Метод __iadd__ для Poly + float')
  496. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  497. _B = 12.35
  498. _A += _B
  499. print(_A)
  500. _A = Poly([2, 0, 1])
  501. _B = -2.0
  502. _A += _B
  503. print(_A)
  504. _A = Poly([Fraction(12, 7), 0, 1])
  505. _B = 13.24
  506. _A += _B
  507. print(_A)
  508. _A = Poly([1.5, 0, 1])
  509. _B = 17.81
  510. _A += _B
  511. print(_A)
  512.  
  513. TEST('Метод __radd__ для Poly + int')
  514. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  515. _B = -7
  516. _C = _B + _A
  517. print(_C)
  518. _A = Poly([2, 0, 1])
  519. _B = -2
  520. _C = _B + _A
  521. print(_C)
  522. _A = Poly([Fraction(12, 7), 0, 1])
  523. _B = 1
  524. _C = _B + _A
  525. print(_C)
  526. _A = Poly([1.5, 0, 1])
  527. _B = 1
  528. _C = _B + _A
  529. print(_C)
  530.  
  531. TEST('Метод __radd__ для Poly + Fraction')
  532. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  533. _B = Fraction(19, 4)
  534. _C = _B + _A
  535. print(_C)
  536. _A = Poly([2, 0, 1])
  537. _B = Fraction(-6, 3)
  538. _C = _B + _A
  539. print(_C)
  540. _A = Poly([Fraction(12, 7), 0, 1])
  541. _B = Fraction(-18, 5)
  542. _C = _B + _A
  543. print(_C)
  544. _A = Poly([1.5, 0, 1])
  545. _B = Fraction(14, 9)
  546. _C = _B + _A
  547. print(_C)
  548.  
  549. TEST('Метод __radd__ для Poly + float')
  550. _A = Poly([2, 3, 1, 3, 4, 5, 1, 2])
  551. _B = 12.35
  552. _C = _B + _A
  553. print(_C)
  554. _A = Poly([2, 0, 1])
  555. _B = -2.0
  556. _C = _B + _A
  557. print(_C)
  558. _A = Poly([Fraction(12, 7), 0, 1])
  559. _B = 13.24
  560. _C = _B + _A
  561. print(_C)
  562. _A = Poly([1.5, 0, 1])
  563. _B = 17.81
  564. _C = _B + _A
  565. print(_C)
  566.  
  567. TEST('Специальные тесты на корректность реализации __iadd__')
  568. _A = Poly([1, 1, 1])
  569. _B = Poly([1, 1])
  570. _D = _A
  571. _A += _B
  572. print(_D)
  573. _A += _B
  574. print(_D)
  575. _A += _B
  576. print(_D)
  577. _A += 1
  578. print(_D)
  579. _A += Fraction(1, 2)
  580. print(_D)
  581. _A += 1.2
  582. print(_D)
  583.  
  584. for i in range(100):
  585.     TEST('Большой случайный тест')
  586.     if i % 4 == 0:
  587.         _A = randPoly()
  588.         _B = randPoly()
  589.         _x = randCoeff()
  590.     elif i % 4 == 1:
  591.         _A = randIntPoly()
  592.         _B = randIntPoly()
  593.         _x = randInt()
  594.     elif i % 4 == 2:
  595.         _A = randFractionPoly()
  596.         _B = randFractionPoly()
  597.         _x = randFraction()
  598.     elif i % 4 == 3:
  599.         _A = randFloatPoly()
  600.         _B = randFloatPoly()
  601.         _x = randFloat()
  602.     _C = _A + _B
  603.     _D = Poly(_A)
  604.     _D += _B
  605.     _E = _A + _x
  606.     _F = Poly(_A)
  607.     _F += _x
  608.     _G = _x + _A
  609.     print("Source data:")
  610.     print("A = ", _A)
  611.     print("B = ", _B)
  612.     print("x = ", _x)
  613.     print("Result:")
  614.     print("C = ", _C)
  615.     print("D = ", _D)
  616.     print("E = ", _E)
  617.     print("F = ", _F)
  618.     print("G = ", _G)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!