Problem z PTwPZ Klub Kibica ze spoja (Python)

Question

Sędzia pokazuje błędną odpowiedź, W zadaniu wykorzystuję Trójkąt Pascala. Proszę o pomoc.

Zadanie: https://pl.spoj.com/problems/PTWPZ076/

Kod: https://pastebin.com/AJsvHAsm

def Factorial(var):
  fac = 1
 
  for i in range(2, var + 1, 1):
    fac *= i
 
  return fac
 
 
def Binomial_theorem(n, k):
  comb = Factorial(n) / ((Factorial(k)) * (Factorial(n - k)))
  return comb
 
tests = int(input())
 
while tests:
  fans, places = [int(fans) for fans in input().split()]
 
  ip = Binomial_theorem(fans, places)
  print(int(ip))
 
  tests -= 1

 

Answer 1

Musiałem porównać z poprawnymi wynikami, żeby zauważyć :) Bo to dość subtelny błąd.

comb = Factorial(n) / ((Factorial(k)) * (Factorial(n - k)))

`/` to w Pythonie dzielenie liczb rzeczywistych. To znaczy np '3/4' dałoby 0.75 (co oczywiście u Ciebie się zdarzyć nie może, ale nie zmienia faktu jak działa dzielenie). Ale dzielenie liczb rzeczywistych daje w wyniku liczby zmiennoprzecinkowe - a one mają ograniczoną precyzję. Tak więc:

a = 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000
b = 69237837345426015193166198943959583654468513190741907865600000000000000
>>> comb = a / b
>>> comb
1.8326241409425905e+18
>>> int(comb)
1832624140942590464

Ale gdy użyjesz dzielenia liczb całkowitych, tego problemu nie ma, bo nie przechodzisz po drodze przez liczby zmiennoprzecinkowe:

>>> comb = a // b
>>> comb
1832624140942590534

 

Comments

A swoją drogą, drobne uwagi:

for i in range(2, var + 1, 1):

ostatni argument jest tu niepotrzebny, bo jest domyślnie 1

while tests:
  (...)
  tests -= 1

Można zamienić na zwykłe

for i in range(tests):

A, no i funkcje w Pythonie zazwyczaj zaczynamy małą literą.

---

Przeszło! Dzięki wielkie :D