离散数学第三章算法之PHP实现

离散数学第三章算法之PHP实现

1. 有限序列中最大元素

2. 线性搜索 （Linear Search）

3. 二分搜索 （Binary Search）

4. 冒泡排序 （Bubble Sort）

5. 插入排序 （Inser Sort）

6. 贪心算法 （Greedy Algorithm）

1. 有限序列中最大元素

$num = [5, 2, 3, 300, 50, 5, 10, 40, 100];

$max = $num[0];

for ($i = 0; $i < count($num); $i++) {

    if ($max < $num[$i]) {
        $max = $num[$i];
    }
}

echo "<h2>有限序列中最大元素的</h2>";
echo "Max Number: {$max}";

2. 线性搜索

$num = [1, 2, 3, 4, 6, 7, 8, 9, 10, 5, 100, 210];
$find = 3;

function linearSearch($list, $data) {
    $count = count($list);

    for ($i = 0; $i < $count; $i++) {
        if ($data == $list[$i]) {
            return $i;
        }
    }
    return 0;
}

$index = linearSearch($num, $find);
echo "Index: {$index}";

3. 二分搜索

$num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
$find = 11;

function binarySearch($list, $data) {
    $low = 0;
    $high = count($list) - 1;

    while ( $low <= $high) {

        $mid = floor(($low + $high) / 2 );
        
        if ($list[$mid] < $data ) { // $data > $list[$mid]
            $low = $mid + 1;
        } else if($list[$mid] > $data) { //$data < $list[$mid]
            $high = $mid - 1;
        } else {
            return $mid;
        }

    }

    return 0;
}

$binaryIndex = binarySearch($num, $find);

echo "BinaryIndex {$binaryIndex}";

4. 冒泡排序

function bubbleSort($list) {
    $count = count($list) - 1;

    for ($i = 0; $i < $count; $i++)
        for ($j = 0; $j < $count - $i; $j++) {
            if ($list[$j] > $list[$j + 1]) {
                $a = $list[$j];
                $tmp = $list[$j];
                $b = $list[$j + 1];

                $a = $b; 
                $list[$j] = $a;

                $b = $tmp;
                $list[$j+1] = $b;
        }
    }
    return $list;       
}

$bubbleSortArray = [9, 7, 5, 4, 10, 3030, 19, 1100, 300, 1 ];
bubbleSort($num);

echo "<br> Bubble Sort";

5. 插入排序

$insertSortNum = [6, 3,  5];

function insertSort($list) {
    $count = count($list);

    for ($i = 1; $i < $count; $i++) {
        $j = $i;
        
        while ($j>0 && $list[$j - 1] > $list[$j] ) {
            $a = $list[$j]; // 3
            $tmp = $list[$j];
            $b = $list[$j - 1]; // 6

            $list[$j - 1]  = $a;
            $list[$j] = $b;
            
            $j--;
        }

    }

    return $list;

}

echo "<br> Insert Sort: <br>";
var_export(insertSort($insertSortNum));

6. 贪心算法

$change = [25, 10, 5, 1];
//$change = [1, 5, 10, 25];

function greedyAlgo($list, $num) {
    $change = [];
    $total = 0;

    //for ($i = count($list) - 1; $i >= 0; $i--) {
    for ($i = 0; $i < count($list); $i++) {
        $coin = $list[$i];
        while ($total + $coin <= $num) {
            array_push($change, $coin);
            $total += $coin;
        }
    }

    return $change;
}

var_dump(greedyAlgo($change, 66));

7. 要点总结