Objectives 学习目标
- To understand the potential applications of simulation as a way to solve real-world problems 理解模拟作为解决现实问题方法的潜在应用
- To understand and be able to apply top-down and spiral design techniques in writing complex programs 理解并能够应用自顶向下和螺旋设计技术来编写复杂程序
- To understand unit-testing and be able to apply this technique in the implementation and debugging of complex programming 理解单元测试并能够在复杂程序实现和调试中应用该技术
Computational Thinking 计算思维
Three Types of Thinking 三种思维方式
# 逻辑思维 - 数学推理
# A→B, B→C ⇒ A→C
def logical_thinking():
# 数学推导：如果A蕴含B，B蕴含C，那么A蕴含C
A_implies_B = True
B_implies_C = True
A_implies_C = A_implies_B and B_implies_C
return A_implies_C
# 实证思维 - 实验验证
def empirical_thinking():
# 物理实验：通过实验验证引力波存在
hypothesis = "gravitational_waves_exist"
experimental_evidence = True
conclusion = hypothesis if experimental_evidence else "need_more_research"
return conclusion
# 计算思维 - 设计与构建
def computational_thinking():
# 汉诺塔递归解决方案
def hanoi(n, source, target, auxiliary):
if n > 0:
# 将n-1个盘子从源移动到辅助
hanoi(n-1, source, auxiliary, target)
# 移动第n个盘子
print(f"Move disk {n} from {source} to {target}")
# 将n-1个盘子从辅助移动到目标
hanoi(n-1, auxiliary, target, source)
return hanoiComputational Thinking Process 计算思维过程
# 抽象与自动化
def computational_thinking_process(problem):
"""
计算思维过程：抽象问题的计算过程并使用计算机自动化解决方案
"""
# 1. 问题抽象
abstract_model = abstract_problem(problem)
# 2. 算法设计
algorithm = design_algorithm(abstract_model)
# 3. 自动化实现
solution = implement_automation(algorithm)
return solution
def abstract_problem(problem):
"""将现实问题抽象为计算模型"""
print(f"抽象问题: {problem}")
return "abstract_model"
def design_algorithm(model):
"""设计解决算法"""
print(f"为模型设计算法: {model}")
return "algorithm"
def implement_automation(algorithm):
"""实现自动化解决方案"""
print(f"实现算法自动化: {algorithm}")
return "automated_solution"Computational Thinking Examples 计算思维示例
Example 1: Sum from 1 to 100 示例1：计算1-100的和
# 数学思维：公式计算
def mathematical_sum(n=100):
return n * (n + 1) // 2
# 计算思维：模拟计算过程
def computational_sum(n=100):
total = 0
for i in range(1, n + 1):
total += i
return total
print(f"数学方法结果: {mathematical_sum()}") # 5050
print(f"计算方法结果: {computational_sum()}") # 5050Example 2: Calculate π 示例2：计算π
import random
import math
# 蒙特卡洛方法模拟计算π
def compute_pi_monte_carlo(num_points=1000000):
points_inside_circle = 0
for _ in range(num_points):
x = random.random() # 0-1之间的随机数
y = random.random()
# 检查点是否在单位圆内
if math.sqrt(x**2 + y**2) <= 1:
points_inside_circle += 1
# π ≈ 4 * (圆内点数 / 总点数)
return 4 * points_inside_circle / num_points
print(f"蒙特卡洛方法计算的π: {compute_pi_monte_carlo()}")
print(f"数学库中的π: {math.pi}")Example 3: Tower of Hanoi 示例3：汉诺塔
def tower_of_hanoi(n, source, target, auxiliary):
"""
汉诺塔问题解决方案
n: 盘子数量
source: 源柱子
target: 目标柱子
auxiliary: 辅助柱子
"""
if n == 1:
print(f"移动盘子 1 从 {source} 到 {target}")
return 1
moves = 0
# 将n-1个盘子从源移动到辅助
moves += tower_of_hanoi(n-1, source, auxiliary, target)
# 移动第n个盘子
print(f"移动盘子 {n} 从 {source} 到 {target}")
moves += 1
# 将n-1个盘子从辅助移动到目标
moves += tower_of_hanoi(n-1, auxiliary, target, source)
return moves
# 测试汉诺塔
total_moves = tower_of_hanoi(3, 'A', 'C', 'B')
print(f"总移动次数: {total_moves} (理论值: {2**3 - 1})")Design Frameworks 设计框架
Basic I-P-O Framework 基本I-P-O框架
def ipo_framework():
"""
输入-处理-输出框架
"""
# Input 输入
inputs = get_inputs()
# Process 处理
results = process_data(inputs)
# Output 输出
display_outputs(results)
return results
def get_inputs():
"""获取输入数据"""
data = input("请输入数据: ")
return data
def process_data(inputs):
"""处理数据"""
processed = inputs.upper() # 示例处理：转换为大写
return processed
def display_outputs(results):
"""显示输出结果"""
print(f"处理结果: {results}")Top-Down Design 自顶向下设计
Concept 概念
def top_down_design(complex_problem):
"""
自顶向下设计：将复杂问题分解为更小、更简单的问题
"""
# Level 1: 主要模块
modules = decompose_problem(complex_problem)
# Level 2: 子模块
submodules = []
for module in modules:
submodules.extend(decompose_module(module))
# Level 3: 基本操作
basic_operations = []
for submodule in submodules:
basic_operations.extend(implement_submodule(submodule))
# 组合解决方案
solution = combine_solutions(basic_operations)
return solution
def decompose_problem(problem):
"""分解复杂问题"""
print(f"分解问题: {problem}")
return ["module1", "module2", "module3"]
def decompose_module(module):
"""分解模块"""
print(f"分解模块: {module}")
return [f"{module}_sub1", f"{module}_sub2"]
def implement_submodule(submodule):
"""实现子模块"""
print(f"实现子模块: {submodule}")
return [f"{submodule}_op1", f"{submodule}_op2"]
def combine_solutions(operations):
"""组合解决方案"""
print("组合所有基本操作")
return "final_solution"Racquetball Simulation Example 壁球模拟示例
flowchart TD Main["main()"] PrintInfo["printInfo()"] GetInputs["getInputs()"] SimNGames["simNGames()"] PrintSummary["printSummary()"] SimOneGame["simOneGame()"] GameOver["GameOver()"] Main --> PrintInfo GetInputs -->|proA, proB, n| Main Main -->|proA, proB, n| SimNGames SimNGames -->|winsA, winsB| Main Main -->|winsA, winsB| PrintSummary SimNGames -->|proA, proB| SimOneGame SimOneGame -->|scoreA, scoreB| SimNGames SimOneGame -->|scoreA, scoreB| GameOver GameOver -->|"true|false"| SimOneGame
Top-Level Design 顶层设计
def main():
"""
壁球模拟主程序 - 顶层设计
"""
# 1. 打印介绍信息
print_intro()
# 2. 获取输入参数
probA, probB, n = get_inputs()
# 3. 模拟n场比赛
winsA, winsB = sim_n_games(n, probA, probB)
# 4. 打印结果摘要
print_summary(winsA, winsB)
def print_intro():
"""打印程序介绍"""
print("壁球比赛模拟器")
print("本程序模拟两名选手之间的多场壁球比赛")
print("选手能力用发球得分概率表示")
print("=" * 50)
def get_inputs():
"""获取用户输入"""
probA = float(input("选手A的发球得分概率: "))
probB = float(input("选手B的发球得分概率: "))
n = int(input("模拟比赛场次: "))
return probA, probB, n
def sim_n_games(n, probA, probB):
"""模拟n场比赛"""
winsA = 0
winsB = 0
for i in range(n):
scoreA, scoreB = sim_one_game(probA, probB)
if scoreA > scoreB:
winsA += 1
else:
winsB += 1
return winsA, winsB
def print_summary(winsA, winsB):
"""打印结果摘要"""
n = winsA + winsB
print("\n模拟结果摘要")
print("=" * 30)
print(f"总模拟场次: {n}")
print(f"选手A胜利: {winsA} ({winsA/n*100:.1f}%)")
print(f"选手B胜利: {winsB} ({winsB/n*100:.1f}%)")Second-Level Design 第二层设计
import random
def sim_one_game(probA, probB):
"""
模拟单场比赛
返回：选手A的分数，选手B的分数
"""
scoreA = 0
scoreB = 0
serving = "A" # A先发球
while not game_over(scoreA, scoreB):
if serving == "A":
if random.random() < probA:
# A发球得分
scoreA += 1
else:
# A发球失分，换B发球
serving = "B"
else:
if random.random() < probB:
# B发球得分
scoreB += 1
else:
# B发球失分，换A发球
serving = "A"
return scoreA, scoreB
def game_over(scoreA, scoreB):
"""
检查比赛是否结束
任意选手达到15分则比赛结束
"""
return scoreA == 15 or scoreB == 15Complete Implementation 完整实现
# racquetball_simulation.py
import random
def main():
print_intro()
probA, probB, n = get_inputs()
winsA, winsB = sim_n_games(n, probA, probB)
print_summary(winsA, winsB)
def print_intro():
print("壁球比赛模拟器")
print("比赛规则:")
print("- 选手A先发球")
print("- 发球方得分")
print("- 接球方得分时获得发球权")
print("- 先得15分者获胜")
print("=" * 40)
def get_inputs():
probA = float(input("选手A的发球得分概率 (0-1): "))
probB = float(input("选手B的发球得分概率 (0-1): "))
n = int(input("模拟比赛场次: "))
return probA, probB, n
def sim_n_games(n, probA, probB):
winsA = winsB = 0
for i in range(n):
scoreA, scoreB = sim_one_game(probA, probB)
if scoreA > scoreB:
winsA += 1
else:
winsB += 1
return winsA, winsB
def sim_one_game(probA, probB):
scoreA = scoreB = 0
serving = "A"
while not game_over(scoreA, scoreB):
if serving == "A":
if random.random() < probA:
scoreA += 1
else:
serving = "B"
else:
if random.random() < probB:
scoreB += 1
else:
serving = "A"
return scoreA, scoreB
def game_over(a, b):
return a == 15 or b == 15
def print_summary(winsA, winsB):
n = winsA + winsB
print("\n模拟结果:")
print(f"比赛总场次: {n}")
print(f"选手A胜场: {winsA} ({winsA/n*100:.1f}%)")
print(f"选手B胜场: {winsB} ({winsB/n*100:.1f}%)")
if __name__ == "__main__":
main()Unit Testing 单元测试
Concept and Implementation 概念与实现
# 单元测试框架示例
def unit_testing():
"""
单元测试：独立测试每个组件
"""
print("开始单元测试...")
# 测试 game_over 函数
test_game_over()
# 测试 sim_one_game 函数
test_sim_one_game()
# 测试其他函数...
print("所有测试完成!")
def test_game_over():
"""测试比赛结束条件"""
print("\n测试 game_over 函数:")
# 测试用例1: 比赛未结束
result1 = game_over(0, 0)
expected1 = False
print(f"game_over(0,0) = {result1}, 期望: {expected1} - {'通过' if result1 == expected1 else '失败'}")
# 测试用例2: A获胜
result2 = game_over(15, 10)
expected2 = True
print(f"game_over(15,10) = {result2}, 期望: {expected2} - {'通过' if result2 == expected2 else '失败'}")
# 测试用例3: B获胜
result3 = game_over(10, 15)
expected3 = True
print(f"game_over(10,15) = {result3}, 期望: {expected3} - {'通过' if result3 == expected3 else '失败'}")
def test_sim_one_game():
"""测试单场比赛模拟"""
print("\n测试 sim_one_game 函数:")
# 设置随机种子以确保可重复测试
random.seed(42)
# 测试平等选手
scoreA, scoreB = sim_one_game(0.5, 0.5)
print(f"平等选手比赛结果: A={scoreA}, B={scoreB}")
print(f"比赛是否有效: {game_over(scoreA, scoreB)}")
# 测试优势选手
scoreA, scoreB = sim_one_game(0.9, 0.1)
print(f"优势选手比赛结果: A={scoreA}, B={scoreB}")
print(f"A是否可能获胜: {scoreA == 15}")
# 交互式测试
def interactive_testing():
"""交互式测试组件"""
print("\n交互式测试模式")
while True:
print("\n选择测试函数:")
print("1. game_over")
print("2. sim_one_game")
print("3. 退出")
choice = input("请输入选择 (1-3): ")
if choice == "1":
a = int(input("输入选手A分数: "))
b = int(input("输入选手B分数: "))
result = game_over(a, b)
print(f"game_over({a}, {b}) = {result}")
elif choice == "2":
probA = float(input("输入选手A概率: "))
probB = float(input("输入选手B概率: "))
scoreA, scoreB = sim_one_game(probA, probB)
print(f"比赛结果: A={scoreA}, B={scoreB}")
elif choice == "3":
break
else:
print("无效选择，请重新输入")Spiral Development 螺旋开发
Concept 概念
def spiral_development():
"""
螺旋开发：从简单原型开始，逐步添加功能
"""
print("螺旋开发过程:")
# Phase 1: 基础原型
prototype_v1 = develop_prototype_v1()
test_prototype(prototype_v1)
# Phase 2: 添加概率参数
prototype_v2 = enhance_prototype_v2(prototype_v1)
test_prototype(prototype_v2)
# Phase 3: 完整比赛规则
prototype_v3 = enhance_prototype_v3(prototype_v2)
test_prototype(prototype_v3)
# Phase 4: 多场比赛
prototype_v4 = enhance_prototype_v4(prototype_v3)
test_prototype(prototype_v4)
# Phase 5: 完整程序
final_program = create_final_program(prototype_v4)
return final_program
def develop_prototype_v1():
"""阶段1: 基础原型 - 固定概率，固定回合"""
print("\n=== 阶段1: 基础原型 ===")
print("功能: 30个回合，固定50%概率")
def prototype_v1():
scoreA, scoreB = 0, 0
serving = "A"
for rally in range(30): # 固定30个回合
if serving == "A":
if random.random() < 0.5: # 固定50%概率
scoreA += 1
else:
serving = "B"
else:
if random.random() < 0.5:
scoreB += 1
else:
serving = "A"
print(f"回合 {rally+1}: A={scoreA}, B={scoreB}, 发球={serving}")
return scoreA, scoreB
return prototype_v1
def enhance_prototype_v2(previous_version):
"""阶段2: 添加概率参数"""
print("\n=== 阶段2: 可配置概率 ===")
print("增强: 支持不同的选手概率")
def prototype_v2(probA=0.5, probB=0.5):
scoreA, scoreB = 0, 0
serving = "A"
for rally in range(30):
if serving == "A":
if random.random() < probA:
scoreA += 1
else:
serving = "B"
else:
if random.random() < probB:
scoreB += 1
else:
serving = "A"
print(f"回合 {rally+1}: A={scoreA}, B={scoreB}")
return scoreA, scoreB
return prototype_v2
def enhance_prototype_v3(previous_version):
"""阶段3: 完整比赛规则"""
print("\n=== 阶段3: 完整比赛规则 ===")
print("增强: 比赛持续到有选手达到15分")
def prototype_v3(probA=0.5, probB=0.5):
scoreA, scoreB = 0, 0
serving = "A"
rally_count = 0
while not game_over(scoreA, scoreB):
rally_count += 1
if serving == "A":
if random.random() < probA:
scoreA += 1
else:
serving = "B"
else:
if random.random() < probB:
scoreB += 1
else:
serving = "A"
print(f"回合 {rally_count}: A={scoreA}, B={scoreB}")
print(f"比赛结束! 总回合数: {rally_count}")
return scoreA, scoreB
return prototype_v3
def enhance_prototype_v4(previous_version):
"""阶段4: 多场比赛支持"""
print("\n=== 阶段4: 多场比赛 ===")
print("增强: 支持模拟多场比赛并统计结果")
def prototype_v4(probA=0.5, probB=0.5, num_games=10):
winsA, winsB = 0, 0
for game in range(num_games):
print(f"\n=== 第 {game+1} 场比赛 ===")
scoreA, scoreB = previous_version(probA, probB)
if scoreA > scoreB:
winsA += 1
print("选手A获胜!")
else:
winsB += 1
print("选手B获胜!")
print(f"\n总战绩: A胜 {winsA}场, B胜 {winsB}场")
return winsA, winsB
return prototype_v4
def create_final_program(previous_version):
"""阶段5: 完整程序"""
print("\n=== 阶段5: 完整程序 ===")
print("增强: 添加用户交互和格式化输出")
def final_program():
print("壁球比赛模拟器 - 完整版")
# 获取用户输入
probA = float(input("选手A的发球得分概率: "))
probB = float(input("选手B的发球得分概率: "))
n = int(input("模拟比赛场次: "))
# 模拟比赛
winsA, winsB = previous_version(probA, probB, n)
# 格式化输出
print("\n" + "="*40)
print("模拟结果摘要")
print("="*40)
print(f"比赛总场次: {n}")
print(f"选手A胜利: {winsA} ({winsA/n*100:.1f}%)")
print(f"选手B胜利: {winsB} ({winsB/n*100:.1f}%)")
return winsA, winsB
return final_program
def test_prototype(prototype):
"""测试原型版本"""
print("测试原型...")
try:
result = prototype()
print(f"测试完成: {result}")
except Exception as e:
print(f"测试错误: {e}")Permanent Calendar Exercise 万年历练习
Top-Down Design 自顶向下设计
# permanent_calendar.py
def main():
"""
万年历主程序
"""
print("万年历程序")
print("=" * 30)
while True:
print("\n选择功能:")
print("1. 查询特定日期是星期几")
print("2. 显示某年某月的日历")
print("3. 显示某年的所有月份日历")
print("4. 退出程序")
choice = input("请输入选择 (1-4): ")
if choice == "1":
query_specific_day()
elif choice == "2":
print_month_calendar()
elif choice == "3":
print_year_calendar()
elif choice == "4":
print("感谢使用!")
break
else:
print("无效选择，请重新输入")
def query_specific_day():
"""查询特定日期是星期几"""
year, month, day = get_date_input()
weekday = get_weekday(year, month, day)
weekday_name = get_weekday_name(weekday)
print(f"{year}年{month}月{day}日是 {weekday_name}")
def print_month_calendar():
"""显示某年某月的日历"""
year, month, _ = get_date_input(rday=False)
display_month(year, month)
def print_year_calendar():
"""显示某年的所有月份日历"""
year = int(input("请输入年份: "))
for month in range(1, 13):
display_month(year, month)
print() # 月份之间空行
def get_date_input(rday=True):
"""获取日期输入"""
year = int(input("请输入年份: "))
month = int(input("请输入月份: "))
if rday:
day = int(input("请输入日期: "))
else:
day = None
return year, month, day
def get_weekday(year, month, day):
"""
计算给定日期是星期几
返回: 0=周日, 1=周一, ..., 6=周六
基准: 1900年1月1日是星期一
"""
total_days = 0
# 计算1900年到目标年份之前的总天数
for y in range(1900, year):
total_days += 366 if is_leap_year(y) else 365
# 计算目标年份中目标月份之前的总天数
month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if is_leap_year(year):
month_days[1] = 29 # 闰年2月29天
for m in range(1, month):
total_days += month_days[m-1]
# 加上目标月份的天数
total_days += day - 1
# 1900年1月1日是星期一 (weekday=1)
# 所以总天数+1对7取模得到星期几
return (total_days + 1) % 7
def is_leap_year(year):
"""判断是否为闰年"""
return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
def get_weekday_name(weekday):
"""获取星期几的名称"""
weekdays = ["星期日", "星期一", "星期二", "星期三", "星期四", "星期五", "星期六"]
return weekdays[weekday]
def display_month(year, month):
"""显示某年某月的日历"""
month_names = ["一月", "二月", "三月", "四月", "五月", "六月",
"七月", "八月", "九月", "十月", "十一月", "十二月"]
print(f"\n{year}年 {month_names[month-1]}")
print("日\t一\t二\t三\t四\t五\t六")
# 获取该月第一天是星期几
first_day_weekday = get_weekday(year, month, 1)
# 打印前置制表符
print("\t" * first_day_weekday, end="")
# 获取该月的天数
month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
if is_leap_year(year):
month_days[1] = 29
days_in_month = month_days[month-1]
# 打印日期
for day in range(1, days_in_month + 1):
print(f"{day:2d}", end="\t")
# 换行检查
if (first_day_weekday + day) % 7 == 0:
print()
print() # 最后换行
if __name__ == "__main__":
main()Summary 总结
Key Concepts 关键概念
-
Computational Thinking计算思维
- Abstract and automate problems 抽象并自动化问题
- Design computational solutions 设计计算解决方案
- Bridge between logic and implementation 连接逻辑与实现
-
Top-Down Design自顶向下设计
- Decompose complex problems 分解复杂问题
- Step-wise refinement 逐步细化
- Modular development 模块化开发
-
Simulation模拟
- Model real-world processes 建模现实世界过程
- Solve otherwise unobtainable problems 解决其他方法无法解决的问题
- Applications in various fields 多领域应用
-
Unit Testing单元测试
- Test components independently 独立测试组件
- Systematic debugging approach 系统化调试方法
- Ensure code reliability 确保代码可靠性
-
Spiral Development螺旋开发
- Start with simple prototypes 从简单原型开始
- Incremental enhancement 增量增强
- Complement to top-down design 对自顶向下设计的补充
Best Practices 最佳实践
- Use abstraction to manage complexity 使用抽象管理复杂性
- Apply step-wise refinement in design 在设计中应用逐步细化
- Test components systematically 系统化测试组件
- Choose appropriate development methodology 选择合适的开发方法
- Practice problem decomposition 练习问题分解