【每日一题】备战冲击蓝桥杯国赛——Python程序设计 | Day10 | 平面切分 | 真题代码解析
今天是2020年省赛的最后一题,大家加油啊!~
每天刷一道题,话不多说,先刷近两年的题吧,从2020的开始,如果有一起的可以加入我们!!!
一起来刷题,冲击国赛!!!
2020年第十一届蓝桥杯赛题总览
2020年的题就是这些,类型分为两种,分别是结果填空和程序设计,我们每天刷一道题,省赛没问题!
平面切分(题目)
(本题总分:25分)
官方练习系统:https://www.lanqiao.cn/problems/505/learning/
—>【问题描述】
平面上有N条直线,其中第 条直线是 。
请计算这些直线将平面分成了几个部分。
—>【输入描述】
第一行包含一个整数 。
以下 行,每行包含两个整数 。
其中, 。
—>【输出描述】
输出一个整数,表示答案。
—>【输入输出样例】
输入:
3
1 1
2 2
3 3
输出:
6
解析
通过阅读题干,本题——难度中上:⭐⭐⭐⭐
考察类型:计算几何、思维
考察知识点:map(),max()
分析:
本道题其实算一道数学题,从输入输出描述来看,输入的是直线描述公式的a和b的值,我们可以简单的在草稿上绘制以下,如下:
由于是鼠标绘制,大家忍耐亿下下,三条直线将整个二维平面划分为了6个区间。
到这里我们大概理解了整个题目的意思,难点在于,我们如何将直线交叉的地方进行划分,最后得出划分的区域。思考一下!
算了,就不墨迹了。
我们从二元一次方程中可以得到的信息有限,是否可以看出某种规律来?在比赛的时候总不能手动去画吧。
面对N个二元一次方程,工科生第一想到的应该就是解方程。是否能够找到一个公共的交点,或者说多个交点呢。从示例的三个方程,一眼能看出有一个交点——(-1,0)。
我们再从一条直线到多条直线看看可以切分多少个平面:
- 1条直线——2平面
- 2条直线——2平面(重叠)、3平面(平行、无交点)、4平面(1个交点)
- 3条直线——2、3平面(重叠)、4平面(平行、无交点)、6平面(1交点、2交点)、7平面(3交点)
- 4条直线——2、3、4平面(重叠)、5平面(平行、无交点)、7平面(3交点,有两条线重叠)、8平面(3交点)、9平面(4交点)、10平面(4交点、5交点)
下面就不再列举了,从上面的列举我们可以看出一些规律法则。
- N条直线,可以切分出N种数量的平面,根据不同的切分方式,N条直线的N种数量平面可以有和无交点,但也要考虑重叠的时候。由此,我们可以根据有无交点的数量来判断N条直线的平面切分数。
- N条直线,我们知道A和B,首先计算出二元一次函数的交点数(这个不难),然后根据法则判断出交点数对应的切割平面数,即最终的结果。
法则:
- 加入平面的直线所分割的平面数:直线与之前直线不重复交点数+1
- 直线如果有重叠的,需要去除重叠的
- 与不同直线的相同交点只计算一次
下面直接开干!!!
代码
Python代码实现:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2022/3/4 15:19
# @Author : 府学路18号车神
# @Email :yurz_control@163.com
# @File : Day10.py
n = int(input("输入平面上直线的条数:"))
# 首先去除重叠的直线
lines = set(tuple(map(int, input("输入每条直线的A和B的值:").split())) for i in range(n))
n = len(lines)
new_lines = list(lines)
# 规则
def get_area(n, lines):
p = 2 # 设置判断条件,一条直线有两个平面
if n == 1: # 出口
return p
for x in range(1, n):
point = set()
for y in range(x):
# 当直线的斜率不同的时候才会出现交叉的时候(在本题中的A就是斜率K),由此我们计算不重复交点数
if lines[x][0] != lines[y][0]:
i = (lines[x][1]-lines[y][1])/(lines[y][0]-lines[x][0]) # 判断两直线是否存在交点
j = (lines[x][0]*lines[y][1]-lines[x][1]*lines[y][0])/(lines[x][0]-lines[y][0])
point.add((i, j))
p += len(point)+1 # 添加计算的不重复交点数
return p
print(get_area(n, new_lines))
示例1:
今天最后一题,稍有难度,加油!
由此,我们可以快速得出结果,验证完毕!
- 点赞
- 收藏
- 关注作者
评论(0)