表4-3 编号与因数个数的关系 n 1 2 3 4 5 6 7 8 9 10 11 12 d(n) 1 2 2 3 2 4 2 4 3 4 2 6 13 2 14 15 4 4 16 …… 5 ……
数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房 的门开始是关着的，这样编号为i的牢房，所含1——i之间的不 重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后 是关闭的。
内蒙古农业大学职业技术学院
蛮力法
| 89 45 68 90 29 34 17
17 | 45 68 90 29 34 89 17 17 17 17 29 | 68 90 45 34 89 29 34 45 | 90 68 89 29 34 45 68 | 90 89 29 34 45 68 89 | 90
受速度对实例求解。
第四，即使效率通常很低，仍然可以用蛮力法解决一些小规模的问
题实例。
2 >
内蒙古农业大学职业技术学院
蛮力法
穷举法
选择排序和冒泡排序
顺序查找和蛮力字符串匹配
3 >
内蒙古农业大学职业技术学院
蛮力法
穷举查找
对于组合问题来说，穷举查找是一种简单的蛮力方法。它要求生 成问题域中的每一个元素，选出其中满足问题约束的元素，然后 再找出一个期望元素（例如，使目标函数达到最值的元素）。
内蒙古农业大学职业技术学院
蛮力法
选择排序和冒泡排序 1 选择排序
A0≤A1≤…Ai-1|Ai ,…,Amin ,…, An-1
已经位于最终的位 置上了 最后的n-1个元素
算法 SelectionSort(A[0..n-1]) //该算法用选择排序对给定的数组排序 //输入：一个可排序数组A[0..n-1] //输出：非降序排序的数组A[0..n-1] for i←0 to n-2 do min ←I for j ←i+1 to n-1 do if A[j]<[min] min ←j swap A[i] and A[min]
内蒙古农业大学职业技术学院
蛮力法
main1( ) {int *a,i,j,n; input(n); a=calloc(n+1,sizeof(int)); for (i=1; i<=n;i++) a[i]=1; for (i=1; i<=n;i++) for (j=i; j<=n;j=j+i) a[i]=1-a[i]; for (i=1; i<=n;i++) if (a[i]=0) print(i,”is free.”); } 算法分析：以一次开关锁计算，算法的时间复杂度为 n(1+1/2+1/3+……+1/n)=O(nlogn)。
任务1 4 人员1 9 人员2 6
任务2 2 4
任务3 7 3
任务 8 7
人员3
人员4
5
7
8
6
1
9
8
内蒙古农业大学职业技术学院
4
蛮力法
9 6 C 5 7 2 7 8 4 3 7 8 1 8 6 9 4
<1,2,3,4> <1,2,4,3> <1,3,2,4> <1,3,4,2> <1,4,2,3> <1,4,3,2>
cost=9+4+1+4=18 cost=9+4+8+9=30 cost=9+3+8+4=24 cost=9+3+8+6=26 cost=9+7+8+9=33 cost=9+7+1+6=23
用穷举法查找解决一个小规模分配问题的最初几次循环
内蒙古农业大学职业技术学院
蛮力法
4 百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出 了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三； 鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何? 算法设计1：
I=2+8+1+7=18 I=2+3+1+5=11 I=5+8+3+7=23 I=5+1+3+2=11 I=7+3+8+5=23 最佳 最佳
adc b a I=7+1+8+2=18 用穷举查找对一个小规模旅行商问题的求解过程
内蒙古农业大学职业技术学院
蛮力法
2 背包问题 这是计算机科学中另一个著名的问题。给定n个重量为 wi,…, wn、价值为vi,…,vn的物品和一承重为W的背包， 求这些物品中一个最有价值的子集。
内蒙古农业大学职业技术学院
蛮力法
算法设计1： 1）用n个空间的一维数组a[n],每个元素记录一个锁的状 态，1为被锁上，0为被打开。 2）用数学运算方便模拟开关锁的技巧，对i号锁的一次开 关锁可以转化为算术运算：a[i]=1-a[i]。 3）第一次转动的是1，2，3，……，n号牢房； 第二次转动的是2，4，6，……号牢房； 第三次转动的是3，6，9，……号牢房； ……第i次转动的是i，2i，3i，4i，……号牢房，是起点为 i，公差为i的等差数列。 4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关 锁过程，最后当第i号牢房对应的数组元素a[i]为0时， 该牢房的囚犯得到大赦。算法1如下：
数学模型2：仔细观察表4-3，发现当且仅当n为完全平 方数时,d(n)为奇数；这是因为n的因子是成对出现的, 也即当n=a*b且a≠b时，必有两个因子a，b; 只有n为 完全平方数，也即当n=a2 时, 才会出现d(n)为奇数的 情形。 算法设计3：这时只需要找出小于n的平方数即可。算 法3如下：
内蒙古农业大学职业技术学院
10
W=7
V=$4 2 W=3 W=4 V=$4 0 W=5 V=$2 5
V=$1 2
背包
物品1
物品2
物品3
物品4
内蒙古农业大学职业技术学院
(a)
蛮力法
子集
ø {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4}
ห้องสมุดไป่ตู้总重量
0 7 3 4 5 10 11 12 7 8
通过对问题的理解，读者可能会想到列出两个三元一次方程，去解 这个不定解方程，就能找出问题的解。这确实是一种办法，但这里 我们要用“懒惰”的枚举策略进行算法设计： 设x，y，z分别为公鸡、母鸡、小鸡的数量。 尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买 100/5=20只，显然x的取值范围1~20之间；同理，y的取值范围在 1~33之间，z的取值范围在1~100之间。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100
内蒙古农业大学职业技术学院
蛮力法
算法分析： 狱吏开关锁的主要操作是a[i]=1- a[i];共执行了 n*(1+1/2+1/3+……+1/n)次，时间近似为复杂度为O（n log n）。使用了n个空间的一维数组。算法2没有使用辅助空间，但 由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执行了n*(1+2+3+……+n)次，时间复杂度为O （n2）。
17 29 34 | 90 45 68 89
内蒙古农业大学职业技术学院
蛮力法
2 冒泡排序 ? A0,…,Aj↔Aj+1,…,An-i-1 | An-i≤…≤An-1
已经位于最终的位 置上了
算法 BubbleSort(A[0..n-1]) //该算法用冒泡排序对数组A[0..n-1]排序 //输入：一个可排序数组A[0..n-1]
内蒙古农业大学职业技术学院
蛮力法
问题分析：转动门锁的规则可以有另一种理解，第一次转动的 是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢 房；第三次转动的是编号为3的倍数的牢房；……则狱吏问题是 一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里 不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2， 2，4。则d(n)有的为奇数，有的为偶数，见下表:
总价值
$0 $42 $12 $40 $25 $36 不可行 不可行 $52 $37
{3,4}
{1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
9
14 15 16 12 19
$65
不可行 不可行 不可行 不可行 不可行
内蒙古农业大学职业技术学院
蛮力法
3 分配问题 有n个任务需要分配给n个人执行，一个任务一个人。（意思是说 ，每个任务只分配给一个人，每个人只分配一个任务。）对于每 一对i,j=1,…,n来说，将第j个任务分配给i个人的成本是C[i,j]。该问 题要找出总成本最小的分配方案。
1 旅行商问题 按照非专业的说法，这个问题要求找出一条n个给定的城 市间的最短路径，使我们在回到出发的城市之前，对每个城市都 只访问一次。
内蒙古农业大学职业技术学院
蛮力法
a 5 8 c
路线
2 7 1
b d
3
旅程
abc d a abd c a acb d a acd b a adb c a
蛮力法
main3( ) {int s,i,j,n;
input(n);
for (i=1;i<=n;i++) if（i*i<=n） print(i,”is else } break; free.”);
由此算法我们应当注意：在对运行效率要求较高的大规模的 数据处理问题时，必须多动脑筋找出效率较高的数学模型及其 对应的算法。