
2018秋学期-算法设计与分析
文章平均质量分 66
铁锅炖鱼,铜锅涮肉
火龙果奇异果芒果橙子和石榴
展开
-
9.14-回溯(//数字全排列//0-1背包//迷宫问题//八皇后问题//又一个迷宫//堡垒问题//三阶幻方//图的m着色问题//字母转换//输出命题公式的真值表)
1.数字全排列 输出N个数字的所有排列组合情况#include<iostream>using namespace std;void search(int m);void output();int n;int arr[10];int main(){ cin >> n; for(int i = 0; i < n; i+...原创 2018-09-16 11:16:19 · 780 阅读 · 0 评论 -
10.13—广搜 //特殊的二阶魔方//推箱子//polygon//木乃伊迷宫
1.特殊的二阶魔方描述:魔方大家应该都玩过。现在有一个特殊的二阶魔方,它只有一面是白色,其余五个面全是黑色。玩这个魔方当然也有特殊的规则,玩家只能通过六种方式去改变它,底层向左转一格(称为DL),底层向右转一格(称为DR),右侧向上转一格(称为RU),右侧向下转一格(称为RD),内侧顺时针转一格(称为C),内侧逆时针转一格(称为CC)。现给一魔方的状态,请在最少的步骤内把魔方还原输入:按照...原创 2018-10-19 10:11:54 · 574 阅读 · 0 评论 -
10.19—动态规划 //最长公共子序列//防卫导弹//田忌赛马//计算矩阵连乘积//最长子序列的长度
1.最长公共子序列描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1, x2,…, xm>,则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>,使得对于所有j=1,2,…,k有:Xij = Zj如果一个序列S即是A的子序列又是B的子序列,则称S是A...原创 2018-10-19 09:59:03 · 730 阅读 · 0 评论 -
10.9-分支界限法(//跳马//独轮车//六数码问题//找倍数//八数码问题)
1.跳马描述:在国际象棋中,马的走法与中车象棋类似,即俗话说的“马走日”,下图所示即国际象棋中马(K)在一步能到达的格子(其中黑色的格子是能到达的位置)。现有一200*200大小的国际象棋棋盘,棋盘中仅有一个马,给定马的当前位置(S)和目标位置(T),求出马最少需要多少跳才能从当前位置到达目标位置。输入:本题包含多个测例。输入数据的第一行有一个整数N(1<=N<=1000),...原创 2018-10-09 22:56:59 · 1534 阅读 · 0 评论 -
9.29-贪心算法(//活动安排//0-1背包//装载问题)
1.活动安排描述:Jack是一名nwpu的大一新生,对学校举办的各种活动都十分的好奇,想尽可能多的参加这些活动。Npwu每天共有N项活动,其开始结束时间分别为B[i],E[i],(i = 1,2,……N)请问Jack一天最多能参加几项活动。当然,Jack在同一时间内只能参加一项活动,即jack参加的活动时间上不能重叠,但时间为[t1,t2],[t2,t3]的两个活动是可以同时参加的。输入...原创 2018-09-29 19:40:28 · 402 阅读 · 0 评论 -
9.29-分支限界法(//加1乘2平方//电子老鼠闯迷宫//农场灌溉问题//满足条件的排列数)
1.加1乘2平方描述:最简单的队列的使用#include <iostream>#include <queue>using namespace std;queue<int> q1;int main(){int temp, x;q1.push(5);//入队q1.push(8);//入队temp = q1.front();//访问队首元素q...原创 2018-09-29 17:24:58 · 1671 阅读 · 0 评论 -
9.28-PRIM算法(//最短公路连接村庄(一)(二))
1.最少修建多长的公路能把所有村庄连起来(一)描述:一个地区有n个村庄,有一些村子之间可以修路,已知每条路的长度,问最少修建多长的公路可以把所有的村子连接起来。输入:先输入两个正整数n,m(n小于10000,m小于100000),表示有n个村庄,m条可以修建的路,接下来的m行每行三个整数,前两个表示村庄的编号(0~n-1),第三个表示这条路的长度。输出:输出路的总长度的最小值。输入...原创 2018-09-28 11:52:23 · 1487 阅读 · 0 评论 -
9.27—并查集
1.并查集(一)描述:一个城市中有n个人,其中一些人是朋友关系,同时他们都认为:朋友的朋友是朋友,现在任给两个人,问他们是否是朋友关系。输入:先输入两个正整数n和m(均小于1000),表示城市里有n个人,并且将给出m对朋友关系,接下来的m行每行给出两个0~n-1之间的整数,表示这两个人是朋友关系。最后一行再输入两个0~n-1之间的整数,问他们是否是朋友关系。输出:是朋友关系则输出"Ye...原创 2018-09-27 17:31:43 · 186 阅读 · 0 评论 -
9.11-分治(//二分搜索//合并排序//快速排序//循环赛日程表)
分治法:将一个规模为n 的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。 大量实践表明,将问题分成大小相等的两个子问题的方法是行之有效的,它几乎总比子问题规模不等的的做法要好。 例1:二分搜索 将n个元素分成大致相同的两半,取a[n/2]与x进行比较。如果x=a[n...原创 2018-09-07 12:27:47 · 521 阅读 · 0 评论 -
9.6-递归(//n!//最大公约数//穷举n位二进制数//四皇后问题//骨牌组合//踩气球)
递归算法:直接或间接调用自身的算法。递归函数:用函数自身给出定义的函数。 递归的优点:算法简洁易于分析理解。递归的缺点:分支较多的函数时间、空间复杂度太大。 例1:求n!#include<iostream>using namespace std;int f(int n);int main(){ int m; cin>>m; co...原创 2018-09-06 21:58:32 · 384 阅读 · 0 评论 -
9.22-动态规划 //石子合并//花生米
1.石子合并描述:在一个圆形操场的四周摆放着n堆石子(n<= 100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n-1次合并,得分的总和最小;比如有4堆石子:4 4 5 9 则最佳合并方案如下:4 4 5 9 score: 0...原创 2019-03-30 08:59:04 · 412 阅读 · 0 评论