算法学习第一章

1.计算两个数的最大公约数
我猜你是不是根本不知道什么是最大公约数吧

苦笑

欧几里得算法：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数是p。否则，p和q的最大公约数即为q和r的最大公约数。

 fun  gcd(p : Int,q : Int) :Int{
    if (q == 0){
      return  p
    }
    val r = p % q
    return gcd(q , r)
}

2.判断一个数是不是素数
我又猜到了，你不知道啥是素数

he

素数定义：素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
素数就是质数，质数就是素数。了解？再通俗讲，就是一个数，除了1和本身，不能被两个其他的自然数相乘而来。

 fun isPrime(N : Int): Boolean{
    if (N < 2) return false
    var i = 2
        while (i * i < N) {
            if (N % i == 0)return  false
            i++
        }
    return true
  }

3.二分法查找
先了解下什么时候递归，不太想解释，自己去看。

傲娇

交代一下写递归最重要的三点
a.递归总是有一个最简单的情况---方法的第一条总是包含return的条件语句
b.递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况，在下面的代码中第三个参数和第四个参数一直在缩小。
c.递归调用的父问题和子问题不应该有交集。

fun rank(a : Int, arr : Array<Int>) : Int{
    return rank(a,arr,0,arr.size)
}

fun rank(a : Int, arr : Array<Int>,lo : Int,hi : Int) : Int{
    if (lo >= hi) return  -1
    val mid = lo + (hi - lo) / 2
   return if (a > arr[mid]) rank(a,arr,mid,hi)
    else if (a < arr[mid]) rank(a,arr,lo,mid)
    else  mid
}

4.打印一个数列
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
很明显后面的数是前面两个数的和

fun print(){
    var f = 0
    var g = 1
    for (i in 0..15){
        Log.d("azy",f.toString())
        f += g;
        g = f - g;
    }
}

5.不实用内置api，计算a的b次方

fun mystery(a: Int,b:Int) : Int{
    if (b == 0)return 1
    if (b % 2 == 0) return mystery(a*a , b/2)
    return mystery(a*a ,b/2) * a
}

思考题：如果上述代码所有*换成+，结果会如何

6.哈哈哈偷懒了。

完犊子.jpeg