精华内容
下载资源
问答
  • 分治算法实现

    2012-09-12 08:31:40
    分治算法几个经典例子及实现,有选择最接近的点,线性时间选择,循环日程赛
  • 分治算法的简单概述

    2020-04-24 18:12:17
    下面我们通过几个经典例子来深入了解分治的思想。 二分查找 问题描述 给定一个按升序排列的数组,找出其中某个特定的值,返回其下标的值。 eg: 1,2,3,4,5,6,7,8,9 ,请找出其中9的位置,返回其...

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。下面我们通过几个经典的例子来深入了解分治的思想。利用分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法,例如二分法检索。

    二分查找

    问题描述
    给定一个按升序排列的数组,找出其中某个特定的值,返回其下标的值。
    eg: 1,2,3,4,5,6,7,8,9 ,请找出其中9的位置,返回其下标。

    问题分析
    当我们拿到这个问题时,第一种方法便是暴力破解,但当数据过于庞大时,暴力破解就会显得效率非常低下。那有没有一种更好的解决方法呢?显然是有的,这便是基于分治思想下的二分查找。对于一个有序的数组,我们可以将其一分为二,要找的的值要么在分界点,要么在分界点的左边,要么在分界点的右边,当我们找到分界点的区间后又可以按照同样的方法继续确定其下一个区间,直到每个区域不可再划分,我们便找到了答案。

    代码

    public class Main{
        public static void main(String[] args){
             int[] date = new int[]{1,2,3,4,5,6,7,8,9};
             int index = binarySeach(0,8,date,9);
             System.out.println(index);
        }
        
        //二分查找
        public static int binarySeach(int low,int high,int[] date,int num){
            while(low <= high){
                int middle = (low+high)/2;
                if(date[middle] == num){
                     return middle;
                } else if (date[middle]>num) {
                     high = middle-1;
                } else {
                     low = middle + 1;
                }
            }
            return -1;   //表示没有找到
        }
    }
    

    快速排序

    在利用快速排序算法解决排序问题时?实际上也使用了分治的思想。快速排序的基本思路是,首先任意选取一个记录作为枢纽(通常选第一个)然后我们将所有关键字较它小的记录安置在他的位置之前,将所有关键字较它大的记录安置在他的位置之后,由此我们已该枢纽为分界点,将序列分为两个子序列,重复上诉过程,直到区间缩短为1.

    /*
    写法一
    使用中间变量temph和templ,此方法不需要枢纽归位
    */
    import java.util.Arrays;
    
    public class Main{
        public static void main(String[] args){
            int[] date = new int[]{49,38,65,97,76,13,27};
            System.out.println(Arrays.toString(quickSort(0,date.length-1,date)));
        }
        
        //快速排序(升序排列)
        public static int[] quickSort(int low,int high,int[] date){
            int keyPoint = date[low];   //将最低位设置为枢纽
            int l = low,h = high;       //保存low,high的值方便递归调用
            
            while(l<h){
                //从high位置依次往前检索,碰到date[high]<keyPoint,就交换位置,否者则继续向前检索
                while(l<h && date[h]>=keyPoint){
                    h--;
                }
                int temph = date[h];
                date[h] = date[l];
                date[l] = temph;
        
                //从low位置依次向前检索碰到date[low]>keyPoint就交换位置,否者则继续向前检索
                while(l<h && date[l]<=keyPoint){
                    l++;
                }
                int templ = date[l];
                date[l] = date[h];
                date[h] = templ;
            }
            
            //递归调用
            if(low<high){
               quickSort(low,l-1,date);
               quickSort(l+1,high,date);
            }
    
           return date;
        }
    }
    

    分析
    附设两个指针low,high,他们的值分别是date[low]和date[high],枢纽的值为keyPoint。一趟快速排序的具体过程是,从high所指位置起向前搜索,当碰到date[high]的值小于keyPoint时交换位置,由于此时keyPoint的位置是date[low],所以代码为date[low] = date[high]。然后在从low的位置依次向前搜索,当碰到一个值大于keyPoint的值时,date[low]与keyPoint再次交换位置,而此时keyPoint的值为date[high],所以代码为date[high] = date[low],由此不停重复上两个过程,直到不满足low<high为止。

    /*
    写法二
    不使用中间变量,需要枢纽归位
    */
    
    public class Main{
        public static void main(String[] args){
             int[] date = new int[]{49,38,65,97,76,13,27};
        }
    
        //快速排序按升序排列
        public static int[] quickSort(int low,int high,int[] date){
             int keyPoint = date[low];  //设置枢纽
             int l = low,h = high;      //保存low和high的值,便于后续递归
             
             while(l<h){
                  while(l<h && date[h]>=keyPoint){
                     h--;
                  }
                  /*
                  直接将date[low]变成date[high],
                  由于第一次交换时必定交换枢纽值,而枢纽值已经保存,我们就可以不必担心
                  而当执行此操作时对应的date[high]的值便变成了两个,
                  再执行覆盖时,也不用担心数据的丢失问题
                  */
                  date[l] = date[h]; 
                  
                  while(l<h && date[l]<=keyPoint) {
                      l++;
                  }
                  date[h] = date[l];
             }
             
             date[l] = keyPoint;  //枢纽归位
    
             //递归
             if(low<high){
                quickSort(low,l-1,date);
                quickSort(l+1,high,date);
             }
              
            return date;
        }
    }
    

    以上即是对分治思想的简单引入,其关键是要理解将问题规模化。分治思想下,二分法是非常常用的方法,往往会配合递归的使用。

    展开全文
  • 求职必须会的几类算法,建议可以用这几个例子做这几个算法的入门练习(已经写了很详细的解释),了解算法思想之后再刷题会好很多。 写在最前边: 递归,分治,归并等等这种按规律依次拆开,又依次合并,...

    介绍一些经典算法,递归(二分法查找、欧几里得算法、汉诺塔、阶乘求解算法),穷举(泊松算法),贪心(背包),分治(循环赛日常表、棋盘问题),动态规划(最长公共子序列),回溯(八皇后),其他算法(约瑟夫杀人法)。

    求职必须会的几类算法,建议可以用这几个例子做这几个算法的入门练习(已经写了很详细的解释),了解算法思想之后再刷题会好很多。

    写在最前边:
    递归,分治,归并等等这种按规律依次拆开,又依次合并,循环迭代的方式最开始那步都是等待变量变成1(递归的出口),也就是分到1个单位,然后再一一合并回去。
    eg:
    if (size == 1){
    return;
    }

    1.递归

    图片: https://uploader.shimo.im/f/e9EeiV6SYEUMqcPr.png

    1.1汉诺塔

    在这里插入图片描述
    解释:现在要把三个盘子从A挪动到C:

    • 要把A最下边的那个盘子从A挪到C,要先把上边两个借助C挪到B;
    • 然后把最下边那个大的从A挪到C;
    • 再把剩下(目前在B上)的两个借助A挪到B(剩下两个的挪法,同上边挪动最大盘子的方法)。

    代码实现:

    package com.algorithm.recursion;
    
    /**
     * recursion:递归;
     * 汉诺塔:递归
     */
    public class HanNota {
        private int i = 1;
        public void hanNota(int n,char from,char dependOn,char to){
            //n表示在挪第n个盘子;
            if (n == 1){
                //当只有一个盘子要挪动的时候,直接从from挪动到to;(表示的是被挪动柱子上最上边的一个盘子)
                move(1,from,to);
            }else{
                hanNota(n-1, from, to, dependOn);//先将n-1个盘子从A利用C挪到B,n会一直减,直到n = 1,直接从from挪动到to
                move(n, from, to);                  //将n这个盘子(底盘)从A挪到C;
                hanNota(n-1, dependOn, from, to);//将n-1个盘子从B利用A挪到C;
            }
    
        }
    
        private void move(int n, char from, char to) {
            //移动过去之后直接打印作表示就可以;
            System.out.println("第" + i++ +"步:第" + n +"个盘子从" + from + "------->" + to);
           /* System.out.println("第" + i++ +"步从" + from + "------->" + to);*/
        }
    
        public static void main(String[] args){
            HanNota hn = new HanNota();
            hn.hanNota(3, 'A', 'B', 'C');
        }
    
    }
    
    

    1.2欧几里德法求两个数的最大公约数

    在这里插入图片描述
    代码:

    package com.algorithm.recursion;
    
    /**
     * 求一个数的最大公约数(简称:gcd)(欧几里德原理)
     * (m>n)m和n的最大公约数 = n 和m%n的最大公约数
     *   eg: 36 和 24  12      24和36%24=12     12和24%12=0  则只剩余12;
     */
    public class Gcd {
        public int gcd(int m ,int n){
            if (n == 0){
                return m;
            }else {
                return gcd(n, m%n);
            }
        }
    
        public static void main(String[] args){
            Gcd test = new Gcd();
            System.out.println(test.gcd(99, 11));
        }
    }
    

    1.3二分法查找

    代码:

    package com.algorithm.recursion;
    import com.sort.MergeSortSelf;
    
    /**
     * @author yn
     * @description 二分法查找:递归的方式和非递归的方式;
     */
    public class BinarySearchSelf {
        /**
         * 递归的方式
         * @param elem
         * @param array
         * @param low
         * @param high
         * @return
         */
        public int binarySearch(int elem,int[] array,int low,int high){
            if (low>high){
                return -1;
            }
            int middle = (low+high)/2;
            if (array[middle] == elem){
                System.out.println("找到这个元素的对应下标值为:" + middle);
                return middle;
            }
            if (array[middle] < elem){
                //找右边
                return binarySearch(elem, array, middle+1, high);
            }
            if (array[middle] > elem){
                //找左边
                return binarySearch(elem, array, low, middle-1);
            }
            return -1;
        }
    
        /**
         * 非递归的方式
         * @param array
         * @param elem
         * @return
         */
        public int directBinarySearch(int[] array,int elem){
            int low = 0;
            int high = array.length-1;
            while (low <= high){
                int middle = (low+high)/2;
                if(elem>array[middle]){
                    //往右边找
                    low = middle+1;
                }else if (elem<array[middle]){
                    //往左边找
                    high = middle-1;
                }else {
                    System.out.println("找到这个元素的下标:" + middle);
                    return middle;
                }
            }
            return -1;//跳出while循环还没有找到的时候,return -1;
        }
        public static void main(String[] args){
            BinarySearchSelf bbs = new BinarySearchSelf();
            int[] array = new int[]{1,2,6,3,5,32,9,10,23,34,45,56,78};
            MergeSortSelf mss = new MergeSortSelf();
            mss.mergeSort(array, 0, array.length-1);
            for (int num:array){
                System.out.print(num + " ");
            }
            bbs.binarySearch(10, array, 0, array.length-1);
            bbs.directBinarySearch(array, 23);
        }
    }
    

    1.4阶乘求解:

    这个比较简单

    package com.algorithm.recursion;
    
    /**
     * 递归求阶乘;
     */
    public class CalNFact {
        public int f(int n){
            if (n ==1){
                return n;
            }
            else{
                return n*f(n-1);
            }
        }
        public static void main(String[] args){
            CalNFact test = new CalNFact();
            System.out.println(test.f(5));
        }
    }
    
    

    2.动态规划:

    在这里插入图片描述

    2.1 最长公共子序列:

    图解:
    在这里插入图片描述
    在这里插入图片描述
    代码:

    package com.algorithm;
    
    /**
     * @author yn
     * 最长公共子序列(LCS)问题
     */
    public class LCS {
        public int findLCS(String m,String n){
            //x和y分别表示两个字符串的长度,根据各自的字符串长度构建二维数组;
            int x = m.length();
            int y = n.length();
            char[] mm = m.toCharArray();
            char[] nn = n.toCharArray();
            int[][] dp = new int[x][y];
    
            //第一行
            for (int i=0;i<x;i++){
                if (mm[i] == nn[0]){
                    dp[i][0] =1;
                    for (int j =i+1;j<x;j++){
                        dp[j][0] =1;
                    }
                    break;
                }
            }
    
            //第一列
            for (int i=0;i<y;i++){
                if (nn[i] == mm[0]){
                    dp[0][i] =1;
                    for (int j =i+1;j<y;j++){
                        dp[0][j] =1;
                    }
                    break;
                }
            }
    
            //计算其他位置要放的数字;这个数字的大小取决于动态规划思想中的前边特殊位置的值
            for (int i=1;i<x;i++){
                for (int j=1;j<y;j++){
                    if (mm[i] == nn[j]){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else {
                        dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                    }
                }
            }
            for (int i=0;i<x;i++){
                for (int j=0;j<y;j++){
                    System.out.print(dp[i][j]+" ");
                }
                System.out.println();
            }
            return dp[x-1][y-1];
        }
    
        public static void main(String[] args){
            LCS lcs = new LCS();
            int count = lcs.findLCS("android", "random");
            System.out.println("序列相同的个数是:" + count);
        }
    }
    

    附加几个动态规划的问题:
    找零钱问题; 走方格问题;
    走台阶问题(爬楼梯问题):
    问题描述:
    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
    链接:https://leetcode-cn.com/articles/climbing-stairs/

    • 方法1:暴力递归;
    • 方法2:记忆性递归;
    • 方法3:动态规划---->第三项等于前两项之和;

    3.穷举法:

    3.1泊松分酒:

    在这里插入图片描述
    代码:

    package com.algorithm;
    
    /**
     * 泊松分酒(穷举法);三个酒瓶,目标盛酒量
     * 制定一定的倒酒策略;
     * 1-->2-->3-->1
     *
     */
    public class ShareWine {
        private int b1 = 12;
        private int b2 = 8;
        private int b3 = 5;
        private int m = 6;  //目标酒量;
    
        //假设一开始是12,0, 0
        public void backBottle(int bb1,int bb2,int bb3){
            System.out.println("bb1:" + bb1 + " bb2:" + bb2 + " bb3:" + bb3);
            if (bb1 == m||bb2 == m||bb3 == m){
                //当有任意一个瓶子的容量等于目标酒量的时候就算是找到了这个瓶子;
                System.out.println("Find the bottle!");
                return;
            }
            //先看瓶子2,分情况,瓶子2里边有酒,瓶子3里边的酒不等于自己的容量,说明瓶子3没有满;
            if (bb2 != 0 && bb3 != b3){
                //把瓶子2的酒倒入瓶子3,将瓶子3倒满;
                //两种情况:把2里边的全部倒进3,3还没有满;3被倒满了,2中还有剩。
                if (bb2+bb3<b3){
                    //3瓶子倒不满。继续递归这个过程;
                    backBottle(bb1, 0, bb2+bb3);
                }else {
                    backBottle(bb1, bb2-(b3-bb3), b3);
                }
            }else if (bb3 == b3){
                //瓶子3满了,往瓶子1里边倒;
                if (bb3+bb1<b1){
                    //说明倒完后瓶子1没有满;
                    backBottle(bb1+bb3, bb2, 0);
                }else{
                    //把瓶子1倒满了;
                    backBottle(b1, bb2, bb3-(b1-bb1));
                }
            }else if (bb2 == 0){
                //从瓶子1往瓶子2里边倒酒;
                if (bb1 >= b2){
                    backBottle(bb1-b2, b2, bb3);
                }else {
                    backBottle(0, bb1, bb3);
                }
            }
        }
    
        public static void main(String[] args){
            ShareWine shareWine = new ShareWine();
            shareWine.backBottle(12, 0, 0);
        }
    
    }
    

    4.贪心算法:

    4.1背包问题:

    4.1.1.取价值最大;

    贪心算法:背包问题;

    1. 求价值,先拿价值大的,先对价值进行排序;
    2. 性价比相同的时候,应该先拿质量大的,因为按比例计算,大的价值更大;

    这个算法的写法没有拿到最优解;

    代码:

    package com.algorithm;
    
    import java.util.Arrays;
    /**
     * 贪心算法:背包问题;
     *
     * 求价值,先拿价值大的,先对价值进行排序;
     * 性价比相同的时候,应该先拿质量大的,因为按比例计算,大的价值更大;
     * 这个算法的写法没有拿到最优解;
     */
    public class GreedyPackage {
        private int MAX_WEIGHT = 150;//背包最大容量;
        private int[] weights = new int[]{35,30,60,50,40,10,25};
        private int[] values = new int[]{10,40,30,50,35,40,30};
    
        private void packageGreedy(int capacity,int[] weights,int[] values){
            int n = weights.length;
            double[] r = new double[n];//性价比数组;
            int[] index = new int[n];//按性价比排序的 物品的下标;
            for (int i=0;i<n;i++){
                r[i] = (double)values[i]/weights[i];//double类型数字除以整数还是double类型;
                index[i] = i;
            }
            
            //对性价比进行排序;用冒泡排序;从大到小排序,性价比高的在前边;(性价比相同的情况下将重量小的排在前边)
              double temp = 0;
            for (int i = 0;i<n-1;i++){
                for (int j=i+1;j<n;j++){
                    if (r[j] > r[i]){
                        temp = r[j];
                        r[j] = r[i];
                        r[i] = temp;
                        //性价比排完序之后,对应的物品的下标也要进行排序,才能使得性价比和对应物品下标一一对应;
                        int x = index[j];
                        index[j] = index[i];
                        index[i] = x;
                    }
                }
            }
    
            //排序好的重量和价值分别存到数组;
            int[] w1 = new int[n];
            int[] v1 = new int[n];
            for (int i=0;i<n;i++){
                w1[i] = weights[index[i]];
                v1[i] = values[index[i]];
            }
    
            //开始给背包里边装东西啦啦啦!挖金子咯!吼吼吼!
            //往背包中装东西这段还有可以改进的空间,根据具体情况修改装东西的规则;
            int[] x = new int[n];   //物品有没有被拿,这里是拿了之后用1标记;
            int MaxValue = 0;       //最终装的所有物品的价值之和,不是重量,重量是由MAX_WEIGHT控制决定的;
            for (int i =0;i<n;i++){
                if (w1[i]<capacity){
                    x[i] = 1;
                    MaxValue += v1[i];
                    System.out.println("重量为" + w1[i] +"的物品被装进包包。");
                    capacity = capacity - w1[i];
                }
            }
            System.out.println("总共放下的物品数量:" + Arrays.toString(x));
            System.out.println("最大价值(所装物品的价值之和):" + MaxValue);
        }
    
        public static void main(String[] args){
            GreedyPackage gptest = new GreedyPackage();
            gptest.packageGreedy(gptest.MAX_WEIGHT, gptest.weights, gptest.values);
        }
    }
    

    但是实际中情况很多
    视频中的疑点:
    在这里插入图片描述
    如果 4对应的是16 那就选第二种情况;

    特殊情况(如下):
    在这里插入图片描述
    视频中的解法没有拿到最优解,只是尽可能大的价值最大值

    4.1.2.单一背包问题:

    最终拿的物品的体积必须是背包的体积,不能多不能少;

    5.分治算法:

    5.1循环赛(体育赛事)日程安排(球赛):

    图片: https://uploader.shimo.im/f/gfpHZnczEwMsEY60.png
    其实就是矩阵的特殊排列,使用到了递归,
    有点像归并,先递归分治,再一一返回合并填充(按照规律);
    代码:

    package com.algorithm;
    
    /**
     * 分治法:球赛的日程安排
     * 中间也叠加了递归的思想;8分4,4分2,2分1;然后开始一一返回去;
     */
    public class SportsSchedule {
        public void sportsSchedule(int[][] table,int n){
            if (n == 1){
                //当n等于1的时候,也就是只有一支球队,二维table数组的[0][0]位置就只有一个1;
                table[0][0] = 1;
            }else{
                //填充左上区域矩阵
                int m = n/2;
                sportsSchedule(table, m);
                //填充右上区域矩阵;
                for (int i=0;i<m;i++){
                    for (int j=m;j<n;j++){
                        table[i][j] = table[i][j-m] + m;
                    }
                }
                //填充左下区域矩阵;
                for (int i=m;i<n;i++){
                    for (int j=0;j<m;j++){
                        table[i][j] = table[i-m][j] + m;
                    }
                }
                //填充右下区域矩阵;
                for (int i=m;i<n;i++){
                    for (int j=m;j<n;j++){
                        table[i][j] = table[i-m][j-m];
                    }
                }
            }
        }
        public static void main(String[] args){
            SportsSchedule sstest = new SportsSchedule();
            int[][] table = new int[16][16];
            int n = 16;
            sstest.sportsSchedule(table,n);
            int c = 0;
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++){
                    System.out.print(table[i][j] + "  ");
                    c++;
                    if (c%n == 0){
                        //到8个数时候换行;一行一行打印;
                        System.out.println();
                    }
                }
            }
        }
    }
    

    5.2棋盘问题(L型,骨盘)

    图片: https://uploader.shimo.im/f/0Ux9IGk7hDwf8pZ8.png
    代码:

    package com.algorithm;
    
    /**
     * 棋盘问题;
     * L型矩阵
     */
    public class ChessBoradProblem {
        private int[][] board;//棋盘
        private int specialRow;//特殊点的行下标;
        private int specialCol;//特殊点的列下标;
        private int size;
        private int type = 0;
    
        //添加构造方法;
        public ChessBoradProblem(int specialRow, int specialCol, int size) {
            super();
            this.specialRow = specialRow;
            this.specialCol = specialCol;
            this.size = size;
            board = new int[size][size];
        }
    
        /**
         *
         * @param speacialRow 特殊点的行下标
         * @param specialCol  特殊点的列下标
         * @param leftRow     矩阵的左边起点行下标
         * @param leftCol     矩阵的左边起点列下标
         * @param size        矩阵的宽或者高
         */
        private void chessBorad(int speacialRow,int specialCol,int leftRow,int leftCol,int size){
            if (size == 1){
                return;
            }
            int subSize = size/2;
            type = type%4 + 1;
            int n = type;
            //假设特殊点在左上角区域:
            if (speacialRow < leftRow + subSize && specialCol < leftCol + subSize){
                chessBorad(speacialRow, specialCol, leftRow, leftCol, subSize);
            }else{
                //不在左上角,左上角矩阵的右下角矩阵就是特殊点;??
                board[leftRow+subSize-1][leftCol+subSize-1] = n;
                chessBorad(leftRow+subSize-1, leftCol+subSize-1, leftRow, leftCol, subSize);
            }
            //假设特殊点在右上角区域:
            if (speacialRow < leftRow + subSize && specialCol >= leftCol + subSize){
                chessBorad(speacialRow, specialCol, leftRow, leftCol + subSize, subSize);
            }else{
                board[leftRow + subSize - 1][leftCol + subSize] = n;
                chessBorad(leftRow + subSize - 1, leftCol + subSize, leftRow, leftCol + subSize, subSize);
            }
            //假设特殊点在左下角区域:
            if (speacialRow >= leftRow + subSize && specialCol < leftCol + subSize){
                chessBorad(speacialRow, specialCol, leftRow + subSize, leftCol, subSize);
            }else{
                board[leftRow + subSize][leftCol + subSize -1] = n;
                chessBorad(leftRow + subSize, leftCol + subSize -1, leftRow + subSize, leftCol, subSize);
            }
            //假设特殊点在右下角区域:
            if (speacialRow >= leftRow + subSize && specialCol >= leftCol + subSize){
                chessBorad(speacialRow, specialCol, leftRow + subSize, leftCol + subSize, subSize);
            }else{
                board[leftRow + subSize][leftCol + subSize] = n;
                chessBorad(leftRow + subSize, leftCol + subSize, leftRow + subSize, leftCol + subSize, subSize);
            }
    
        }
    
        public static void main(String[] args){
            int N =4;
            int specialRow = 0;
            int specialCol = 1;
            ChessBoradProblem cbptest = new ChessBoradProblem(specialRow, specialCol, N);
            cbptest.chessBorad(specialRow, specialCol, 0, 0, N);
            cbptest.printChess();
    
        }
    
        private void printChess() {
            for (int i =0;i<size;i++){
                for (int j =0;j<size;j++){
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
    
    

    6.回溯:

    6.1 八皇后问题:

    图片: https://uploader.shimo.im/f/KGQPmNYRlsgoVtuH.png
    代码:

    package com.algorithm;
    
    /**
     * @author yn
     * @description 八皇后的问题
     */
    public class Queen {
        public static int num = 0;//累计方案;
        public static final int MAXQUEEN = 8;
        public static int[] cols = new int[MAXQUEEN];//定义cols数组,表示8列棋子皇后摆放的位置;
    
        /**
         *  n 表示第n列的皇后,rows[]表示这列中那个位置不能放的标记;
         * @param n 填第n列的皇后;
         */
        public void getCount(int n){
            boolean[] rows = new boolean[MAXQUEEN];//记录每列每个方格是否可以放皇后;
            for (int m =0;m<n;m++){
                rows[cols[m]] = true;
                int d = n - m;//斜对角
                //正斜方向
                if (cols[m]-d>=0){
                    rows[cols[m] - d] = true;
                }
                //反斜方向
                if (cols[m]+d<=(MAXQUEEN-1)){
                    rows[cols[m]+d] = true;
                }
            }
            //到此知道了哪些位置不能放皇后;
            for (int i = 0;i<MAXQUEEN;i++){
                if (rows[i]){
                    //不能放
                    continue;
                }
                cols[n] = i;
                if (n < MAXQUEEN - 1) {
                    getCount(n+1);
                }else {
                    //找到完整的一套方案
                    num++;
                    printQueen();
                }
                //下面可能仍有合法位置;
            }
        }
    
        private void printQueen() {
            System.out.println("第"+num+"种方案");
            for (int i=0;i<MAXQUEEN;i++){
                for (int j=0;j<MAXQUEEN;j++){
                    if (i == cols[j]){
                        System.out.print("0 ");
                    }else{
                        System.out.print("+ ");
                    }
                }
                System.out.println();
            }
        }
        public static void main(String[] args){
            Queen queen = new Queen();
            queen.getCount(0);
        }
    
    }
    
    

    7.其他

    7.1约瑟夫杀人法

    package com.algorithm;
    
    /**
     * @description: 约瑟夫杀人法
     */
    public class JosephKill {
        public static int n = 5;//一共n个人
        public static int m = 3;//数到m就咔嚓一个人。
        class Node{
            int val;
            Node next;
            public Node(int val){
                this.val = val;
            }
        }
    
        public void killNode(){
            Node header = new Node(1);//第一个节点;
            Node x = header;//被点到的人;
            for (int i=2;i<n+1;i++){
               x=(x.next = new Node(i));
            }
            x.next = header;
            System.out.println("被咔嚓的顺序为:");
            while(x!=x.next){
                //至少还有两人;
                for (int i=1;i<m;i++){
                     x = x.next;
                }
                System.out.println(x.next.val + "被干掉了。");
                x.next = x.next.next;
            }
            System.out.println("最后留下来的是" + x.val);
        }
        public static void main(String[] args){
            JosephKill josephKill = new JosephKill();
            josephKill.killNode();
        }
    }
    
    

    这也是自己学习算法的一篇笔记,共勉,欢迎大家留言批评指正!

    展开全文
  • 算法:减治法分治法和变治法

    千次阅读 2019-03-11 17:54:28
    减治法、分治法和变治法是优化算法的三种基本方法,本篇主要描述三种方法的基本思想,不提供经典 例子以供分析,但在随后的篇文章当中会具体讲解实例深刻理解这三种方法。本篇以及随后的算法文章 的理论以及...

    概要

    		减治法、分治法和变治法是优化算法的三种基本方法,本篇主要描述三种方法的基本思想,不提供经典
    	例子以供分析,但在随后的几篇文章当中会具体讲解实例深刻理解这三种方法。本篇以及随后的算法文章
    	的理论以及示例主要依据Anany Levitin教授所编写的《算法设计与分析基础》。
    

    减治法

    			减治法(decrease-and-conquer method)利用了一个问题给定的解和同样较小的实例的解之间的某
    		种关系。一旦这种关系确定之后,我们既可以从顶至下,也可以从底至上地来运用该关系。
    

    它主要有三种变换的形式:

    • 减去一个常量

    • 减去一个常量因子

    • 减去的规模是可变的

        下面来谈一下对概念的理解,通过这个概念的前几句可以看出,是将大问题分解成小问题来解决的,像是一个金字塔的层次结构,由大问题分成一层一层的问题从最基础的几个单元开始,最后堆砌成一个大的金字塔,但在后续的学习过程中通过示例又发现它和传统意义上的分层次的金字塔又不太一样,更像是一种层层嵌套的一种结构。如下图所示:

        如上图所示,我们可以将它视为一个集合有n个元素,我们有理由的相信,这个集合可以通过一系列规则只用知道其中的一个元素就可以求出其它所有元素,然后就形成了如上图的一种结构。而减治法大概也采用的是这样一种思路。
        再说明一下减治法的三种基本形式,减去一个常量就是n个元素我们减去C个元素(C是一个正整数),减去一个常量因子我们可以认为将这个集合的元素一分为二或者分成多份。比如将上图中的n-1改为n/2,减去的规模是可变的我们可以认为一个集合中每次减去的规模不一样,比如有n个元素的集合,我第一次减去一个元素成为n-1第二次减去了n/2的元素成为(n-1)/2.

    分治法

    		分治法(divide-and-conquer method)是将一个问题划分成多个同一类型的子问题(子
    	问题最好规模相同),之后求这些子问题的解,如果有必要的话合并这些子问题的解,以得到	
    	原始问题的答案。
    

      因为这个基础概念比较容易理解因此不再绘图,我们可以将其理解一个树结构的处理问题方式,比如一个问题将其抽象为求n,然后分成了两个求n/2的问题,之后两个求n/2的问题又接着分形成了四个求n/4的问题,最后求得n/4的解,经过回溯得到了原本求n问题的答案。

    变治法

    		变治法(transform-and-conquer)将同样的问题变成一个简单的方便的实例,或者变换同样实例
    	的不同表现,或者变换为另一个问题的实例。
    

      这个方法的思路类似于数学建模的思路,将生活的问题进行简单的抽象,以便对此进行研究,举一个简单的例子:
      在操场(欧几里得平面)上有n>=3个人,每个人都有唯一一位最近的邻居,他们手上拿着1块奶油块,收到信号后,都会把派扔向他最近的邻居。假设n是奇数,而且每个人都可以100%命中对方,请判断对错:每次至少有一个人不会被奶油派击中
      这个问题应该是正确的,我们来以3个人A,B,C举例,假如A与B的距离为c,B与C的距离为a,C与A的距离为b,那么如果每个人都会被扔到那么他们的距离关系应当满足c<a,b<c,a<c;显然我们发现这是存在前后矛盾的因此我们可以断定每次至少有一个人不会被奶油派击中是正确的。
      这是将实际问题抽象的一个例子,将人抽象成点,将距离抽象成线的长度,并且利用反证法来证明这个假设。

    展开全文
  • 数据结构与算法分析

    2013-10-15 22:42:42
     4.8.4 使用几个map的例子   小结   练习   参考文献  第5章 散列   5.1 基本思想   5.2 散列函数   5.3 分离链接法   5.4 不使用链表的散列表   5.4.1 线性探测   5.4.2 ...
  • 3.5.1 分治算法基本思想 92 3.5.2 分治算法示例 92 3.6 概率算法思想 96 3.6.1 概率算法基本思想 96 3.6.2 概率算法示例 97 3.7 小结 98 第2篇 算法基本应用篇 99 第4章 排序算法 100 4.1 排序算法概述 100 ...
  • 3.5.1 分治算法基本思想 92 3.5.2 分治算法示例 92 3.6 概率算法思想 96 3.6.1 概率算法基本思想 96 3.6.2 概率算法示例 97 3.7 小结 98 第2篇 算法基本应用篇 99 第4章 排序算法 100 4.1 排序算法概述 100 ...
  • 通过学习“算法设计与分析”课程,我想对于那些经典算法,除了在理论上“认识”他们外,最主要是在思想上学会他们,接受他们,这样不知不觉地培养了我们一种严密的思维能力... 下面介绍的几个应用例子都是相对来说不

          通过学习算法设计与分析课程,我想对于那些经典的算法,除了在理论上认识他们外,最主要是在思想上学会他们,接受他们,这样不知不觉地培养了我们一种严密的思维能力,并且运用所学知识结合具体问题设计适用的算法的能力。而且那些经典算法也有很多复杂的应用领域,但是对于没有涉足这方面的人来说,由认识他们再上升到算法思想上的掌握也是很有必要的。

        下面介绍的几个应用例子都是相对来说不是很难的,主要是先有一种感性的认识。
    •     有关 分治法思想
        分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以: 1) 把它分成两个或多个更小的问题;
    2) 分别解决每个小问题;
    3) 把各小问题的解答组合起来,即可得到原问题的解答。
    小问题通常与原问题相似,可以递归地使用分而治之策略来解决。
       中位数问题
        问题的提出
       对于两个长度均为n的已排序的序列,确定这两个序列的2n个元素的中位数
       解决此问题的算法思想
     设两个长度为n的数列分别为x[ 0 : n -1]y[ 0 : n -1],分别找出这两个数列的中位数x[i]
    y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取
    两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果
     求解过程
     查找范围确定:
    •  n为奇数时,令n=2m +1,则两个数列的中位数分别为x[ m ] y[ m ],则:
      x[0:m-1]<x[m]<x[m+1:2m]

      y[0:m-1]<y[m]<y[m+1:2m]
      x[m]<y[m]
      若整体中位数x[k]x[0:m-1]中,则
      x[k]<x[m]<x[m+1:2m] x[k]<y[m]<y[m+1:2m]
      x[k]至少小于2m+2n+1个数,而整体的中位数应该是第n个数,它小于n个数,所以整体中位数不在x的前半部分,同样不会在y的后半部分。
       x[m]至少小于n个数,y[m]至少大于n个数,所以这两个局部中位数都有可能成为整体中位数.    
       所以再次查找范围为x[m:2m]y[0:m]
    • n为偶数时,令n=2m ,则两个数列的中位数分别为x[ m-1 ] y[ m-1 ],则:
      x[0:m-2]<x[m-1]<x[m:2m-1]

      y[0:m-2]<y[m-1]<y[m:2m-1]
      x[m-1]<y[m-1]
      若整体中位数x[k]x[0:m-2]中,则
      x[k]<x[m-1]<x[m:2m-1] x[k]<y[m-1]<y[m:2m-1]
      x[k]至少小于2m+1即n+1个数,而整体的中位数应该是n个数,它小于n个数,所以整体中位数不在x的前半部分,同样不会在y的后半部分。
       x[m-1]至少小于n+1个数,所以其不会成为整体中位数,y[m-1]至少大于n-1个数,所以它有可能成为整体中位数
       所以再次查找范围为x[m:2m-1]y[0:m-2]
    举个例子:
    x={10, 15, 16, 19, 24}
    y={11, 17, 18, 20, 23}
    x1={16, 19, 24} y1= {11, 17, 18 }
    x2={16,19} y2={17,18}
    x2={19} y2={17}  ————
    出口,应单独处理
    x={10, 15, 16, 19}
    y={11, 17, 18, 20}
    x1={16, 19} y1= {11, 17}
    x2={16} y2={17}
    mid=16
    数据输入
    由文件input.txt提供输入数据。文件的第1行中有1个正整数nn<=200),表示每个数组有n个数。接下来的两行分别是XY数组的元素。 
    输入文件示例
    输出文件示例
    input.txt
    output.txt
    3
    5 15 18
    3 14 21
    14
    C++实现:
     
    #include <iostream>
    #include <fstream>
    using namespace std;

    int findMedian(int*, int*, int);

    int main()
    ...{
        ifstream 
    in("in.txt");
        ofstream 
    out("d://out.txt");

        
    int n;
        
    int *x,*y;

        
    in>>n;
        x=
    new int[n];
        y=
    new int[n];

        
    for(int i=0;i<n;i++)
            
    in>>x[i];
        
    for(i=0;i<n;i++)
            
    in>>y[i];

        
    int median=findMedian(x, y, n);

        cout<<median<<endl;

        
    out<<median;

        
    in.close();
        
    out.close();

        
    return 1;
    }

    int findMedian(int* x, int* y, int n)
    ...{
        
    if(n==1)
            
    return *x <= *y? *x:*y;
        
        
    int m=(n-1)/2;    //
    中位数位置
        int p=m+1;    //中位数小者子数字起始位置

        
    if(n%2!=0)    //n为奇数
            p--;

        
    if(*(x+m)==*(y+m))
            
    return *(x+m);
        
    else if(*(x+m)(y+<*m))
            
    return findMedian(x+p,y,m+1);
        
    else
            
    return findMedian(x,y+p,m+1);
    }
    Gray码问题
    Gray码是一个长度为2n的序列。序列中无相同的元素,每个 元素长度都为n位的串,相邻元素恰好之有一位不同,对任意的n位如何构造相应的Gray码。
    对于n=4的Gray码,如下图所。
     
    上图 第1列从最左边算起
    实现这个问题的方法是,递归上半部分,下半部分对称复制上半分部即可
    由文件input.txt提供输入数据n。
    用C++ 实现:
     
    #include <iostream>
    #include 
    <fstream>
    #include 
    <stdio.h>
    #include 
    <math.h>

    using namespace std;

    void Graycode( int a, int b, int ** arr)
    {
        
    //递归出口
        if(a==1)
            
    return;
        
    //处理当前列
         for(int i = 0; i < a/2 ; i++)
         
    {
             arr[i][b
    -1= 0;//上半部分赋值为0
             arr[a-i-1][b-1]=1//下半部分赋值为1
         }


        
    //处理子问题
        Graycode(a/2,b-1,arr);//递归调用子问题,生成列数为b-1的Gray码,填写高半部分    

        
    for(int k = a/2; k<a; k++)//将(n-1)位的Gray码逆序后,填入目标码字/的低半部分
            forint j =0; j<b-1; j++)
                 arr[k][j]
    =arr[a-k-1][j];

            
    }


    int main()
    {

        
    int n;
        ifstream 
    in("in.txt");
        ofstream 
    out("d://out.txt");
        
    in>>n;
        
    int row=pow(2,n);
        
    int **arr=new int*[row];
        
    for(int m=0;m<row;m++){
        arr[m]
    =new int[n];
        }

        Graycode(row,n,arr);
        
    for(int i=0;i<row;i++)
        
    {
            
    for(int j=0;j<n;j++)
                cout
    <<arr[i][j];
                cout
    <<endl;
        }

        
    in.close();
        
    out.close();
        
    return 1;
    }
    • 有关动态规划的思想
    零钱问题

    设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱,可以实用的各种面值的硬币个数不限。当只用硬币面值T[1],T[2],…,T[i]时,可找出钱数j的最少硬币个数记为C(i,j)。若只用这些硬币面值,找不出钱数j时,记C(i,j)=∞:

    « 数据输入

    由文件input.txt提供输入数据。文件的第1行中有1个正整数nn<=13),表示有n种硬币可选。接下来的一行是每种硬币的面值。由用户输入待找钱数j

    使用C++语言实现

    #include <fstream>
    #include 
    <iostream>
    #include 
    <algorithm>

    using namespace std;

    int changeCoins(int *T, int n, int v);

    int main()
    {
        ifstream 
    in("in.txt");
        ofstream 
    out("d://out.txt");

        
    int n;
        
    int v;

        
    in>>n;
        
    int *T=new int[n];
        
    for(int i=0;i<n;i++)
        
    {
            
    in>>T[i];
        }


        
    in>>v;

        
    int result=changeCoins(T,n,v);
        
        cout
    <<result<<endl;

        
    out<<result;

        
    in.close();
        
    out.close();

        
    return 1;
    }



    int changeCoins(int *T, int n, int v)
    {
        
    //先对3个硬币按面值进行排序
        sort(T,T+n);
        
    int **c=new int*[n];
       
    for(int m=0;m<n;m++){
        c[m]
    =new int[v+1];
        }

        
    //初始化第一行,只有一个硬币时的情况
       for(int i=0;i<=v;i++)
            
    if(i%T[0]==0)
                c[
    0][i]=i/T[0];
            
    else
                c[
    0][i]=INT_MAX;
        
    //从第二行开始
        for(int j=1;j<n;j++)
            
    for(int k=0;k<=v;k++)
                      
    //新加进来的硬币大于要找的钱,用不到这个硬币,所以还是跟上一行的一样
                if(k<T[j])
                    c[j][k]
    =c[j-1][k];
                
    else
                    c[j][k]
    =c[j-1][k]<c[j][k-T[j]]+1?c[j-1][k]:c[j][k-T[j]]+1;
        
    return c[n-1][v];


        delete[] c;
    }



    展开全文

空空如也

空空如也

1 2 3
收藏数 60
精华内容 24
关键字:

分治算法几个经典例子