unsigned long long ullgcd(unsigned long long a, unsigned long long b) {
/* compute the greatest common divisor using Euclid's elegant method */
if (a < b)
return ullgcd(b, a);
else
if (b == 0)
return a;
else
return ullgcd(b, a % b);
}
double least_multiple(double *a, size_t n, double epsilon) {
for (double mult = 1;; mult += 1) {
size_t i;
unsigned long long div = 0;
for (i = 0; i < n; i++) {
double d = fabs(a[i] * mult);
unsigned long long v = round(d);
if (fabs(v - d) > epsilon)
break;
div = ullgcd(v, div);
}
if (i == n)
break;
}
/* mult is the smallest non zero integer that fits your goal.
the smallest multiplier is obtained by dividing it
by the greatest common divisor of the resulting integer array.
*/
return mult / div;
}
1.0，则我们将数字列表的最大公约数除以它。否则，我们返回唯一分母的乘积。import math
import operator
def f(arr):
epsilon = 4
fractions = [rat_approx(i, 16**epsilon) for i in arr]
# The denominators in the fraction conversion are all 1.0
if sum([denom for (num, denom) in fractions]) == len(fractions):
return 1.0 / gcd_of_many([num for (num, denom) in fractions])
else:
# Otherwise, return the product of unique denominators
return reduce(operator.mul, set([denom for (num, denom) in fractions]), 1)
def gcd(a, b):
if a < b:
return gcd(b, a)
elif b == 0:
return a;
else:
return gcd(b, a % b)
def gcd_of_many(arr):
result = arr[0]
for i in xrange(1, len(arr)):
result = gcd(result, arr[i])
return result
# Converted from
# https://rosettacode.org/wiki/Convert_decimal_number_to_rational#C
def rat_approx(f, md):
# a: continued fraction coefficients.
h = [0, 1, 0]
k = [1, 0, 0]
n = 1
neg = 0
num = 0
denom = 0
if md <= 1:
denom = 1
num = f
return num, denom
if f < 0:
neg = 1
f = -f
while f != math.floor(f):
n <<= 1
f *= 2
d = f
# continued fraction and check denominator each step
for i in xrange(65):
a = d // n if n else 0
if i and not a:
break
x = d
d = n
n = x % n
x = a;
if k[1] * a + k[0] >= md:
x = (md - k[0]) // k[1]
if x * 2 >= a or k[1] >= md:
i = 65
else:
break
h[2] = x * h[1] + h[0]
h[0] = h[1]
h[1] = h[2]
k[2] = x * k[1] + k[0]
k[0] = k[1]
k[1] = k[2]
denom = k[1]
num = -h[1] if neg else h[1]
return (num, denom)
输出：
f([8, 10])
=> 0.5
f([1.66667, 2.33333])
=> 3.0
5结尾的小数分数可以被表示为某个二的幂次方的整数：您的输入数据是不精确的，但有少数例外。 - greybeard