如何在仅支持加法、乘法、比较与相等性操作的非零自然数类中实现模运算(%)？

First, let's clarify the expected behavior given your constraints (natural numbers are {1,2,3,...}, no zero allowed, only addition, multiplication, <, and == permitted):

• If a < b: Return a (since you can't subtract b from a without leaving the natural set, so the remainder is just a).
• If a == b: Return a (per @JaMiT's suggestion for this edge case).
• If a > b:
  • Find the largest multiple of b that's less than a (let's call this current_multiple).
  • If a is exactly a multiple of b (i.e., current_multiple + b == a), return b (since zero isn't allowed, this is the natural replacement for the usual zero remainder).
  • Otherwise, find the smallest natural number r such that current_multiple + r == a—this r is your remainder (it will be between 1 and b-1, which is valid).

Here's the implementation of __mod__ that follows these rules, using only allowed operations:

def __mod__(self, other):
    """
    Compute a % b for Natural numbers (exclusive of 0), using only allowed operations.
    """
    assert isinstance(other, Natural), "other must be a Natural"
    
    # Case 1: self is smaller than the divisor, remainder is self
    if self < other:
        return self
    
    # Case 2: self equals the divisor, return self per @JaMiT's suggestion
    if self == other:
        return self
    
    # Case 3: self is larger than the divisor
    current_multiple = other
    next_multiple = current_multiple + other
    
    # Find the largest multiple of 'other' that's less than 'self'
    while next_multiple < self:
        current_multiple = next_multiple
        next_multiple = next_multiple + other
    
    # If self is exactly a multiple of 'other', return 'other' (since 0 is invalid)
    if next_multiple == self:
        return other
    
    # Find r where current_multiple + r = self
    r = Natural(1)
    temp = current_multiple + r
    
    while temp < self:
        r = r + Natural(1)
        temp = temp + Natural(1)
    
    return r

Test Cases #

Let's verify this works with your sample and other edge cases:

• Natural(7) % Natural(2) returns 1 (correct, since 7 = 3*2 +1).
• Natural(4) % Natural(2) returns 2 (since 4 is exactly 2*2, and zero isn't allowed).
• Natural(5) % Natural(3) returns 2 (5=1*3+2).
• Natural(3) % Natural(5) returns 3 (since 3 <5).
• Natural(6) % Natural(3) returns 3 (exact multiple case).
• Natural(7) % Natural(7) returns 7 (matches @JaMiT's suggestion).

This approach stays strictly within your constraints—no subtraction or division, only addition, comparisons, and equality checks. It handles all edge cases while keeping results within the natural number set.

内容的提问来源于stack exchange，提问作者Jasper