「考研算法」

考研算法

前言

本系列文章涉及的算法内容，针对的是哈尔滨工业大学854科目。在本文中通过具体的算法题进行讲解相应算法。

今天涉及的算法主要有线性筛，十大排序中快速排序和归并排序。

后续会有动态规划的相关算法以及尝试模型的总结，如果对动态规划有兴趣的，可以看我之前的这篇文章，后边都是以这样的形式进行每个动态规划知识点的讲解。
链接如下：https://blog.csdn.net/qq_45992664/article/details/123341143?spm=1001.2014.3001.5502

---

一、线性筛算法

算法题目：筛质数

给定一个正整数 n，请你求出 1∼n中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n中质数的个数。

数据范围

1 ≤ n ≤ 10^6

输入样例：

8

输出样例：

4

算法思路：

1. 切记1不是质数
2. 核心：把某一个合数用它的质因数进行筛走。

---

我们常见的筛法有：朴素筛法（O(LogN * N)），埃式筛法（O(N*log(logN)），线性筛法（O(N)）。本文中选择时间复杂度最好的线性筛法。

算法代码：

#include <iostream>
using namespace std;
const int N = 1e6 + 5;
bool st[N];
int primes[N];
int cnt;
void getPrimes(int n){for(int i = 2; i <= n; ++i){if(!st[i]){primes[cnt++] = i;//把质数添加进去}//for循环每次进行从0开始到primes[j] * i ~ n,最大到nfor(int j = 0; primes[j] <= n / i; ++j){st[primes[j] * i] = true;if(i % primes[j] == 0){break;}}// 1. 如果 i % primes[j] == 0, 说明primes[j]是i的最小质因子，primes[j]一定是primes[j] * i  的最小质因子。// 2. 如果 i % primes[j] != 0, 说明primes[j]一定小于i的所有质因子，primes[j]一定是primes[j] * i 的最小质因子。}
}
int main(){int n;scanf("%d", &n);getPrimes(n);printf("%d\n", cnt);return 0;
}

---

今天的算法除了线性筛比较难点，剩下的排序算法都很简单，直接上代码，不再进行注释。

---

二、快速排序

算法题目： 快速排序

给定你一个长度为 n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼10^9 范围内），表示整个数列。

输出格式

输出共一行，包含 n个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

算法代码：

java版本

import java.util.Scanner;public class Main {public static void quicksort(long a[],int l,int r){if(l >= r)return;int i = l-1,j = r + 1;long x = a[(l + r)/2];while(i<j){do i++;while (a[i]<x);do j--;while (a[j]>x);if(i<j)swap(a,i,j);}quicksort(a,l,j);quicksort(a,j+1,r);}public static void swap(long[] a,int i,int j){long tmp = a[i];a[i] = a[j];a[j] = tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();long[] arr = new long[n];for (int i = 0;i < n;i++){arr[i] = sc.nextInt();}quicksort(arr,0,n-1);for (int i = 0;i < n;i++){System.out.print(arr[i] + " ");}}
}

C++版本

#include<iostream>using namespace std;const int N=1e6 + 10;
int a[N];
void  quick_sort(int l,int r)
{if(l>=r) return ;int i=l-1,j=r+1,x=a[l+r>>1];while(i<j){do i++;while(a[i]<x);do j--;while(a[j]>x);if(i<j) swap(a[i],a[j]);}quick_sort(l,j);quick_sort(j+1,r);
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++) scanf("%d",&a[i]);quick_sort(0,n-1);for(int i=0;i<n;i++) printf("%d ",a[i]);return 0;
}

三、归并排序

注：由归并排序衍生出的小和问题，逆序对的数量的问题，后边会进行一一讲解。

算法题目：归并排序

给定你一个长度为 n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼10^9 范围内），表示整个数列。

输出格式

输出共一行，包含 n个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

算法代码：

java版本

import java.io.*;
import java.util.Scanner;public class Main {public static void mergeSort(long[] arr){mergeSort(arr, 0, arr.length - 1);}public static void mergeSort(long[] arr, int l, int r){if(l >= r){return;}int mid = l + ((r - l) >> 1);mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);long[] help = new long[r - l + 1];int i = 0;int p1 = l;int p2 = mid + 1;while(p1 <= mid && p2 <= r){help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while(p1 <= mid){help[i++] = arr[p1++];}while(p2 <= r){help[i++] = arr[p2++];}for(i = 0; i < help.length; ++i){arr[l + i] = help[i];}}public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));String[] str1 = in.readLine().split(" ");int n = Integer.parseInt(str1[0]);//int k = Integer.parseInt(str1[1]);long[] arr = new long[n];String[] str2 = in.readLine().split(" ");for(int i = 0; i < n; i++){arr[i] = Integer.parseInt(str2[i]);}mergeSort(arr, 0, n - 1);for(int i = 0; i < n; i++){System.out.print(arr[i] + " ");}out.flush();out.close();in.close();}
}

C++版本

#include <algorithm>
#include <iostream>
using namespace std;
void merge_sort(int a[], int l, int r){if(l >= r){return;}int mid = l + ((r - l) >> 1);merge_sort(a, l, mid);merge_sort(a, mid + 1, r);int help[r - l + 1];int i = 0;int p1 = l;int p2 = mid + 1;while(p1 <= mid && p2 <= r){help[i++] = a[p1] < a[p2] ? a[p1++] : a[p2++];}while(p1 <= mid){help[i++] = a[p1++];}while(p2 <= r){help[i++] = a[p2++];}for(p1 = l, p2 = 0; p1 <= r; p1++, p2++){a[p1] = help[p2];}
}
int main(){int n;cin >>n;int a[n];for(int i = 0; i < n; i++){cin >> a[i];}merge_sort(a, 0, n - 1);for(int i = 0; i < n; i++){cout<< a[i] << " ";}return 0;
}

最后介绍一个有意思的算法：高精度阶乘

算法题目： 高精度阶乘

随意输入一个n，要求返回n的阶乘。

一、代码如下：

import java.util.Scanner;public class LargeIntegerFactorial {public static void main(String[] args){Scanner sc = new Scanner(System.in);long[] ans = new long[10001000];long n = sc.nextLong();ans[0] = 1;int l = 0;long num = 0;for(int i = 1; i<=n;++i){num = 0;for(int j = 0; j <= l; j++){num = num + ans[j] * i;ans[j] = num % 10;num /= 10;}while(num != 0){ans[++l] =num % 10;num /= 10;}}for(int i = l; i >= 0; --i){System.out.print(ans[i]);}return;}
}#### 代码解析：```java我们接下来把n设置为4，进行代码的实例演示以及解析{long[] ans = new long[10001000];//定义答案数组n = 4;//设置指定数字为4ans[0] = 1;	//将答案数组的第一位设置为1int l = 0;//定义变量l，用来记录n！的数字有多少位long num = 0;//定义变量numfor(int i = 1; i<=n;++i)//核心代码，将在下边进行实例解析{num = 0;for(int j = 0; j <= l; j++){num = num + ans[j] * i;ans[j] = num % 10;num /= 10;}while(num != 0){ans[++l] =num % 10;num /= 10;}	   }{当i == 1时，j == 0， j <= l (0 <= 0), num = 0;num = num + ans[0] * i = 0 + 1 * 1 = 1;ans[0] = num % 10 = 1 % 10 = 1;num = num / 10 = 1 / 10 = 0;当i == 2时，j == 0，j <= l (0 <= 0),num = 0;num = num + ans[0] * i = 0 + 1 * 2 = 2;ans[0] = num % 10 = 2 % 10 = 2;num = num / 10 = 2 / 10 = 0;当i == 3时，j == 0，j <= l (0 <= 0),num = 0;num = num + ans[0] * i = 0 + 2 * 3 = 6;ans[0] = num % 10 = 6 % 10 = 6;num = num / 10 = 6 / 10 = 0;当i == 4时，j == 0，j <= l (0 <= 0),num = 0;num = num + ans[0] * i = 0 + 6 * 4 = 24;ans[0] = num % 10 = 24 % 10 = 4;num = num / 10 = 24 / 10 = 2;进入while循环，num = 2 != 0;ans[++l] = num % 10 = 2 % 10 = 2;(此时l == 1);ans[1] = 2;num = num / 10 = 2 / 10 = 0;当i == 5时，j == 0，j <= l (0 <= 1),num = 0;num = num + ans[0] * i = 0 + 4 * 5 = 20;ans[0] = num % 10 = 20 % 10 = 0;num = num / 10 = 2;当i == 5时，j == 1，j <= l (1 <= 1),num = 2;num = num + ans[1] * i = 2 + 2 * 5 = 12;ans[1] = num % 10 = 12 % 10 = 2;num = num / 10 = 12 / 10 = 1;进入while循环，num = 1 != 0;ans[++l] = num % 10 = 1 % 10 = 1;(此时l == 2);ans[2] = 1;num = num / 10 = 0;结束。}}

代码测试：

1.n = 1000

1000! = 402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

计算时间是非常快的，大家可以对照这个链接下的1000！，来看看程序是否算对了，我大致看了下，没有问题。

链接如下：https://www.haomeili.net/JieCheng?JieCheng=1000