lineaire-combinatie-van-2-getallen
Gesponsorde koppelingen
PHP script bestanden
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
<?php
/** Getting the greatest common divisor of $a and $b:
$a = $b * $x + $q
@param integer, see above
@param integer, see above
@param reference to $x (Array), so those can be stored
@return return the $q, always 1 or 0
@require $a > $b, $a && $b to be integer, $x != null, $x == Array()
@ensure return = 0 or 1, &$x has all $x versions stored like this:
$x[0] = $x from first line $a = $b * $x + $q
$x[1] = $x from second line $a = $b * $x + $q
@info This function is recursive
*/
function getGCD($a,$b,&$x) {
$new_b = $a % $b;
$x[count($x)] = floor($a / $b);
return ($new_b == 0 || $new_b == 1) ? $new_b : getGCD($b,$new_b,$x);
}
/** Printing the lineair combination of $a and $b
(0 || 1) = $y[0]*$a + $y[1]*$b;
@param integer, see above
@param integer, see above
@return null
@require $a > $b, $a && $b to be integer
@ensure print as above is correct and is the lineair combination of $a and $b
*/
function LineairCombination($a,$b) {
$x = Array();
$y = Array(1,0);
$gcd = getGCD($a,$b,$x);
for($i = count($x)-1; $i >= 0; $i--)
if ($i % 2 == 0)
$y[1] = $y[1] + $y[0] * -1 * $x[$i];
else
$y[0] = $y[0] + $y[1] * -1 * $x[$i];
printf("%d = %d x %d %d x %d",$gcd,$y[0],$a,$y[1],$b);
}
// just a test
(isset($_GET['a']) && isset($_GET['b'])) ? LineairCombination($_GET['a'],$_GET['b']) : LineairCombination(42,11);
?>
/** Getting the greatest common divisor of $a and $b:
$a = $b * $x + $q
@param integer, see above
@param integer, see above
@param reference to $x (Array), so those can be stored
@return return the $q, always 1 or 0
@require $a > $b, $a && $b to be integer, $x != null, $x == Array()
@ensure return = 0 or 1, &$x has all $x versions stored like this:
$x[0] = $x from first line $a = $b * $x + $q
$x[1] = $x from second line $a = $b * $x + $q
@info This function is recursive
*/
function getGCD($a,$b,&$x) {
$new_b = $a % $b;
$x[count($x)] = floor($a / $b);
return ($new_b == 0 || $new_b == 1) ? $new_b : getGCD($b,$new_b,$x);
}
/** Printing the lineair combination of $a and $b
(0 || 1) = $y[0]*$a + $y[1]*$b;
@param integer, see above
@param integer, see above
@return null
@require $a > $b, $a && $b to be integer
@ensure print as above is correct and is the lineair combination of $a and $b
*/
function LineairCombination($a,$b) {
$x = Array();
$y = Array(1,0);
$gcd = getGCD($a,$b,$x);
for($i = count($x)-1; $i >= 0; $i--)
if ($i % 2 == 0)
$y[1] = $y[1] + $y[0] * -1 * $x[$i];
else
$y[0] = $y[0] + $y[1] * -1 * $x[$i];
printf("%d = %d x %d %d x %d",$gcd,$y[0],$a,$y[1],$b);
}
// just a test
(isset($_GET['a']) && isset($_GET['b'])) ? LineairCombination($_GET['a'],$_GET['b']) : LineairCombination(42,11);
?>