北京大学《算法基础》课程---枚举的基本思想

48 阅读 0 评论 32 点赞

我是靠谱客的博主无心鞋垫，最近开发中收集的这篇文章主要介绍北京大学《算法基础》课程---枚举的基本思想，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

程序设计实习MOOC
http://cxsjsxmooc.openjudge.cn/

枚举 
基于已有知识进行答案猜测的一种问题求解策略 
例如: 求小于N的最大素数 
• 找不到一个数学公式, 使得根据N就可以计算出这个素数 
• N-1是素数吗? N-2是素数吗? …… 
• N-K是素数的充分必要条件: 
  N-K不能被任何一个大于1, 小于N-K的素数整除 
判断N-K是否是素数的问题 
转化为求小于N-K的全部素数

枚举 
解决办法 
• 2是素数, 记为PRIM0 
• 根据PRIM0, PRIM1, …, PRIMk, 寻找比PRIMk大的最小素数PRIMk+1 
• 如果PRIMk+1大于N, 则PRIMk是我们需要找的素数, 
否则继续寻找

枚举的思想: 猜测 
枚举 
从可能的集合中一 一列举各元素 
• 根据所知道的知识, 给一个猜测的答案 
• 2是素数 
枚举算法 
• 对问题可能解集合的每一项 
• 根据问题给定的检验条件判定哪些是成立的 
• 使条件成立的即是问题的解

枚举的思想: 猜测 
枚举过程 
• 判断猜测的答案是否正确 
 2是小于N的最大素数吗? 
• 进行新的猜测: 有两个关键因素要注意 
• 猜测的结果必须是前面的猜测中没有出现过的. 每次猜测
是素数一定比已经找到的素数大 
• 猜测的过程中要及早排除错误的答案. 除2之外, 只有奇数
才可能是素数

枚举中三个关键问题 
问题一 
给出解空间, 建立简洁的数学模型 
可能的情况是什么 
模型中变量数尽可能少, 它们之间相互独立 
• “求小于N的最大素数” 中的条件是 “n不能被[2,n)中任意
一个素数整除” 
• 而不是 “n不能被[2,n)中任意一个整数整除”

枚举中三个关键问题 
问题二 
减少搜索的空间 
利用知识缩小模型中各变量的取值范围, 避免不必要的
计算 
减少代码中循环体执行次数 
• 除2之外, 只有奇数才可能是素数, {2,2*i+1|1<=i, 2*i+1<n}

枚举中三个关键问题 
问题三 
采用合适的搜索顺序 
搜索空间的遍历顺序要与模型中条件表达式一致 
• 对{2,2*i+1|1<=i, 2*i+1<n}按照从小到大的顺序

中国古代的枚举问题 
百钱百鸡问题 
• 鸡翁一值钱五, 鸡母一值钱三, 鸡雏三值钱一. 
百钱买百鸡, 问鸡翁, 鸡母, 鸡雏各几何 
                  —— 张丘建《算经》 
• 求解方法: 
• 先构造可能的解的集合 S={(X,Y,Z)|0<=X,Y,Z<=100} 
  X, Y, Z分别代表买公鸡, 母鸡和小鸡的只数 
• 然后验证条件X+Y+Z=100, 5X+3Y+Z/3=100 
• 复杂度: O(100^2)

中国古代的枚举问题 
百钱百鸡问题 
10 
for (int x=0; x<=100; x++) 
for (int y=0 ; y<=100-x; y++){ 
  z = 100 - x - y; 
  if (z % 3==0) then 
  if (5*x+3*y+z/3==100)   
        then (x,y,z) is solution 
        }