算法设计与分析实验一-分治和递归

【问题1】在n×n的方格棋盘上,放置n个皇后,要求每个皇后不同行、不同列、不同左右对角线,求所有皇后放置方法。

#include <vector>
#include <iostream>
using namespace std;

vector<int> vQueen;
bool Place(int k, int j, int n)
{
	if (k == 1)
		return true;
	for (int i = 1; i < k; i++)
	{
		if (vQueen[i] == j || abs(i - k) == abs(vQueen[i] - j))
			return false;;
	}
	return true;
}
void Queen(int k, int n)
{
	if (k > n)
	{
		for (int i = 1; i <= n; i++)
			cout << vQueen[i] << " ";
		cout << endl;
	}
	else
	{
		for (int j = 1; j <= n; j++)
		{
			if (Place(k, j, n))
			{
				vQueen[k] = j;
				Queen(k + 1, n);
			}
		}
	}
}
int main(void)
{
	int n;
	cin >> n;
	for (int i = 0; i <= n; i++)
		vQueen.push_back(0);
	Queen(1, n);
	return 0;
}

【问题2】对于给定的含有n元素的无序序列,求这个序列中最小和次小的两个不同的元素。

#include<iostream>
#include<vector>

using namespace std;

const int INF = 0x3f3f3f3f;

int n;
vector<int> vData;

#define MIN(a,b) ((a) >=( b) ? (b) : (a))
#define MAX(a,b) ((a) >=( b) ? (a) : (b))


void FindTwoMin(int left, int right, int& min1, int& min2)
{
	if (left == right)
	{
		min1 = vData[left];
		min2 = INF;
	}
	else if (left == right - 1) {
		min1 = MIN(vData[left], vData[right]);
		min2 = MAX(vData[left], vData[right]);
	}
	else {
		int mid = (right + left) / 2;
		int lmin1, lmin2;
		FindTwoMin(left, mid, lmin1, lmin2);
		int rmin1, rmin2;
		FindTwoMin(mid + 1, right, rmin1, rmin2);

		if (lmin1 < rmin1)
		{
			min1 = lmin1;
			min2 = MIN(lmin2, rmin1);
		}
		else {
			min1 = rmin1;
			min2 = MIN(rmin2, lmin1);
		}
	}
}
int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vData.push_back(a);
	}
	int min1, min2;
	FindTwoMin(0, n - 1, min1, min2);
	cout << "最小数:" << min1 << "," << "次小数:" << min2 << endl;
	return 0;
}

【问题3】对于给定的含有n元素的无序序列,求这个序列中第k (1≤k≤n)大的元素。

#include <iostream>
#include <vector>

using namespace std;

int QuickFind(vector<int> a, int left, int right, int k)
{
	if (left < right)
	{
		int i = left;
		int j = right;

		int temp = a[left];
		while (i != j)
		{
			while (j > i && a[j] < temp)
			{
				j--;
			}
			a[i] = a[j];

			while (i<j && a[i]>temp)
			{
				i++;
			}
			a[j] = a[i];
		}
		a[i] = temp;

		if (k - 1 == i)
		{
			return a[i];
		}
		else if (k - 1 < i)
		{
			return QuickFind(a, left, i - 1, k);
		}
		else
		{
			return QuickFind(a, i + 1, right, k);
		}
	}
	else if (left == right && k - 1 == left)
	{
		return a[k - 1];
	}
}


int main()
{
	int n;
	cin >> n;

	vector<int> vData;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vData.push_back(a);
	}

	int k;
	cin >> k;

	int result = QuickFind(vData, 0, n - 1, k);
	cout << "第" << k << "大的数:" << result << endl;
	return 0;
}
---完---