Devlyp

算法设计与分析

cpc(2) Docker(2) git(1) idea(3) java(19) javaweb(49) java技术(4) pta(7) python(1) redis(1) Springboot(2) sql(3) ssm(1) 搜索(1) 未归档(4) 科创板(1) 题解(1)

/ 注册

全部文章 / 算法设计与分析（共9篇）

算法设计与分析----全排列问题

对于全排列问题，用到的是递归分治策略，对于12345的全排列来说，采用递归分治，划分为更小规模的子问题，要求12345的全排列，就要求2345的全排列，要求2345的全排列，就要求345的全排列，以此类推。 #include<bits/stdc++.h> using n...

2020-04-16

0 962

算法设计与-分析---去重全排列

去重全排列与之前的全排列不同的是，序列不一定是像12345这样每一个元素只出现过一次，有可能是这样的：112345，这样的话，之前的算法就会出现重复的情况，比如1跟1交换，那么就出现了重复，但如果在交换元素之前判断一下，之前是否有元素和当前要交换的元素一样，如果一样，那么就不交换。 #include...

2020-04-16

0 780

算法设计与分析----半数集问题

半数集问题描述：给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)； (2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。例如，set(6)={6,16,26,126,36,...

2020-04-16

0 1780

算法设计与分析----循环赛日程表

设有n个运动员，要进行网球循环赛。现在要设计一个满足以下要求的比赛日程表（1）.每个选手必须与其他n-1个选手各赛一场（2）.每个选手一天只能赛一次（3）.循环赛一共进行n-1天此题一般都是用递归分治解决，但是就是有点麻烦，这次介绍一种简单点的方法：多边形轮转法。基本思路...

2020-04-16

0 2139

算法设计与分析----矩阵连乘

给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10 * 100，100 * 5和5 * 50，采用（A1A2）A3，乘法次数...

2020-04-16

0 1344

算法设计与分析----最长公共子序列

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA 对于这个问题，用一个二维数组记录两个字符串的状态，例如dp[2][3...

2020-04-16

0 647

算法设计与分析----最优二叉树动态规划

概念就不赘述了。 #include<bits/stdc++.h> using namespace std; double a[10],b[10]; double dp[10][10]; int s[10][10]; double ...

2020-04-16

0 738

算法设计与分析----动态规划之数字三角形问题

题目：在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1小于等于100，数字为 0 - 99。利用动态规划自底而上求解。 #include<bits/std...

2020-04-16

0 1212

算法设计与分析----马的周游路线

8 * 8的国际象棋棋盘上的一只马，恰好走过除起点外的其他63个位置各一次，最后回到起点，这条路线称为马的一条Hamilton周游路线。对于给定的m * n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|≤2，试设计一个分治算法找出马的一条Hamilton周游路线。下面的代码是实现，并不...

2020-04-16

0 1446