袋鼠数学一题多解 | 遍历算法的优化

上海小升初
上海小升初 这家伙很懒,还没有设置简介

0 人点赞了该文章 · 116 浏览







今天选 3 个由易到难得任务,继续讨论如何提高算法效率。
3个任务都是想办法缩小计算的规模,换言之,降低无效的计算次数!
首先,要有缩小计算规模的思路,需要培养磨练;
其次,从数学角度论证缩小计算规模,但不会漏掉正确输出;
最后,编程技巧开始发挥作用;到这一步可以放心地选择与👆思路匹配的数据结构和算法,不必考虑算法的完备性。下面从容易的任务开始:
1、完全平方数引申问题
整数64是第一个所有数字都是偶数的整数,而且是一个完全平方数字。第二个是400,第三个是484 ... ...

已知是给出序列中在[a,b]范围内的数字(两个值是左右边界都包括在内),a和b总是正整数,并且 a < b。

例如100到1000之间的偶数方阵:[400,484] 

输出应该是排序的 1000到4000之间的偶数方阵:[] 

随机测试的特点:

测试次数=167

a的最大值=1e10  #大数对算法的效率提出要求

b的最大值=1e12  #大数对算法的效率提出要求

def even_digit_squares(a, b):
    # 时间复杂度考虑
    # 遍历的长度缩小
    ans = []
    for n in range(int(a**0.5)+1,int(b**0.5)+1):
        if all([int(i)%2==0 for i in str(n**2)]):
            ans.append(n**2)
    return ans

2、中等难度 棋盘挑战—算法优化

编写一个函数,该函数需要一个参数,代表棋盘的尺寸。棋盘总是方形的,所以5意味着你需要一个5x5的棋盘。

图片

深色方块将用unicode白色方块表示,而浅色方块将用unicode黑色方块表示。保持行列都满足黑白相间,即没有同色的方块挨在一起共一条边;
它应该返回一个棋盘的字符串,每个方格之间有一个空格,并考虑到新的线条。
偶数应该返回一个以深色方块开始的棋盘。奇数应该返回一个以浅色方块开始的棋盘。CASE 测试用例:
输入:5
输出:
■ □ ■ □ ■
□ ■ □ ■ □
■ □ ■ □ ■
□ ■ □ ■ □
■ □ ■ □ ■

每行末尾不应有尾部的白色空间,也不应有字符串末尾的新行字符。

备注方块是字符,■是\u25A0和 □是\u25A1

不要使用HTML实体的方块(例如□代表白色方块),因为代码不认为它是有效的方块。检查的一个好方法是你的解决方案是否在本地终端上打印出了正确的棋盘。编码愉快!!
3、较难的自恋数任务来自七年级袋鼠数学

下面的 3任务适合编程和数学挑战一题两解

- 在学习立方体数分享Srinivasa Ramanujan和数字1729的故事。
- 使用帕斯卡尔三角形的模式,质数、倍数、2的幂、三角形数字

- 分享苏菲-杰曼所表现出的对抗困难的决心,苏菲-杰曼质数

- 在学习幂数时使用自恋的数字 153, 370 , 371, 407, 1634, 8208, 9474, 54748, ...),也称Armstrong数,按着下面的规则反复,在有限的次数内即陷入循环,重复自己,不可自拔 图片 ——自恋数的来由?

图片

自恋数

详细解法见链接👉 为什么要用set?

图片

python的集合 set 充分发挥去重复的威力,极大的降低了运算次数!

同时,不该放弃如何运用数论知识判别自恋数?

附录1.  参考七年级的袋鼠math课程提纲

1. 使用正整数幂和相关的实根 l l l
2. 应用包括括号在内的运算顺序 l l
3. 小数和分数之间的转换 l l
4. 把一个量写成另一个量的分数或百分比 l
5. 使用乘法推理来解释百分比的变化 l l
6. 理解如何用分数和混合数进行乘法运算 l l
7. 检查使用逆运算的计算结果 l l
8. 在各种情况下选择和使用检查策略 l
9. 通过收集同类项来简化和处理表达式 l
10. 通过将单项乘以括号来简化和处理表达式 l
11. 将数字代入公式 l l
12. 解决一个未知数的线性方程 l
13. 计算长方体和正方体的表面积 l l
- 学生了解到约翰-纳皮尔发明了小数点
- 学生完成玛雅人的乘法拼图
- 在介绍重要数字时,探讨了杰夫-贝佐斯的财富和以秒为单位的增长。
- 学生们发现,等号是由威尔士数学家罗伯特-雷科德发明的。
- 在探索更简单的多面体和欧拉公式时,使用了阿基米德实体。
- 在代入公式时,使用戈德堡多面体在相邻单位之间建立联系
- 在处理比率问题时使用条形模型
- 学生在处理线性序列时探索增长模式
- 让学生了解长度(以及质量和容量)的简要历史
- 学生在学习百分比的过程中,了解了英国退税的一些特点。
- 在用分数除法时,提出了 "不除法 "的例子
- 在Al Khwarizmi的代数活动中分享代数的起源
- 向学生展示库里三角的悖论
- 探讨赫伦的三角形面积的替代公式
- 学生了解到,苏格兰工程师威廉-普莱菲尔发明了柱状图和饼状图。

- 学生发现弗洛伦斯-南丁格尔其实是一位统计学家

图片

附录2  推荐袋鼠数学学习工具软件
让STEM主题变得生动
您可以通过添加照片和图像以及将函数与自然现象进行拟合,使数学变得更加相关和令人兴奋。

无论是通过五点拟合四边形来寻找拱门的方程,还是弹丸的轨迹,或者建筑的几何特征,使用Autograph都可以快速而轻松地将数学带入生活。
https://autograph.completemaths.com/

图片

图片

图片

图片

图片

图片


图片



发布于 2024-03-20 19:46

免责声明:

本文由 上海小升初 原创发布于 家长帮 ,著作权归作者所有。

登录一下,更多精彩内容等你发现,贡献精彩回答,参与评论互动

登录! 还没有账号?去注册

暂无评论

广告
All Rights Reserved Powered BY WeCenter V4.1.0 © 2025 京ICP备20005761号-2