Сколько перерывов нужно, чтобы полностью разделить шоколад?

Question

CodeWars снова бросает вызов.Сегодня у меня есть проблема с этим:

"Ваша задача состоит в том, чтобы разбить плитку шоколада данного размера nxm на маленькие квадраты. Каждый квадрат имеет размер 1x1 и не разбивается. Реализуйте функцию, которая будет возвращать минимальное числонеобходимых перерывов.

Например, если вам дают шоколадку размером 2 x 1, вы можете разбить ее на отдельные квадраты всего за один перерыв, но для размера 3 x 1 вы должны сделать два перерыва.

Если входные данные недействительны, вы должны вернуть 0 (так как без разрывов не требуется, если у нас нет шоколада для разделения). Ввод всегда будет неотрицательным целым числом. "

Дляпо какой-то причине вывод постоянно равен 0, независимо от того, какие стороны шоколадной плитки я предоставляю.

Что я уже пробовал:

object breakChocolate {

    var result = 0

    def breakChocolate(n: Int, m: Int) = {

        var t = n*m
        var i =0
        def breaking(y:Int): Unit ={
            if (t ==0 || t ==1)
                result = i
            else {
                breaking(t%2)
                i +=1
            }
        }
        result
    }
}

Вот тесты:

Результаты теста: TestCases breakChocolate (5, 5) должен вернуть 24 Test Failed

0 не равно 24 Трассировка стека завершена за 38мс breakChocolate (7, 4) должен вернуть 27 Test Failed

0не был равен 27 трассировке стека, выполненной за 1 мс, завершенной за 76 мс

Answer 1

Для решения этой проблемы вам вообще не нужна рекурсия. Рассмотрим частный случай шоколадной тарелки: (1 x n). Чтобы полностью разделить эту пластину, вам нужно (n-1) перерывы. Теперь у вас есть тарелка м х н. Чтобы разделить его на m частей формы (1 x n), вам нужно (m-1) разрывы. Таким образом, общее количество перерывов составляет

(m-1) + m*(n-1) ~ 
m - 1 + m*n - m ~ 
m*n - 1

Answer 2

Если я правильно читаю Scala, вы ошиблись в базовом алгоритме.

Это на самом деле очень простая проблема, похожая на старую загадку: если в турнире с одним отбором играют 55 команд, очевидно, что некоторые из них должны получить прощание в первом раунде, поэтому не будет идеально ровная скобка. Так сколько всего игр будет сыграно?

Ответ: 54. Независимо от того, как устроен кронштейн, это турнир с одним отборочным. Каждая игра уменьшает количество оставшихся команд на одну. Таким образом, чтобы получить 55 участников до одного победителя, необходимо сыграть 54 игры.

Есть аналогичный аргумент в пользу вашей плитки шоколада. В какой-то момент перед вами p кусочков шоколада. Какой бы из них вы не выбрали, вы взяли 1 из стопки и положили обратно 2, что означает, что в стопке теперь есть p + 1 фигур. Таким образом, для каждого разделения вы добавляете один кусок в кучу. Это должно привести непосредственно к ответу ...

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

Answer 3

Вы получаете 0, потому что не работаете breaking.

Если вы хотите использовать рекурсию, одним из вариантов может быть использование хвостовой рекурсивной функции.

Первый декремент a проверка, что он больше 1, чтобы получить количество «горизонтальных» разрывов, чтобы получить кусочки. Добавьте 1 к аккумулятору во время цикла.

Затем уменьшите b, проверяя, больше ли оно 1, чтобы получить количество "вертикальных" разрывов. На этот раз добавьте начальное «горизонтальное» значение, потому что это количество раз, которое вам действительно нужно разбить ломтиками.

object breakChocolate {    
  def breakChocolate(n: Int, m: Int): Int = {
    def breaking(a: Int, b: Int, acc: Int = 0): Int = {
      if (a > 1) breaking(a - 1, b, acc + 1)
      else if (b > 1) breaking(a, b - 1, acc + n)
      else acc
    }
    breaking(n, m)
  }
}

Демо Scala