順次追加

#Newton法

fun main(args : Array<String>) {

    val x = newton(
            x  = 1.0,
            f  = {it * it - 2.0},
            fd = {it * 2.0},
            eps = 1.0e-10)
    println(x)
}


fun newton(x : Double, f : (Double)->Double, fd : (Double)->Double, eps : Double) : Double{
    return if(Math.abs(f(x)) < eps) x
    else newton(x - f(x)/fd(x), f , fd , eps)
}

#割線法

fun main(args : Array<String>) {

    val x = secantMethod(
            newX  = 1.5,
            oldX  = 1.6,
            f     = {it * it - 2.0},
            eps = 1.0e-10)
    println(x)
}


fun secantMethod(newX : Double, oldX : Double, f : (Double) -> Double, eps : Double) : Double{
    return if(Math.abs(f(newX)) < eps) newX
    else secantMethod(
            newX = newX - (f(newX) * (newX - oldX)) / (f(newX) - f(oldX)),
            oldX = newX,
            f    = f,
            eps  = eps
            )
}

#二分法

fun main(args : Array<String>) {

    val x = bisectionMethod(
            left  = 1.5,
            right = 0.0,
            f     = {it * it - 2.0},
            eps = 1.0e-10)
    println(x)
}


fun bisectionMethod( left : Double, right : Double, f : (Double) -> Double, eps : Double) : Double{
    val center = (left + right) / 2

    return if(right - left < eps )left
    else if(f(left)*f(center) <= 0)
        bisectionMethod(
            left  = left,
            right = center,
            f     = f,
            eps   = eps )

    else bisectionMethod(
            left  = center,
            right = right,
            f     = f,
            eps   = eps )

}

#区分求積法

fun main(args : Array<String>) {

    val num = quadratureByParts(a = 0, b = 1 , h = 0.125, f = {4 / (1 + it * it)})
    print(num)

}

fun quadratureByParts(a : Int, b : Int, h : Double, f : (Double)->Double): Double {
    var sum = 0.0
    var x : Double = a.toDouble()
    while(x <= b){
        x += h
        sum += f(x)
    }
    return sum * h
}

#シンプソンの公式

fun main(args : Array<String>) {

    val num = compositeSimpson(a = 0, b = 1 , h = 0.125, f = {4 / (1 + it * it)})
    print(num)

}

fun compositeSimpson(a : Int, b : Int, h : Double, f : (Double)->Double): Double {
    var sum = 0.0
    var x : Double = a.toDouble()
    var coefficient = 4
    sum += f(x)
    while(x < b - h){
        x += h
        sum += coefficient*f(x)
        coefficient = 6 - coefficient
    }
    x += h
    sum += f(x)
    return sum * h / 3.0
}

#ラグランジェ補完多項式

fun main(args : Array<String>) {


    val f = LagrangianFunction.make(listOf(Point(1.0,1.0),Point(2.0,2.0),Point(4.0,3.0),Point(8.0,4.0)))
    print(f(5.0))


}

data class Point(val x : Double, val y : Double)

object LagrangianFunction{

    fun make(points : List<Point>): (Double) -> Double {
        val f = fun (x : Double):Double{
            var res = 0.0
            for(point in points){
                val rest  = mutableListOf<Point>()
                rest.addAll(points)
                rest.remove(point)
                res += point.y * makeMolecute(rest)(x) / makeDenominator(point,rest)
            }
            return res
        }
        return f
    }

    private fun makeDenominator(point : Point,others : List<Point>): Double {
        var res : Double = 1.0
        for(other in others){
            res *= point.x - other.x
        }
        return res
    }

    private fun makeMolecute(points: List<Point>): (Double) -> Double {
        val f = fun (x : Double): Double {
            var res = 1.0
            for(point in points) res *= x - point.x
            return res
        }
        return f
    }
}

#ルンゲクッタ法

fun main(args : Array<String>) {

    val num = rungeKuttaMethod(
            points = mutableListOf(Point(0.0,0.5)),
            step   = 3,
            h      = 0.5,
            fd     = {x : Double,y : Double -> 2 * y / (1 + x)})

    print(num)

}

data class Point(val x : Double, val y : Double)
fun rungeKuttaMethod(points : MutableList<Point>, step : Int, h : Double, fd: (Double, Double)->Double): MutableList<Point> {
    if(step == 0) return points
    val point = points.last()
    val k1 = h * fd(point.x, point.y)
    val k2 = h * fd(point.x + h / 2,point.y + k1 / 2)
    val k3 = h * fd(point.x + h / 2,point.y + k2 / 2)
    val k4 = h * fd(point.x + h    ,point.y + k3 )

    val nextX = point.x + h
    val nextY = point.y + (k1 + 2 * k2 + 2 * k3 + k4) / 6
    points.add(Point(x = nextX, y = nextY))
    return rungeKuttaMethod(points, step = step -1, h = h, fd = fd)

}

#エラトステネスの篩

fun main(args : Array<String>) {
    printPrimeNumber(n = 1000)
}

fun printPrimeNumber(n : Int){
    val  collection = makeCollection(n)
    for(i in 2..n){
        val uncheckedLeastCommonMultiple : Boolean= collection[i].second
        if(uncheckedLeastCommonMultiple){
            print(collection[i].first)
            print(" ")
            sieve(i,n,collection)
        }
    }
}

fun makeCollection(n: Int) : MutableList<Pair<Int,Boolean>>{
    val list = mutableListOf<Pair<Int,Boolean>>()
    return (0..n).mapTo(list) { it to true }
}

fun sieve(i : Int, n : Int, collection : MutableList<Pair<Int,Boolean>>){
    for(j in (i)*2..n step i) collection[j] = (j to false)
}

#クイックソート


fun main(args : Array<String>) {
    print(qsort(listOf(1,2,31,42,15,1,54,3,545,2)))

}

fun <T : Comparable<T>> qsort(list : List<T>): List<T> {
    fun qsortFilter(list: List<T>,key : T, leftList: MutableList<T>, equalList: MutableList<T>, rightList: MutableList<T>): Triple<MutableList<T>, MutableList<T>, MutableList<T>> {
        if(list.size == 0) return Triple(leftList,equalList,rightList)

        val head = list.first()
        val rest = list.drop(1)
        return when{
            head  < key -> qsortFilter(rest,key,leftList.plus(head) as MutableList<T>,equalList,rightList)
            head == key -> qsortFilter(rest,key,leftList,equalList.plus(head) as MutableList<T>,rightList)
            else        -> qsortFilter(rest,key,leftList,equalList,rightList.plus(head) as MutableList<T>)
        }

    }

    if(list.size <= 1 ) return list

    val key = list.first()

    val filtered  = qsortFilter(list,key, mutableListOf(), mutableListOf(),mutableListOf())
    val leftList  = filtered.first
    val equalList = filtered.second
    val rightList = filtered.third
    if(leftList.size == 0 && rightList.size == 0)return equalList
    else return qsort(leftList)+ qsort(equalList)+ qsort(rightList)

}

#川渡り問題、狼とヤギ、宣教師と先住民

fun main(args : Array<String>) {
    RiverClossingPuzzle.search(c = 3,m = 3)

}

object RiverClossingPuzzle{

    private val moves = listOf<Mpat>(Mpat(2,0), Mpat(1,1), Mpat(0,2), Mpat(1,0), Mpat(0,1))
    private  var cInitial : Int = 0
    private  var mInitial : Int = 0

    fun search(c : Int, m : Int){
        cInitial = c
        mInitial = m
        search(mutableListOf(State(c,m, pos = 0, parent = null)))
    }

    private fun search(theQueue : MutableList<State>){

        fun enQueueChildren(state : State, moves : List<Mpat>): List<Mpat> {
            if (moves == emptyList<Mpat>()) return emptyList<Mpat>()

            val nextState = move(state = state, mpat = moves.car())
            if ((nextState != null) && checkState(nextState) && checkEqState(state, nextState)) theQueue.enqueue(nextState)
            return enQueueChildren(state, moves = moves.cdr())
        }

        if(theQueue == emptyList<Any>()) {
            println("No more solutions")
            return
        }
        val state = theQueue.dequeue()
        if((state.c == 0) && (state.m == 0)){
            printResult(state)
            println("**************")

        }
        else enQueueChildren(state,moves)
        return search(theQueue)

    }

    private fun printResult(state: State?){
        if(state == null) return

        printResult(state.parent)

        print("${listOf<Any>(state.c, state.m, "  ", cInitial - state.c, mInitial - state.m)}")
        if(state.pos == 0)print("=>") else print("<=")
        println()
    }



    private fun checkEqState(state1: State?,state2: State): Boolean {
        if(state1 == null) return true

        if((state1.c == state2.c) && (state1.m == state2.m) && (state1.pos == state2.pos)) return false
        return checkEqState(state1 = state1.parent ,state2 = state2)
    }

    private fun checkState(state : State) : Boolean{
        val c = state.c
        val m = state.m

        return !((0 < m && m < c) || (m < mInitial) && ((mInitial-m) < (cInitial-c)))
    }

    private fun move(state : State, mpat : Mpat) : State? {
        val pos = state.pos
        val dc  = mpat.c
        val dm  = mpat.m
        val c   = if(pos == 0 )state.c   else cInitial - state.c
        val m   = if(pos == 0 )state.m   else (mInitial - state.m)

        if((dc > c ) || (dm > m)) return null
        if(pos == 0) return State(c = c - dc, m =  m - dm, pos = 1 - pos, parent = state)
        else         return State(c = cInitial - c + dc, m = mInitial - m + dm, pos = 1 - pos, parent = state)
    }


    private data class Mpat(val c : Int, val m : Int)
    private data class State(val c: Int, val m: Int, val pos: Int, val parent: State?)

}


/********ExFun for List*************/

fun <T> List<T>.car(): T {
    return this.first()
}
fun <T> List<T>.cdr() : List<T>{
    return this.drop(1)
}
fun <T> List<T>.cadr() : T{
    return this.drop(1).first()
}
fun <T> List<T>.caddr() : T{
    return this.drop(2).first()
}
fun <T> List<T>.cadddr() : T{
    return this.drop(3).first()
}

fun <T> MutableList<T>.enqueue(element : T){
    this.add(element)
}
fun <T> MutableList<T>.dequeue(): T {
    return this.removeAt(0)
}

/***************************************/

#末尾再帰最適化


fun main (vararg args : String) {

    f(0,last = 100000)
}

tailrec fun f(i : Int,last :Int){
    if(i > last) return print("completed!")
    print("$i ")
     return f(i + 1,last)
}

#template method パターン


class View(val doDisplay : ()->Unit){
    fun setFocus(){/*実装*/}

    fun resetFocus(){/*実装*/}

    fun display(){
        setFocus()
        doDisplay()
        resetFocus()
    }

}

val myView = View{ print("")}