遞歸方法檢查一行整數是否遞減：return true/false

我必須在Java中編寫一個遞歸方法，如果行是遞減的，則返回true，否則返回false。遞歸方法檢查一行整數是否遞減：return true/false

這是我嘗試過，但它不能正常工作：我覺得你有不必要的情況下，如果大小小於2，你只能假設真

ArrayList<Integer> getallen = new ArrayList(); 
     getallen.add(500); 
     getallen.add(400); 
     getallen.add(300); 
     getallen.add(200); 
     getallen.add(100); 
     getallen.add(0); 

     System.out.println(isDescending(getallen)); 
    } 

public static boolean isDescending(ArrayList<Integer> getallen) { 
    if (getallen.size() >= 2) { 
     if (getallen.get(0) < getallen.get(1)) { 
      return false; 
     } else if (getallen.size() > 0) { 
      getallen.remove(0); 
      return isDescending(getallen); 
     } else { 
      return true; 
     } 
    } else { 
     return false; 
    } 
}

來源

2015-09-12 MJM

什麼不起作用？ –

您的問題與基本案例。什麼是'isDescending'應該返回長度爲1的列表？ – Tunaki

@Tunaki - 我不認爲也有這個問題。他正在檢查列表是遞減的，並且大小列表不能被稱爲遞減。因此否則塊應該很好。 –

。

嘗試：

public static boolean isDescending(ArrayList<Integer> getallen) { 
    if (getallen.size() >= 2) { 
     if (getallen.get(0) < getallen.get(1)) { 
      return false; 
     } else { 
      getallen.remove(0); 
      return isDescending(getallen); 
     } 
    } else { 
     return true; 
    } 
}

來源

2015-09-12 15:31:27 WillShackleford

謝謝！這幫了我。 – MJM

只是想添加幾乎相同的解決方案:) 順便說一句。當我使用List 集合時，調用'remove（0）'會拋出'UnsupprtedOperationException'（NetBeans 8.0.2，Java 8.0.45），所以我使用'subSet（）'傳遞參數以進一步遞歸。 – AndrewMcCoist

@AndrewMcCoist''ArrayList'永遠不會在'remove'方法中拋出'UnsupportedOperationException'。你確定你沒有使用'Arrays.asList（...）'返回的列表嗎？ –

如果我不得不檔次這一點，它會得到

一個大胖子X已經被欺騙性地問在計算器
是相當低效（試運行此在一百萬個元素的列表上測試，然後意識到移除ArrayList中的元素0會導致所有元素向下移位）

而是考慮：

public static boolean isDescending(List<Integer> getallen) { 
    return isDescending(getallen, 0); 
} 

public static boolean isDescending(List<Integer> getallen, int from) { 
    return from >= getallen.size() - 1 
      || getallen.get(from) < getallen.get(from + 1) 
      && isDescending(getallen, from + 1); 
}

來源

2015-09-12 18:04:37 Arend

我知道刪除ArrayList的第一個元素時，所有元素都向下移動，但我不明白爲什麼這個方法很重要。該方法的目的是檢查元素是否按降序排列。你能解釋一下嗎？ – MJM

@MJM重要的不是功能，而是效率。在'ArrayList'中，向下移動的步驟與列表很長的步驟相同。所以你的算法具有二次時間複雜度（在列表長度中），而最好的算法（像我的）具有線性複雜度。當數據變大時，這一點非常重要。請注意''LinkedList'沒有同樣的缺點（刪除需要一定的時間），所以這已經可以改善你的解決方案。 – Arend

@MJM修改列表作爲該方法的副作用的另一個缺點是該列表可能是共享的。所有別名之後都會有一個空列表。 – Arend

如何用對數遞歸深度點點更有效的方法？就像練習一樣。

public static void main(String[] args) { 
    List<Integer> getallen = new ArrayList<Integer>();   
    getallen.add(500); 
    getallen.add(400); 
    getallen.add(300); 
    getallen.add(200); 
    getallen.add(100); 
    getallen.add(0); 

    System.out.println(isDescending(getallen)); 
} 

public static boolean isDescending(List<Integer> getallen) { 
    return isDescending(getallen, 0, getallen.size()); 
} 

private static boolean isDescending(List<Integer> getallen, 
     int start, int end) { 
    if (end - start <= 1) 
     return true; 
    if (end - start == 2) { 
     return getallen.get(start) > getallen.get(start + 1); 
    } 
    int middle = (start + end - 1)/2 + 1; 
    return (getallen.get(middle - 1) > getallen.get(middle)) && 
      isDescending(getallen, start, middle) && 
      isDescending(getallen, middle, end); 
}

來源

2015-09-12 23:51:06 rsutormin

遞歸方法檢查一行整數是否遞減：return true/false

回答

相關問題