算法课习题汇总(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;
}
原文地址：https://blog.csdn.net/2302_79180171/article/details/142395976
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！