算法学习之 ---枚举

算法学习之 ---枚举


[1] 枚举算法的思想是:

将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,舍弃不合适的。

[2] 使用枚举算法解题的基本思路如下:

1.确定枚举对象、范围和判定条件。
2.逐一枚举可能的解并验证每个解是否是问题的解。

[3] 枚举算法步骤:

1.确定解题的可能范围,不能遗漏任何一个真正解,同时避免重复。
2.判定是否是真正解的方法。
3.为了提高解决问题的效率,使可能解的范围将至最小。

[4] 枚举算法的流程图如下所示:

QQ截图20180321231455.png

算法实列 ---(枚举)

例一:百钱买白鸡

1,问题描述:
公鸡每只5元,母鸡每只3元,三只小鸡1元,用100元买100只鸡,问公鸡、母鸡、小鸡各多少只?
2,算法分析:
利用枚举法解决该问题,以三种鸡的个数为枚举对象,分别设为mj,gj和xj,用三种鸡的总数(mj+gj+xj=100)和买鸡钱的总数(1/3*xj+mj*3+gj*5=100)作为判定条件,穷举各种鸡的个数。

例二:使用枚举法解决“填写运算符问题”

1,问题描述:
在下面的算式中,添加“+”、“-”,“*”,“/”,4个运算符,使得这个式子成立: 5 5 5 5 5=5
2,算法分析:
上述式子左侧有5个数字,一共需要4个运算符。根据题目要求,两个数字之间的运算符只能有4中选择。在具体编程时,可以通过循环来填入各种运算符,然后再判断算式左侧的值是否等于右侧的值。并保证,当填入的是除号时,则右侧的数不能为0,并且乘除的优先级高于加减的优先级。

算法实现

例一:百钱买白鸡

m = g = x = 0 #定义变量分别表示母鸡、公鸡、小鸡并初始化
for g in range(0,20): #公鸡最多可买20个
    for m in range(0,33):#母鸡最多可买33个
        x = 100 - g - m #三种鸡的总数是100只
        if x % 3 == 0 and 5 * g + 3 * m + x / 3 == 100:
            #总花费为100元
            print ("公鸡:",g,"母鸡:",m,"小鸡:",x)

结果:

公鸡 0 母鸡 25 小鸡 75
公鸡 4 母鸡 18 小鸡 78
公鸡 8 母鸡 11 小鸡 81
公鸡 12 母鸡 4 小鸡 84

例二:使用枚举法解决“填写运算符问题”

j = 0                        #循环变量
sign = 0                     #累加运算时的符号
result = 0                   #保存运算式子的结果值
count = 0                    #计数器,统计符合条件的方案
left = right = 0             #存中间结果
i = []                       #用来表示4个运算符
num = []                     #保存操作数
oper = [' ','+','-','*','/'] #运算符

def jia():
    global left
    global sign
    global right
    left = left + sign*right
    sign = 1
    right = num[j + 1]
    
def jian():
    global left
    global sign
    global right
    left = left + sign*right
    sign = -1
    right = num[j + 1]
    
def chen():
    global right
    right = right*num[j + 1]
    
def chu():
    global right
    right = right / num[j + 1]

print("输入5个数,之间用空格隔开:")
for j in range(1,5):
    num[j] = input()
print("输入结果:")
result = input()
#注:这里i[1]代表的第一个运算符的意思,i[1]=1代表第一个运算符是“+”,i[1]=2代表第一个运算符是“减”,i[1]=3代表第一个运算符是“-”,i[1]=4代表第一个运算符是“/”
#注:这里i[2]代表的第二个运算符的意思,i[2]=1代表第二个运算符是“+”,i[2]=2代表第二个运算符是“减”,i[2]=3代表第二个运算符是“-”,i[2]=4代表第二个运算符是“/” 
#i[3],i[4]依次类推

#循环4种运算符,1表示+,2表示-,3表示*,4表示/
for i[1] in range(1,4):
    #运算符若是/,则第二个运算数不能为0,(注:“||”是或运算,两个条件至少要有一个成立,即第一个运算符为/时,第二个运算数不为0)
    if i[1]<4 or num[2] != 0:
        for i[2] in range(1,4):
            #当第二个运算符为/时,第三个运算数不为0
            if i[2]<4 or num[3] != 0:
                for i[3] in range(1,4):
                    #当第三个运算符为/时,第四个运算数不为0
                    if i[3]<4 or num[4] != 0:
                        for i[4] in range(1,4):
                            #当第四个运算符为/时,第五个运算数不为0
                            if i[4]<4 or num[5] != 0:
                                left = 0
                                right = num[1]
                                sign = 1
                                #使用case语句,将4种运算符填到对应的空格位置,并进行计算
                                for j in range(1,4):
                                    switcher = {
                                        '+':jia,
                                        '-':jian,
                                        '*':chen,
                                        '/':chu,
                                    }
                                    switcher.get(oper[i[j]])
                                #开始判断,如果运算式子的结果和输入的结果相同,则表示找到一种算法,并输出这个解
                                if left + sign*right == result:
                                    count = count + 1
                                    print(count,':')
                                    for j in range(1,4):
                                        print(num[j],oper[i[j]])
                                    print(num[5],result)
if count == 0 :
    print("没有符合要求的方法!")

运算 right 小鸡 公鸡 母鸡

8 条回复
  1. 灵徒
    灵徒

    第二题用php写,很简单额!
    $fh = ['+','-','*','/'];

    foreach ($fh as $item1) {

    foreach ($fh as $item2) { foreach ($fh as $item3) { foreach ($fh as $item4) { eval("\$re = 5 $item1 5 $item2 5 $item3 5 $item4 5;"); if($re == 5) var_dump("5 $item1 5 $item2 5 $item3 5 $item4 5"); } } }

    }

  2. 灵徒
    灵徒

    右侧那个悬浮的书签是咋个弄的啊?

    1. ixixixe2
      ixixixe2 回复灵徒

      写文章的时候 用H(12345) 都是属于副标题

      1. 灵徒
        灵徒 回复ixixixe2

        好像没有用啊,加了H还是没有那个书签!只有评论一下!另外editor.md 编辑器怎么去掉自动加的链接啊???有的地方网址不需要加链接

      2. 灵徒
        灵徒 回复ixixixe2

        https://www.hehaoke.com/index.php/archives/20 你看我发的这个文章,确实没有生成那个书签!而且H(1234)生成的元素跟你都有区别!

        1. ixixixe2
          ixixixe2 回复灵徒

          打开MAIN.JS 文件 把var allTitleNode = contnet.children('h5,h4,h3,h2,h1'); 这行修改为var allTitleNode = contnet.find('h5,h4,h3,h2,h1');