java - 使用递归将数组最小值的伪代码转换为 Java 代码

Question

我对这个考试复习题一片空白，有人可以帮助我开始吗？在 findMinPos 中，我对三个参数感到困惑，如何访问数据数组中的节点？即使它是递归方法，我也可以使用循环吗？

public class ArraySwapMin
{
    public static void swapMin( int[] data, int cur )  
    {   
        int min = findMinPos( data, cur, cur );
        /////////////////////////////////////////////////////////////
        // swap the min position value with the one in the cur position
        ////////////////////////////////////////////////////////////////
    } 
    /**
     * Check the nodes in "data" from position "start" to the end of the array.
     * to see if any value in this part of the array is less than the min
     * value found so far (up to the "cur" position).
     */ 
    private static int findMinPos( int[] data, int cur, int minPosSoFar )
    {
        //////////////////////////////////////////////////////////////
        // Compare this entry's value (if it is a valid entry) with the
        // value in the entry "minPosSoFar". If this value is less, then 
        // this entry is now the "minPosSoFar". 
        // Recurse for the rest of the array.
        ///////////////////////////////////////////////////////////////


           return minPosSoFar;
    }

    /**
     * unit tester
     */
    public static void  main( String[] args )
    {
        int[] data = { 12, 3, 10, 5, 1, 8 };

        int count = 0;
        System.out.println( "++++++++++++++++ ArraySwapMin ++++++++++++++++" );
        printArray( "starting array ", data );

        for ( int i = 0; i < data.length - 1; i++ )
        {
            swapMin( data, i );
            printArray( "swap Min with " + i, data );
        }

    }
    public static void printArray( String label, int[] data )
    {
        System.out.print( label + ": [ " );
        for ( int i = 0; i < data.length - 1; i++ )
            System.out.print( data[ i ] + ", " );
        System.out.println( data[ data.length - 1 ] + " ]" );
    }
}

Answer 1

在 swapMin() 中，您必须将当前位置与最小值切换。

public static void swapMin( int[] data, int cur )  
{   
    int min = findMinPos( data, cur, cur );

    int minValue = data[min];
    data[min] = data[cur];
    data[cur] = minValue;
}

最小值将在findMinPos()中递归确定。递归编程的整个思想是使用内部方法调用的返回值而不是使用循环。您需要的是一个整体中断条件(在您的情况下是数组的长度)并且通常是多个返回语句。

这里的这个就可以解决问题:

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
    if(cur < data.length)
    {
        if(data[cur] < data[minPosSoFar]) // set new minimum to position cur
        {
            return findMinPos(data, cur + 1, cur);
        }
        else // keep old minimum
        {
            return findMinPos(data, cur + 1, minPosSoFar);
        }
    }

    return minPosSoFar;
}

由于 if-else block 中的多个 return 语句使代码又长又乱，您可以像这样缩短它

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
    if(cur < data.length)
    {
        return (data[cur] < data[minPosSoFar]) ? 
            findMinPos(data, cur + 1, cur) :
            findMinPos(data, cur + 1, minPosSoFar);
    }

    return minPosSoFar;
}