算法實(shí)驗(yàn)4《回溯法》

1. 編寫一個(gè)簡(jiǎn)單的程序，解決8皇后問(wèn)題。

#include

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;

}

1）作業(yè)數(shù) 2）每個(gè)作業(yè)完成時(shí)間表：

作業(yè)完成時(shí)間

機(jī)器1

機(jī)器2

作業(yè)1

2

1

作業(yè)2

3

1

作業(yè)3

2

3

要求輸出： 1）最佳完成時(shí)間 2）最佳調(diào)度方案

提示：算法復(fù)雜度為O(n!),建議在測(cè)試的時(shí)候n值不要太大，可以考慮不要超過(guò)12。

#include

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個(gè)作業(yè)

{

bool place = true;

for (int j = 0; j < t; j++)if (list[j] == i)place = false; //判斷這個(gè)作業(yè)是否可選

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行計(jì)算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]; //作業(yè)在機(jī)器1上運(yùn)行的時(shí)間t11-t1n

int *list2 = new int[n]; //作業(yè)在機(jī)器2上運(yùn)行的時(shí)間t21-t2n

int *t1 = new int[n]; //作業(yè)在機(jī)器1上完成的時(shí)間F11-F1n

int *t2 = new int[n]; //作業(yè)在機(jī)器2上完成的時(shí)間F21-F2n

int sumTime = 0; //總時(shí)間上界

for (int i = 0; i < n; i++)

{

cin >> list1[i] >> list2[i];

sumTime += (list1[i] + list2[i])*(i + 1);

}

int *list = new int[n]; //記錄作業(yè)運(yùn)行的順序

int time = 0; //總時(shí)間

backtrack(t1, t2, list1, list2, list, sumTime, time, 0, n);

cout << sumTime << endl;

system("pause>nul");

return 0;

}

3. 數(shù)字全排列問(wèn)題

任意給出從1到N的N個(gè)連續(xù)的自然數(shù)，求出這N個(gè)自然數(shù)的各種全排列。如N=3時(shí)，共有以下6種排列方式：123，132，213，231，312，321。

注意：數(shù)字不能重復(fù)，N由鍵盤輸入（N<=9）。

#include

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;

}

MapReduce

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。