GUIKAR741
10/10/2019 - 10:02 PM
Maratona
Algoritmos para Maratona
- exponenciação binaria
- fatorial prog dinamica
- fibonacci prog dinamica
- grafo
- heapsort
- mdc
- mergesort
- prime_check
- primes
def binary_exponentiation(a, n):
"""Calcula a exponenciação em O(logn)."""
if n == 0:
return 1
elif n % 2 == 1:
return binary_exponentiation(a, n - 1) * a
else:
b = binary_exponentiation(a, n / 2)
return b * b# Factorial of a number using memoization
result = [-1] * 10
result[0] = result[1] = 1
def factorial(num):
"""
>>> factorial(7)
5040
>>> factorial(-1)
'Number should not be negative.'
>>> [factorial(i) for i in range(5)]
[1, 1, 2, 6, 24]
"""
if num < 0:
return "Number should not be negative."
if result[num] != -1:
return result[num]
else:
result[num] = num * factorial(num - 1)
# uncomment the following to see how recalculations are avoided
# print(result)
return result[num]def fibonacci(n: int): # noqa: E999 This syntax is Python 3 only
if n < 0:
raise ValueError("Negative arguments are not supported")
return _fib(n)[0]
# returns (F(n), F(n-1))
def _fib(n: int): # noqa: E999 This syntax is Python 3 only
if n == 0:
# (F(0), F(1))
return (0, 1)
else:
# F(2n) = F(n)[2F(n+1) − F(n)]
# F(2n+1) = F(n+1)^2+F(n)^2
a, b = _fib(n // 2)
c = a * (b * 2 - a)
d = a * a + b * b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)if __name__ == "__main__":
# Accept No. of Nodes and edges
n, m = map(int, input().split(" "))
# Initialising Dictionary of edges
g = {}
for i in range(n):
g[i + 1] = []
"""
----------------------------------------------------------------------------
Accepting edges of Unweighted Directed Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
x, y = map(int, input().strip().split(" "))
g[x].append(y)
"""
----------------------------------------------------------------------------
Accepting edges of Unweighted Undirected Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
x, y = map(int, input().strip().split(" "))
g[x].append(y)
g[y].append(x)
"""
----------------------------------------------------------------------------
Accepting edges of Weighted Undirected Graphs
----------------------------------------------------------------------------
"""
for _ in range(m):
x, y, r = map(int, input().strip().split(" "))
g[x].append([y, r])
g[y].append([x, r])
"""
--------------------------------------------------------------------------------
Depth First Search.
Args : G - Dictionary of edges
s - Starting Node
Vars : vis - Set of visited nodes
S - Traversal Stack
--------------------------------------------------------------------------------
"""
def dfs(G, s):
vis, S = set([s]), [s]
print(s)
while S:
flag = 0
for i in G[S[-1]]:
if i not in vis:
S.append(i)
vis.add(i)
flag = 1
print(i)
break
if not flag:
S.pop()
"""
--------------------------------------------------------------------------------
Breadth First Search.
Args : G - Dictionary of edges
s - Starting Node
Vars : vis - Set of visited nodes
Q - Traveral Stack
--------------------------------------------------------------------------------
"""
from collections import deque
def bfs(G, s):
vis, Q = set([s]), deque([s])
print(s)
while Q:
u = Q.popleft()
for v in G[u]:
if v not in vis:
vis.add(v)
Q.append(v)
print(v)
"""
--------------------------------------------------------------------------------
Dijkstra's shortest path Algorithm
Args : G - Dictionary of edges
s - Starting Node
Vars : dist - Dictionary storing shortest distance from s to every other node
known - Set of knows nodes
path - Preceding node in path
--------------------------------------------------------------------------------
"""
def dijk(G, s):
dist, known, path = {s: 0}, set(), {s: 0}
while True:
if len(known) == len(G) - 1:
break
mini = 100000
for i in dist:
if i not in known and dist[i] < mini:
mini = dist[i]
u = i
known.add(u)
for v in G[u]:
if v[0] not in known:
if dist[u] + v[1] < dist.get(v[0], 100000):
dist[v[0]] = dist[u] + v[1]
path[v[0]] = u
for i in dist:
if i != s:
print(dist[i])
"""
--------------------------------------------------------------------------------
Topological Sort
--------------------------------------------------------------------------------
"""
from collections import deque
def topo(G, ind=None, Q=None):
if Q is None:
Q = [1]
if ind is None:
ind = [0] * (len(G) + 1) # SInce oth Index is ignored
for u in G:
for v in G[u]:
ind[v] += 1
Q = deque()
for i in G:
if ind[i] == 0:
Q.append(i)
if len(Q) == 0:
return
v = Q.popleft()
print(v)
for w in G[v]:
ind[w] -= 1
if ind[w] == 0:
Q.append(w)
topo(G, ind, Q)
"""
--------------------------------------------------------------------------------
Reading an Adjacency matrix
--------------------------------------------------------------------------------
"""
def adjm():
n = input().strip()
a = []
for i in range(n):
a.append(map(int, input().strip().split()))
return a, n
"""
--------------------------------------------------------------------------------
Floyd Warshall's algorithm
Args : G - Dictionary of edges
s - Starting Node
Vars : dist - Dictionary storing shortest distance from s to every other node
known - Set of knows nodes
path - Preceding node in path
--------------------------------------------------------------------------------
"""
def floy(A_and_n):
(A, n) = A_and_n
dist = list(A)
path = [[0] * n for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k] + dist[k][j]:
dist[i][j] = dist[i][k] + dist[k][j]
path[i][k] = k
print(dist)
"""
--------------------------------------------------------------------------------
Prim's MST Algorithm
Args : G - Dictionary of edges
s - Starting Node
Vars : dist - Dictionary storing shortest distance from s to nearest node
known - Set of knows nodes
path - Preceding node in path
--------------------------------------------------------------------------------
"""
def prim(G, s):
dist, known, path = {s: 0}, set(), {s: 0}
while True:
if len(known) == len(G) - 1:
break
mini = 100000
for i in dist:
if i not in known and dist[i] < mini:
mini = dist[i]
u = i
known.add(u)
for v in G[u]:
if v[0] not in known:
if v[1] < dist.get(v[0], 100000):
dist[v[0]] = v[1]
path[v[0]] = u
"""
--------------------------------------------------------------------------------
Accepting Edge list
Vars : n - Number of nodes
m - Number of edges
Returns : l - Edge list
n - Number of Nodes
--------------------------------------------------------------------------------
"""
def edglist():
n, m = map(int, input().split(" "))
l = []
for i in range(m):
l.append(map(int, input().split(" ")))
return l, n
"""
--------------------------------------------------------------------------------
Kruskal's MST Algorithm
Args : E - Edge list
n - Number of Nodes
Vars : s - Set of all nodes as unique disjoint sets (initially)
--------------------------------------------------------------------------------
"""
def krusk(E_and_n):
# Sort edges on the basis of distance
(E, n) = E_and_n
E.sort(reverse=True, key=lambda x: x[2])
s = [set([i]) for i in range(1, n + 1)]
while True:
if len(s) == 1:
break
print(s)
x = E.pop()
for i in range(len(s)):
if x[0] in s[i]:
break
for j in range(len(s)):
if x[1] in s[j]:
if i == j:
break
s[j].update(s[i])
s.pop(i)
break
def heapify(unsorted, index, heap_size):
largest = index
left_index = 2 * index + 1
right_index = 2 * index + 2
if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
largest = left_index
if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
largest = right_index
if largest != index:
unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
"""
Pure implementation of the heap sort algorithm in Python
:param collection: some mutable ordered collection with heterogeneous
comparable items inside
:return: the same collection ordered by ascending
"""
n = len(unsorted)
for i in range(n // 2 - 1, -1, -1):
heapify(unsorted, i, n)
for i in range(n - 1, 0, -1):
unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
heapify(unsorted, 0, i)
return unsorteddef mdc(a, b):
"""Calculate Maior divisor comum (MDC)."""
return b if a == 0 else mdc(b % a, a)def merge(a,b,m,e):
l=a[b:m+1]
r=a[m+1:e+1]
k=b
i=0
j=0
while i<len(l) and j<len(r):
#change sign for Descending order
if l[i]<r[j]:
a[k]=l[i]
i+=1
else:
a[k]=r[j]
j+=1
k+=1
while i<len(l):
a[k]=l[i]
i+=1
k+=1
while j<len(r):
a[k]=r[j]
j+=1
k+=1
return a
def mergesort(a,b,e):
"""
>>> mergesort([3,2,1],0,2)
[1, 2, 3]
>>> mergesort([3,2,1,0,1,2,3,5,4],0,8)
[0, 1, 1, 2, 2, 3, 3, 4, 5]
"""
if b<e:
m = (b+e)//2
#print("ms1",a,b,m)
mergesort(a,b,m)
#print("ms2",a,m+1,e)
mergesort(a,m+1,e)
#print("m",a,b,m,e)
merge(a,b,m,e)
return adef prime_check(number):
"""
Check to See if a Number is Prime.
A number is prime if it has exactly two dividers: 1 and itself.
"""
if number < 2:
# Negatives, 0 and 1 are not primes
return False
if number < 4:
# 2 and 3 are primes
return True
if number % 2 == 0:
# Even values are not primes
return False
# Except 2, all primes are odd. If any odd value divide
# the number, then that number is not prime.
odd_numbers = range(3, int(math.sqrt(number)) + 1, 2)
return not any(number % i == 0 for i in odd_numbers)"""
Created on Thu Oct 5 16:44:23 2017
@author: Christian Bender
This python library contains some useful functions to deal with
prime numbers and whole numbers.
Overview:
isPrime(number)
sieveEr(N)
getPrimeNumbers(N)
primeFactorization(number)
greatestPrimeFactor(number)
smallestPrimeFactor(number)
getPrime(n)
getPrimesBetween(pNumber1, pNumber2)
----
isEven(number)
isOdd(number)
getDivisors(number) // all divisors of 'number' inclusive 1, number
isPerfectNumber(number)
NEW-FUNCTIONS
simplifyFraction(numerator, denominator)
"""
from math import sqrt
def isPrime(number):
"""
input: positive integer 'number'
returns true if 'number' is prime otherwise false.
"""
# precondition
assert isinstance(number, int) and (
number >= 0
), "'number' must been an int and positive"
status = True
# 0 and 1 are none primes.
if number <= 1:
status = False
for divisor in range(2, int(round(sqrt(number))) + 1):
# if 'number' divisible by 'divisor' then sets 'status'
# of false and break up the loop.
if number % divisor == 0:
status = False
break
# precondition
assert isinstance(status, bool), "'status' must been from type bool"
return status
# ------------------------------------------
def sieveEr(N):
"""
input: positive integer 'N' > 2
returns a list of prime numbers from 2 up to N.
This function implements the algorithm called
sieve of erathostenes.
"""
# precondition
assert isinstance(N, int) and (N > 2), "'N' must been an int and > 2"
# beginList: conatins all natural numbers from 2 upt to N
beginList = [x for x in range(2, N + 1)]
ans = [] # this list will be returns.
# actual sieve of erathostenes
for i in range(len(beginList)):
for j in range(i + 1, len(beginList)):
if (beginList[i] != 0) and (beginList[j] % beginList[i] == 0):
beginList[j] = 0
# filters actual prime numbers.
ans = [x for x in beginList if x != 0]
# precondition
assert isinstance(ans, list), "'ans' must been from type list"
return ans
# --------------------------------
def getPrimeNumbers(N):
"""
input: positive integer 'N' > 2
returns a list of prime numbers from 2 up to N (inclusive)
This function is more efficient as function 'sieveEr(...)'
"""
# precondition
assert isinstance(N, int) and (N > 2), "'N' must been an int and > 2"
ans = []
# iterates over all numbers between 2 up to N+1
# if a number is prime then appends to list 'ans'
for number in range(2, N + 1):
if isPrime(number):
ans.append(number)
# precondition
assert isinstance(ans, list), "'ans' must been from type list"
return ans
# -----------------------------------------
def primeFactorization(number):
"""
input: positive integer 'number'
returns a list of the prime number factors of 'number'
"""
# precondition
assert isinstance(number, int) and number >= 0, "'number' must been an int and >= 0"
ans = [] # this list will be returns of the function.
# potential prime number factors.
factor = 2
quotient = number
if number == 0 or number == 1:
ans.append(number)
# if 'number' not prime then builds the prime factorization of 'number'
elif not isPrime(number):
while quotient != 1:
if isPrime(factor) and (quotient % factor == 0):
ans.append(factor)
quotient /= factor
else:
factor += 1
else:
ans.append(number)
# precondition
assert isinstance(ans, list), "'ans' must been from type list"
return ans
# -----------------------------------------
def greatestPrimeFactor(number):
"""
input: positive integer 'number' >= 0
returns the greatest prime number factor of 'number'
"""
# precondition
assert isinstance(number, int) and (
number >= 0
), "'number' bust been an int and >= 0"
ans = 0
# prime factorization of 'number'
primeFactors = primeFactorization(number)
ans = max(primeFactors)
# precondition
assert isinstance(ans, int), "'ans' must been from type int"
return ans
# ----------------------------------------------
def smallestPrimeFactor(number):
"""
input: integer 'number' >= 0
returns the smallest prime number factor of 'number'
"""
# precondition
assert isinstance(number, int) and (
number >= 0
), "'number' bust been an int and >= 0"
ans = 0
# prime factorization of 'number'
primeFactors = primeFactorization(number)
ans = min(primeFactors)
# precondition
assert isinstance(ans, int), "'ans' must been from type int"
return ans
# ----------------------
def isEven(number):
"""
input: integer 'number'
returns true if 'number' is even, otherwise false.
"""
# precondition
assert isinstance(number, int), "'number' must been an int"
assert isinstance(number % 2 == 0, bool), "compare bust been from type bool"
return number % 2 == 0
# ------------------------
def isOdd(number):
"""
input: integer 'number'
returns true if 'number' is odd, otherwise false.
"""
# precondition
assert isinstance(number, int), "'number' must been an int"
assert isinstance(number % 2 != 0, bool), "compare bust been from type bool"
return number % 2 != 0
def getPrime(n):
"""
Gets the n-th prime number.
input: positive integer 'n' >= 0
returns the n-th prime number, beginning at index 0
"""
# precondition
assert isinstance(n, int) and (n >= 0), "'number' must been a positive int"
index = 0
ans = 2 # this variable holds the answer
while index < n:
index += 1
ans += 1 # counts to the next number
# if ans not prime then
# runs to the next prime number.
while not isPrime(ans):
ans += 1
# precondition
assert isinstance(ans, int) and isPrime(
ans
), "'ans' must been a prime number and from type int"
return ans
# ---------------------------------------------------
def getPrimesBetween(pNumber1, pNumber2):
"""
input: prime numbers 'pNumber1' and 'pNumber2'
pNumber1 < pNumber2
returns a list of all prime numbers between 'pNumber1' (exclusiv)
and 'pNumber2' (exclusiv)
"""
# precondition
assert (
isPrime(pNumber1) and isPrime(pNumber2) and (pNumber1 < pNumber2)
), "The arguments must been prime numbers and 'pNumber1' < 'pNumber2'"
number = pNumber1 + 1 # jump to the next number
ans = [] # this list will be returns.
# if number is not prime then
# fetch the next prime number.
while not isPrime(number):
number += 1
while number < pNumber2:
ans.append(number)
number += 1
# fetch the next prime number.
while not isPrime(number):
number += 1
# precondition
assert (
isinstance(ans, list) and ans[0] != pNumber1 and ans[len(ans) - 1] != pNumber2
), "'ans' must been a list without the arguments"
# 'ans' contains not 'pNumber1' and 'pNumber2' !
return ans
# ----------------------------------------------------
def getDivisors(n):
"""
input: positive integer 'n' >= 1
returns all divisors of n (inclusive 1 and 'n')
"""
# precondition
assert isinstance(n, int) and (n >= 1), "'n' must been int and >= 1"
ans = [] # will be returned.
for divisor in range(1, n + 1):
if n % divisor == 0:
ans.append(divisor)
# precondition
assert ans[0] == 1 and ans[len(ans) - 1] == n, "Error in function getDivisiors(...)"
return ans
# ----------------------------------------------------
def isPerfectNumber(number):
"""
input: positive integer 'number' > 1
returns true if 'number' is a perfect number otherwise false.
"""
# precondition
assert isinstance(number, int) and (
number > 1
), "'number' must been an int and >= 1"
divisors = getDivisors(number)
# precondition
assert (
isinstance(divisors, list)
and (divisors[0] == 1)
and (divisors[len(divisors) - 1] == number)
), "Error in help-function getDivisiors(...)"
# summed all divisors up to 'number' (exclusive), hence [:-1]
return sum(divisors[:-1]) == number
# ------------------------------------------------------------
def simplifyFraction(numerator, denominator):
"""
input: two integer 'numerator' and 'denominator'
assumes: 'denominator' != 0
returns: a tuple with simplify numerator and denominator.
"""
# precondition
assert (
isinstance(numerator, int)
and isinstance(denominator, int)
and (denominator != 0)
), "The arguments must been from type int and 'denominator' != 0"
# build the greatest common divisor of numerator and denominator.
gcdOfFraction = gcd(abs(numerator), abs(denominator))
# precondition
assert (
isinstance(gcdOfFraction, int)
and (numerator % gcdOfFraction == 0)
and (denominator % gcdOfFraction == 0)
), "Error in function gcd(...,...)"
return (numerator // gcdOfFraction, denominator // gcdOfFraction)