2

我会先说这是家庭作业。我只是在寻找一些指示。我一直在用这个来绞尽脑汁，而对于我的一生，我就是不明白。我们被要求找到列表中的最小元素。我知道我需要一个子列表，但在那之后我不确定。任何指针都会很棒。谢谢。

/** Find the minimum element in a list.
 * 
 * @param t a list of integers
 * 
 * @return the minimum element in the list
 */ 
  public static int min(List<Integer> t) { 
  if (t.size() == 1){ 
  return t.get(0); 
  } 
  else{ 
      List<Integer> u = t.subList(1, t.size());
4

5 回答 5

3

递归算法的要点是必须计算的所有内容都是通过返回值或附加参数完成的。在递归步骤的本地调用之外，您不应该有任何东西。

由于您必须找到最小元素，因此您应该考虑一些因素：

  • 由一个元素组成的列表的最小元素是那个元素
  • 通用列表的最小元素是第一个元素和剩余列表的最小值之间的最小值

考虑到这些，应该很容易实现。特别是因为递归算法具有与其算法描述非常相似的便利性。

于 2013-03-27T02:29:52.090 回答
1

您需要找到应用于列表的函数 min 和应用于子列表的函数 min 之间的关系。

min([abcde ...]) = f(a, min([bcde ...]))

现在你只需要找到函数 f。一旦你有了关系，那么实现它就很容易了。祝你好运。

于 2013-03-27T02:34:26.727 回答
0

在最一般的意义上，递归是一个基于分解工作的概念，然后将较小的工作块委托给您自己的副本。要使递归起作用，您需要三个主要的东西：

  1. 工作分解。你将如何让每一步“更简单”？
  2. 递归调用。在某些时候，您的函数必须调用自己，但“工作”较少。
  3. 基本情况。什么是会停止递归过程的（通常是微不足道的）最终情况？

在您的情况下，您正在尝试创建一个min在列表上运行的函数。您认为您可以通过每次将列表缩小一个来以某种方式减少（分解）您的工作是正确的（子列出第一个元素）。正如其他人所提到的，这个想法是根据“列表的其余部分”检查第一个元素（您刚刚提取的）。好吧，这就是信仰飞跃的地方。此时，您可以“假设”您的min函数将在子列表上运行，并且只需对子列表进行函数调用（递归调用）。现在你必须确保你的所有调用都会返回（即确保它不会永远递归）。这就是您的基本情况的用武之地。如果您的列表大小为 1，则唯一的元素是列表中最小的元素。无需致电min再次，只需返回（您在原始帖子中已经拥有的那部分）。

于 2013-03-27T03:08:28.067 回答
0 
/**
 * The function computes the minimum item of m (-1 if m is empty). 
 * @param m: The MyList we want to compute its minimum item.
 * @return: The minimum item of MyList    
 */ 
public int minimum(MyList<Integer> m){

    int res = 0;
    int e0 = 0;
    int e1 = 0;

    // Scenarios Identification
    int scenario = 0;

    // Type 1. MyLyst is empty
    if(m.length() == 0) {
        scenario = 1;
    }else {
    // Type 2. MyLyst is not empty
        scenario = 2;
    }

    // Scenario Implementation
    switch(scenario) {

    // If MyLyst is empty
    case 1:
        res = -1;
        break;
        // If there is 1 or more elements   
    case 2:
        //1. Get and store first element of array
        e0 = m.getElement(0);
        //2. We remove the first element from MyList we just checked
        m.removeElement(0);
        //3. We recursively solve the smaller problem
        e1 = minimum(m); 
        //4. Compare and store results
        if(e0 < e1) {
            res = e0;
        }
        else {
            res = e1;
        }
        //5. Return removed element back to the array
        m.addElement(0, e0);
        break;
    }
    //6. Return result 
    return res;
}
于 2018-11-27T23:20:23.783 回答
-1

好了，在方法中试试这个：

    public static Integer minimum(List<Integer> t) {
        int minInt;
       if (t.size() == 1) {
        return t.get(0);
       } else {
            int first = t.get(0);
            List<Integer> u = t.subList(1, t.size());
            minInt = Math.min(first, u.get(0));
            minInt = IntegerList.minimum(u);
          }
         return minInt;
      }

希望这可以解决您的问题。

于 2013-12-11T20:29:01.277 回答