php - 如何通过递归重新分配值？

Question

给定一个层次结构(如轮廓)，其中每个级别都由一个整数表示(例如，第一级为 0，第二级为 1，并且在任何时候您都可以在较早的级别开始一个新点)，我想重新分配整数，以便不跳过数字，但同时尊重原始关系。我将输入表示为数组:

$stuff = 数组(0,1,2,2,4,1,9,9,10,3,8,4);

所需的输出(当表示为数组时)是:

$stuff = 数组(0,1,2,2,3,1,2,2,3,2,3,3);

规则是:

• 如果给定值与最近的先验值相同，则输出值应与最近的先验值的输出值相同
• 如果给定值比最近的先验值更高(即更深)，则输出值应比最近的先验值的输出值大 1
• 如果给定值低于(即浅)于最近的先验值，则找到小于给定值的最近的先验值，并且输出值应比该值大 1。

我想到的唯一方法是通过递归。我可以让它适用于上述输入数组中除最后一种情况之外的所有情况。如果我将输入数组中的最后一个案例更改为“5”而不是“4”，那么它就可以工作。

这是我正在尝试的:

<?php

$input = array(0,1,2,2,4,1,9,9,10,3,8,4);
$debug = false;
for ($i =0; $i < count($input); $i++) {
    if ($debug) {
        echo '<hr />Old level: '.$input[$i];
        $newLevel = newLevel($input,$i,$input[$i],$debug);
        echo '<br />New level: '.$newLevel.'<br /><br /><br /><hr />';
    }
    else {
        echo 'Old level: '.$input[$i].'; New level: '.newLevel($input,$i,$input[$i],$debug).'<br />';
    }
}

function newLevel($input, $index,$origValue,$debug) {
    if ($index == 0) return 0;
    else {
        if ($input[$index] > $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/if';
            return newLevel($input,$index-1,$origValue,$debug)+1;
        }
        elseif ($input[$index] == $input[$index-1]) {
            if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif1';
            return newLevel($input,$index-1,$origValue,$debug);
        }
        elseif ($input[$index] < $input[$index-1]) {
            for ($i = $index-2; $i >= 0; $i--) {
                if ($input[$index] == $input[$i]) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/if';
                    return newLevel($input,$i,$origValue,$debug);
                }
                elseif ($input[$index] == ($input[$i] + 1)) {
                    if ($debug) echo '<br />Orig value: '.$origValue.' in else/elseif2/for/elseif';
                    return newLevel($input,$i,$origValue,$debug);
                }
            }
                die ("Error with going to outer level -- should never hit this.");
        }
    }
}

?>

这是我想要的输出:

Old level: 0; New level: 0
Old level: 1; New level: 1
Old level: 2; New level: 2
Old level: 2; New level: 2
Old level: 4; New level: 3
Old level: 1; New level: 1
Old level: 9; New level: 2
Old level: 9; New level: 2
Old level: 10; New level: 3
Old level: 3; New level: 2
Old level: 8; New level: 3
Old level: 4; New level: 3

但是我得到的输出有一个“2”代表最后一行的新级别。非常感谢任何帮助。

Answer 1

实际上，你根本不需要递归。您在没有使用递归的情况下很好地解释了您的算法，因此您的代码也不应该需要它。

这是我的算法版本，没有递归。

$original = array(0,1,2,2,4,1,9,9,10,3,8,4);
$revised = array();

foreach($original as $index=>$value) {
    $output = 0;
    $previous = false;

    if ($index > 0)
        $previous = $original[$index-1];

    if ($previous === false) 
        $output = 0;
    else if ($value == $previous)
        $output = $revised[$index-1];
    else if ($value > $previous)
        $output = $revised[$index-1] + 1;
    else {
        $output = 1; // worst case scenario
        for($rindex = $index-1; $rindex >= 0; $rindex--) {
            if ($value > $original[$rindex]) {
                $output = $revised[$rindex]+1;
                break;
            }
        }
    }

    $revised[] = $output;
}

echo "\n";
print_r($original);
print_r($revised);