In [13]:
from sympy import *
import random
import matplotlib.pyplot as plt
x, y, z, a, b, c = var('x y z, a, b, c')
1. 排队接水¶
In [14]:
def cost(times):
wait_t, tot_t = 0, 0
for t in times:
tot_t += wait_t
wait_t += t
return tot_t / len(times)
cost([a, b, c])
Out[14]:
$\displaystyle \frac{2 a}{3} + \frac{b}{3}$
我们在什么情况下能通过交换 $a \to b$ 到 $b \to a$,改变总的打水时间?
In [15]:
cons = cost([x, y, a, b, c]) > cost([x, y, b, a, c])
cons
Out[15]:
$\displaystyle \frac{2 a}{5} + \frac{b}{5} + \frac{4 x}{5} + \frac{3 y}{5} > \frac{a}{5} + \frac{2 b}{5} + \frac{4 x}{5} + \frac{3 y}{5}$
让我们化简它!
In [16]:
simplify(cons)
Out[16]:
$\displaystyle a > b$
我们也可以尝试 “交换” 不相邻的两个同学:
In [17]:
simplify(cost([a, b, c, x, y]) > cost([a, x, c, b, y]))
Out[17]:
$\displaystyle b > x$
更有趣的是,我们可以尝试 “交换” 不止两个同学,例如以下是满足 “反序” 能使总代价最小的条件:
In [18]:
simplify(cost([a, b, c, x, y]) > cost([y, x, c, b, a]))
Out[18]:
$\displaystyle 2 a > - b + x + 2 y$
2. 拼数与排序¶
Verification (证明) v.s. Validation (测试):先直觉,再找证明。
In [19]:
fragments = [
'1', '2', '7', '8', '9', '88', '99', '888', '999'
]
def gen(n):
return ''.join(
random.choice(fragments) for _ in range(n)
)
def less(a, b):
return a + b < b + a
def check_reflexive(a):
assert not (a < a)
def check_antisymmetric(a, b):
if a != b:
assert (a < b) or (b < a)
def check_transitive(a, b, c):
if less(a, b) and less(b, c):
assert less(a, c)
for i in range(100000):
a = gen(random.randint(3, 5))
b = gen(random.randint(3, 5))
c = gen(random.randint(3, 5))
check_reflexive(a)
check_reflexive(b)
check_reflexive(c)
check_antisymmetric(a, b)
check_antisymmetric(a, c)
check_antisymmetric(b, c)
check_transitive(a, b, c)
print('Checked')
Checked
3. 区间与选择¶
和之前的例子不同
In [20]:
# ---------- GPT-4-turbo 生成的代码 (绘图 & 生成) ----------
def plot_intervals(intervals):
_, ax = plt.subplots(figsize=(6,2))
y, ymax = 0, 0 # Initial y position
plotted_intervals = [] # Keep track of plotted intervals to handle overlaps
ax.set_xticks([])
ax.set_yticks([])
for interval in intervals:
# Check for overlap and adjust y if necessary
overlap = True
while overlap:
overlap = False
for pi in plotted_intervals:
if not (interval[1] <= pi[0] or interval[0] >= pi[1]) and pi[2] == y:
y += 0.25 # Move up if there's an overlap
ymax = max(y, ymax)
overlap = True
break
# Plot the interval
ax.plot(interval, [y, y], marker='|', markersize=15)
plotted_intervals.append((interval[0], interval[1], y))
# Reset y if it was adjusted, for the next interval
if y != 0:
y = 0
# Set limits and labels
ax.set_ylim(-0.25, ymax + 0.25) # Adjust y limits to fit all intervals
plt.show()
def generate_intervals(n):
def generate_helper(numbers):
if not numbers:
return [[]]
intervals = []
# We skip the first number for the end point because an interval
# cannot have the same start and end point.
for i in range(1, len(numbers)):
# Choose the current number as the start point and numbers[i] as the end point
start, end = numbers[0], numbers[i]
# Generate all combinations for the remaining numbers
for rest in generate_helper(numbers[1:i] + numbers[i+1:]):
intervals.append([(start, end)] + rest)
return intervals
# Start with a list of numbers from 1 to 2n
numbers = list(range(1, 2 * n + 1))
n = 0
for intervals in generate_helper(numbers):
n += 1
plot_intervals(intervals)
print(f'{n} configurations generated.')
# ---------- GPT 生成的代码结束 ----------
In [21]:
generate_intervals(2)
3 configurations generated.
In [22]:
generate_intervals(3)
15 configurations generated.
4. 不显然的结论和更多的推导¶
这次,我们就不借助程序了,这个问题看起来就像是人为 “构造” 出来的。