算法设计与分析实验考试复习
理论题
1.算法的基本概念，性质及其与程序的联系与区别
算法：算法是指解决问题的一系列计算步骤，是解决方案准确而完整的描述。
算法的基本性质：
- 输入性：有零个或多个外部量作为算法的输入。
- 输出性：算法产生至少一个量作为输出。
- 确定性：组成算法的每条指令必须是清晰的，无二义性的。
- 有限性：算法中指令的执行次数有限和执行的时间有限。
- 可行性：算法中每一条运算都必须足够基本，能够精确的执行。
程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。
2.算法的复杂性，如何度量，算法的渐进复杂度和阶
一个算法的评价主要从时间复杂度和空间复杂度来考虑。
时间复杂度是指执行算法所需要的时间；空间复杂度是指算法所消耗的内存空间。一般来说，计算机算法的复杂性是问题规模n 的函数f(n)，当问题规模n充分大时，我们只需考虑算法复杂性在渐近意义下的阶。
3.大O表示法的定义和渐近时间复杂度
称f(n)=O(g(n))，当且仅当存在常数c>0和n0>0，使得当n>=n0时，f(n)<=g(n)恒成立。
如果一个问题的规模是n，解决这一问题的算法所需要的时间是T(n)，它是关于n的一个函数，称其为该算法的时间复杂度，当n充分大时，T(n)的极限状态称为算法的渐近时间复杂度。
4.几大算法的基本思想
-
分治法：将问题规模为n的问题分解成k个规模较小的子问题，这些子问题互相独立且与原问题相同，递归地解这些子问题，然后将子问题的解合并得到原问题的解。
-
回溯算法：在包含原问题所有解的解空间树中，用深度优先搜索的策略，从根节点出发深度搜索解空间树。当搜索到某一节点时，先判断该节点是否包含原问题的解，若包含则继续搜索下去，否则逐层向其祖先节点回溯。
-
分支限界法：以广度优先搜索的方法搜索解空间树。每个活结点只有一次机会成为扩展节点，当成为扩展节点后一次性生成所有儿子节点，在这些儿子节点中，导致不可行解或非最优解的儿子节点被抛弃，其余的儿子节点加入到活结点表的队尾。此后从活结点表的队头取下一个节点成为扩展节点，重复上述步骤，直到找到最优解或活结点表为空时结束。
-
动态规划：将原问题分解成若干个规模较小的子问题，先求解这些子问题，然后通过子问题的解得到原问题的解。
基本步骤：
- 找出最优解的性质，并刻画其结构特征；
- 递归地定义最优值；
- 以自底向上的方式计算出最优值；
- 根据计算最优解时得到的信息，构造最优解。
基本要素：最优子结构性质，无后效性和子问题重叠性质。
最优子结构性质是指问题的最优解所包含的子问题的解也是最优的；
无后效性是指某个状态以前的过程不会影响以后状态的决策，而只与当前状态有关；
子问题重叠性质是指一个子问题在下一阶段的决策中可能会被多次使用，动态规划法正是利用了这一特性，对每一个子问题只计算一次然后将结果保存在一个表格中，当需要时只需要从表格中取出结果即可。
-
贪心算法：贪心算法总是做出在当前看来是最好的选择，即贪心算法不是从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优选择。
基本步骤：
- 从问题的某个初始解出发；
- 采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个局部最优解，缩小问题的规模；
- 将所有局部最优解综合起来，得到原问题的解。
基本要素：贪心选择性质，最优子结构性质，无后效性。
贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。
-
备忘录法：用表格保存已解决的子问题答案，通过自顶向下的递归方式求解，当递归到已经求解过的子问题时，直接从表格中返回子问题的解。
5.几大算法的联系与区别
-
分治算法vs动态规划
联系：基本思想相同，都是将原问题分解成若干个子问题，先求解子问题，然后通过子问题的解得到原问题的解。
区别：适用于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的，分治法的子问题被重复多次计算，而动态规划法将子问题的解存在一个表格中，从而避免了子问题重复计算的问题。
-
动态规划vs备忘录法（记忆化搜索）
联系：都是用表格保存已解决的子问题答案，避免子问题重复计算
区别：动态规划法的递归方式是自底向上的，而备忘录法的递归方式是自顶向下的。
-
分支限界法vs回溯法
区别：对扩展节点采用的扩展方式不同，分支限界法采用广度优先搜索，当搜索到最优解或活结点表为空时结束，而回溯法采用深度优先搜索，只有当活结点的所有可行子节点都被遍历之后才结束。
-
贪心算法vs动态规划
联系：都要求问题具有最优子结构性质和无后效性
区别：在动态规划法中，每一步所做的选择往往依赖于相关子问题的解，因此只有在求出相关子问题后才能做出选择，所采用的递归方式是自底向上的；而在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择之后产生的相应子问题，所采用的递归方式是自顶向下的。
6.一些算法的一般模式
-
回溯算法的一般模式
int n,a[N]; //n为考察对象的个数 void backtrack (int m) { if (m>n) output(); //叶子节点，输出可行解 else for(int i=0;i<=k;i++) //当前节点的所有子节点 { a[m]=value(i); //每个子节点的值赋值给a[m] if (constraint(m)&&bound(m)) //满足约束条件和限界条件 backtrack(m+1); //递归下一层 } } -
回溯法搜索子集树
int n,a[N]; //n为考察对象的个数 void search(int m) //m为当前考察对象 { if(m>n) //递归结束条件 output(); //相应的输出 else for(int i=0;i<=1;i++) //控制分支数目，此处只有两个分支，0、1表示是否装入背包 { a[m]=i; if(constraint(m)&&bound(m)) //剪枝函数：约束函数+限界函数 ——> 递归 search(m+1); } } -
回溯法搜索排列树
int n,a[N]; //n为考察对象的个数，a[N]初始化为排列的一种 void search(int m) //m为当前考察对象 { if(m>n) //递归结束条件 output(); //相应的输出 else for (int i=m;i<=n;i++) { swap(a[m],a[i]); //调换位置 if (constraint(m)&&bound(m)) //若不满足限制函数则不继续深入 search(m+1); swap(a[m],a[i]); //调回原位 } } -
分支限界法的一般模式
struct node { int x,y; }e1,e2; vector <node> q; int flag[N][N]; //标记节点是否已经到达过，初始化为0 void search() { cin>>e1.x>>e1.y; q.push(e1); flag[e1.x][e1.y]=1; //标记e1到达过 while(!q.empty()) { e2=q.front(); q.pop(); for(对扩展节点e2得到的每个新节点e1) { if(e1是目标节点) { output(); return; //输出结果并返回 } if(flag[e1.x][e1.y]==0&&bound(e1)) //满足限界条件且未到达过 { q.push(e1); flag[e1.x][e1.y]=1; //标记e1到达过 } } } }
上机题
以下空格两行显示的代码为核心代码
1. 二分查找
#include <iostream>
using namespace std;
const int N=10001;
int a[N];
void binarysearch(int l,int r,int x)
{
if(l>r)
{
cout<<"No"<<endl;
return;
}
int mid=l+r>>1;
if(a[mid]==x)
{
cout<<"Yes"<<endl;
return;
}
else if(a[mid]>x)
binarysearch(l,mid-1);
else
binarysearch(mid+1,r);
return;
}
int main()
{
int n,m,x;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>m;
for(int i=0;i<m;i++)
{
cin>>x;
binarysearch(0,n-1,x);
}
}
2. 归并排序
#include <iostream>
using namespace std;
const int N=10010;
int a[N];
void Merge(int l,int mid,int r)
{
int tmp[r-l+1];
int cnt=0,i,j;
for(i=l,j=mid+1;i<=mid&&j<=r;)
{
if(a[i]<a[j])
tmp[cnt++]=a[i++];
else
tmp[cnt++]=a[j++];
}
while(i<=mid)
tmp[cnt++]=a[i++];
while(j<=r)
tmp[cnt++]=a[j++];
for(int i=0;i<cnt;i++)
a[l+i]=tmp[i];
}
void mergesort(int l,int r)
{
if(l<r)
{
int mid=r+l>>1;
mergesort(l,mid);
mergesort(mid+1,r);
Merge(l,mid,r);
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
mergesort(0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<endl;
return 0;
}
3. 01背包
#include <iostream>
#include <cstring>
using namespace std;
int dp[10000010];
int main()
{
int n,c;
while(cin>>n>>c)
{
if(n==0&&c==0)
break;
int w[11],v[11];
for(int i=1;i<=n;i++)
cin>>w[i];
for(int i=1;i<=n;i++)
cin>>v[i];
memset(dp,0,(c+1)*sizeof(int));
for(int j=1;j<=n;j++)
for(int i=c;i>=w[j];i--) //特别注意
dp[i]=max(dp[i],dp[i-w[j]]+v[j]);
cout<<dp[c]<<endl;
}
return 0;
}
4. 八皇后问题
#include <iostream>
using namespace std;
int a[8],cnt,usedcol[8],used1[15],used2[15];
void output()
{
cnt++;
cout<<"No "<<cnt<<':'<<endl;
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
if(j==a[i]) cout<<'A';
else cout<<'.';
}
cout<<endl;
}
}
void dfs(int i)
{
if(i==8) {output();return;}
for(int j=0;j<8;j++)
{
if(!usedcol[j]&&!used1[j+i]&&!used2[j-i+7])
{
a[i]=j;
usedcol[j]=used1[j+i]=used2[j-i+7]=1;
dfs(i+1);
usedcol[j]=used1[j+i]=used2[j-i+7]=0;
}
}
return;
}
int main()
{
dfs(0);
return 0;
}
5. 加一乘二平方
#include <iostream>
#include <queue>
using namespace std;
struct T
{
int num,cnt;
}e1,e2;
queue <T> q;
bool flag[10001];
int main()
{
int m,n;
cin>>m>>n;
e1.num=m;
e1.cnt=0;
q.push(e1);
flag[e1.num]=true;
while(!q.empty())
{
e2=q.front();
q.pop();
if(e2.num==n)
{cout<<e2.cnt<<endl;break;}
else
{
e1.cnt=e2.cnt+1;
e1.num=e2.num+1;
if(e1.num<=n&&!flag[e1.num])
{
q.push(e1);
flag[e1.num]=true;
}
e1.num=e2.num<<1;
if(e1.num<=n&&!flag[e1.num])
{
q.push(e1);
flag[e1.num]=true;
}
e1.num=e2.num*e2.num;
if(e1.num<=n&&!flag[e1.num])
{
q.push(e1);
flag[e1.num]=true;
}
}
}
}
6. 电子老鼠闯迷宫
#include<iostream>
#include<queue>
using namespace std;
int flag[13][13], ex, ey, dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };
struct brid
{
int x, y;
int cnt;
}e1, e2;
queue <brid> m;
int main()
{
cin >> e1.x >> e1.y >> ex >> ey;
for (int i = 1; i <= 12; i++)
for (int j = 1; j <= 12; j++)
{
char s;
cin >> s;
if (s == 'X')
flag[i][j] = 1;
}
m.push(e1);
while (!m.empty())
{
e2 = m.front();
m.pop();
if (e2.x == ex && e2.y == ey)
{
break;
}
else
{
for (int k = 0; k < 4; k++)
{
e1.x = e2.x + dx[k];
e1.y = e2.y + dy[k];
if (e1.x >= 1 && e1.x <= 12 && e1.y >= 1 && e1.y <= 12 && !flag[e1.x][e1.y])
{
e1.cnt = e2.cnt + 1;
m.push(e1);
flag[e1.x][e1.y] = 1;
}
}
}
}
cout << e2.cnt << endl;
return 0;
}
7. 最长公共子序列
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
string origin, target;
int dp[201][201];
int main()
{
cin >> origin >> target;
int len1 = origin.size();
int len2 = target.size();
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
if (origin[i - 1] == target[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[len1][len2] << endl;
}
8. 最大连续子序列和
#include <iostream>
using namespace std;
int a[1001];
int main()
{
int n,sum(0);
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int Max=a[0];
for(int i=0;i<n;i++)
{
sum+=a[i];
if(sum>Max) Max=sum;
if(sum<0) sum=0;
}
cout<<Max<<endl;
}
9. 活动安排
#include <iostream>
#include <algorithm>
using namespace std;
struct active
{
int b,e;
}a[1001];
struct rule
{
bool operator()(const active &a,const active &b)
{
return a.e<b.e;
}
};
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i].b>>a[i].e;
sort(a,a+n,rule());
int r=a[0].e;
int ans=1;
for(int i=1;i<n;i++)
{
if(a[i].b>=r)
{
ans++;
r=a[i].e;
}
}
cout<<ans<<endl;
return 0;
}
10. 循环赛日程表
#include <iostream>
#include <cmath>
using namespace std;
int n,a[130][130];
void Merge (int left,int mid,int right)
{
int r=right-left+1;
r/=2;
for(int i=1;i<=r;i++)
{
for(int j=left;j<=mid;j++)
a[i+r][j+r]=a[i][j];
for(int j=mid+1;j<=right;j++)
a[i+r][j-r]=a[i][j];
}
}
void Partition(int left,int right)
{
if(left<right)
{
int mid=(right+left)/2;
Partition(left,mid);
Partition(mid+1,right);
Merge(left,mid,right);
}
}
int main()
{
cin>>n;
n--;
int num=2<<n; //2的n次方
for(int i=1;i<=num;i++)
a[1][i]=i;
Partition(1,num);
for(int i=1;i<=num;i++)
{
int j;
for(j=1;j<num;j++)
cout<<a[i][j]<<' ';
cout<<a[i][j]<<endl;
}
return 0;
}
11. 计算矩阵连乘积
#include<iostream>
#include <cmath>
using namespace std;
const int N = 11;
int row[N], col[N], n, dp[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> row[i] >> col[i];
for(int cnt = 1;cnt<=n;cnt++)
for (int i = 1,j=cnt; j <= n; i++,j++)
{
if (i == j) dp[i][j] = 0;
else
{
dp[i][j] = 100000;
for (int k = i; k < j; k++) //k必须从i开始
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + row[i] * col[k] * col[j]);
}
}
cout << dp[1][n] << endl;
return 0;
}
12. 快速排序
#include<iostream>
using namespace std;
#define maxn 100001
int n, a[maxn];
void quicksort(int l, int r)
{
if (l >= r) return;
int i = l, j = r, mid=l + (r - l >> 1); //选中间值作基准点
while (i < j)
{
for (; a[i] < a[mid]; i++);
for (; a[j] > a[mid]; j--);
if (i < j) swap(a[i], a[j]); //注意此处要判断i<j
}
quicksort(l, i);
quicksort(i + 1, r);
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
quicksort(0, n - 1);
for (int i = 0; i < n; i++)
cout << a[i] << ' ';
return 0;
}
13. Fibonacci 数列
//用备忘录法实现
int result[n];
int fib (int m)
{
if(m<=2)
return 1;
if(result[m]!=0)
return result[m];
result[m]=fib(m-1)+fib(m-2);
return result[m];
}
//用动态规划法实现
int dp[n];
int fib(int m)
{
if(m<=2)
return 1;
dp[1]=dp[2]=1;
for(int i=3;i<=m;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp[m];
}
14. 装载问题
#include<iostream>
using namespace std;
int sign = 0, n, c1, c2, weigh[100];
void FoundPath(int c1_w, int c2_w, int times)
{
if (c1_w > c1 || c2_w > c2) return;
if (times == n)
{
sign = 1;
return;
}
FoundPath(c1_w + weigh[times], c2_w, times + 1);
FoundPath(c1_w, c2_w + weigh[times], times + 1);
return;
}
int main()
{
int cnt = 0, c1_w = 0, c2_w = 0, times = 0, ans[100];
while (cin >> c1 >> c2 >> n)
{
if (n == 0 && c1 == 0 && c2 == 0) break;
for (int i = 0; i < n; i++)
cin >> weigh[i];
sign = 0, c1_w = 0, c2_w = 0, times = 0;
FoundPath(c1_w, c2_w, times);
ans[cnt++] = sign;
}
for (int i = 0; i < cnt; i++)
{
if (ans[i] == 0)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
return 0;
}
15. 图的m着色问题
#include<iostream>
#include<vector>
using namespace std;
int n, m, r, ans;
int color[20];
vector <int> b[20]; //邻接表储存无向图
bool check(int v,int k)
{
for (int i = 0; i < b[v].size(); i++)
{
int u = b[v][i];
if (color[u] == k)
return false;
}
return true;
}
void dfs(int v,int c)
{
color[v] = c;
for (int i = 0; i < b[v].size(); i++)
{
int u = b[v][i];
if (color[u]) continue;
for (int k = 1; k <= m; k++)
{
if (check(u, k))
{
dfs(u, k);
int j;
for (j = 0; j < n; j++)
{
if (!color[j])
break;
}
if (j >= n)
ans++;
color[u] = 0; //特别注意此处需要消除标记
}
}
}
}
int main()
{
cin >> n >> r >> m;
for (int i = 0; i < r; i++)
{
int u, v;
cin >> u >> v;
b[u].push_back(v);
b[v].push_back(u);
}
for(int i=1;i<=m;i++)
dfs(0,i);
cout << ans << endl;
return 0;
}
16. 八数码问题
#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
string str;
map<string, int> visit;
struct Node
{
string status;
int cnt;
Node(string s = "", int c = 0) :status(s), cnt(c) {}
};
void swap(string& s, int i, int j)
{
char c = s[i];
s[i] = s[j], s[j] = c;
}
string Up(string str) {
int pos = str.find("0");
if (pos <= 2) return "";
swap(str, pos, pos - 3);
return str;
}
string Down(string str) {
int pos = str.find("0");
if (pos >= 6) return "";
swap(str, pos, pos + 3);
return str;
}
string Left(string str) {
int pos = str.find("0");
if (pos == 0 || pos == 3 || pos == 6) return "";
swap(str, pos, pos - 1);
return str;
}
string Right(string str) {
int pos = str.find("0");
if (pos == 2 || pos == 5 || pos == 8) return "";
swap(str, pos, pos + 1);
return str;
}
int bfs()
{
visit[str] = 1;
queue<Node> Q;
Q.push(Node(str));
while (!Q.empty())
{
Node cn = Q.front();
Q.pop();
if (cn.status == "123456780")
return cn.cnt;
string news = Up(cn.status);
if (news != "" && visit[news] != 1)
{
Q.push(Node(news, cn.cnt + 1));
visit[news] = 1;
}
news = Down(cn.status);
if (news != "" && visit[news] != 1)
{
Q.push(Node(news, cn.cnt + 1));
visit[news] = 1;
}
news = Left(cn.status);
if (news != "" && visit[news] != 1)
{
Q.push(Node(news, cn.cnt + 1));
visit[news] = 1;
}
news = Right(cn.status);
if (news != "" && visit[news] != 1)
{
Q.push(Node(news, cn.cnt + 1));
visit[news] = 1;
}
}
return -1;
}
int main()
{
string tmp;
int n = 9;
while (n && cin >> tmp)
{
str += tmp;
n--;
}
cout << bfs() << endl;
return 0;
}
17. 最优服务次序问题
vector<double> st[N],su[N]; //st[j]是第j个服务点上某一个顾客的等待时间，su[j]是第j个服务点上所有顾客的等待时间
double time[N]; //time[j]是指第j个顾客所花费的时间
double greedy(int s)
{
sort(time.begin(),time.end());
for(int i=0,j=0;i<time.size();i++) //从小到大遍历所有顾客
{
st[j]+=time[i];
su[j]+=st[j];
j++;
if(j==s) j=0;
//如果j超出服务点数目，就从第一个服务点继续
}
double t=0;
for(int i=0;i<time.size();i++)
t+=su[i];
t/=n; //计算所有服务点所有顾客的等待时间的平均值
return t;
}
18. 最短路径问题
一个求单源最短路径的问题。给定有向带权图 G =(V, E ),其中每条边的权是非负实数。此外,给定 V 中的一个顶点,称为源点。现在要计算从源到所有其他各顶点的最短路径长度,这里路径长度指路上各边的权之和。
基本思想
设置已访问顶点集合visited,并不断贪心选择扩充这个集合,直到所有都是true,初始的时候,visited只有source顶点置为true,其余均为false,然后更新dist[i]，其存放了source顶点到i顶点的距离,若不是直接相连,则是INT_MAX,然后从第一个顶点开始遍历,更新dist,记录下它的下边和权值,将visited数组对应的下标置为true,代表已经找到了,然后更新dist数组,需要注意的是更新的前提是:
1.该顶点还没有访问(也就是还没有找到source顶点到此顶点的最短路径)
2.确保找到的这个权值最小顶点和此顶点有直接相连的边
3.权值之和小于此顶点当前的值
具体步骤如下：
- 用带权的邻接矩阵matrix表示带权有向图， 设S为当前已知最短路径的终点的集合，它的初始状态为空集。从源点到经过S到图上其余点的vi的当前最短路径长度的初始值为：dist[i]=matrix[i] [j]。
- 选择vu，使得dist[u]=min{dis[i] | vi属于V-S}，即vu是长度最短的最短路径的终点，标记vu为已访问。
- 修改从源点v到其余点的当前最短路径长度：如果dist[u]+matrix[u] [j]<dist[j]，则修改dist[j]=dist[u]+matrix[u] [j]。
- 重复操作2，3共n-1次。
//贪心算法
#include<iostream>
using namespace std;
int matrix[100][100]; //邻接矩阵表示带权有向图
bool visited[100]; //标记数组
int dist[100]; //源点到顶点i的最短距离
int path[100]; //记录最短路的路径
int source; //源点
int vertex_num; //顶点数
int arc_num; //边数
void Dijkstra(int source)
{
visited[source] = true;
for (int i = 1; i <= vertex_num; i++)
{
dist[i] = matrix[source][i]; //dist表示当前从源点到顶点i的最短特殊路径
if(dist[i]!=INT_MAX)
path[i] = source; //记录从源点到顶点i的最短特殊路径i的前一个顶点
}
int min_cost; //权值最小
int min_cost_index; //权值最小的下标
for (int i = 1; i <= vertex_num; i++) //找到源点到另外vertex_num-1个点的最短路径
{
min_cost = INT_MAX;
for (int j = 1; j <= vertex_num; j++)
{
if (visited[j] == false && dist[j] < min_cost) //找到权值最小
{
min_cost = dist[j];
min_cost_index = j;
}
}
visited[min_cost_index] = true; //该点已找到，进行标记
for (int j = 1; j <=vertex_num; j++) //更新dist数组
{
if (visited[j] == false &&
matrix[min_cost_index][j] != INT_MAX && //确保两点之间有边
matrix[min_cost_index][j] + min_cost < dist[j])
{
dist[j] = matrix[min_cost_index][j] + min_cost;
path[j] = min_cost_index;
}
}
}
}
void output()
{
for (int i = 1; i <= vertex_num; i++)
{
if (i != source)
{
cout << source << "到" << i << "最短距离是：" << dist[i] << "，路径是：" << i;
for (int t = path[i];t != source; t = path[t])
cout << "--" << t;
cout << "--" << source << endl;
}
}
}
//单源最短路径
int main()
{
cin >> vertex_num >> arc_num;
for (int i = 0; i <= vertex_num; i++)
{
for (int j = 0; j <= vertex_num; j++)
if(i==j)
matrix[i][j]=0;
else
matrix[i][j] = INT_MAX; //初始化matrix数组
}
int u, v, w;
for (int i = 0; i < arc_num; i++)
{
cin >> u >> v >> w;
matrix[u][v] = w; //u到v的长度为w
}
cin >> source;
Dijkstra(source);
output();
return 0;
}
19. 哈夫曼编码问题
算法步骤
- 对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,…,Ti,…,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
- 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
- 从F中删除这两棵树，并把这棵新的二叉树同样以降序排列(因为在末尾进行删除和增加更加方便)加入到集合F中。
- 重复二和三两步，直到集合F中只有一棵二叉树为止。
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
//类定义
template<class Type>
class Huffman
{
friend BinaryTree<int> HuffmanTree(Type[],int);
public:
operator Type() const
{
return weight;
}
private:
BinaryTree<int> tree;
Type weight;
};
//算法实现
template<class Type>
BinaryTree<int> HuffmanTree(Type f[],int n) //f是每一字符的频率，n是节点个数
{
//生成单节点树
Huffuman<Type> *w=new Huffuman<Type>[n+1];
BinaryTree<int> z,zero; //zero是指空节点
for(int i=1;i<=n;i++)
{
z.MakeTree(f[i],zero,zero);
w[i].weight=z;
w[i].tree=z; //第i个位置的权值和树
}
//建立优先队列
MinHeap<Huffman<Type>> Q(n);
for(int i=1;i<=n;i++)
Q.Insert(w[i]); //降序排序
//反复合并最小值
Huffuman<Type> x,y;
for(int i=1;i<n;i++) //一共需要n-1次合并
{
x=Q.RemoveMin(); //将Q中权值最小的节点付给x，然后将该节点删除
y=Q.RemoveMin();
z.MakeTree(x.weigt+y.weight,x.tree,y.tree); //以x和y作为儿子节点建立一个二叉树
x.weight=z;
x.tree=z;
Q.Insert(x);
}
x=Q.RemoveMin();
delete[] w;
return x.tree;
}
20. 求解素数环问题
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[21] = {}, used[21] = {}, flag = 0;
int check(int x)
{
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return 0;
return 1;
}
void dfs(int i)
{
if (flag == 1) return;
if (i == 21)
{
if (flag == 0)
{
flag = 1;
for (int m = 1; m < 20; m++)
cout << a[m] << ' ';
cout << a[20] << endl;
}
return;
}
if (i == 20)
{
for (int j = 1; j <= 20; j++)
if (!used[j] && check(j + a[1]))
{
a[i] = j;
used[j] = 1;
dfs(i + 1);
used[j] = 0;
}
}
else if (i == 1)
{
for (int j = 1; j <= 20; j++)
{
if (!used[j])
{
a[i] = j;
used[j] = 1;
dfs(i + 1);
used[j] = 0;
}
}
}
else
{
for (int j = 1; j <= 20; j++)
{
if (!used[j] && check(j + a[i - 1]))
{
a[i] = j;
used[j] = 1;
dfs(i + 1);
used[j] = 0;
}
}
}
return;
}
int main()
{
dfs(1);
return 0;
}
21. 数字三角形
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1001;
vector <int> a[N];
int main()
{
int r;
cin >> r;
for (int i = 1; i <= r; i++)
{
int x;
for (int j = 0; j < i; j++)
{
cin >> x;
a[i].push_back(x); //邻接表储存数据
}
}
for (int i = r-1; i>=1;i--) //注意i从r-1开始
{
for (int j = 0; j < i; j++)
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
cout << a[1][0];
return 0;
}
22. 最大整数
#include <iostream>
#include <stdlib.h>
using namespace std;
int n;
string a[100];
string result = "";
bool compare(string s1, string s2) {
string ts1 = s1 + s2;
string ts2 = s2 + s1;
if (ts1 > ts2)
return false;
else
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (compare(a[i], a[j]))
{
string tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
for (int i = 0; i < n; i++)
result += a[i];
cout << result << endl;
return 0;
}
23. 跳马问题
#include<iostream>
#include<queue>
using namespace std;
int ans[1001], flag[201][201];
struct brid
{
int x, y, cnt;
}e1,e2;
queue <brid> q;
int dx[] = { -2,-2,-1,-1,1,1,2,2 }, dy[] = { 1,-1,2,-2,2,-2,1,-1 };
int main()
{
int n, tx, ty, num = 0;
cin >> n;
while (n--)
{
memset(flag, 0, sizeof(flag));
cin >> e1.x >> e1.y >> tx >> ty;
flag[e1.x][e1.y] = 1;
q.push(e1);
while (!q.empty())
{
e2 = q.front();
q.pop();
if (e2.x == tx && e2.y == ty)
{
ans[num++] = e2.cnt;
while (!q.empty())
{
q.pop();
}
break;
}
for (int i = 0; i < 8; i++)
{
e1.x = e2.x + dx[i], e1.y = e2.y + dy[i];
if (e1.x < 1 || e1.y < 1 || e1.x>200 || e1.y>200 || flag[e1.x][e1.y])
continue;
e1.cnt = e2.cnt + 1;
flag[e1.x][e1.y] = 1;
q.push(e1);
}
}
e1.cnt = 0, e2.cnt = 0;
}
for (int i = 0; i < num; i++)
cout << ans[i] << endl;
return 0;
}
by xz