网站建设可行性研究报告范文,asp.net 网站授权,成立公司有什么好处和坏处,公司网站制作的公司考研算法
前言
本系列文章涉及的算法内容#xff0c;针对的是哈尔滨工业大学854科目。在本文中通过具体的算法题进行讲解相应算法。 今天涉及的算法主要有线性筛#xff0c;十大排序中快速排序和归并排序。
后续会有动态规划的相关算法以及尝试模型的总结#xff0c;如果…考研算法
前言
本系列文章涉及的算法内容针对的是哈尔滨工业大学854科目。在本文中通过具体的算法题进行讲解相应算法。 今天涉及的算法主要有线性筛十大排序中快速排序和归并排序。
后续会有动态规划的相关算法以及尝试模型的总结如果对动态规划有兴趣的可以看我之前的这篇文章后边都是以这样的形式进行每个动态规划知识点的讲解。 链接如下https://blog.csdn.net/qq_45992664/article/details/123341143?spm1001.2014.3001.5502 一、线性筛算法
算法题目筛质数
给定一个正整数 n请你求出 1∼n中质数的个数。
输入格式
共一行包含整数 n。
输出格式
共一行包含一个整数表示 1∼n中质数的个数。
数据范围
1 ≤ n ≤ 10^6
输入样例
8输出样例
4算法思路
切记1不是质数核心把某一个合数用它的质因数进行筛走。 我们常见的筛法有朴素筛法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(ij){do i;while (a[i]x);do j--;while (a[j]x);if(ij)swap(a,i,j);}quicksort(a,l,j);quicksort(a,j1,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版本
#includeiostreamusing namespace std;const int N1e6 10;
int a[N];
void quick_sort(int l,int r)
{if(lr) return ;int il-1,jr1,xa[lr1];while(ij){do i;while(a[i]x);do j--;while(a[j]x);if(ij) swap(a[i],a[j]);}quick_sort(l,j);quick_sort(j1,r);
}
int main()
{int n;cinn;for(int i0;in;i) scanf(%d,a[i]);quick_sort(0,n-1);for(int i0;in;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; in;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; in;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 0j 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 0j 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 0j 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 0j 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 1j 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?JieCheng1000
