PHP प्रोग्राम: दो संख्याओं का बार-बार घटाव (यूक्लिडियन एल्गोरिदम)

बार-बार घटाव: GCD के लिए यूक्लिडियन एल्गोरिदम

उदाहरण

<?php
function repeated_sub($val_1, $val_2) {
    if ($val_1 % $val_2 == 0) {
        return floor((int)$val_1 / $val_2);
    }
    return floor((int)$val_1 / $val_2) + repeated_sub($val_2, $val_1 % $val_2);
}

$val_1 = 1000;
$val_2 = 189;
print_r("The repeated subtraction results in ");
echo repeated_sub($val_1, $val_2);
?>

आउटपुट

The repeated subtraction results in 18

एल्गोरिदम विश्लेषण

यह फंक्शन यूक्लिडियन एल्गोरिदम का एक वेरिएंट है जो GCD (ग्रेटेस्ट कॉमन डिवाइजर) ढूंढता है, लेकिन भागफलों का योग लौटाता है।

चरण दर चरण (1000, 189):

1. 1000 ÷ 189 = 5 शेष 55 → भागफल 5
2. 189 ÷ 55 = 3 शेष 24 → भागफल 3
3. 55 ÷ 24 = 2 शेष 7 → भागफल 2
4. 24 ÷ 7 = 3 शेष 3 → भागफल 3
5. 7 ÷ 3 = 2 शेष 1 → भागफल 2
6. 3 ÷ 1 = 3 शेष 0 → भागफल 3
7. योग: 5+3+2+3+2+3 = 18

सुधारा गया संस्करण

<?php
function euclideanQuotientSum(int $a, int $b): int {
    $a = abs($a);
    $b = abs($b);
    
    if ($b == 0) return 0;
    if ($a < $b) return euclideanQuotientSum($b, $a);
    
    $quotient = (int)($a / $b);
    $remainder = $a % $b;
    
    if ($remainder == 0) {
        return $quotient;
    }
    
    return $quotient + euclideanQuotientSum($b, $remainder);
}

// GCD के लिए मानक यूक्लिडियन एल्गोरिदम
function gcd(int $a, int $b): int {
    return $b == 0 ? abs($a) : gcd($b, $a % $b);
}

echo "Quotient sum: " . euclideanQuotientSum(1000, 189) . "\n"; // 18
echo "GCD: " . gcd(1000, 189) . "\n"; // 1
?>

उपयोग

• यह एल्गोरिदम कॉन्टिन्यूड फ्रैक्शन एक्सपैंशन में उपयोगी है
• GCD के लिए PHP का बिल्ट-इन: gmp_gcd() या कस्टम फंक्शन
• PHP 8.0+ में intdiv() इंटीजर डिवीजन के लिए