目錄
1. 問題描述
2. 解題分析
2.1 分割成兩組
2.2 N=5時的分割例
2.3 阻值計算例
2.4 演算法實作流程
3. 代碼及測驗
4. 后記
4.1 分割的洞見
4.2 另一種思路
1. 問題描述
我們在物理課上都學過“電阻”，通過把電阻串聯或者并聯可以使電阻值變大或者變小，電阻值分別為 R1、R2、R3的 3 個電阻串聯后，合成電阻的值為R1＋R2＋R3，同樣3個電阻并聯時，合成電阻的值則為“倒數之和的倒數”，如下圖所示：
現在假設有n個電阻值為1 ?的電阻，組合這些電阻，使總電阻值接近黃金分割比1.6180339887…，舉個例子，當 n ＝ 5 時，如果下圖這樣組合，則可以使電阻值為 1.6，
問題：求n=10時，在所有可能的電阻網路中，所得到的電阻中最接近黃金分割比的數值，精確到小數點后10位，
2. 解題分析
2.1 分割成兩組
本題解的最關鍵的insight是對于任何電阻網路，總是可以把它分割成兩個組，兩個組內部的拓撲結構任意，兩個組之間或串聯或并聯，然后，每個組又可以同樣繼續分割下去，因此本題可以用動態規劃的策略來解決，詳細分析程序如下，
2.2 N=5時的分割例
2.3 阻值計算例
以下為到N=4為止的筆算計算例，
2.4 演算法實作流程
3. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 15 07:13:17 2021
@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from typing import List
# from queue import Queue
# from collections import deque
import itertools as it
F = dict()
F[1] = {1}
golden_ratio = (math.sqrt(5) + 1)/2
def parallel(x,y):
return x*y/(x+y)
def findValueClosest2GoldenRatio(N):
for k in range(2,N+1):
valueSet = set()
for l in range(1,k//2+1):
g1_size = l
g2_size = k - l
for e1 in F[g1_size]:
for e2 in F[g2_size]:
valueSet.add(e1+e2)
valueSet.add(parallel(e1, e2))
F[k] = valueSet
# Find the value closest to golden ratio
valueWithMinDiff = 0
minDiff = golden_ratio
for v in F[N]:
diff = abs(v-golden_ratio)
if diff < minDiff:
minDiff = diff
valueWithMinDiff = v
return valueWithMinDiff, F[N]
N = 10
tStart = time.perf_counter()
valueWithMinDiff, valueSet = findValueClosest2GoldenRatio(N)
tCost = time.perf_counter() - tStart
print('golden_ratio={0:11.10f}, valueWithMinDiff={1:11.10f}, tCost= {2:6.3f}(sec)'.format(golden_ratio,valueWithMinDiff,tCost))
print('Totally there are {0} kinds value for N = {1} element circuit network'.format(len(valueSet),N))
運行結果：
golden_ratio=1.6180339887, valueWithMinDiff=1.6181818182, tCost= 0.003(sec)
Totally there are 3158 kinds value for N = 10 element circuit network
由以上結果還可以看出，在N=10時總共有3158中可能的電阻值，那可能的拓撲結構數至少不小于這個數，因為有些不同的拓撲結構的電阻值可能是相同的，
4. 后記
4.1 分割的洞見
這道題是到目前為止看完題目后覺得最沒有頭緒的題目，覺得無從下手，原書中給的提示沒看懂要說啥，即便做完了這道題目再回頭看依然沒有看懂要說啥，“偷看”了幾個網友的解答，也沒有看出什么頭緒（只上代碼很難說有什么參考意義，這種問題直接讀代碼很難讀懂），在程式員的演算法趣題：Q29 合成電阻的黃金分割比（Java版）_lanying100的博客-CSDN博客讀到“分割成兩組”的思路，一開始也沒有想明白，最后終于想明白了，覺得這個洞見確實妙極！想通了這一點后面就水到渠成了，最后，希望本文的解說能夠讓人更容易理解一些，
4.2 另一種思路
一開始我按照另外一種思路走，即把串聯和并聯看作是兩種運算子，再加上括號，這樣任何一種電路網路都可以表示為一個由若干個1為運算元，包含以上兩種運算子以及括號的“算術”運算式，遍歷所有可能的 “算術”運算式然后評估運算式的值即可，
但是在“遍歷所有可能的“算術運算式”這點上卡殼了，由于括號的位置拜訪的自由度很高，而且還存在深度嵌套的情況，對于這種非常“非結構性”的東西要遍歷沒有想到什么好辦法，暫時只好放棄了，但是覺得這個把問題轉變為算術運算式求值的思路還是不錯的，
上一篇：Q28: 社團活動的最優分配方案
下一篇：Q30: 插線板連接方式
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300436.html
標籤：其他