12/6 다시 푸는 Assignment 1

package hw1
import scala.annotation.tailrec
import scala.util.control.TailCalls._

object Main {
  /**
   * Implement given functions, which are currently left blank. (???)
   * **WARNING: Please read the restrictions below carefully.**
   *
   * If you do not follow these, **your submission will not be graded.**
   *
   * 1. Do not use the keyword `var`. Use `val` and `def` instead.
   * 2. Do not use any library functions or data structures like `List`, `Array`,
   *   `Range` (`1 to n`, `1 until n` ...), `fold`, `map`, `reduce` or etc.
   *    You can only use tuples, `scala.annotation.tailrec`, and
   *    `scala.util.control.TailCalls._` from the library.
   * 3. Do not use Scala's iteration(loop) syntax (`for`, `while`, `do-while`, `yield`)
   *
   * Again, your score will be zero if you do not follow these rules.
   *
   * Note that these rules will be gradually relaxed through the next assignments.
   *
   *
   * For problem 1 and 3, 50% of the test cases will require tail call optimizations (i.e., large inputs)
   *   and the other 50% will not (i.e., small inputs).
   *
   * So, you will get at least 50% of the score if you submit a correct program without
   *   tail call optimization.
   */

  /**
   * Exercise 1-1: Basic summation
   *
   * Calculate a + (a + 1) + ... + b  `(0 <= a, b <= 10^5)`
   *
   * when a > b, return 0
   */
  def sum(a: Long, b: Long): Long = {
    def sumf(idx:Long,res:Long=0):Long={
      if(idx==b+1) res
      else sumf(idx+1, res+idx)
    }
    if(a>b) 0
    else sumf(a)
  }


  /**
   * Exercise 1-2: fold
   *
   * Calculate f(a, f(a + 1, f(a + 2, ... f(b - 1, b))))  `(0 <= a, b <= 10^6)`
   *
   * when a >= b, return 0
   *
   * We guarantee that any (f, a, b) in the test set will not raise integer overflow.
   */
  def fold(f: (Long, Long) => Long, a: Long, b: Long): Long = {
    def func(idx:Long, res:Long=b):Long={
      if(idx==a) f(a, res)
      else func(idx-1, f(idx,res))
    }
    if(a>=b) 0
    else func(b-1)
  }

  /**
   * Exercise 2: Binomial Coefficient
   *
   * Calculate the binomial coefficient with n and k, i.e. nCk  (0 <= k <= n <= 64)
   *
   * Check https://en.wikipedia.org/wiki/Binomial_coefficient
   *
   * WARNING: You must not raise any integer overflow during the calculation.
   * In other words, every basic calculation should be in the range of `Long`.
   *
   * Hint: Find an appropriate formula from the above link.
   * Hint 2: GCD
   **/
  def fac(n:Long,res:Long=1):Long={
      if(n==0) res
      else fac(n-1, res*n)
  }
  def gcd(a:Long, b:Long):Long={
    if(a>b) gcd(b,a)
    else{
      def func(idx:Long):Long={
        if(idx==1) idx
        else if((a%idx==0)&&(b%idx==0)) idx
        else func(idx-1)
      }
      func(a)
    }
  }
  def coeff(n: Long, k: Long): Long = {
    def func(n:Long, k:Long,mo:Long=1, ja:Long=1):Long={
      if(gcd(mo,ja)!=1) func(n,k,mo/gcd(mo,ja), ja/gcd(mo,ja))
      else if(k==0) ja
      else func(n-1,k-1,mo*k,ja*n)
    }
    func(n,k)
  }

  /**
   * Exercise 3: Termination checker
   *
   * Find the first integer `n` which makes `pred(f^n(init))` True.
   *
   * For example, if pred(init), pred(f(init)), and pred(f(f(init))) is all False,
   *   and pred(f(f(f(init)))) gives the first True value, then return 3.
   * If pred(init) is True, return 0.
   *
   * f: repeating function
   * pred: Termination predicate. If p(n) returns True,
   * init: initial input
   *
   * We guarantee that every input in the test set will always
   *   terminate the checker if your checker is correct and efficient.
   **/
  def terminate(pred: Long => Boolean, f: Long => Long, init: Long): Long = {
    def func(counter:Long=0,res:Long=init):Long={
      if(pred(res)) counter
      else func(counter+1, f(res))
    }
    func()
  }
}

 

테스트 코드도 모두 통과했다.

푸는데 20-30분 정도 걸린듯