4 // recursively calculate the number of steps needed |
4 // recursively calculate the number of steps needed |
5 // until the collatz series reaches the number 1. |
5 // until the collatz series reaches the number 1. |
6 // If needed, you can use an auxiliary function that |
6 // If needed, you can use an auxiliary function that |
7 // performs the recursion. The function should expect |
7 // performs the recursion. The function should expect |
8 // arguments in the range of 1 to 1 Million. |
8 // arguments in the range of 1 to 1 Million. |
|
9 def stepsCounter(n: Long, s: Long) : Long = n match{ |
|
10 case 1 => s |
|
11 case n if(n%2==0) => stepsCounter(n/2,s+1) |
|
12 case _ => stepsCounter(3*n+1, s+1) |
|
13 } |
|
14 |
|
15 def collatz(n: Long) : Long = n match { |
|
16 case n if(n>0) => stepsCounter(n,0) |
|
17 case n if(n<=0) => stepsCounter(1,0) |
|
18 } |
9 |
19 |
10 |
20 |
11 // def collatz(n: Long) : Long = { |
|
12 // if (n == 1) 1 //else |
|
13 // // if (n % 2 == 0) { |
|
14 // // collatz(n/2) |
|
15 // // steps + 1 |
|
16 // // } //else |
|
17 // // if (n % 2 != 0) { |
|
18 // // collatz((3 * n) + 1) |
|
19 // // steps + 1 |
|
20 // // } |
|
21 // } |
|
22 |
|
23 // val steps: Long = 1 |
|
24 // val lst = List() |
|
25 // def collatz(n: Long) : Long = { |
|
26 // if (n == 1) { steps + 1 } |
|
27 // else if (n % 2 == 0) { |
|
28 // collatz(n/2); |
|
29 // } |
|
30 // else { |
|
31 // collatz((3 * n) + 1); |
|
32 // } |
|
33 // steps + 1 |
|
34 // } |
|
35 // collatz(6) |
|
36 |
|
37 def collatz(n: Long, list: List[Long] = List()): Long = { |
|
38 if (n == 1) { |
|
39 n :: list |
|
40 list.size.toLong |
|
41 } |
|
42 else if (n % 2 == 0) { |
|
43 collatz(n / 2, n :: list) |
|
44 } |
|
45 else { |
|
46 collatz((3 * n) + 1, n :: list) |
|
47 } |
|
48 } |
|
49 |
|
50 val test = collatz(6) |
|
51 |
21 |
52 //(2) Complete the collatz_max function below. It should |
22 //(2) Complete the collatz_max function below. It should |
53 // calculate how many steps are needed for each number |
23 // calculate how many steps are needed for each number |
54 // from 1 up to a bound and then calculate the maximum number of |
24 // from 1 up to a bound and then calculate the maximum number of |
55 // steps and the corresponding number that needs that many |
25 // steps and the corresponding number that needs that many |
56 // steps. Again, you should expect bounds in the range of 1 |
26 // steps. Again, you should expect bounds in the range of 1 |
57 // up to 1 Million. The first component of the pair is |
27 // up to 1 Million. The first component of the pair is |
58 // the maximum number of steps and the second is the |
28 // the maximum number of steps and the second is the |
59 // corresponding number. |
29 // corresponding number. |
60 |
30 |
61 //def collatz_max(bnd: Long) : (Long, Long) = ... |
31 def collatz_max(bnd: Long) : (Long, Long) = { |
62 def collatz_max(bnd: Long) : (Long, Long) = { |
32 val allCollatz = for(i<-1L until bnd) yield collatz(i) |
63 val stepsTable = for (n <- (1 to bnd.toInt).toList) yield (collatz(n), n.toLong) |
33 val pair = (allCollatz.max, (allCollatz.indexOf(allCollatz.max) +1).toLong) |
64 //println(stepsTable) |
34 pair |
65 stepsTable.max |
|
66 } |
35 } |
67 |
36 |
68 |
|
69 } |
37 } |
70 |
|