Collatz - максимальное количество шагов и соответствующее количество

Question

Я пытаюсь написать функцию Scala, которая принимает верхнюю границу в качестве аргумента и вычисляет шаги для чисел в диапазоне от 1 до этой границы. Он должен был вернуть максимальное количество шагов и соответствующее количество, которое требует столько шагов. (как пара - первый элемент - это число шагов, а второй - соответствующий индекс)

Я уже создал функцию под названием "collatz", которая вычисляет количество шагов. Я очень новичок в Scala, и я немного застрял из-за ограничений. Вот как я думал, чтобы запустить функцию:

def max(x:Int):Int = {
  for (i<-(1 to x).toList) yield collatz(i) 

Я думаю, что для решения этой проблемы нужно: 1. пройти через диапазон и применить collatz ко всем элементам, помещая их в новый список, в котором хранится количество шагов. 2. найдите максимум нового списка с помощью List.max. 3. Используйте List.IndexOf, чтобы найти индекс. Тем не менее, я действительно застрял, так как я не знаю, как это сделать без использования var (и только с использованием val). Спасибо!

Answer 1

Что-то вроде этого:

def collatzMax(n: Long): (Long, Long) = {
  require(n > 0, "Collatz function is not defined for n <= 0")

  def collatz(n: Long, steps: Long): Long = n match {
    case n if (n <= 1)     => steps
    case n if (n % 2 == 0) => collatz(n / 2, steps + 1)
    case n if (n % 2 == 1) => collatz(3 * n + 1, steps + 1)
  }

  def loop(n: Long, current: Long, acc: List[(Long, Long)]): List[(Long, Long)] = 
    if (current > n) acc
    else {
      loop(n, current + 1, collatz(current, 0) -> current :: acc)
    }

  loop(n, 1, Nil).sortBy(-_._1).head
}

Пример:

collatzMax(12)
result: (Long, Long) = (19,9) // 19 steps for collatz(9)

Использование для:

def collatzMax(n: Long) = 
  (for(i <- 1L to n) yield collatz(i) -> i).sortBy(-_._1).head

Или (продолжая вашу идею):

def maximum(x: Long): (Long, Long) = {
  val lst = for (i <- 1L to x) yield collatz(i) 
  val maxValue = lst.max
  (maxValue, lst.indexOf(maxValue) + 1)
} 

Answer 2

Пытаться:

(1 to x).map(collatz).maxBy(_._2)._1