Scala: IndexOutOfBoundsException: -1

Я пошел шаг за шагом, глядя на эту функцию, и мне кажется, что следует избегать вызова sortedCoins(0-1), используя только sortedCoins(0) и заканчивая при y == -1, но почему-то это не так. Зачем?Scala: IndexOutOfBoundsException: -1

def countChange(amount: Int, coins: List[Int]): Int = { 
    var x = coins.length 
    var y = x 
    val sortedCoins = coins.sortWith(_ < _) 
    def cc(amount: Int, x: Int): Int = { 
     y -= 1 
     if (amount == 0) 1 
     else if (y == 0) cc(amount - x, sortedCoins(y)) 
     else if (amount < 0 || y == -1) 0 
     else cc(amount, sortedCoins(y - 1)) + cc(amount - x, sortedCoins(y))  
    } 

    cc(amount, x) 
}

источник

2017-02-02 Megoh

Я предлагаю научиться использовать отладчик, чтобы шаг за шагом выполнять программу. Это было бы очень полезно для вас (для этой и будущих проблем). Удивительно, сколько вопросов задают вопрос, который мог бы попросить более простой для себя ответчик –

на другой ноте, которую он убивает, когда я вижу «монеты: Список [Int]», где это должно быть «монеты»: «Список [Монета] '. Как минимум, вы должны использовать класс значений, но на самом деле вы должны использовать ADT (Algebraic Data Type) –

Является ли это домашней проблемой? Похоже, я видел это в курсе Coursera .... – WillD

Вам необходимо переосмыслить способ написания этого алгоритма. Вы видите ваш Y переменной «глобальную» область видимости в вашей рекурсивной функции, при выполнении вашей функции он будет идти к

cc(amount, sortedCoins(y - 1)) + cc(amount - x, sortedCoins(y))

нескольких раз, и он будет выполнять первую часть уравнения, и она будет уменьшать Y каждый раз. Тогда, у будет 0 и ваш

else if (y == 0) cc(amount - x, sortedCoins(y))

строка будет выполнена, рядом, потому что у = -1 ваш

else if (amount < 0 || y < 0) 0

строка будет выполнена. И здесь мы приходим к исключению, поскольку эта линия возвращается 0, рекурсивно вторая часть уравнения последних еще будет выполнена, что

cc(amount - x, sortedCoins(y))

, и теперь у = -1, поэтому у вас есть это исключение , Надеюсь, это понятно.

источник

2017-02-02 14:42:55

'else if (amount <0 || y == -1) 0' Если это возвращает 0, то функция должна завершиться, потому что функция возвращает Int. Почему он продолжается и проверяет следующее «другое»? – Megoh

Он не проверяет следующее, вы рекурсивно вызываете функцию времени cc. Когда левая сторона уравнения возвращает 0, вызывается правая часть уравнения с такими параметрами, как (amount-x, sortedCoins (y)) и почему существует -1. sortedCoins - это список, поэтому у вас есть indexOutOfBound –

ответ

Смежные вопросы