当前位置: 首页 > news >正文

「考研算法」

考研算法

前言

本系列文章涉及的算法内容,针对的是哈尔滨工业大学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

相关文章:

「考研算法」

考研算法 前言 本系列文章涉及的算法内容&#xff0c;针对的是哈尔滨工业大学854科目。在本文中通过具体的算法题进行讲解相应算法。 今天涉及的算法主要有线性筛&#xff0c;十大排序中快速排序和归并排序。 后续会有动态规划的相关算法以及尝试模型的总结&#xff0c;如果…...

Android Framework-操作系统基础

最近在看《深入理解Android内核设计思想&#xff08;第2版&#xff09;》&#xff0c;个人感觉很不错&#xff0c;内容很多&#xff0c;现将书里个人认为比较重要的内容摘录一下&#xff0c;方便后期随时翻看。 计算机体系结构 硬件是软件的基石&#xff0c;所有的软件功能最…...

美国最新调查显示 50% 企业已在用 ChatGPT,其中 48% 已让其代替员工,你怎么看?

美国企业开始使用ChatGPT&#xff0c;我认为这不是什么新闻。 如果美国的企业现在还不使用ChatGPT&#xff0c;那才是个大新闻。 据新闻源显示&#xff0c;已经使用chatGPT的企业中&#xff0c;48%已经让其代替员工工作。 ChatGPT的具体职责包括&#xff1a;客服、代码编写、招…...

[Java·算法·中等]LeetCode17. 电话号码的字母组合

每天一题&#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2题目 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。…...

C#7/C#8/C#9 与dotnetSDK 以及dotnet framework对应关系

语言版本 对应的.net framework版本 对应的.net sdk版本 推荐使用的vs studio C#7.3 3.5、 4.0、 4.5 、4.5.1、 4.5.2 、4.6 、4.6.1、 4.6.2 4.7.1、 4.7.2 .netcore 2.0、.netcore2.1、 .netcore2.2 C#8.0 / F#4.7 不支持 .netcore 3.0、.netcore 3.1 C# 9.0 …...

jvm调优经验总结

最近一段时间很忙&#xff0c;忙到每天10点多11点下班还是感觉有很多事没有做完&#xff0c;不过倒也没有什么太过低落的情绪&#xff0c;有时候只安静的看一个视频&#xff0c;简单看点文字&#xff0c;或者平静的坐着&#xff0c;并没有太多想法。短时间的工作压力是可以接受…...

等保合规知识常见问题解答

Q1&#xff1a;什么是等级保护&#xff1f; 答&#xff1a;等级保护是指对国家重要信息、法人和其他组织及公民的专有信息以及公开信息和存储、传输、处理这些信息的信息系统分等级实行安全保护&#xff0c;对信息系统中使用的信息安全产品实行按等级管理&#xff0c;对信息系统…...

分享5款Windows同类软件中的翘楚

今天要给大家推荐的是5款软件&#xff0c;每个都是同类软件中的个中翘楚&#xff0c;请大家给我高调地使用起来&#xff0c;不用替我藏着掖着。1.沙盒工具——Sandboxie Sandboxie是一个电脑必备的沙盘工具&#xff0c;对于从网上下载的软件安装包、文件、视频、图片等等一切不…...

记--springboot-工具类中使用@Component、@Resource与@Value失效

写一个工具类 需要使用Resource注入RedisTemplate 使用Value获取application.properties配置文件中配置 并使用Component将该工具类交个spring管理 调试的时候RedisTemplate以及所有的变量全是是null 看了网上的各种解决方式五花八门 有的说出现问题的原因&#xff1a;Compon…...

手写一个react,看透react运行机制

适合人群 本文适合0.5~3年的react开发人员的进阶。 讲讲废话&#xff1a; react的源码&#xff0c;的确是比vue的难度要深一些&#xff0c;本文也是针对初中级&#xff0c;本意让博友们了解整个react的执行过程。 写源码之前的必备知识点 JSX 首先我们需要了解什么是JSX。…...

JS判断输入值是否为正整数,判断变量是否为数字

这篇文章将讨论如何确定一个变量是否代表 JavaScript 中的有效数字。 1.JS中的test是原来是JS中检测字符串中是否存在的一种模式&#xff0c;JS输入值是否为判断正整数代码&#xff1a; <script type”text/javascript”> function test() { var num document.getElem…...

Android开发八股文,Android也有自己的八股文了

前言别的行业都有自己的八股文&#xff0c;凭什么Android没有。2023春招即将来临&#xff0c;很多同学会问 Android开发的面试题有必要背吗&#xff1f;我的回答是&#xff1a;很有必要。你可以讨厌这种模式&#xff0c;但你一定要去背&#xff0c;因为不背你就进不了大厂。国内…...

你需要同款“Unreal项目自动化编译、打包和部署”方案吗?

在过往几期的UWA Pipeline最佳实践案例中&#xff0c;我们分享了如何通过Pipeline实现性能优化、性能管理、游戏内容验收和云真机系统的应用&#xff08;实现批量真机设备的自动化测试&#xff0c;以及针对特效性能优化的方式&#xff09;&#xff0c;其实这些高效的方法并不局…...

电子技术——CMOS-AB类输出阶

电子技术——CMOS-AB类输出阶 本节我们研究CMOS-AB类输出阶。 经典配置 下图展示了一个经典的CMOS-AB类输出阶&#xff1a; 这个很像BJT二极管偏置版本的AB类输出阶&#xff0c;在这里二极管偏置变成了 Q1Q_1Q1​ 和 Q2Q_2Q2​ 偏置。不想BJT的情况&#xff0c;这里 QNQ_NQN​…...

2023王道考研数据结构笔记第二章线性表

第二章 线性表 2.1 线性表的定义 2.1.1 线性表的基本概念 线性表是具有相同数据类型的n(n>0)个数据元素的有限序列&#xff0c;其中n为表长&#xff0c;当n0时线性表是一个空表。若用L命名线性表&#xff0c;则其一般表示为&#xff1a; L(a1,a2,...,ai,ai1,...,an)L(a_1…...

[chapter 11][NR Physical Layer][Layer Mapping]

前言&#xff1a;这里参考Curious Being系列 &#xff0c;简单介绍一下NR 5G 物理层核心技术层映射.我们主要讲了一下what is layer Mapping, why need layer Mapping, how layer Mapping 参考文档&#xff1a;3GPP 38.211- 6.3.1.3 Layer mapping《5G NR Physical Layer | Cha…...

什么是工业物联网(IIoT)?

什么是工业物联网(IIoT)?工业物联网(IIoT) 被定义为一组设备和应用&#xff0c;允许大企业创建从核心到边缘的端到端连接环境。其还包括传统的物理基础设施&#xff0c;如集装箱和物流卡车&#xff0c;以收集数据&#xff0c;对事件做出反应&#xff0c;并在智能设备的帮助下做…...

「TCG 规范解读」PC 平台相关规范(4)

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…...

CSS背景属性之颜色渐变

颜色渐变 颜色渐变其实在网页设计中并不是特别常见&#xff0c; 但也不可避免的会出现导航栏是渐变色这种情况或者别的不是单一颜色的情况&#xff0c; 例如&#xff1a;这样的设计解决方案并不是只可以使用颜色渐变&#xff0c;我们可以使用两个div拼接&#xff0c;将文字放…...

IPv4地址细讲

文章目录一、IPv4地址简介二、IPv4地址的表示方法点分十进制记法三、IP地址的分类四、特殊IPv4地址&#xff1a;全 “0” 和全 “1”五、常用的三类IP地址使用范围六、五类IP地址的范围一、IPv4地址简介 IPv4地址分5类&#xff0c;每一类地址都由固定长度的字段组成&#xff1…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

二叉树-144.二叉树的前序遍历-力扣(LeetCode)

一、题目解析 对于递归方法的前序遍历十分简单&#xff0c;但对于一位合格的程序猿而言&#xff0c;需要掌握将递归转化为非递归的能力&#xff0c;毕竟递归调用的时候会调用大量的栈帧&#xff0c;存在栈溢出风险。 二、算法原理 递归调用本质是系统建立栈帧&#xff0c;而非…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...

CppCon 2015 学习:Simple, Extensible Pattern Matching in C++14

什么是 Pattern Matching&#xff08;模式匹配&#xff09; ❝ 模式匹配就是一种“描述式”的写法&#xff0c;不需要你手动判断、提取数据&#xff0c;而是直接描述你希望的数据结构是什么样子&#xff0c;系统自动判断并提取。❞ 你给的定义拆解&#xff1a; ✴ Instead of …...

性能优化中,多面体模型基本原理

1&#xff09;多面体编译技术是一种基于多面体模型的程序分析和优化技术&#xff0c;它将程序 中的语句实例、访问关系、依赖关系和调度等信息映射到多维空间中的几何对 象&#xff0c;通过对这些几何对象进行几何操作和线性代数计算来进行程序的分析和优 化。 其中&#xff0…...