算法课习题汇总(2)

整数划分问题

将正整数n表示成一系列正整数之和，n=n1+n2+…+nk(n1>=n2>=…>=nk,k>=1)。正整数n的这种表示称为正整数n的划分。

思路：

n表示待划分数，m表示最大减数。

#include<iostream>
using namespace std;

int q(int n, int m)
{
	if (m == 1)
		return 1;
	if (m > n)
		return q(n, n);
	if (n == m)
		return q(n, n-1) + 1;
	return q(n - m, m) + q(n, m-1);
}

int main()
{
	int n = 0;
	cin >> n;
	cout << q(n, n) << endl;
	return 0;
}

Hanoi问题 T(n)=2^n-1

具体看：汉诺塔问题

#include<iostream>
using namespace std;

void move(char A, char B)
{
	cout << A <<"->" << B << endl;
}

void hanoi(int n, char A, char B, char C)
{
	if (n == 0)
		return;
	hanoi(n - 1, A, C, B);
	move(A, B);
	hanoi(n - 1, C, B, A);
}

int main()
{
	int n = 0;
	cin >> n;
	hanoi(n,'A','B','C');
	return 0;
}

二分搜索 O(n)=nlogn

int Search(int* arr, int x, int n)
{
	int left = 0;
	int right = n;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (x == arr[mid])
			return mid;
		else if (x > arr[mid])
			left = mid + 1;
		else
			right = mid - 1;
	}
	return -1;
}

int main()
{
	int n = 0;
	cin >> n;
	int arr[1000];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	cout << Search(arr, 5, n - 1) << endl;
	return 0;
}

合并排序 O(n)=nlogn

#include<iostream>
using namespace std;

void Merge(int* arr, int l, int r)
{
	if (l == r)
		return;
	int mid = l + (r - l) / 2;
	Merge(arr, l, mid);
	Merge(arr, mid + 1, r);
	int i = l, j = mid + 1, k = l;
	int arr2[10000] = {0};
	while (i <= mid && j <= r)
	{
		if (arr[i] >= arr[j])
		{
			arr2[k++] = arr[j++];
		}
		else
		{
			arr2[k++] = arr[i++];
		}
	}
	while (i <= mid)
	{
		arr2[k++] = arr[i++];
	}
	while (j <= r)
	{
		arr2[k++] = arr[j++];
	}
	for (i = l; i <= r; i++)
	{
		arr[i] = arr2[i];
	}
}

int main()
{
	int n;
	cin >> n;
	int arr[10000];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	Merge(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
		cout << arr[i]<<" ";
	cout << endl;
	return 0;
}

快速排序 O(n)=nlogn

#include<iostream>
using namespace std;

void q(int* arr, int l, int r)
{
	if (l >= r)
		return;
	int mid=l+(r-l)/2;
	swap(arr[1], arr[mid]);
	int tmp = arr[1];
	int i = l, j = r;
	while (1)
	{
		while (i < j && arr[j] >= tmp)
			j--;
		while (i < j && arr[i] <= tmp)
			i++;
		if (i >= j)
			break;
		swap(arr[i], arr[j]);
	}
	swap(arr[i],arr[1]);
	q(arr, l, i - 1);
	q(arr, i + 1, r);
}

int main()
{
	int n;
	cin >> n;
	int arr[100];
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	q(arr, 0, n - 1);
	for (int i = 0; i < n; i++)
		cout << arr[i]<<" ";
	cout << endl;
	return 0;
}