- 博客(15)
- 收藏
- 关注
RSS订阅原创 算法设计与分析动态规划思维导图和总结
0-1背包问题给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？详细思路和代码
2021-11-02 20:54:48
314
原创 最长公共子序列（动态规划）
题目描述求两个字符串的最长公共子序列输入：两行，分别为待测的两组字符串。每个字符串长度不大于1000.。输出：第一行表示表示最长公共子序列长度。每组结果占一行。第二行输出最长的公共子序列输入样例1asdfadfsd输出样例13asd输入样例2123abcabc123abc输出样例26123abc思路c[i][j] :表示序列{x1,x2,…xi}和序列{y1,y2…yj}最长公共子序列的长度状态转移方程：c[i][j] = 0
2021-11-02 20:39:00
185
原创 最长上升子序列（动态规划）
题目描述求一个字符串的最长递增子序列的长度。输入第一行一个整数0<n<20,表示有n个字符串要处理随后的n行，每行有一个字符串，该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入3aaaababcabklmncdefg样例输出137思路一：动态规划例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。 前1个数 d(1)=1 子序列为2
2021-11-02 20:28:06
430
原创 矩阵连乘问题
题目描述给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序 计算矩阵连乘积需要的数乘次数最少。样例输入15 10 4 6 10 2样例输出348(A1(A2(A3(A4A5))))思路例如：A1是5 * 10 的矩阵A2是10 * 100的矩阵A3是100 * 2的矩阵那么有两种加括号的方法：1、 （A1A2）A32、 A1（A2A3）第一种方法的计算量：510100+5100
2021-11-02 20:08:59
297
原创 0-1背包问题
问题描述给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？思路分析m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值 ，那么我们可以很容易分析得出 m[i][j] 的计算方法，（1）j < w[i] ，容量不足，这时候背包容量不足以放下第 i 件物品，只能选择不拿 m[ i ][ j ] = m[ i-1 ][ j ]（2） j>=w[i]
2021-11-01 21:45:47
79
原创 环形石子合并问题
题目描述在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编写程序，读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n－1次合并,得分的总和最大（小）。输入样例44 4 5 9输出样例4354思路类似于直线上环形石子合并问题，将原数组复制一份放到数组的尾部，可以巧妙地实现了每个石子作为起点的情况。枚举i-j的之间的分裂点k，则花费为f[i][k] + f[k+1
2021-11-01 19:38:22
287
原创 算法设计与分析递归与分治思维导图和总结
主定理：**1、二分查找**问题描述：在一有序数组T[ l…r ]中查找x，如果x在T中，输出x在T中的下标j，否则输出-1基本思想1、如果l > r，则查找结束，x不在数组中，返回-1，否则将x与中间元素T[mid]比较，如果相等，则返回mid2、如果x比T[mid]小,则到T[ l…mid-1]进行查找3、否则到T[mid+1…r ]查找实现int BinarySearch(int a[], int x, int n){ int l = 0, r = n - 1;.
2021-10-10 16:57:12
474
原创 阶乘尾部零的个数
试统计正整数n的阶乘n!的尾部连续零的个数。算法分析：由于n的规模比较大，其尾数的个数也会非常多，所以在这里我们可以用一个数组来存储阶乘的的各位数字，a[0]存储个位，a[1]存储十位，依次类推。（1）首先求出 n! 的总位数（取lg最后不要忘了+1） 总位数m = lg(2 * 3 * 4 * 5 * .... * n) +1 = lg2 + lg3 +lg4 + lg5 + ...lg n +1（2）开两重循环模拟乘法（阶乘
2021-09-14 20:17:02
316
原创 正整数拆分问题
将一个给定的正整数拆分成若干个连续的正整数之和，对于给定的正整数n，求出所有符合这种拆分要求的连续正整数序列的方案个数。例如输入n=15，输出315 = 1 + 2 +3 +4 +515 = 4 + 5 + 615 = 7 +8例如输入n=16，无解，输出0思路本题直接暴力枚举即可，开两重循环，外层循环从最小正整数1开始枚举，里层循环枚举序列长度。用等差求和公式即可判读符不符合题意。#include<iostream>using namespace std;const in
2021-09-14 19:12:30
1189
原创 纯粹素数（素数筛）
纯粹素数题目描述纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。这样下去一直到最后剩下的个位数也还是素数。给定一个正整数n，求出从1,000开始从小到大的第n个纯粹素数。输入从标准输入设备（通常为键盘）中读入多组测试数据，每组测试数据仅占一行，每行仅包括一个正整数n（1 ≤ n ≤ 20）。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。输出对于每一组测试数据，需要计算出一组相应
2021-09-11 15:15:46
1580
原创 最多约数问题
最多约数问题题目描述正整数x的约数是能整除x的正整数。正整数x的约数个数记为div（x）。例如，1,2,5,10都是正整数10的约数，且div(10)=4。 对于给定的2个正整数a<=b，编程计算a与b之间约数个数最多的数。输入输入的第1行有两个正整数a和b。输出若找到的a和b之间约数个数最多的数是x，则输出div(x)。样例输入1 36样例输出9思路一：遍历[a,b]之间每个数，分别求出每个数的约数个数，不断更新最大值即可#include<iostream>#
2021-09-11 15:07:24
339
原创 高精度加法（vector逆序存储）
高精度加法vector存储原题链接 [https://www.acwing.com/problem/content/793/]题目描述给定两个正整数，计算它们的和。输入格式共两行，每行包含一个整数。输出格式共一行，包含所求的和。数据范围1≤整数长度≤100000输入样例：1223输出样例：35代码模板//高精度加法 #include<iostream>#include<vector>#include<algorithm>using
2021-08-10 00:44:56
168
原创 分数类的设计
基本描述定义一个分数类，完成以下功能：每个分数都具有属性——分子和分母；定义方法set，设置分数的分子和分母；定义方法print，打印分数，格式如：2/7；定义方法getValue，返回double型的分数值；定义方法invert, 分子和分母交换。然后根据用户输入的指令，测试各个功能。例如：用户界面可以设计如下：welcome to Fraction TestWha...
2020-04-08 11:53:16
918
原创 统计个位数字
本题要求实现一个函数，可统计任一整数中某个位数出现的次数。例如-21252中，2出现了3次，则该函数应该返回3。函数接口定义：int Count_Digit ( const int N, const int D );其中N和D都是用户传入的参数。N的值不超过int的范围；D是[0, 9]区间内的个位数。函数须返回N中D出现的次数。裁判测试程序样例：#include <stdio.h...
2020-04-07 23:40:24
1281
原创 寻找孪生素数
数学家希尔伯特在1900年国际数学家大会的报告上提出一个“孪生素数猜想”，即： 存在无穷多个素数p，使得p + 2是素数。p和p+2这一对差为2的素数，被称为“孪生素数”。看起来，这个猜想是成立的，我们总能找到很多对孪生素数，例如：3和5,5和7,11和13…… 这一猜想至今还未被证明。现在，对于给定的整数n， 请寻找大于n的最小的一对孪生素数p和q（q=p+2）。输入格式:一个不超过7位...
2020-04-07 23:29:30
3410
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人