如何让Python选择符合要求的最大随机值？

Question

所以我正在尝试编写一个程序，选择分子和分母之和等于 n 的最大不可约真分数。这是我目前所拥有的：

import random


def fraction(n): 
    if n < 3 or n > 10 ** 12:
        error_message = 'n must lie in the range (3; 10^12)'
        print(error_message)
    while True: # cycle for repeated variable checking
        if n >= 3 or n <= 10 ** 12:
            b = random.randint(2, 100) # generating two random numbers a and b, where a is the nominator and b the denominator
            a = random.randint(2, 100) # the range is shortened for testing
        if a + b != n: # continue picking random ints until they fit
            continue
        if a + b == n:
            if a != b and a < b: # if a=b the fraction is reducible and doesn't fit, and if a>b it is improper and doesn't fit either
                print(str(a) + '/' + str(b)) # printing an appropriate ordinary fraction
            else:
                continue
        break


n = int(input('n: '))
fraction(n)

困难在于：当我开始测试更大的 n 个数字（如 12）时，输出不同，有些分数小于其他分数，而我只需要最大的一个。有什么办法可以让 Python 选择这样的分数吗？

Answer 1

要找到最大的一个，您不需要随机生成分子和分母。只需从(n - 1) // 2开始向下循环分子a，使分母b = n - a，如果math.gcd(a, b) == 1（读Greated Common Divisor）那么我们找到最大的不可约真分数a / b.

这是因为任何分数最多可以减少分子和分母的最大公约数（GCD）。如果 GCD 为 1，则它是不可约的。

在我的代码中，如果返回元组 (0, n)，则表示没有答案，换句话说，给定 n 没有解决方案。您也可以 return None 而不是最后一行的 return 0, n。

Try it online!

import math

def fraction(n):
    for a in range((n - 1) // 2, -1, -1):
        b = n - a
        if math.gcd(a, b) == 1:
            return a, b
    return 0, n

# Doing some tests below

for i, n in enumerate(range(100)):
    f = fraction(n)
    print(f'n {n:>2} frac {f[0]:>2}/{f[1]:>2}  |  ', end = '')
    if (i + 1) % 4 == 0:
        print()

输出：

n  0 frac  0/ 0  |  n  1 frac  0/ 1  |  n  2 frac  0/ 2  |  n  3 frac  1/ 2
n  4 frac  1/ 3  |  n  5 frac  2/ 3  |  n  6 frac  1/ 5  |  n  7 frac  3/ 4
n  8 frac  3/ 5  |  n  9 frac  4/ 5  |  n 10 frac  3/ 7  |  n 11 frac  5/ 6
n 12 frac  5/ 7  |  n 13 frac  6/ 7  |  n 14 frac  5/ 9  |  n 15 frac  7/ 8
n 16 frac  7/ 9  |  n 17 frac  8/ 9  |  n 18 frac  7/11  |  n 19 frac  9/10
n 20 frac  9/11  |  n 21 frac 10/11  |  n 22 frac  9/13  |  n 23 frac 11/12
n 24 frac 11/13  |  n 25 frac 12/13  |  n 26 frac 11/15  |  n 27 frac 13/14
n 28 frac 13/15  |  n 29 frac 14/15  |  n 30 frac 13/17  |  n 31 frac 15/16
n 32 frac 15/17  |  n 33 frac 16/17  |  n 34 frac 15/19  |  n 35 frac 17/18
n 36 frac 17/19  |  n 37 frac 18/19  |  n 38 frac 17/21  |  n 39 frac 19/20
n 40 frac 19/21  |  n 41 frac 20/21  |  n 42 frac 19/23  |  n 43 frac 21/22
n 44 frac 21/23  |  n 45 frac 22/23  |  n 46 frac 21/25  |  n 47 frac 23/24
n 48 frac 23/25  |  n 49 frac 24/25  |  n 50 frac 23/27  |  n 51 frac 25/26
n 52 frac 25/27  |  n 53 frac 26/27  |  n 54 frac 25/29  |  n 55 frac 27/28
n 56 frac 27/29  |  n 57 frac 28/29  |  n 58 frac 27/31  |  n 59 frac 29/30
n 60 frac 29/31  |  n 61 frac 30/31  |  n 62 frac 29/33  |  n 63 frac 31/32
n 64 frac 31/33  |  n 65 frac 32/33  |  n 66 frac 31/35  |  n 67 frac 33/34
n 68 frac 33/35  |  n 69 frac 34/35  |  n 70 frac 33/37  |  n 71 frac 35/36
n 72 frac 35/37  |  n 73 frac 36/37  |  n 74 frac 35/39  |  n 75 frac 37/38
n 76 frac 37/39  |  n 77 frac 38/39  |  n 78 frac 37/41  |  n 79 frac 39/40
n 80 frac 39/41  |  n 81 frac 40/41  |  n 82 frac 39/43  |  n 83 frac 41/42
n 84 frac 41/43  |  n 85 frac 42/43  |  n 86 frac 41/45  |  n 87 frac 43/44
n 88 frac 43/45  |  n 89 frac 44/45  |  n 90 frac 43/47  |  n 91 frac 45/46
n 92 frac 45/47  |  n 93 frac 46/47  |  n 94 frac 45/49  |  n 95 frac 47/48
n 96 frac 47/49  |  n 97 frac 48/49  |  n 98 frac 47/51  |  n 99 frac 49/50

您还可以通过记住最大值 a 来稍微修改您的变体，过滤掉 a 小于当前最大值或 gcd(a, b) > 1 的结果。然后，如果给定足够的时间，您的随机解决方案在大多数情况下也可能有效，尽管它当然很慢。

在下面尝试修改后的代码。如果找不到更大的分数，它会反复打印越来越大的分数，直到它冻结很长时间。

Try it online!

import random, math

def fraction(n): 
    if n < 3 or n > 10 ** 12:
        error_message = 'n must lie in the range (3; 10^12)'
        print(error_message)
    amax = -1
    while True: # cycle for repeated variable checking
        if n >= 3 or n <= 10 ** 12:
            b = random.randint(1, n) # generating two random numbers a and b, where a is the nominator and b the denominator
            a = random.randint(1, n) # the range is shortened for testing
        if a + b != n: # continue picking random ints until they fit
            continue
        if a + b == n:
            if a != b and a < b and a > amax: # if a=b the fraction is reducible and doesn't fit, and if a>b it is improper and doesn't fit either
                if math.gcd(a, b) == 1:
                    print(str(a) + '/' + str(b)) # printing an appropriate ordinary fraction
                    amax = a
            else:
                continue

n = int(input('n: '))
fraction(n)

输出：

如何让Python选择符合要求的最大随机值？

How do I make Python choose the largest random value which fits the requirements?

python

random

algorithm

max