【武汉理工大学】算法设计与分析必背算法总结(伪代码)
本文总结了算法设计与分析课程著主要的算法(伪代码),主要用于快速复习
·
目录
第一章 算法设计基础
| 求大于n的最小Smith数
//求质因数的逐位和
int getEvenSum(int n){
int sum = 0;
for(int i=2 ; i<=n ; i++){
while(n%i == 0){
int temp = i;
sum = sum + getSum(i);
i = temp;
n /= i;
}
}
}
//主函数
//一个结果数组、输入n
while(n!=0){
for(int j=n+1 ; j++){
cin >> n;
if(getSum(j) == getEvenSum(j)){
returnt[flag++] = j;
break;
}
}
}
第二章 算法分析基础
| 斐波那契数列
int f(int n){
if(n==0 || n==1){
return n;
}
else{
return f(n-1) + f(n-2);
}
}
第三章 分治法
| 快速排序
//快速排序主函数
void quickSort(int R[] , int s , int t){
if(s < t){
int i = Partition(R , s, t);
quickSort(R, s, i-1);
quickSort(R, i , t);
}
}
//获取每一次的分界点函数
int Partition(int R[], int s, int t){
//i左边,j右边
int i=s;
int j=t;
int temp = R[s];
while(i!=j){
while(j>i && R[j]>=temp){
j--;
}
R[i] = R[j];
while(i<j && R[i]<=temp){
i++;
}
R[j] = R[i];
}
}
| 查找第k小的元素
//在快速排序的基础上,判断i与k的关系,然后继续递归子区间。
| 最大子段和
int maxSubSum(int a[], int n){
int max = 0;
int sum = 0;
for(int i=0 ; i<n ; i++){
sum = sum + a[i];
if(sum < 0){
sum = 0;
}
if(sum > max){
max = sum;
}
}
return max;
}
| 数组左移k个位置
//翻转数组元素 1 3 4 5 6 → 6 5 4 3 1
void reverse(char c[] , int begin , int end){
for(int i=0 ; i<(end-begin+1)/2 ; i++){
char temp;
temp = c[begin + i];
c[begin + i ] = c[end - i];
c[end - i] = temp;
}
}
//主要函数 c数组、n元素个数、k移动个数
void leftK(char c[] , int n , int k ){
//m 实际要移动的个数
int m = n % k;
reverse(c , 0 , m-1);
reverse(c , m , n-1);
reverse(c , 0 , n-1);
}
//main函数
//输入,调用leftK函数等……
| 寻找数组逆序数的个数 *
template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end){
if (start >= end) {
return;
}
int len = end - start, mid = (len>>2) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
if (arr[start1] < arr[start2]) {
reg[k++] = arr[start1++];
}
else{
reg[k++] = arr[start2++];
++cnt;
}
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
for (k = start; k <= end; k++) {
arr[k] = reg[k];
}
}
template<typename T>
void merge_st(T arr[], const int len){
T reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
int main(int argc, const char * argv[]) {
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; ++i) {
cin>>a[i];
}
merge_st(a, n);
cout<<cnt<<endl;
return 0;
}
第四章 动态规划
| 数塔问题
//创建数塔
for(int i=1 ; i<=n ; i++){
for(int j=1 ; i<=i ; j++){
cin >> a[i][j];
}
}
//动归求最小值
dp = a[i]; //把数组最后一行的首地址给dp
for(int i=n-1 ; i>=1 ; i--){
fot(int j=1 ; j<=i ; j++){
dp[j] = max(dp[j],dp[j+1]) + a[i][j];
}
}
| 最长递增子序列
voif f(int a[] , int n){
fot(int i=0 ; i<n ; i++){
dp[i] = 1;
for(int j=0 ; j<i ; j++){
if(a[i] > a[j]){
dp[i] = max(dp[i] , dp[j]+1);
}
}
}
return dp[i];
}
| 最长公共子序列
voif f(int x[] , int y[]){
//长度
int n = x.length();
int m = y.length();
//初始化
for(int i=0 ; i<=m ; i++){
dp[i][0] = 0;
}
for(int j=0 ; j<=n ; i++){
dp[0][j] = 0;
}
//核心算法
for(int i=1 ; i<=m ; i++){
for(int j=1 ; j<=n ; j++){
if(x[i] == y[j]){
dp[i][j] = dp[i-1]dp[j-1] + 1;
}
else{
dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
}
}
}
}
| 0-1背包问题
int n = 5; //物品数
int c = 10; //背包可以装的最大重量
int w = {0,2,2,6,5,4}; //物品重量
int v = {0,6,3,5,4,6}; //物品价值
int dp[][]; //动归数组
int maxV; //最大价值
void f(){
//初始化物品 n为物品个数
for(int i=0 ; i<n ; i++){
dp[i][0] = 0;
}
//初始化背包 c为背包最大重量
for(int r=0 ; r<=c ; r++){
dp[0][r] = 0;
}
//核心算法
for(int i=1 ; i<=n ; i++){
for(r=1 ; r<=c ; r++){
if(r < w[i]){
dp[i][r] = dp[i-1][r];
}
else{
dp[i][r] = max(dp[i-1][r] , dp[i-1][r-w[i]] + v[i]);
}
}
}
}
| 导弹拦截问题(最长递减子序列)
voif f(int a[] , int n){
fot(int i=0 ; i<n ; i++){
dp[i] = 1;
for(int j=0 ; j<i ; j++){
if(a[i] < a[j]){
dp[i] = max(dp[i] , dp[j]+1);
}
}
}
return dp[i];
}
| 机器人最短路径
void f(int m , int n){
//存储路径条数的数组
int a[m][n];
//初始化
fot(int i=0 ; i<m ; i++){
a[i][0] = 1;
}
for(int j=0 ; j<n ; j++){
a[0][j] = 1;
}
//核心算法
for(int i=1 ; i<m ; i++){
for(int j=1 ; j<=n ; j++){
a[i][j] = a[i-1][j] + a[i][j-1];
}
}
cout << a[m-1][n-1];
}
第五章 贪心算法
| 部分背包问题
void f(){
double v = 0;
double r = c;//最大容量
int i = 1;
int x[]; //用来表示每一个物品装的比例
while(p[i].w < r){
x[i] = 1;
r = r - p[i].w;
v = v + p[i].v;
i++;
}
if(r > 0){
//x[i] 装第i个物品的比例
x[i] = r / p[i].w;
v = v + x[i]*p[i].v;
}
}
| 活动安排问题
inf f(int a , action a[]){
int ans = 1;//已选择的总活动数
//核心算法
sort(a+1 , a+n+1);
int selected = 1;//被选择的活动 从1开始
for(int i=2 ; i<=n ; i++){
if(a[i].begin >= a[selected]){
ans++;
selected = i;
}
}
return ans;
}
| 木棍覆盖区间问题
//n 点的个数 k木棍长度
set<int> pots; //去掉坐标一致的点
tempral = 0; //当前可覆盖的最大点坐标
//获得集合的首元素地址,然后每次地址++
for(auto it = pots.begin() ; it!=pots.end() ; it++){
if(tempral < *it){
return ++;
tempral = *it + k;
}
cout << result;//输出需要的最少木棍数量
}
第六章 回溯
| target目标和
int sum(int num){
int sum = 0;
for(int i=0 ; i<=num ; i++){
sum = sum + x[i];
}
return sum;
}
//核心算法
void find(int s){
if(s<n && b!=1){
for(int i=s ; i<n&&b!=1 ; i++){
x[s] = a[i];
if(sum(s) < k){
find(i+1);
}
if(sum(s) == k){
cout << "存在";
b = 1;
}
if(b == 0){
cout << "不存在"
}
}
}
}
int main(){
int x[20];
for(int i=0 ; i<n ; i++){
cin >> a[i];
}
//进入算法
find(0);
return 0;
}
实验题
| 实验1-1 返回两个有序数组的中位数
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;
int median1 = 0, median2 = 0;
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
if (nums_im1 <= nums_j) {
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
}
| 实验1-2 格雷编码
class Solution {
public List<Integer> grayCode(int n) {
/**
关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
如 n = 3:
G(0) = 000,
G(1) = 1 ^ 0 = 001 ^ 000 = 001
G(2) = 2 ^ 1 = 010 ^ 001 = 011
G(3) = 3 ^ 1 = 011 ^ 001 = 010
G(4) = 4 ^ 2 = 100 ^ 010 = 110
G(5) = 5 ^ 2 = 101 ^ 010 = 111
G(6) = 6 ^ 3 = 110 ^ 011 = 101
G(7) = 7 ^ 3 = 111 ^ 011 = 100
**/
List<Integer> ret = new ArrayList<>();
for(int i = 0; i < 1<<n; ++i)
ret.add(i ^ i>>1);
return ret;
}
}
| 实验2-1 最大K乘积问题
package EXP2;
import java.io.*;
import java.util.ArrayList;
public class LargestKMultiple {
public static void main(String[] args) throws IOException {
//定义算法所需变量
int a[] = new int[101];
int m[][] = new int[101][101];//表示第i位到第j位整数组成的(j-i+1)位整数
int dp[][] = new int[101][101];//表示前i位整数被划分为j+1段所得到的最大乘积
//输入n(数字长度)、k(分割段数)、x(十进制整数)
BufferedReader in = null;
ArrayList<Integer> nums = new ArrayList<Integer>();
try {
in = new BufferedReader(new FileReader("EXP\\src\\EXP2\\input.txt"));
String sb;
while (in.ready()) {
sb = (new String(in.readLine()));
String[] s;
s = sb.split(" ");
for(String i : s){
nums.add(Integer.parseInt(i));
}
}
in.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
int n = nums.get(0);
int k = nums.get(1);
int x = nums.get(2);
//算法===================================================
//把数字的各个位存入数组中
for(int i=n; i>0; i--) {
a[i]=x%10;
x=x/10;
}
//填补m数组 计算 第i位到第j位组成的j-i+1位整数
for(int i=1; i<=n; i++)
m[i][i]=a[i];
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
m[i][j]=m[i][j-1]*10+m[j][j];
//枚举数的长度(动态规划)
for(int i=1; i<=n; i++) {
for(int j=0; j<i; j++) {//枚举分段数
if(j==0) {//被划分为一段的情况,最大值为其本身
dp[i][0]=m[1][i];
continue;
}
for(int p=1; p<i; p++)//以p为界,枚举分割点
dp[i][j]=Math.max(dp[i][j],dp[p][j-1]*m[p+1][i]);
}
}
// 输出结果
try {
output(dp[n][k-1]);
} catch (IOException e) {
e.printStackTrace();
}
}
//输出函数
public static void output(double x) throws IOException {
BufferedWriter out = new BufferedWriter(new FileWriter("EXP\\src\\EXP2\\output.txt"));
out.write(String.format("%f", x));
out.close();
}
}
| 实验2-2 游艇租用问题
/*
思路:本题的思路和矩阵链相乘思路一样,但递推方程不一样
1:首先判断是否用动态规划:从1到最后的站N,那么这个求解的过程是跳跃性的
可以从1到2 然后从2到 N,或则从1到3,从3到N,其是跳跃性的,判断其是动态规划
2:回归本题我们在考虑的时候,其中涉及到划分问题,比如从2到N,可以从2到3,然后从
3到N,那么的我们可以找类似的思路,那就是矩阵连相乘
3: 总结出递归方程:m[i][j] = m[i][k]+m[k][j] 这里和矩阵链相乘有区别
注意递推方程的区别:游艇:比如:从1到3,然后从3到N
矩阵链:比如从1到3,那么接下来就是4到N(A1*A2*A3*A4*A5)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int m[300][300];//注意定义二维数组不可定义的范围过大
int N;
cin >> N;
// int m[N+1][N+1];
//二维数组初始化 自己到自己为0
for(int i = 0; i <= N; i++){
m[i][i] = 0;
}
for(int i = 1; i <= N; i++){
for(int j = i + 1; j <= N; j++){//这里的i+1 是 从 一个站到另一个站
cin >> m[i][j];
}
}
//直接开始更新二维数组当中的值
for(int i = N; i >= 1; i--){//
for(int j = i + 1; j <= N; j++){
//开始划分
for(int k = i + 1; k < j; k++){
int temp = m[i][k] + m[k][j];
if(temp < m[i][j]){ //求取最小值
m[i][j] = temp;
}
}
}
}
cout << m[1][N];
}
//3
//5 15
//7
为武汉地区的开发者提供学习、交流和合作的平台。社区聚集了众多技术爱好者和专业人士,涵盖了多个领域,包括人工智能、大数据、云计算、区块链等。社区定期举办技术分享、培训和活动,为开发者提供更多的学习和交流机会。
更多推荐
已为社区贡献4条内容
所有评论(0)