HW1. Exercise 2

def factorial(n:Int, res:Int = 1):Int = {
    if(n==0) res*1 
    else factorial(n-1, res*n) }

이어서 세번째 문제이지만 두번째 문제 

 

/**
   * 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 coeff(n: Long, k: Long): Long = ???

 

흠... 힌트까지 주시는걸보니 어렵나보다

같이 듣는 친구가 이 문제 64C26?? 까지만 되고 나머지는 overflow 된다고 했던게 기억난다 덕분에 호달달 떨고있다.......... 감도 안잡힘

 

팩토리얼 함수를 코드 짜는건 어렵지 않으니 고딩때 배웠던 조합 개념으로 팩토리얼로 짜면 편하겠지만 팩토리얼이 어마어마하게 커지는 함수라서 overflow가 생길 것 같다. (문제 조건이 Long 의 범위를 벗어나지 말라고 했으니 )

 

 

 

일단 위에 주석에서 알려준 위키피디아 링크로 가서 좀 읽어보자.

 

https://en.wikipedia.org/wiki/Binomial_coefficient

 

 

오.. 파스칼의 삼각형을 이용해서 recursion 을 사용하면 overflow 문제를 해결할 수 있을 것 같다.

 

 

 

아래 사진들은 유용해보이는 부분을 대충 캡쳐한 것이다

 

 

 

 

 

 

아니 근데 힌트가 왜 최대공약수지 ...

이해를 못하겠음

 

def coeff(n:Long, k:Long):Long = {
	if (

 

 

 

 

---

 

 

tail recursion에 대해서 공부 하다가 factorial을 tail recursion으로 부르는 코드를 배웠다 !!!! 이걸로 하면 그냥 간단하게 끝나지 않을까?? 일단 해보고 안되면 다시 힌트 해석하기에 돌입해야지 ...

 

 

def coeff(n:Long, k:Long):Long = {
	def factorial(n:Long, res:Long):Long = {
    	if (n==0) res*1
        else factorial(n-1,res*n)
    }
    val a = factorial(n)
    val b = factorial(k)
    val c = factorial(n-k)
    return a/(b*c)
}

 

 

def coeff(n:Long, k:Long):Long = {
	def muldiv(a:Long,b:Long,res:Long=1):Long ={
    	if (b==0) res*1 
        else muldiv(a-1,b-1,res*a/b)
    }
    if ((n-k)<k) muldiv(n,n-k)
    else muldiv(n,k)
}

==> 문제점 

res *a/b가 Long으로 선언돼서 소숫점을 잃어버려서 아예 다른 값이 나옴 ^___^;;;;

 

 

위에 코드는 진짜 답을 찾은 줄 알고 기뻤는데 덕분에 최대공약수라는 힌트를 조금이나마 이해할 수 있게 됐다

def coeff(n: Long, k: Long): Long = {

  def gcd(a: Long, b: Long): Long = {
    if (b == 0) a
    else gcd(b, a % b)
  }

  def muldiv(a: Long, b: Long, num: Long = 1, den: Long = 1): Long = {
    if (b == 0) return num / den
    if (gcd(num, den) != 1) {
      muldiv(a - 1, b - 1, num * a / gcd(num, den), den * b / gcd(num, den))
    } else {
      muldiv(a - 1, b - 1, num * a, den * b)
    }
  }
  if ((n - k) < k) muldiv(n, n - k)
  else muldiv(n, k)
}

coeff(64,32)
//val res0: Long = 1832624140942590534
//coeff(64, 32) == 1832624140942590534L

 

 

 

와 미친 내가 해냄

 

 

 

세상에 ..............

 

 

 

이번 문제를 풀면서 느낀 점:

컴퓨터가 계산한다고 어마어마한 계산량을 물려주지 말고

내가 푼다고 생각하고 그 방식을 구현하는 것이 핵심이다.

저번 LongInt ADT 구현 방식에서도 곱셈??을 구현할 때 비슷한 교훈을 얻었었다.