如何讓Python選擇符合要求的最大隨機值？

所以我正在嘗試撰寫一個程式，該程式選擇分子和分母之和等于 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 選擇這樣的分數？

uj5u.com熱心網友回復：

要找到最大的一個，您不需要隨機生成分子和分母。只需a從 開始向下回圈分子(n - 1) // 2，使分母b = n - a和如果math.gcd(a, b) == 1（閱讀Greated Common Divisor）然后我們找到最大的不可約真分數a / b。

任何分數最多可以通過分子和分母的最大公約數 (GCD) 減少這一事實。如果 GCD 為 1，則它是不可約的。

在我的代碼中，如果(0, n)回傳tuple則意味著沒有答案，換句話說，沒有針對 given 的解決方案n。你也可以return None代替return 0, n最后一行。

在線試試吧！

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。然后，如果有足夠的時間，您的隨機解決方案在大多數情況下也可能有效，盡管它當然很慢。

在下面嘗試修改后的代碼。如果找不到更大的分數，它會迭代列印越來越大的分數，直到它凍結很長時間。

在線試試吧！

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)

輸出：

n: 456
67/389
127/329
179/277
185/271
211/245
215/241
221/235
223/233
227/229

標籤：Python 算法 随机的 最大限度

上一篇：分明滅燈

下一篇：查找在其他陣列中重復的陣列