順次追加
#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("")}