飞道的博客

educoder:实验13 算法-穷举法和二分法

390人阅读  评论(0)

第1关:百钱百鸡

任务描述

我国古代数学家张丘建在《算经》一书中提出的数学问题:鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?

相关知识

为了完成本关任务,你需要掌握:1.穷举法历数组。

穷举法

也称之为枚举算法、暴力破解法,就是按照问题本身的性质,一 一列举出该问题所有可能的解,并在列举的过程中,逐一检验每个可能解是否是问题的真正解。若是则采纳这个解;否则抛弃它。

编程要求

根据提示,在右侧编辑器编写代码,输出每种买法,及共几种买法。

测试说明

平台会对你编写的代码进行测试:

预期输出:

代码:


  
  1. ### 百钱百鸡 ###
  2. q= 0
  3. for i in range( 30):
  4. for x in range( 50):
  5. a=( 100- 5*i- 3*x)* 3
  6. if 100-i-x==a:
  7. print( '鸡翁的数量是{} 鸡母的数量是{} 鸡雏的数量是{}'. format(i,x,a))
  8. q=q+ 1
  9. print( '共有{}种买法'. format(q))

第2关:鸡兔同笼

任务描述

鸡兔同笼问题,是我国古代著名趣题之一。大约在1500年前,《孙子算经》中就记载了这个有趣的问题。书中是这样叙述的:“今有雉兔同笼,上有三十五头,下有九十四足,问雉兔各几何?” 这四句话的意思是:有若干只鸡兔同在一个笼子里,从上面数,有35个头;从下面数,有94只脚。求笼中各有几只鸡和兔?

本关任务:编写一个程序,能根据输入的鸡兔头数和脚数,计算鸡和兔子数。

编程要求

根据提示,在右侧编辑器补充代码,计算并输出鸡和兔子数。

测试说明

平台会对你编写的代码进行测试: 样例1 测试输入: 35 94 预期输出: 请输入总的头数 请输入总的脚数 鸡有23只 兔有12只

样例2: 测试输入: 51 31 预期输出: 请输入总的头数 请输入总的脚数 51只动物31条腿的情况无解


开始你的任务吧,祝你成功!

代码:


  
  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Thu Dec 10 08:19:29 2020
  4. 鸡兔同笼
  5. @author: Admin
  6. """
  7. print( "请输入总的头数")
  8. t = int( input())
  9. print( "请输入总的脚数")
  10. j = int( input())
  11. a= 0
  12. ### Begin ###
  13. if t<= 0 or j<= 0:
  14. print( '{}只动物{}条腿的情况无解'. format(t,j))
  15. else:
  16. for i in range(t+ 2):
  17. if j== 2*i+ 4*(t-i):
  18. a=i
  19. break
  20. if i==t+ 1:
  21. print( '{}只动物{}条腿的情况无解'. format(t,j))
  22. else:
  23. d=t-a
  24. print( '鸡有{}只 兔有{}只'. format(a,d))
  25. ### End ###

第3关:读心术

任务描述

猜数字游戏:请编码实现一款经典的猜数字游戏。玩家先随机在 1-1000之间给出一个数字,让AI猜,如果猜的数大了,提示“大了”,反之,则提示“小了”。直到AI猜中为止。

相关知识

二分法的核心:每次都将解的搜索空间大小缩小为原先的一半。 二分查找的基本思想(列表先已经有序)

  1. 在列表A的区间i, j中查找x,其中i, j为索引。
  2. 考察区间中间的元素的值,y=A[(i+j)//2],若x==y,算法结束;若x<y,则x必定位于原区间的左半边即[i,(i+j)//2-1];若x>y,则x必定位于原区间的右半边,即[(i+j)//2+1,j]
  3. 在新的区间(原区间一半大小)中继续查找。
  4. 重复2、3的步骤,区间不断缩小直到找到
  5. 若直到区间无效时(i>j),还没找到x,则x不在A中。

编程要求

根据提示,在右侧编辑器补充guess(x,low,high)函数代码。其中,x为要猜测的随机数,low为猜测范围的下界,high为上界。函数体中采用二分法猜测数据,如果二分法生成的数比要猜的数大,提示“大了”,并调整数据范围;如果小于要猜的数,提示“小了”,也调整数据范围。再重新猜数,直到猜中为止。函数需要返回猜测的次数。

测试说明

平台会调用评测函数对你编写的代码进行测试:

测试输入:590 预期输出: 小了 大了 大了 小了 大了 小了 小了 小了 大了 恭喜你猜中了,共猜了9次,猜中数是590


开始你的任务吧,祝你成功!

代码:


  
  1. def guess( x,low,high):
  2. '''AI猜数函数,猜测x的值
  3. low:数据x所在范围的下界
  4. high:数据x所在范围的上界
  5. 返回猜测的次数
  6. '''
  7. ### Begin ###
  8. a= 0
  9. while high-low> 0:
  10. m=(low+high)// 2
  11. if m>x:
  12. print( '大了')
  13. high=m- 1
  14. a=a+ 1
  15. elif m==x:
  16. break
  17. else:
  18. print( '小了')
  19. low=m+ 1
  20. a=a+ 1
  21. return a
  22. ### End ###


转载:https://blog.csdn.net/weixin_62174595/article/details/128347453
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场