0

我在这个考试复习问题上空白，有人可以帮我开始吗？在 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 ] + " ]" );
    }
}
4

2 回答 2

1

他们给了你伪代码。只需按照它所说的去做。首先将说明改为逐步进行。

  1. 将此条目的值（如果它是有效条目）与条目“minPosSoFar”中的值进行比较。
  2. 如果这个值更小，那么这个条目现在是“minPosSoFar”。
  3. 对数组的其余部分进行递归。

所以：

private static int findMinPos( int[] data, int cur, int minPosSoFar )
{
  if (cur < data.length) { // Needed for stopping at the end of the array
    if (data[cur] < data[minPosSoFar]) { // 1.
      minPosSoFar = cur; // 2.
    }
    return findMinPos(data, cur+1, minPosSoFar); // 3.
  }
  return minPosSoFar;
}

因为这是给学校的，我不想为你做所有的事情，希望这会给你一个好主意。

于 2013-05-08T13:49:59.757 回答
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 块中的多个 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;
}
于 2013-05-08T14:05:57.910 回答