上节课作业部分(点击跳转)
引入
分治算法概念
二分法分治思想
编程题
二分查找能解决的问题不仅仅是找到一个值
题1：
要在一个有序序列中查找一个数，可以使用二分算法。
include <iostream>
using namespace std;
int BinarySearch(int a[], int l, int r,int x) {
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] == x) return mid;
else if (a[mid] > x) r = mid - 1;
else l = mid + 1;
}
return -1;
}
int main() {
int n;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int l = 1, r = n;
cout << BinarySearch(a, 1, n, x);
return 0;
}
题2：[【二分查找】第一个大于等于x的数]
要在一个有序序列中查找第一个大于等于 x 的数，可以使用二分算法。
include <iostream>
using namespace std;
int BinarySearch(int a[], int l, int r,int x) {
int ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] >= x) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
}
return ans;
}
int main() {
int n;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int l = 1, r = n;
cout << BinarySearch(a, 1, n, x);
return 0;
}
最后一个等于x
这俩题同一个代码，都是往右找
要在一个有序序列中查找最后一个等于 x 的数，可以使用二分算法。
include <iostream>
using namespace std;
int BinarySearch(int a[], int l, int r,int x) {
int ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] <= x) {
l = mid + 1;
ans = mid;
}
else {
r = mid - 1;
}
}
if (a[ans] == x) {
return ans;
}
return -1;
}
int main() {
int n;
int a[109];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int l = 1, r = n;
cout << BinarySearch(a, 1, n, x);
return 0;
}
[【二分查找】lower_bound函数]
[【二分查找】upper_bound函数]
[根号2]
实数二分，按照题意进行二分。
include <iostream>
include <cstdio>
using namespace std;
int main() {
double l = 1, r = 2;
while (l + 1e-5 < r) {
double mid = (l + r) / 2;
printf("%.2f\n", mid);
if (mid * mid >= 2) r = mid;
else l = mid;
}
printf("%.2f\n", l);
return 0;
}urn 0;
}
作业部分：
************
作业1：[【递推】平行线分割平面问题]
【算法分析】 用 a[i] 表示 i 组平行直线最多能将这个圆分割成的部分数 当 i=1 时，a[1]=3 当 i=2 时，a[2]=9 第 i 组平行线的一条直线和前 i–1 组平行线都有不同的交点，且交点数为 2×(i−1)i>=2时，a[i]=a[i−1]+(交点数+1)×2
代入得： a[i]=a[i−1]+((i−1)×2+1)×2=a[i−1]+4×i−2【参考代码】
include <iostream>
using namespace std;
const int N = 1e4 + 10;
long long a[N];int main() {
int n;
cin >> n;
a[1] = 3;
for(int i = 2; i <= n; i++){
// 递推式
a[i] = a[i - 1] + 4 * i - 2;
}
cout << a[n];
return 0;
}
[【递推】小码君的牛肉串]
【算法分析】
f[i] 表示长度为 n 的字符串的涂法个数
f[1]=3
f[2]=8
总长度为 i 时，思考最后一个字符：
1.为 E 或 F，前 i−1 个字符串随便涂，为 2∗f[i−1]
2.为 O 时，i−1 的位置上不能为 O，则最后两个字符为 EO 或 FO，填法数为 2∗f[i−2]
所以递推式为 f[i]=2∗f[i−1]+2∗f[i−2]
【参考代码】
include <iostream>
using namespace std;
long long f[50];
int main(){
int n;
cin >> n;
f[1] = 3;
f[2] = 8;
for(int i = 3; i <= n; i++){
f[i] = 2 * f[i - 1] + 2 * f[i - 2];
}
cout << f[n];
return 0;
}
选择题
正确答案
解析
因为两端不能排女生，所以两端只能挑选 5 个男生中的 2 个，有 $A_{5}^2$ 种不同的排法，对于其中任意一种排法，其余六位都有 $A_{6}^6$ 种排法，所以共有 $A_{5}^2 \times A_{6}^6 = 14400$ 种不同的排法。
正确答案
解析
先把 1 填入方格有 3 种方法，第二步把填入方格的对应数字填入其它方格，有三种排法，第三步填剩下的两个数字只有一种排法，共有 $3 \times 3 \times 1$ 种排法。
选做题
【算法分析】
设置二维数组 f，f[i][j] 表示到 (i,j) 的不同的移动路线的数目。
当 i1 或者 j1 时，因为蚂蚁只能向上或者向右走，所以划分的方案数为 1。
其他情况：
f[i][j] 可以由 f[i-1][j] 向上走一步和 f[i][j-1] 向右走一步得来，所以递推式为：f[i][j]=f[i−1][j]+f[i][j−1]
【参考代码】
include <iostream>
using namespace std;
int f[30][30];
int main() {
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 || j == 1) {
f[i][j] = 1;
} else {
f[i][j] = f[i][j - 1] + f[i - 1][j];
}
}
}
cout << f[m][n];
return 0;
}
【算法分析】
设置二维数组 f，f[i][j] 表示将 i 个数划分为 j 个子集的划分数。
当 ij 或者 j1 时，划分的方案数为 1。
其他情况：
f[i][j] 可以由两个部分得来：
(1) 相比于 f[i−1][j−1]，f[i][j] 多出的 i 可以单独作为一个子集，有 f[i−1][j−1] 种方法
(2) 相比于 f[i−1][j]，f[i][j] 多出的 i 可以放入划分的 j 个子集中的一个，有 f[i−1][j]∗j 种方法
所以 f[i][j]=(f[i−1][j]∗j+f[i−1][j−1])%10007
【参考代码】
include <iostream>
using namespace std;
int f[110][110];
int main() {
int n, r;
cin >> n >> r;
for (int i = 1; i <= n; i++) {
f[i][i] = f[i][1] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= r; j++) {
f[i][j] = (f[i - 1][j] * j + f[i - 1][j - 1]) % 10007;
}
}
cout << f[n][r];
}