2025年10月14日 星期二
最大化最小距離（牛棚放牛問題）
# 例題 ：
# 題目：
# 有 N 個牛棚位置（已排序），要放 K 頭牛，
# 希望「任意兩頭牛之間的最小距離」最大化。
# 輸入：
# ```
# 位置 = [1, 2, 8, 12, 17]
# K = 3
# ```
# 期望輸出：
# ```
# 最大化後的最小距離 = 7
# # 放在位置 1, 8, 17
# ```
# 思路：
# 設最小距離為 d，
# 若能成功放完 K 頭牛，代表 d 可行；
# 否則 d 太大，需縮小。
# 用二分搜尋尋找最大的可行距離。
def can_place(a, k, d):
count = 1
last = a[0]
for x in a[1:]:
if x-last >=d:
count+=1
last=x
if count==k:
return True
return False
def max_min_d(a, k):
a.sort()
lo,hi = 0,a[-1]-a[0]
while lo<=hi:
m = (lo+hi)//2
if can_place(a,k,m):
ans = m
lo = m+1
else:
hi = m-1
return ans
print(max_min_d([1, 2, 8, 12, 17], 3)) # 7
# 重點概念：
# 「距離越大越難放下」具有單調性 → 二分搜尋最大可行距離。
二分搜簡例
# 題目：
# 某公司每天能完成 x 單位工作量，共有 n 項工作要完成。
# 請問至少要幾天才能做完？
# 例如：
# 每天完成量 = 3
# 總量 = 17
# 則答案為 6 天（因為 3×5=15 <17，3×6=18 ≥17）。
# 思路：
# 天數越多 → 工作越可能完成，
# 這是一個「單調可行性」問題。
def min_days(w,ws):
lo,hi = 0,ws
ans = hi
while lo<=hi:
m = (lo+hi)//2
if m * w ==ws:
ans = m
return ans
elif m*w>ws:
ans = m
hi = m -1
else:
lo = m +1
return ans
print(min_days(3, 17)) # 6
print(min_days(5, 25)) # 5
print(min_days(15, 150)) # 10
print(min_days(105, 150000000000000000150000000000000))
# Output:
# 6
# 5
# 10
# 1428571428571428572857142857143
最小可能的「最大段和」-- 二分搜應用
題目（Problem）
給定一個長度為 n 的正整數陣列 A[0..n-1]，你要把它切成 恰好 k 段連續子陣列（k ≤ n）。定義每段的「段和」為該段元素總和。目標是最小化所有段和中的最大值。
必須保持原來順序、只能切割、段與段不可交錯（連續切段）。
回傳（或輸出）。
def can_split(A, k, cap):
"""在每段和 ≤ cap 的限制下，最少需要幾段；是否 ≤ k。"""
segments = 1
cur = 0
for x in A:
if cur + x <= cap:
cur += x
else:
segments += 1
cur = x
if segments > k: # 及早停止
return False
return True # 需要的段數 ≤ k
def minimize_largest_sum(A, k):
lo, hi = max(A), sum(A) # 下界：至少要容得下最大元素；上界：全部一段
ans = hi
while lo <= hi:
mid = (lo + hi) // 2
if can_split(A, k, mid): # mid 可行 → 嘗試更小
ans = mid
hi = mid - 1
else: # mid 不可行 → 增大容量
lo = mid + 1
return ans
A ,k = [7, 2, 5, 10, 8], 2
print(minimize_largest_sum(A, k))
A ,k = [7, 2, 5, 10, 8], 3
print(minimize_largest_sum(A, k))
# Output:
# 18
# 14
最小可能的「最大段和」暴力解
題目（Problem）
給定一個長度為 n 的正整數陣列 A[0..n-1]，你要把它切成 恰好 k 段連續子陣列（k ≤ n）。定義每段的「段和」為該段元素總和。目標是最小化所有段和中的最大值。
必須保持原來順序、只能切割、段與段不可交錯（連續切段）。
回傳（或輸出）最小可能的「最大段和」。
例子
A = [7, 2, 5, 10, 8], k = 2
最佳切法是 [7, 2, 5] | [10, 8]，兩段和分別為 14 與 18，最大為 18；證明不存在更小的可能，答案是 18。
a = [7, 2, 5, 10, 8]
k = 2
minmax = float('inf')
for i in range(0,5-1):
left = a[:i+1]
right = a[i+1:]
print(left,right)
if max(sum(left),sum(right))
二分搜應用簡例-求根號2
lo,hi = 0,2
m = (lo+hi)/2
while abs(m*m-2)>0.0000001:
if m*m > 2:
hi = m
else:
lo = m
m = (lo+hi)/2
print(m)
# Output:
# 1.4142135381698608
2025年10月7日 星期二
適合初學者的暴力法-背包
import itertools
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
vmax = 0
smax = []
for s in range(len(weights)+1):
for c in itertools.combinations(weights, s):
if sum(c)<=capacity:
# print(c)
v = 0
for j in c:
v =v+ values[weights.index(j)]
# print(v)
if v > vmax:
vmax = v
smax = c
print(vmax,smax)
# Output:
# 10 (3, 5)
2025年9月17日 星期三
使用深津式 框架 Prompt 範例
提示詞: #Instructions 你是一位英文老師，負責解釋文法並設計練習題。 #Constraints 文章限制 200 字 使用繁體中文 每個例句附上翻譯 #Input 主題：被動語態（Passive Voice）的用法 #Output 簡單定義 三個例句（英文 + 中文翻譯） 兩題練習題（附答案） AI輸出的示範結果 簡單定義 被動語態（Passive Voice）強調「動作的接受者」。 句型結構為：主詞 + be 動詞 + 過去分詞 (p.p.) + (by + 動作者)。 若動作者不重要，可省略 by 片語。 例句 The homework was finished by Tom.（這份作業被湯姆完成了。） English is spoken in many countries.（英文在許多國家被使用。） The window has been broken.（這扇窗戶已經被打破了。） 練習題 改寫成被動語態：The teacher teaches math. 答案：Math is taught by the teacher. 翻譯成英文：這本書是昨天出版的。 答案：The book was published yesterday.
訂閱：
意見 (Atom)