YouTip

## C Programming: The "Five Fish" Sharing Problem This tutorial explains how to solve the classic mathematical puzzle known as the **"Five Fish" (五人分鱼)** problem using the C programming language. This is a classic recursive division problem that demonstrates how to use loops, conditional statements, and basic arithmetic operations in C to find a brute-force solution. --- ### Problem Description Five people—A, B, C, D, and E—went fishing together one night. By dawn, they were exhausted, so they decided to go to sleep. 1. **Person A** woke up first. He divided the total catch of fish into five equal portions, found there was **one extra fish**, threw the extra fish away, took his one-fifth share, and went back to sleep. 2. **Person B** woke up second. Unaware of what A had done, he divided the remaining fish into five equal portions, found there was **one extra fish**, threw it away, took his one-fifth share, and went back to sleep. 3. **Persons C, D, and E** woke up one after another and repeated the exact same process (dividing the remaining fish into five portions, throwing away the one leftover fish, and taking their share). **Questions:** * What is the minimum number of fish they could have caught in total? * How many fish did each person see when they woke up? --- ### Mathematical Logic & Algorithm Design Let $n$ be the initial number of fish. * For **A** to divide the fish, the total number of fish $n$ must satisfy: $$n \equiv 1 \pmod 5$$ After A throws away 1 fish and takes $\frac{1}{5}$ of the remainder, the remaining fish $j$ is: $$j = \frac{4 \times (n - 1)}{5}$$ * For **B** to divide the fish, the remaining fish $j$ must also satisfy: $$j \equiv 1 \pmod 5$$ The remaining fish $k$ after B's turn is: $$k = \frac{4 \times (j - 1)}{5}$$ * This pattern continues for **C**, **D**, and **E**. Each person must find that the number of fish they see ($x$) satisfies $x \equiv 1 \pmod 5$. We can solve this in C by starting with a minimum guess of $n = 5$ and incrementing $n$ by 1 in an infinite loop until we find the first value of $n$ that satisfies the condition for all five people. --- ### C Source Code Implementation Below is the complete C program to solve the "Five Fish" problem. ```c #include int main() { int n; // Total initial fish caught int j, k, l, m; // Remaining fish seen by B, C, D, and E respectively // Start searching from 5 fish upwards for (n = 5; ; n++) { // Calculate the remaining fish after each person takes their share j = 4 * (n - 1) / 5; // Remaining fish after A takes their share k = 4 * (j - 1) / 5; // Remaining fish after B takes their share l = 4 * (k - 1) / 5; // Remaining fish after C takes their share m = 4 * (l - 1) / 5; // Remaining fish after D takes their share // Check if the division condition (remainder of 1 when divided by 5) // is met at every single step for all 5 people. if (n % 5 == 1 && j % 5 == 1 && k % 5 == 1 && l % 5 == 1 && m % 5 == 1) { printf("Minimum total fish caught: %d\n", n); printf("Fish seen by B, C, D, and E respectively: %d, %d, %d, %d\n", j, k, l, m); break; // Exit the loop once the minimum solution is found } } return 0; } ``` --- ### Output Analysis When you compile and run the program, it produces the following output: ```text Minimum total fish caught: 3121 Fish seen by B, C, D, and E respectively: 2496, 1996, 1596, 1276 ``` #### Step-by-Step Verification: 1. **Initial Catch ($n$):** **3121** fish. 2. **Person A** wakes up, sees 3121 fish. $(3121 - 1) / 5 = 624$ fish per share. A throws away 1, takes 624, leaving **2496** fish ($j$). 3. **Person B** wakes up, sees 2496 fish. $(2496 - 1) / 5 = 499$ fish per share. B throws away 1, takes 499, leaving **1996** fish ($k$). 4. **Person C** wakes up, sees 1996 fish. $(1996 - 1) / 5 = 399$ fish per share. C throws away 1, takes 399, leaving **1596** fish ($l$). 5. **Person D** wakes up, sees 1596 fish. $(1596 - 1) / 5 = 319$ fish per share. D throws away 1, takes 319, leaving **1276** fish ($m$). 6. **Person E** wakes up, sees 1276 fish. $(1276 - 1) / 5 = 255$ fish per share. E throws away 1, takes 255, leaving **1020** fish. Every step yields a perfect integer division with a remainder of exactly 1, validating the solution. --- ### Considerations & Optimization * **Brute-Force Efficiency:** While a brute-force `for` loop starting from 5 and incrementing by 1 works quickly for this specific problem, it can be optimized. Since the initial number of fish $n$ must leave a remainder of 1 when divided by 5 ($n \equiv 1 \pmod 5$), you can initialize `n = 6` and increment by `5` in each iteration (`n += 5`) to significantly reduce the number of loop cycles. * **Integer Division:** In C, the `/` operator performs integer division (truncating the decimal part). The code relies on the `if` statement's modulo checks (`% 5 == 1`) to ensure that the division at each step is mathematically exact before accepting the result.