「考研算法」

考研算法

前言

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

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

---

一、线性筛算法

算法题目：筛质数

给定一个正整数 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 <stdio.h>
#include <stdbool.h>
#define N  1000005
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,最大到n
        for(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

算法代码：

C版本

#include<stdio.h>

#define N 1000005
int a[N];
void swap(int i,int j){
    int a1 = a[i];
    a[i] = a[j];
    a[j] = a1;
}
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(i,j);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);
}
int main()
{
    int n;
    scanf("%d", &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

算法代码：

C版本

#include <stdio.h>
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;
    scanf("%d",&n);
    int a[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
    }
    merge_sort(a, 0, n - 1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

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

算法题目： 高精度阶乘

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

一、代码如下：

#include <stdio.h>
int main()
{
    long ans[1000100];
    long n;
    scanf("%lld", &n);
    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)
    {
        printf("%d",ans[i]);
    }
    return 0;
}

代码解析：

	我们接下来把n设置为4，进行代码的实例演示以及解析
	{
		long[] ans = new long[10001000];//定义答案数组
		n = 4;//设置指定数字为4
		ans[0] = 1;	//将答案数组的第一位设置为1
	    int l = 0;//定义变量l，用来记录n！的数字有多少位
	    long num = 0;//定义变量num
	    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;
            }	   
       }
       
       
       {
       		当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