算法课习题汇总(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;elseright = 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;
}