算法总结篇-(1)--算法思想

作者: 小酷哥 | 来源:发表于2017-02-10 14:24 被阅读0次
    • 算法包括三部分:算法思想 + 排序算法 + 查找算法
    算法思想:

    算法思想 就是 解题思路
    常见的解题思路有如下:
    1)穷举算法思想:为了解决问题和解决问题
    2)递推算法思想:根据已知结果和关系,求解。适合在有明显数学公式的情况下
    3)递归算法思想:在程序中不断重复调用自身来达到求解的目地。 如求阶乘问题
    4)分治算法思想:大问题分解成小问题
    5)概率算法思想:根据概率统计的思路求近似值

    • 穷举算法:
    /**
     * Created by malei on 2016/12/4.
     * 1)穷举算法思想:为了解决问题和解决问题
     */
    public class a_穷举算法 {
    
        /**
         * 笼子里有鸡和兔,从上面说有35个头,下面共有94个脚,求鸡和兔的各自数量
         */
        public static void main(String[] args){
            qiongju(35,94);
        }
        /**
         * chook + rabbit = head;
         * chook*2 + rabbit*4 = foot;
          */
        private static void qiongju(int head, int foot) {
            for (int chook = 0 ; chook <= head ; chook++){
                if((chook*2 + (head - chook)*4) == foot){
                    Log.show("鸡的个数:"+chook +" 兔子的个数:"+(head-chook));
                }
            }
        }
    }
    
    • 递推算法:
    /**
     * Created by malei on 2016/12/4.
     * 递推算法思想:根据已知结果和关系,求解。适合在有明显数学公式的情况下
     */
    public class b_递推算法 {
    
        /**
         * 一对两个月大的兔子以后每一个都可以生一对小兔子,而一对新生的兔子出生两个月
         * 以后,才能生小兔子。也就是说1月份出生,3月份才可以产仔。没有兔子死亡的情况下,‘
         * 一年后共有多少只兔子?
         */
        public static void main(String[] args){
            int count = opreate(12);
            Log.show(count);
        }
    
        /**
         * 第一个月 :1
         * 第二个月:1
         * 第三个月:2
         * 第四个月:3
         * 第五个月:5
         * 已知结果和关系:每个月都是前两个月的相加  f(n) = f(n-1)+f(n-2)
         */
        private static int  opreate(int count) {
            if(count <=2 ){
                return 1;
            }
            int total = 0;
            total = opreate(count-1)+opreate(count-2);
            return total;
        }
    }
    
    • 递归算法
    /**
     * Created by malei on 2016/12/4.
     * 递归算法思想:在程序中不断重复调用自身来达到求解的目地。 如求阶乘问题
     */
    public class c_递归算法 {
    
        /**
         * 求解从1到100相乘的结果
         * @param args
         */
        public static void main(String[] args){
            long count = opreate(12);
            Log.show(count+"");
        }
    
        /**
         * n! = 1*2*3*...n 因此通过阶乘公式:
         * n!= n*(n-1)!
         * 这里有个坑,阶乘的返回值可能具体超过int的范围
         */
        private static long opreate(int num) {
            if(num <= 1 ){
                return 1;
            }
            return num * opreate(num-1);
        }
    }
    
    • 分治算法
    /**
     * Created by malei on 2016/12/4.
     * 分治算法思想:大问题分解成小问题
     */
    public class d_分治算法 {
    
        /**
         * 30个硬币,其中有一个是假币,假币比真币轻,求什么办法可以找到假币?
         * 硬币是有编号的
         */
        public static void main(String[] args){
            int[] coins = {2,2,1,2,2,2,2,2,2};
            int count = opreate(coins,0,coins.length-1);
            Log.show(count+"");
        }
    
        /**
         * 解题思路:把钱分两堆,比较轻重,轻的在分。。。
         */
        private static int opreate(int[] coins, int low, int high) {
    
            int sum1=0; //前半段和
            int sum2=0; //后半段和
    
            //仅剩下两个进行比较了
            if(low+1 == high){
                if(coins[low] > coins[high]){
                    return high;
                }else{
                    return low;
                }
            }
    
            //个数为偶数
            if((high+1 - low) % 2 == 0){
                //前半段的和
                for (int i =0;i<= (low+(high-low))/2 ; i++){
                    sum1 += coins[i];
                }
                //后半段的和
                for(int i= (low+(high-low))/2+1 ; i <= high ; i++){
                    sum2 += coins[i];
                }
                //前后半段的比较
                if(sum1 > sum2){
                    //前段大
                    //小的继续循环
                    return opreate(coins,(low+(high-low))/2+1,high);
                }else{
                    //后端大
                    return opreate(coins,low,(low+(high-low))/2);
                }
    
            }else {
                //个数问奇数时
                //前半段和
                for (int i = low; i<(low+(high-low))/2-1 ; i++){
                    sum1 += coins[i];
                }
                //后半段和
                for (int i = low; i<(low+(high-low))/2+1 ; i++){
                    sum2 += coins[i];
                }
                //前后相等,中间值问题
                if(sum1 == sum2){
                    return (low+(high-low))/2+1;
                }
                //前后两段进行比较
                if(sum1 >sum2){
                    //前段大
                    //小的继续循环
                    return opreate(coins,(low+(high-low))/2+1,high);
                }else {
                    return opreate(coins,low,(low+(high-low))/2-1);
                }
            }
        }
    }
    

    相关文章

      网友评论

        本文标题:算法总结篇-(1)--算法思想

        本文链接:https://www.haomeiwen.com/subject/ngvgittx.html