diff -r b84ea52bfd8f -r cdfb2ce30a3d testing1/collatz.scala --- a/testing1/collatz.scala Tue Nov 12 10:47:27 2019 +0000 +++ b/testing1/collatz.scala Tue Nov 19 00:40:27 2019 +0000 @@ -1,51 +1,70 @@ -// Part 1 about the 3n+1 conjecture -//================================== +object CW6a { -// generate jar with -// > scala -d collatz.jar collatz.scala - -object CW6a { +//(1) Complete the collatz function below. It should +// recursively calculate the number of steps needed +// until the collatz series reaches the number 1. +// If needed, you can use an auxiliary function that +// performs the recursion. The function should expect +// arguments in the range of 1 to 1 Million. -/* - * def collatz(n: Long): Long = - if (n == 1) 0 else - if (n % 2 == 0) 1 + collatz(n / 2) else - 1 + collatz(3 * n + 1) -*/ +// def collatz(n: Long) : Long = { +// if (n == 1) 1 //else +// // if (n % 2 == 0) { +// // collatz(n/2) +// // steps + 1 +// // } //else +// // if (n % 2 != 0) { +// // collatz((3 * n) + 1) +// // steps + 1 +// // } +// } + +// val steps: Long = 1 +// val lst = List() +// def collatz(n: Long) : Long = { +// if (n == 1) { steps + 1 } +// else if (n % 2 == 0) { +// collatz(n/2); +// } +// else { +// collatz((3 * n) + 1); +// } +// steps + 1 +// } +// collatz(6) -def collatz_max(bnd: Long): (Long, Long) = { - val all = for (i <- (1L to bnd)) yield (collatz(i), i) - all.maxBy(_._1) +def collatz(n: Long, list: List[Long] = List()): Long = { + if (n == 1) { + n :: list + list.size.toLong + } + else if (n % 2 == 0) { + collatz(n / 2, n :: list) + } + else { + collatz((3 * n) + 1, n :: list) + } +} + +val test = collatz(6) + +//(2) Complete the collatz_max function below. It should +// calculate how many steps are needed for each number +// from 1 up to a bound and then calculate the maximum number of +// steps and the corresponding number that needs that many +// steps. Again, you should expect bounds in the range of 1 +// up to 1 Million. The first component of the pair is +// the maximum number of steps and the second is the +// corresponding number. + +//def collatz_max(bnd: Long) : (Long, Long) = ... +def collatz_max(bnd: Long) : (Long, Long) = { + val stepsTable = for (n <- (1 to bnd.toInt).toList) yield (collatz(n), n.toLong) + //println(stepsTable) + stepsTable.max } -/* some test cases -val bnds = List(10, 100, 1000, 10000, 100000, 1000000) - -for (bnd <- bnds) { - val (steps, max) = collatz_max(bnd) - println(s"In the range of 1 - ${bnd} the number ${max} needs the maximum steps of ${steps}") } -*/ - - - - -def collatz(n: Long) : Long = { - if (n == 1) { - 1L - } else { - if (n % 2 == 0) { - collatz(n/2) + 1 - } else { - collatz((n*3)+1) + 1 - } - } -} - -} - - -