算法实验4《回溯法》
【摘要】
1. 编写一个简单的程序，解决8皇后问题。
#include<iostream>using namespace std; bool backtrack(int list[8], int t){ if (t >= 8)return true; for (int i = 0; i < 8; i++) { li...
1. 编写一个简单的程序，解决8皇后问题。
-
#include<iostream>
-
using namespace std;
-
-
bool backtrack(int list[8], int t)
-
{
-
if (t >= 8)return true;
-
for (int i = 0; i < 8; i++)
-
{
-
list[t] = i;
-
bool place = true;
-
for (int j = 0; j < t; j++)if (list[j] == i || j-t==list[j]-i || j-t==i-list[j])place = false;
-
if (place && backtrack(list, t+1))return true;
-
continue;
-
}
-
return false;
-
}
-
-
int main()
-
{
-
int list[8];
-
for (int i = 0; i < 8; i++)list[i] = 0;
-
backtrack(list, 0);
-
for (int i = 0; i < 8; i++)cout << list[i] << " ";
-
system("pause>nul");
-
return 0;
-
}
2. 批处理作业调度问题
[问题描述]给定n个作业的集合J=(J1, J2, … , Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2, … ,n; j=1,2。
对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。
要求输入：
1）作业数 2）每个作业完成时间表：
| 作业完成时间 |
机器1 |
机器2 |
| 作业1 |
2 |
1 |
| 作业2 |
3 |
1 |
| 作业3 |
2 |
3 |
要求输出： 1）最佳完成时间 2）最佳调度方案
提示：算法复杂度为O(n!),建议在测试的时候n值不要太大，可以考虑不要超过12。
-
#include<iostream>
-
using namespace std;
-
-
void backtrack(int *t1, int *t2, int *list1, int *list2, int *list, int &sumTime, int &time, int t, int n)
-
{
-
if (t >= n)
-
{
-
if (sumTime > time)sumTime = time;
-
return;
-
}
-
for (int i = 0; i < n; i++) //选择1个作业
-
{
-
bool place = true;
-
for (int j = 0; j < t; j++)if (list[j] == i)place = false; //判断这个作业是否可选
-
if (!place)continue;
-
-
list[t] = i;
-
if (t)t1[t] = t1[t - 1];
-
else t1[t] = 0;
-
t1[t] += list1[i];
-
-
if (t)t2[t] = (t1[t]>t2[t - 1]) ? t1[t] : t2[t - 1]; //这3行计算t2[i]
-
else t2[t] = t1[t];
-
t2[t] += list2[i];
-
-
time += t2[t];
-
if (time <= sumTime)backtrack(t1, t2, list1, list2, list, sumTime, time, t + 1, n);
-
time -= t2[t];
-
}
-
}
-
-
int main()
-
{
-
int n;
-
cin >> n;
-
int *list1 = new int[n]; //作业在机器1上运行的时间t11-t1n
-
int *list2 = new int[n]; //作业在机器2上运行的时间t21-t2n
-
int *t1 = new int[n]; //作业在机器1上完成的时间F11-F1n
-
int *t2 = new int[n]; //作业在机器2上完成的时间F21-F2n
-
int sumTime = 0; //总时间上界
-
for (int i = 0; i < n; i++)
-
{
-
cin >> list1[i] >> list2[i];
-
sumTime += (list1[i] + list2[i])*(i + 1);
-
}
-
int *list = new int[n]; //记录作业运行的顺序
-
int time = 0; //总时间
-
backtrack(t1, t2, list1, list2, list, sumTime, time, 0, n);
-
cout << sumTime << endl;
-
system("pause>nul");
-
return 0;
-
}
3. 数字全排列问题
任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。
注意：数字不能重复，N由键盘输入（N<=9）。
-
#include<iostream>
-
using namespace std;
-
-
void backtrack(int n,int t,int *list)
-
{
-
if (t >= n)
-
{
-
for (int i = 0; i < n; i++)cout << list[i]+1 << " ";
-
cout << endl;
-
}
-
for (int i = 0; i < n; i++)
-
{
-
bool flag = true;
-
for (int j = 0; j < t; j++)if (list[j] == i)flag = false;
-
if (flag)
-
{
-
list[t] = i;
-
backtrack(n, t + 1, list);
-
}
-
}
-
}
-
-
int main()
-
{
-
int n;
-
cin >> n;
-
int list[9];
-
backtrack(n, 0, list);
-
system("pause>nul");
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/78868638
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）