万字长文,佩奇算法八大思想!
零、前言
1. 什么是算法?
2. 算法的重要性?
3. 算法怎么学?
一、枚举
X
,然后逐一在 f()
计算中进行验证,根据验证结果对「可能解」进行验证。这是一种结果导向型的思想,简单粗暴地试图从最终结果反向分析「可能解」。《案例》
这个问题源于1500年前的《孙子算经》原文如下: 今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?
* 穷举算法思想
* 今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何?
* 解法:通过题目可以知道,鸡和兔的总数量为0-35只(每个动物都是一个脑袋,这就不用说了吧),
* 我们可以假设鸡为0,兔子为35,用鸡的个数*2 兔子的个数*4就可以得到总的脚的数量,如果等于94,那么便是答案,
* 如果不等,则鸡的数量 1,兔子数量-1,依次类推,穷举所有情况直到得到答案
*/
public static void enumeratingAlgorithm() {
int head = 35, foot = 94;
int j;
for (int i = 0; i <= 35; i ) {//i代表鸡的数量
j = head - i;//j代表兔子的数量
if (i * 2 j * 4 == foot) {
System.out.printf('鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。', i, j);
return;
}
}
System.out.printf('此题无解!你家鸡和兔子有三只脚的吧?');
}
二、递推
《案例》
这个问题癞子13世纪意大利数学家斐波那契的《算盘书》,问题的大意如下: 如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子初剩两个月后才可以生小兔子。也就是说,1月份出生,3月份才可以产仔。那么假定一年没有产生兔子死亡事件,问一年后共有多少对兔子?
Fn=F(n-1) F(n-2)
,这里的n是第n个月,这里初始第1个月的兔子数为F1=1,F2=1
。* 递推算法
* 如果一对两个月大的兔子以后每一个月都可以生一对小兔子,而一对新生的兔子初剩两个月后才可以生小兔子。
* 那么假定一年没有产生兔子死亡事件,问一年后共有多少对兔子?
* 解法:
* 头两个月,兔子都是只有一对,第三个月是2对,第四个月是3对,第五个月是5对。。。
* 由此可以看出。从第三个月开始,每个月的兔子对数,等于前两个月之和。
* 所以第n个月的兔子对数为 fₙ = fₙ₋₂ fₙ₋₁
*
* @param month 月份
*/
public static int recursiveDeduceAlgorithm(int month) {
int f1, f2;
if (month == 1 || month == 2) {
return 1;
}
f1 = recursiveDeduceAlgorithm(month - 1);//递归调用
f2 = recursiveDeduceAlgorithm(month - 2);//递归调用
return f1 f2;//根据fₙ₋₁和fₙ₋₂,推导出fₙ
}
int num = recursiveDeduceAlgorithm(month);
System.out.println('经过 ' month ' 个月,共有 ' num ' 对兔子。');
三、递归
直接递归 ,在方法中调用自身。 间接递归,间接的调用一个方法。比如方法a调用方法b,方法b又调用方法a。
《案例》
所谓阶乘,就是从1到指定数之间的所有自然数相乘的结果。n的阶乘为:n! = n * (n-1) * (n-2) * ······ * 2 * 1
* 递归算法思想
* 求阶乘(factorial)问题
* n的阶乘为:n! = n * (n-1) * (n-2) * ······ * 2 * 1
* 解法,每一项都等于前一项-1,结果也等于之前的结果*前一项-1
* 我们这里用int,要注意int的取值范围,不要超过int的上限。
* @param n 求n的阶乘
* @return n的阶乘
*/
public static int recursiveAlgorithm(int n) {
if (n <= 1) {
return 1;
}
return n * recursiveAlgorithm(n - 1);//递归调用
}
int result = recursiveAlgorithm(n);
System.out.println(n ' 的阶乘为: ' result)
四、分治
《案例》
* @description: 归并排序
* 时间复杂度:O(nlogn)
* 空间复杂度:O(n)
* 稳定排序
* 非原地排序
* @author: Kevin
* @createDate: 2020/2/13
* @version: 1.0
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 5, 3, 9};
userMergeSort(arr);
System.out.println('sorted arr:');
for (Integer i:arr) {
System.out.println(i);
}
}
private static void userMergeSort(int[] arr){
if (arr == null || arr.length == 0) {
return;
}
mergeSort(arr,0,arr.length-1);
}
/**
* 将数组 arr[left] --> arr[right] 进行归并排序
* @param arr 要排序的数组
* @param left 左边界
* @param right 右边界
*/
private static void mergeSort(int[] arr,int left,int right){
//终止条件 --> left == right 的时候,就递归到只有一个元素,则不用递归
if (left < right) {
// [分]: 将数组一分为二
int center = (left right)/2;
// int center = (left right)>>1; // 位运算写法
// [治]: 将左边的数组排序(left --> center)
mergeSort(arr,left,center);
// [治]: 将右边的数组排序(center 1 --> right)
mergeSort(arr,center 1,right);
// [合]: 合并两个有序数组
merge(arr, left, center, right);
}
}
/**
* 将 arr[left...center] 和 arr[center 1...right] 两个有序数组合并为一个有序数组
* @param arr
* @param left
* @param center
* @param right
*/
private static void merge(int[] arr, int left, int center, int right) {
//先用一个临时数组把他们合并汇总起来
int[] temp = new int[arr.length];
int i = left,j = center 1;
// 先通过比较将两个有序数组合并为一个有序数组,结果暂存到 temp 数组
for (int k = left;k<=right;k ){
// 如果左边数组 arr[left...center] 中的元素取完[即比较完](i>center),
// 则直接复制右边数组的元素到辅助数组。右边数组同理
if (i>center) { temp[k] = arr[j ]; }
else if(j>right) { temp[k] = arr[i ]; }
// 合并时,比较两有序数组值,将小的放入辅助数组中
else if(arr[i]<=arr[j]) {temp[k] = arr[i ]; }
else {temp[k] = arr[j ]; }
}
// 再将已经排序好的辅助数组中的值复制到原数组 arr 中
for (int k=left;k<=right;k ){
arr[k] = temp[k];
}
}
}
五、动态规划
动态规划是我比较喜欢的一个算法,它就像人生规划,我们当前所做的抉择受到之前状态的影响,我们当下所遇到的问题可能在之前已经有过答案,并且不论过去状态和决策如何,对之前状态而言,当下的决策必须构成最优策略。
F0
等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。G()
函数,这也是动态规划很难真正掌握的原因。《案例》
有一个可载重量为 W
的背包和N
件物品,每个物品有重量和价值两个属性。其中第i
个物品的重量为weight[i]
,价值为value[i]
。现在让你用这个背包装物品,最多能装的价值是多少?
public static void main(String[] args) {
int W = 4, N = 3;
int[] weight = {2,1,3}, value = {4,2,3};
int maxValue = knapsack(W,N,weight,value);
System.out.println(maxValue); //6
}
/**
* 0-1背包问题
*
* @param W 背包容量
* @param N 物品种类
* @param weight 物品重量
* @param value 物品价值
* @return
*/
public static int knapsack(int W, int N, int[] weight, int[] value) {
// 初始化动态规划数组,「状态」有两个:用二维数组:一维表示可选的物品,二维表示背包的容量
int[][] dp = new int[N 1][W 1];
// 已经有初始值,dp[0][j] = dp[i][0] = 0 (没有物品或者没有背包空间的时候,能装的最大价值就是0)
for (int i = 1; i < N 1; i ) {
for (int j = 1; j < W 1; j ) {
if (j - weight[i - 1] < 0) {
// 当前背包容量装不下,只能选择不装入背包
dp[i][j] = dp[i - 1][j];
} else {
// 两种选择:不装 或装入背包,择优
// 如果不装第 i 个物品:最大价值为 dp[i-1][j](dp[i][j] = dp[i-1][j] 0)
// 如果装入第 i 个物品:最大价值为 dp[i][j] = dp[i-1][j- weight[i-1]] value[i-1]
// 因为 i 是从 1 开始的,所有 weight 和 value 的取值是 i-1
// dp[i-1][j- weight[i-1]]:在装第 i 个物品前提下,背包能装的最大价值是多少
// value[i-1]:加上第 i 个物品的价值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] value[i - 1]);
}
}
}
// 容量为W的背包能装入物品的最大价值
return dp[N][W];
}
}
六、贪心
《案例》
活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 设有n个活动的集合e={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i,则它在半开时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交,则称活动i与活动j是相容的。也就是说,当si≥fi或sj≥fj时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
/**
* 活动时间安排
*/
public static void main(String[] args) {
int[] start = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int[] end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
List<Integer> results = arrangeActivity(start, end);
for (int i = 0; i < results.size(); i ) {
int index = results.get(i);
System.out.println('开始时间:' start[index] ',结束时间:' end[index]);
}
//开始时间:1,结束时间:4
//开始时间:5,结束时间:7
//开始时间:8,结束时间:11
//开始时间:12,结束时间:14
}
/**
* 活动安排
*
* @param s 开始时间
* @param e 结束时间
* @return
*/
public static List<Integer> arrangeActivity(int[] s, int[] e) {
int total = s.length;
int endFlag = e[0];
List<Integer> results = new ArrayList<>();
results.add(0);
for (int i = 0; i < total; i ) {
if (s[i] > endFlag) {
results.add(i);
endFlag = e[i];
}
}
return results;
}
}
七、回溯
《案例》
给定一个 没有重复 数字的序列,返回其所有可能的全排列。 例如: [1,2,3]其全排列为:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
/* 主函数,输入一组不重复的数字,返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}
// 路径:记录在 track 中
// 选择列表:nums 中不存在于 track 的那些元素
// 结束条件:nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i ) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}
八、模拟
《案例》
用计算机实现一个随机数1到100之间的数字,然后由用户来猜这个数,根据用户的猜测数量分别给出不同的提示
public static void main(String[] args) {
int aimNum = 0, guessNum = 0, guessCount = 0; // 目标数字,猜的数字,猜的次数
int max = 100, min = 1; // 比较数范围
Random rand = new Random();
aimNum = rand.nextInt(100) 1; // 生成[1, 100]的随机数
System.out.printf('aim num: %d\n', aimNum);
do {
System.out.printf('%d < 目标数 < %d, 输入你猜的数字:', min, max);
Scanner scanner = new Scanner(System.in);
guessNum = scanner.nextInt(); //输入你猜的数字
guessCount ; // 统计猜数字的次数
if (guessNum > aimNum) {
System.out.printf('猜大了\n');
max = guessNum; // 刷新最大值
}else if (guessNum < aimNum) {
System.out.printf('猜小了\n');
min = guessNum; // 刷新最小值
}
} while (guessNum != aimNum);
System.out.println('恭喜你~猜对啦!');
System.out.printf('共猜了%d次\n', guessCount);
if (guessCount <= 5){
System.out.println('你也太聪明了吧,这么快就猜出来了!');
}else {
System.out.println('还需改进哦,相信你下次可以更快的!');
}
}
}
九、总结
虚心求赞,我是小浩。