Created
May 12, 2019 12:59
-
-
Save LostInKadath/09c910c1a5b8bfd71dd936de7f5e4442 to your computer and use it in GitHub Desktop.
Реализовать операции вычитания, умножения и деления через операцию сложения
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def reverse(a): | |
'''Complexity - O(a).''' | |
if a == 0: | |
return 0 | |
result = 0 | |
change = -1 if a > 0 else +1 | |
while a != 0: | |
result += change | |
a += change | |
return result | |
assert(reverse(-10) == 10) | |
assert(reverse(-1) == 1) | |
assert(reverse(-0) == 0) | |
assert(reverse(0) == 0) | |
assert(reverse(1) == -1) | |
assert(reverse(10) == -10) | |
def abs(a): | |
'''Complexity - O(a) in case a is negative.''' | |
if a >= 0: | |
return a | |
return reverse(a) | |
assert(abs(-10) == 10) | |
assert(abs(-1) == 1) | |
assert(abs(-0) == 0) | |
assert(abs(0) == 0) | |
assert(abs(1) == 1) | |
assert(abs(10) == 10) | |
def add(a, b): | |
'''The only realized operation.''' | |
return a + b | |
assert(add(-10, 10) == 0) | |
assert(add(-10, -10) == -20) | |
assert(add(-10, 0) == -10) | |
assert(add(0, -10) == -10) | |
assert(add(0, 0) == 0) | |
assert(add(0, 10) == 10) | |
assert(add(10, 0) == 10) | |
assert(add(10, 10) == 20) | |
assert(add(10, -10) == 0) | |
def subtract(a, b): | |
'''Complexity - O(b).''' | |
return a + reverse(b) | |
assert(subtract(-10, 10) == -20) | |
assert(subtract(-10, -10) == 0) | |
assert(subtract(-10, 0) == -10) | |
assert(subtract(0, -10) == 10) | |
assert(subtract(0, 0) == 0) | |
assert(subtract(0, 10) == -10) | |
assert(subtract(10, 0) == 10) | |
assert(subtract(10, 10) == 0) | |
assert(subtract(10, -10) == 20) | |
def multiply(a, b): | |
'''Complexity - 2*(a + b): | |
abs(a) -> a | |
abs(b) -> b | |
reverse(mx) -> max(|a|,|b|) | |
range(mnabs) -> min(|a|,|b|) | |
''' | |
if not a or not b: | |
return 0 | |
# Searhing absolute minimum to take less loop steps below | |
mn, mx, result = a, b, 0 | |
mnabs, mxabs = abs(a), abs(b) | |
if mnabs > mxabs: | |
mn, mx = mx, mn | |
mnabs, mxabs = mxabs, mnabs | |
if mn < 0: | |
mx = reverse(mx) | |
# Main calculation loop | |
for i in range(mnabs): | |
result += mx | |
return result | |
assert(multiply(-10, 10) == -100) | |
assert(multiply(-10, -10) == 100) | |
assert(multiply(-10, 0) == 0) | |
assert(multiply(0, -10) == 0) | |
assert(multiply(0, 0) == 0) | |
assert(multiply(0, 10) == 0) | |
assert(multiply(10, 0) == 0) | |
assert(multiply(10, 10) == 100) | |
assert(multiply(10, -10) == -100) | |
def divide(a, b): | |
'''Division is checked by multiplication. | |
We calculate the sign of result and operate with absolute values of a and b. | |
Then we count how many times b is in a. | |
Complexity - O(a + b + a//b): | |
abs(a) -> a | |
abs(b) -> b | |
main loop -> a//b | |
''' | |
if b == 0: | |
return 0 | |
raise Exception | |
absa, absb = abs(a), abs(b) | |
if absa < absb: | |
return 0 | |
if a == b: | |
return 1 | |
if absa == absb: | |
return -1 | |
# Sign of result | |
change = +1 if a > 0 and b > 0 or a < 0 and b < 0 else -1 | |
# Main calculation loop | |
accumulator, result = 0, 0 | |
while accumulator < absa: | |
accumulator += absb | |
result += change | |
# If a mod b == 0, so we return result. | |
if accumulator == absa: | |
return result | |
# Otherwise we have made one unnecessary step and need to decrease result by 1. | |
return subtract(result, change) | |
assert(divide(-1, 0) == 0) | |
assert(divide(0, 0) == 0) | |
assert(divide(1, 0) == 0) | |
assert(divide(0, 1) == 0) | |
assert(divide(0, -1) == 0) | |
assert(divide(-2, -2) == 1) | |
assert(divide(-1, -1) == 1) | |
assert(divide(1, 1) == 1) | |
assert(divide(2, 2) == 1) | |
assert(divide(-2, 2) == -1) | |
assert(divide(-1, 1) == -1) | |
assert(divide(1, -1) == -1) | |
assert(divide(2, -2) == -1) | |
assert(divide(-1, -2) == 0) | |
assert(divide(-1, 2) == 0) | |
assert(divide(1, -2) == 0) | |
assert(divide(1, 2) == 0) | |
assert(divide(-2, -1) == 2) | |
assert(divide(-2, 1) == -2) | |
assert(divide(2, -1) == -2) | |
assert(divide(2, 1) == 2) | |
assert(divide(-5, -2) == 2) | |
assert(divide(-5, 2) == -2) | |
assert(divide(5, -2) == -2) | |
assert(divide(5, 2) == 2) | |
assert(divide(-5, -3) == 1) | |
assert(divide(-5, 3) == -1) | |
assert(divide(5, -3) == -1) | |
assert(divide(5, 3) == 1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment