根據第一章節反激拓撲1—反激電路的由來最后演變而來的反激拓撲,將開關S更換為產品開發過程中常用的MOSFET
1、反激電源的分類,根據其電流的連續性分為CCM(連續工作模式)、CRM(臨界工作模式)、DCM(斷續工作模式)三種,根據我開關頻率f可以分為固定頻率模式和變頻模式
理想狀態下,CCM、CRM和DCM三種工作模式的驅動波形、MOSFET電壓Vds和原副邊電流波形如下:
記得剛開始接觸反激時,一直以為反激就是斷續模式,因為不管看原邊電流還是副邊電流,確實時斷續的,當了解了反激電源的演變過程,就發現不能只看其中一側的電流去判斷,區分三種模式最明顯的方法就是電流,CCM模式最容易識別,在開關管開通瞬間,原邊或者副邊的電流波形不為0即為連續模式,想要比較清楚的區分CRM和DCM模式,就需要同時把原副邊的電流波形測量出來進行對比了。
2、CCM工作模式分析
(CRM模式可以看做是勵磁電感直流分量電流為0時的CCM模式)CCM模式下,一個周期T=ton+toff
①在MOSFET導通過程中,即0-ton階段變壓器原邊繞組與輸入電源連接,原邊繞組儲存能量,且Vp=Vin,根據變壓器原理,其副邊繞組電壓Vs=Ns*Vin/Np,二極管D反向截止,Is=0根據Vin*△t=Lp*△Ip,△Ip=Vin*ton/Lp
②在MOSFET斷開過程中,即toff階段變壓器原邊工作結束,ton階段儲存在電感Lp中的能量通過副邊Ls進行釋放,Vs=Vd+Vout,根據變壓器的原理,在原邊繞組上會感生出一個電壓VOR=Np*Vs/Ns,該電壓通常被稱為反射電壓,而MOSFET所承受的電壓VDS=Vin+VOR
圖1 MOSFET導通過程
圖2 MOSFET斷開過程
②DCM模式分析DCM模式與CCM模式基本原理相同,差異在于DCM模式一個周期的時間T>ton+toff,T-(ton+toff)的時間段內,變壓器副邊電流Is=0,Vs=0,所以原邊繞組不存在反射電壓VOR,MOSFET的電壓VDS=Vin。以上分析均為理想條件下的分析,實際應用時,由于變壓器不可避免的存在漏感等寄生參數,會對實際的工作過程產生比較大的影響。
查看原文:https://www.dianyuan.com/eestar/article-8422.html
這是一個LED恒流電路板:
電路板上有燒毀的痕跡,最后再說燒毀的原因,現在咱們先不管。
復原其電路原理圖:
既然說是LED的恒流電路,它是怎樣實現恒流的呢?
為了直觀地演示它的“恒流”效果,請看以下的仿真動圖。
當用24V供電時:
流過LED的電流為:
當用12V供電時:
流過LED的電流為:
分別用24V和12V供電,電壓相差一倍,流過LED的電流大小卻差別不大,也就是電流基本“恒定”。
下面以12V供電為例,分析實現恒流的電路原理。
所謂知彼知己,百戰不殆,首先找出實現恒流時的已知條件:
后面就比較簡單了,從已知條件出發,推導出未知量即可。
1、從12V出發,每經過1個LED電壓降低2.1V,可以確定以下3個電路節點的電壓分別為9.9V、7.8V、5.7V:
2、從地GND出發,每經過一個三極管的發射極和基極,電壓上升0.7V:
這樣電路中所有節點的電壓都確定了:
能實現恒流,是因為電阻R4被三極管Q2的基極發射極(be極)鉗位為0.7V,流過它的電流也就固定為:
0.7V / R4 = 0.7V / 20ohm = 35mA
因為三極管的基極只流入很小的電流,所以可以忽略,于是這個35mA基本就是流過三極管Q1的電流,也基本就是流過LED燈的電流:
上述的理論分析跟仿真動圖展示的結果基本一致。
根據該電路恒流的原理,要改變恒流值,調整電阻R4的大小即可。
需要注意的是,三極管Q1的功耗是否過高。三極管的功耗Pc等于:
Vce * Ic
Vce為集電極與發射極的壓差。
Ic為集電極流過的電流。
對于SOT-23封裝的三極管來說:
其可承受的最大功耗是比較小的,這份數據手冊里寫的是200mW:
讀者朋友們可以自行計算一下,在24V供電情況下,Q1的功耗是否已經超出200mW。(光看不練,效果減半,大家可試著動動手)
提示:使用下圖紅色箭頭的數值進行計算即可。
另外,電阻R2是為了給三極管Q1提供基極電流通路,給三極管Q2提供集電極電流通路:
最后,前面有提到這個電路板實物有燒焦的痕跡,是什么原因呢,這篇文章里有詳細分析:《LED恒流電路批量在即,貼片電容幾率性炸開,大佬會診破案》(點擊前往)
查看原文:https://www.dianyuan.com/eestar/article-8424.html
1.前言
最近在工作中遇到了一個時鐘輻射(RE)超標的問題,前前后后經過差不多2周的時間,終于在這周五把問題解決了。解決的手段采用了三種:降低驅動電流;增加pF級別的電容;增加地搭接。
上述使用的三種方法,其實也是解決EMC問題常見的手法。本周周報將結合工作中遇到的EMC問題,把為什么要用這三種方法的原因和背后的原理進行分析,并分析產生這些問題的根本原因。
高速PCB的設計是高速電路中非常重要的環節,一般大廠的硬件和PCB是分開的,硬件工程師出原理圖和PCB設計指導書;考慮到DFX方面,在原理圖設計時,也會有EMC和射頻工程師的加入。
PCB工程師完成PCB設計后,會發給EMC工程師,射頻工程師,硬件工程師檢查。比較尷尬的是,原理圖是硬件工程師畫的,而EMC和射頻的東西又需要非常專業的理論作為指導。PCB工程師在完成Layout之后,如果EMC和射頻工程師沒有發現問題,硬件工程師估計也很難發現。但是,這個單板的負責人還是硬件。
因此,作為一名合適的單板硬件開發工程師來說,掌握基本的高速PCB設計規則還是非常有必要的。
2. EMC之輻射干擾
從下面整理EMC包含的內容可以看出,任何一款需要面向消費者的產品,僅僅在EMC方面的設計就要考慮這些問題。
雖然EMC工程師能幫我們在原理圖階段發現某些問題,但是他們經常需要一對多,不可能面面俱到。我們自身如果能掌握EMC基本的設計規則掌握,按照2/8定律來看,80%的產品也不會存在一些簡單的EMC設計缺陷。
項目中出現的時鐘超標的問題,是屬于EMC中的EMI當中的輻射干擾。在測試輻射干擾時,我們需要遵循國標。對于工業產品來說,輻射干擾必須小于 Class A 等級;對于民用產品來說,輻射干擾必須小于 Class B等級。考慮到實際產品使用的場合,最好能留有一定的裕量,不同的公司可能標準還不一樣。
測量輻射干擾所用的電波暗室如下。在測試時,先測量水平,再測量垂直,最后疊加的輻射就是總的輻射干擾。
圖片來源于網絡
上圖顯示的ClassA和ClassB是歐盟CISPR 22的標準中對ClassA和ClassB等級的要求。從圖中可以得到的信息是,同等頻率條件下,民用產品對RE的要求更苛刻。國標中也是一樣。ClassB等級更嚴格。
3. PCB之傳輸線
高速PCB設計中,按照傳輸線的結構,PCB上的走線可以分為微帶線和帶狀線。微帶線是指在PCB表層的走線。即我們設定的TOP層或者BOTTOM層,僅與一個參考層相鄰。如下圖所示。
帶狀線指在PCB內層的走線,即我們設定的除TOP和BOTTOM層的走線層,位于兩個參考層之間的走線。如下圖所示。
還有一種是嵌入式的微帶線,它是標準微帶線的改進型,區別在于導線的表面覆蓋了一層介質材料。如下圖所示。
微帶線和帶狀線的各自的特點如下:
(1)阻抗控制難易程度不一樣
微帶線一邊是空氣,一邊是PP固態樹脂,阻抗不好控制;帶狀線兩邊都是填充介質,阻抗可以更好的控制。
(2)走線速率不一樣
空氣的介電常數比PCB板材小,信號傳輸速率高。相比帶狀線,微帶線的傳輸速率略高,延時更小。
(3)抗輻射程度不一樣
微帶線由于一面直接與空氣接觸,容易產生對外的輻射;帶狀線在兩個參考層之間,能有效的屏蔽。
根據上述的特點可以看出,如果是走高速的時鐘信號,最好是走在內層,并且用地線進行包地處理,可以有效的降低對外的輻射。
4. 信號上升速率
高速數字電路的PCB設計中,當布線長度大于λ/20(λ波長)或信號延時超過1/6信號上升沿時,PCB上的布線可以被視為傳輸線。信號上升沿越陡,高頻分量越豐富,越容易出現信號完整性的問題。
下圖所示的信號,輸入信號和輸出信號上升沿斜率不一樣,高頻分量就會不一樣。
在PCB中需要關注的信號完整性問題主要是反射,串擾,輻射。
項目中遇到的EMC輻射超標問題,就歸屬于信號完整性中的輻射。出現問題后,特地的查看了PCB的走線,發現CLK在從第六層穿到第二層的時候,沒有放置地過孔,而且在穿層的旁邊還有其他的數據信號,因此可能還出現了串擾的問題。大概示意圖如下。
檢查到PCB上存在上面的問題后,進行了兩個方面的調整:
(1)降低時鐘輸出端的驅動能力,從12mA降低到4mA
(2)增加12pF的電容,原理圖設計時預留了電容工位
經過修改后再去測試EMC,輻射直接降了20dB,但是還是過不了ClassB。然而,從結果看兩個措施的效果還是比較明顯,其本質都是降低了信號上升沿的斜率。
信號從Drive出發,從第六層穿到第二層,再從第二層穿到第一層。時鐘信號在整個路徑中換了2次。穿層對高速的信號影響主要有兩個方面:
(1)過孔寄生電感和電容,阻抗發生突變,容易出現反射
(2)過孔是容性負載,會降低信號的速率,在時序設計時可能會因為延時導致接收到時序裕量不足。
(3)過孔處信號的參考層發生改變,導致回流路徑發生變化,從板材之間的寄生電容導致向外的輻射。
時鐘信號在第一層走線時,是參考的第二層,在第一次穿層時,回流路徑發生了改變,此時增加電源的過孔,可以引導CLK以電源屬性為參考平面,阻抗小(當然,這里也可以直接打孔到GND上)。在第二層走線時,以GND為參考層。因此,回流路徑在電源層和GND層發生了變化。
雖然電源和GND之間有很多去耦電容來降低電源的阻抗,但是寄生電容還是會存在(PCB板的固有屬性)。因此,在該層會因為阻抗回流路徑發生改變導致高頻信號通過寄生電容往外輻射。
這也是為什么項目中設備輻射超標的一個原因,穿層時沒有加過孔。回流路徑以相鄰的走線作為回流參考路徑,因此就發生了串擾。而降低驅動能力和增加電容,可以降低信號的邊沿上升速率,降低高頻有效頻率,既能夠降低串擾的程度,也能降低往外輻射的高頻能量。
5. 接地
將驅動和增加電容措施導入后,還是滿足不了EMC的要求。經過分析,發現設備在測試時,主設備和輻設備之間只使用一根FPC相連接,FPC上的地線數量比較少,推測應該是接地面積不夠大帶來的問題。
在解決EMC設計時,經常用到屏蔽,隔離,濾波,接地。其中接地在某種程度上來說,也是提供了一個良好的回路。
由于FPC線的地線比較少,高頻信號在回流時會有一部分通過設備和地之間的寄生電容作為回流路徑。這些寄生電容其實也是共模電流的返回路徑。如下所示。
于是就將主設備和輔設備放在了同一塊金屬板上,同時在主設備和輔設備之間增加了兩條較粗的金屬導線。如下所示。經過上面的措施后,再去測試EMC后,ClassB等級直接通過,還多出來了5dB的裕量。
至此,項目中遇到的問題得到了完美的解決,看似一個很簡單的輻射超標問題,但是從這個問題出發,還是有很多值得去挖掘的地方。
對上面的內容進行回顧,即知:時鐘信號驅動能力較強,信號上升沿斜率較高,導致時鐘高頻奇次諧波往外輻射,RE測試超標;主設備和輔設備的的接地較差,輔設備傳輸到主設備的時鐘靠寄生電容作為信號回流路徑,導致向外的輻射較大。
6.總結
高速PCB設計中SI是非常關鍵的一環,其中涉及到阻抗匹配,信號參考路徑,串擾,接地,過孔穿層等方面的問題。在設計的時候,要盡可能保證阻抗的一致性;盡可能保證回流面積最小;高速信號少穿層;走帶狀線和包地處理來降低敏感信號的輻射。通過這些手段來降低可能出現的EMC問題。
EMC的設計最好是在原理圖設計之初就進行考慮,或者直接讓EMC和射頻工程師參與原理圖的設計,避免等單板設計完出現問題之后再考慮如何整改。越是離產品發布的時間近,調整起來的成本就越高。
查看原文:https://www.dianyuan.com/eestar/article-8314.html
scp(Secure Copy Protocol)是一個用于在本地主機和遠程主機之間安全地復制文件或目錄的命令。它使用 SSH(Secure Shell)協議來進行安全的文件傳輸。以下是 scp 命令的基本用法和詳解:
1. 基本用法
scp [選項] [源文件或目錄] [目標主機:目標路徑]
2. 選項
3. 示例
從本地復制到遠程主機
scp localfile username@remote:/path/to/destination
從遠程主機復制到本地
scp username@remote:/path/to/file /local/path
遞歸復制整個目錄
scp -r localdir username@remote:/path/to/destination
指定非標準 SSH 端口
scp -P 2222 localfile username@remote:/path/to/destination
保留文件權限和時間
scp -p localfile username@remote:/path/to/destination
使用特定密鑰文件
scp -i keyfile.pem localfile username@remote:/path/to/destination
4. 使用 SSH 密鑰對身份驗證
scp 使用 SSH 協議進行安全傳輸,因此可以通過 SSH 密鑰對來進行身份驗證,而不必輸入密碼。確保公鑰已經被添加到目標主機的 ~/.ssh/authorized_keys 文件中。
5. 注意事項
6. 高級用法和示例
通過跳板主機(Jump Host)進行傳輸
有時候,需要通過一個跳板主機來連接目標主機。可以通過 -J 選項指定跳板主機:
scp -J jumpuser@jumphost:jumpfile user@remote:/path/to/destination
限制帶寬
可以使用 -l 選項限制傳輸的帶寬,例如限制為 100kbps:
scp -l 100 localfile username@remote:/path/to/destination
使用不同的 SSH 配置文件
如果有多個 SSH 配置文件,可以使用 -F 選項指定配置文件路徑:
scp -F /path/to/ssh/config localfile username@remote:/path/to/destination
傳輸時顯示進度
使用 -v 選項顯示詳細信息,而 -q 選項則關閉輸出。可以通過 --progress 選項顯示傳輸進度:
scp --progress localfile username@remote:/path/to/destination
7. 使用通配符
scp 支持通配符,可以使用通配符來傳輸多個文件:
scp localdir/*.txt username@remote:/path/to/destination
8. 使用壓縮
通過 -C 選項使用壓縮傳輸,可以減少網絡傳輸時間:
scp -C localfile username@remote:/path/to/destination
9. 使用代理跳板主機
如果通過 SOCKS 代理跳板主機,可以使用 -o 選項指定 ProxyJump 選項:
scp -o ProxyJump=proxyuser@proxyhost:proxyport localfile username@remote:/path/to/destination
總結
scp 提供了許多選項和功能,可以根據實際需求進行靈活配置。無論是簡單的文件傳輸還是復雜的跳板主機、限制帶寬、顯示進度等高級用法,scp 都是一個強大而實用的工具。詳細的選項和用法可以查閱 scp 的 man 手冊(man scp)。
查看原文:https://www.dianyuan.com/eestar/article-8426.html
更多精彩內容,盡在電子星球 APP(https://www.eestar.com/)
六篇技術文章,讓你秒懂電容的脾氣秉性
七篇DIY技術文章獻給你,讓你腦洞全開
五篇文章幫你開啟DSP的學習思路
匯總篇:關于PID知識,重點在此
016年10月,諾貝爾物理學獎授予 David J. Thouless、 F. Duncan M. Haldane 和 J.Michael Kosterlitz ,以表彰他們對“物質的拓撲相變和拓撲相的理論發現”。今天的文章是對這屆諾獎的一個回顧。
撰文 | 滿威寧(加州州立大學舊金山分校物理與天文系終身教授)
受邀寫一篇希望家長看后可以用來給孩子講解的(或中學生能勉強看懂的)關于今年諾貝爾物理學獎的介紹,這真不是一件容易的事。拓撲相變實在比細胞自噬體等要抽象復雜得多,很多人直呼“好幾個號稱說人話的版本還是看不懂。”那么請試試這篇,讓我們一點一點來了解它。相信你看完能對這個特別抽象深奧的領域多一層理解,對基礎科學多一層好奇和敬佩。
今年的諾貝爾物理學獎被授予美國華盛頓大學的索利斯(David J. Thouless)、普林斯頓大學的霍爾丹(F. Duncan M. Haldane)和布朗大學的科斯特利茲(J. Michael Kosterlitz),以表彰他們的“理論研究發現了物質的拓撲相變和拓撲相。”諾貝爾獎官網說:“他們打開了通往奇異狀態物質這一未知世界的大門。他們用高等數學方法研究不尋常的相、態、物質,比如超導體、超流體或薄磁膜。得益于他們的先驅性工作,對新型反常相物質的獵尋(hunt)開展起來了。很多人認為它們未來有望在材料科學和電子學上得以應用。”
眾所周知,純水可以有冰、水、水蒸氣三種狀態,也就是固體液體氣體三種相。融化沸騰結霜等都是相變。值得注意的是,相變意味著存在不連續的躍變。比如說固相和液相之間并沒有中間狀態。你可以把冰和水混合在一起,但在冰水混合物(包括碎冰沙飲品)里,固相液相仍是分離的(phase separation),不像酒精和水溶液成為融合的單相。小朋友可能會好奇那軟白甜的冰激凌,難道不是水在固液兩相之間的中間相?注意,冰激凌不是水,是混合了蛋白質、脂肪、冰晶、糖、液態水以及氣泡的典型軟凝聚態——凝聚態物理的另一個重要分支。
在不同的相里,分子原子整體遵循不同的規律做運動。比如,在固態晶體里,分子排成一個固定的點陣,像是操練立體方陣的士兵。在液態下,晶格瓦解,分子們卻還緊挨著,所以保持有限的體積,但有了流動性,失去了固定的形狀。等到了氣態,分子們各奔東西,不僅沒了固定形狀,體積也會充滿所在容器的整個空間。除了固液氣相,物質還可能有很多其他復雜的相,呈現出不尋常的特征,比如超導和超流,后面會解釋。
總而言之,不同的相是指同一個物質內的原子們,有不同的組織結構,對應于不同的物態。相與相之間的變化,是躍變的(存在不連續的物理量),而不是漸變的 (比如將一塊鐵的溫度慢慢升高)。
拓撲是topology 音譯的詞匯。拓撲學是數學的一個分支,主要研究在空間連續變化(比如拉伸和彎曲,但是不撕裂和粘合)的情況下維持不變的性質。
最著名的例子就是,一團橡皮泥可以捏成一個球或者一個碗,或者捏成諾獎發布會上,主持人手里的實心肉桂面包(不管怎樣做連續變化,這些形狀都是一回事:它們都沒有洞)。而被打穿了一個洞的橡皮泥,或者有一個把手的茶杯,以及主持人手里的圓圈面包,或者一個筒裙,在拓撲學上他們都是一回事,擁有同樣的不變性:一個洞。而穿了兩個洞的橡皮泥,就像那個八字形的堿水面包,還有你的長褲和短褲,都具有相同的拓撲不變性。除了洞的個數,還有別的特征數用來描述不同的拓撲特性。
請注意,拓撲性也是躍變的,不是漸變的。有個笑話說,當禪師說任何事物都有兩面,你可以把一張紙條擰一下然后兩頭反過來粘住,形成一個莫比烏斯環。在上面爬的螞蟻會發現它只有一面。可是如果禪師說事物都有整數面,那他就對了。同樣,拓撲描述里,可以有零個、一個、兩個或N個洞,但是不會有中間態1.5個或1.618個洞。掌紋指紋的奇異點(構成“籮斗”或“簸箕”)、打結的耳機線、椰子絨毛的漩(和你頭發的漩)無不要遵守拓撲學的描述。而且拓撲性必須看物質的整體而不是局部才能知曉。
拓撲的本質是在連續變化下的不變性。如果一根繩子上打了一個結,然后把這根繩子首尾相連,要去除這個繩結就只能把繩子割斷,拓撲性質也是如此的堅固。比如說,當空間發生連續變化(伸縮扭曲等),左圖的二維的波浪式運動可以被消除,而右圖轉圈的漩渦只能被扭曲或移動,因為拓撲結構獲得保護,漩渦不能被輕易地消除。后面會提到漩渦在二維拓撲相變里面的重要作用。
為了幫助理解后面的話題,我們先看看什么是電導率。想象一下你在一個管子(比如注射器)的一端施加壓力,兩端出現壓強差,管內的液體會朝低壓的方向流去,而流速流量不僅由壓強差、管道長度、管道粗細決定,還會與液體的粘滯阻力有關,就像水和蜂蜜的區別。同樣的,決定電流大小的,除了導線兩端的電壓差,材料的長短粗細,還有材料本身的導電性能(電導率)。比如金或者銅的電導率優于鋁。我們平時說的電阻率,是電導率的倒數。一般情況下,電阻來源于電荷在移動過程中遭遇的阻礙(與其余微觀粒子的頻繁碰撞),類似于粘滯阻力和摩擦力。于是很大一部分電能就被消耗成了熱能,所以你的手機會發熱而且沒用一天就要充電了。在三維導體和半導體中,電導率(電阻率)會隨溫度等狀態發生變化,一般這樣的變化是連續的,不是躍變的。
在特殊情況下,比如非常低溫的條件下,物質可能發生特殊的相變,突然完全喪失電阻(或者粘滯系數),變成超導體(或者超流體),于是電流不再產生熱量消耗電能(或超流液體在環形容器中無休止地流動下去)。
現在,我們再來試圖理解拓撲相變。
在低溫下,微觀粒子體現出量子力學的效應。而在薄層物質里,想象一下那些“運載”電流的電荷(或流體的分子),像螞蟻一樣被限制在桌面薄薄一層空間,只能做二維運動。那么他們中的一些有可能轉著圈形成漩渦。
如果本節后面的文字讀起來費勁,讀完這一段你就可以跳到下一節。簡短地說,今年的物理諾獎獎勵了下列幾個工作:
總的來說,他們的理論開創了把拓撲概念應用到凝聚態物理研究的領域,打開了通往豐富的拓撲物態世界的大門。
從前的理論認為超導或者超流不可能在薄層中發生。而上世紀七八十年代,David J. Thouless和J. Michael Kosterlitz 提出拓撲量子流體的理論,描述了在極低溫下薄層物質中的漩渦會順時針逆時針成對出現,互相補給電荷(或者補給流體),作為整體形成準長程有序的束縛態,伴隨超導或超流現象。在溫度升高后,這些成對的漩渦突然遠離,開始自由運動,破壞了超導或超流的長程位相有序性,導致物理性質突變。這個過程不同于普通的伴隨對稱性破缺(局部熱擾動破壞的各方向對稱性)的相變(比如結冰),而是由漩渦束縛態與自由態之間的轉變導致的,要用到拓撲的不連續性來描述和解釋,是拓撲相變的一種。已故前蘇聯科學家Berezinskii也獨立地提出了這一相變機理,但由于東西方冷戰而不為許多人知曉, 這一相變也被稱為是BKT相變。
另外一個啟發了科學家們去把拓撲性應用到物理里的一個重要現象,是在極低溫強磁場下薄層物質的霍爾電導率成臺階式整數倍變化,而不能連續變化,即整數量子霍爾效應。(1980年德國科學家 Klaus von Klitzing 發現整數量子霍爾效應,于1985年獲得諾貝爾物理學獎。)實驗所測得的霍爾電導率非常精確地嚴格等于一個物理常數的整數倍。這個物理常數是大家熟悉的基本電荷(一個電子的電量)的平方除以量子力學里的極小量普朗克常數。(霍爾電導率不同于普通的電導率,但也同樣是電流密度與電壓梯度的比值。)
為什么霍爾電導率會如此固執地取這一系列整數倍數值呢?David J. Thouless等人把整數量子霍爾效應與陳數的整數拓撲不變量聯系在了一起,用拓撲理論深刻解釋了二維電子層中的整數量子霍爾效應。陳數是以華人數學家陳省身命名的。在數學上,陳省身提出的陳類(Chern Class)及相關理論在微分幾何和代數拓撲學里面有舉足輕重的位置。
另外,1982年,美籍華裔物理學家崔琦(Daniel Chee Tsui)、美國物理學家施特默(Horst L. Stormer)等發現“分數量子霍爾效應”,不久由美國物理學家勞弗林(Rober B. Laughlin)給出理論解釋,三人共同獲得1998年諾貝爾物理學獎。
而今年的另一位得獎者,F. Duncan M. Haldane的理論計算在八十年代末第一個提出了與已知機理不同的,不需要外加磁場的量子霍爾效應。這一預言終于在2014年,被以薛其坤為首的清華大學和中科院物理所的研究團隊,用前所未有的磁性摻雜拓撲絕緣體在實驗上驗證。他的理論為現在非常活躍的拓撲絕緣體領域提供了前期基礎。他還用拓撲的概念研究一維的原子鏈,在八十年代年打破前人對一維原子鏈的認知,指出一串磁性原子的自旋常數決定了他們是否存在拓撲性。他近期的工作進一步升華了分數量子霍爾效應的理論。
這些研究的意義是什么,它們有什么用,這是大家很關心的問題。
我首先要強調的是,把非常抽象的拓撲學應用到凝聚態物理研究中,形成全套嶄新的理論,用以成功解釋物質的奇異性質和相變,并預言前所未有的拓撲相和新物態,就像拿三角函數來描述帶有方向的物理量(力和速度等矢量),拿微積分來描述漸進的物理過程,拿黎曼幾何來描述引力的本質是時空的扭曲從而創立的廣義相對論一樣,這些“異想天開”的開創性理論研究打開了一扇扇新學科的大門,是具有劃時代意義的。
拓撲激發態兩個重要特點,一是全局性,二是對局部擾動的穩定性,不受材料里面雜質等干擾。到今天對拓撲物態的研究成為一個內容豐富又飛速發展的領域, 更多的奇異拓撲相(包括一維、二維、三維)和拓撲相變被預言和發現。
比如1990年左右,華裔物理學家牛謙、文小剛等人的工作使我們理解了量子霍爾效應邊界的奇特拓撲性質。近十年來,包括傅亮、張首晟在內的科學家發現和預言了多種三維拓撲絕緣體。近八年來,顧正澄、文小剛,還有陳諧、劉正鑫揭示了 Haldane 磁性鏈的對稱保護的拓撲內涵。這些工作使拓撲物態吸引了更多的關注。
特別是量子霍爾態,其中和陳數相關的拓撲性質,導致了它的邊界是電阻為零的理想導體。電子在一個邊界上都有相同的運動方向,好似行駛在暢通無阻的高速公路,不再遭遇普通導體內類似于跑車沖進歌舞廳菜市場的電阻。這樣特別的的材料有望被用來解決電子產品發熱電能浪費的問題。
還有一種新型拓撲物態——帶非阿貝爾任意子的拓撲序,可能可以被用以實現量子計算機。總而言之,拓撲序拓撲物態在過去二十多年來主導了凝聚態物理的前沿研究,這些新型的拓撲材料和奇異性能,可能對下一代電子元件和量子計算機的發展有重要的潛在應用。
作為專業的物理科研人員,在這里我謹慎保守地措辭“可能”和“潛在應用”,因為這樣劃時代發現全新物態和物理機制的開拓性研究本身已經意義非常重大,無需再吹噓應用前景。類似地,一百年前愛因斯坦提出激光概念,五六十年前激光得以實現。那時候的人們完全想象不到激光的“潛在應用”有多么廣泛。在今天幾乎任何角落,從引力波探測、芯片制造,到普通電腦光盤、互聯網光纖,到哪怕超市里的掃條碼,都離不開激光——這種“一反常態”的具有單色、單向性、大功率、相干性等等的全新光源。
三位獲獎者是全新拓撲物態研究領域的理論先驅,在他們之前和之后的眾多的數學家、理論物理學家和實驗物理學家,都為這一領域的發展做出了卓越的貢獻。是他們對未知世界無法阻擋的好奇心、孜孜不倦的探索和極其敏銳的洞察力讓這一切成為可能。
作者簡介
滿威寧,博士,本科畢業于吉林大學少年班,博士畢業于普林斯頓大學物理系,在普林斯頓大學和紐約大學從事博士后工作。現任加州州立大學舊金山分校物理與天文系終身教授,從事軟凝聚態物理、準晶、光子能隙、無序材料及非線性光學的研究。
參考資料
[1] 諾獎官網公告
https://www.nobelprize.org/nobel_prizes/physics/laureates/2016/press.html
[2] Nature: Physics of 2D exotic matter wins Nobel.
http://www.nature.com/news/physics-of-2d-exotic-matter-wins-nobel-1.20722
[3] 果殼網:物理學獎:平面世界里的奇幻現象
http://www.guokr.com/article/441761/
[4] 拓撲為何
http://iscientists.baijia.baidu.com/article/342721
[5] 輕松理解凝聚態中的拓撲|諾獎深度解析 (之一)
http://www.weixinduba.com/n/348732
[6] 輕松理解凝聚態中的拓撲|諾獎深度解析 (之二)
http://mt.sohu.com/20161009/n469783911.shtml
[7] Physics Today: The QuantumSpin Hall Effect and Topological Insulators
http://scitation.aip.org/content/aip/magazine/physicstoday/article/63/1/10.1063/1.3293411
[8] https://i.ytimg.com/vi/9NlqYr6-TpA/maxresdefault.jpg
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單“精品專欄“,可查閱不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號,回復四位數組成的年份+月份,如“1903”,可獲取2019年3月的文章索引,以此類推。
《返樸》,科學家領航的好科普。國際著名物理學家文小剛與生物學家顏寧共同出任總編輯,與數十位不同領域一流學者組成的編委會一起,與你共同求索。關注《返樸》(微信號:fanpu2019)參與更多討論。二次轉載或合作請聯系fanpusci@163.com。
.在C++中,下面哪個關鍵字用于聲明一個變量,其值不能被修改? ( )
A. unsigned
B. const
C. static
D. mutable
【答案】B
【考點】考點: C++語法知識: 變量與常量
【解析】變量是存儲信息的容器,變量在計算機內有一個內存地址,里面放的內容即變量的值,變量是允許被修改,但是常量的值不允許被修改,常量的定義格式如下:
const 數據類型 常量名 = 常量值;
數據類型 const 常量名 = 常量值;
題目說其值不能被修改指的是常量,因此選擇 const 修飾,所以答案選擇 B。
2. 八進制數 12345670 和 07654321 的和為 ( )
A. 22222221
B. 21111111
C. 22111111
D. 22222211
【答案】D
【考點】進制轉換 (初賽集訓內容)
【解析】R 進制的運算逢 R 進一,題目是八進制加法,所以每一個進制位上的數字是逢 8 進一。
12345670
+ 07654321
--------------
22222211
3. 閱讀下述代碼,請問修改 data 的 value 成員以存儲 3.14,正確的方式是( )
union Data{
int num;
float value;
char symbol;
};
union Data data;
A. data.value = 3.14;
B. value.data = 3.14;
C. data->value = 3.14;
D. value->data = 3.14;
【答案】A
【考點】聯合體(NOI新大綱內容)
【解析】共用體定義格式:
union 共用體名{
成員列表
};
共用體的所有成員占用同一段內存,修改一個成員會影響其余所有成員。
共用體占用的內存等于最長的成員占用的內存。
共用體使用了內存覆蓋技術,同一時刻只能保存一個成員的值,如果對新的成員賦值,就會把原來成員的值覆蓋掉。
題目中 data 占用 4 個字節,修改 value 使用 . 運算符,-> 適用于指針。
4. 假設有一個鏈表的節點定義如下:
struct Node { int data; Node* next;};
現在有一個指向鏈表頭部的指針:Node* head。如果想要在鏈表中插入一個新節點,其成員 data 的值為 42,并使新節點成為鏈表的第一個節點,下面哪個操作是正確的? ( )
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;
【答案】A
【考點】鏈表的插入(數據結構)
【解析】題目使用頭插法即可
B. 賦值錯誤。
C. 新插入的結點的后繼未確認。
D. 表頭結點的后繼未指向新生成的結點。
5. 根節點的高度為 1,一根擁有 2023 個節點的三叉樹高度至少為 ( )
A. 6
B. 7
C. 8
D. 9
【答案】C
【考點】樹
【解析】觀察下圖
第 1 層有 1 個結點
第 2 層有 3 個結點
第 3 層有 27 個結點
......
第 n 層有 3n 個結點
根據性質知道是一個等比數列,公比為 3,根據等比數列求和公式:
計算過程如下:
6. 小明在某一天中依次有七個空閑時間段,他想要選出至少一個空閑時間段來練習唱歌,但他希望任意兩個練習的時間段之間都有至少兩個空閑的時間段讓他休息,則小明一共有( )種選擇時間段的方案。
A. 31
B. 18
C. 21
D. 33
【答案】B
【考點】枚舉法
【解析】枚舉的方法講解
① 只有一個練習時間段的情況
② 只有兩個練習時間段的情況
③ 只有三個練習時間段的情況
7. 以下關于高精度運算的說法錯誤的是( )
A. 高精度計算主要是用來處理大整數或需要保留多位小數的運算
B. 大整數除以小整數的處理的步驟可以是,將被除數和除數對齊,從左到右逐位嘗試將除數乘以某個數,通過減法得到新的被除數,并累加商
C. 高精度乘法的運算時間只與參與運算的兩個整數中長度較長者的位數有關。
D. 高精度加法運算的關鍵在于逐位相加并處理進位。
【答案】C
【考點】高精度運算
【解析】高精度乘法的時間取決于兩個大整數的長度的乘積有關,高精度乘低精度 O(n) 的時間復雜度,高精度乘高精度 O(n*n) 的時間復雜度。
8. 后綴表達式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”對應的中綴表達式是 ( )
A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
【答案】A
【考點】棧的應用
【解析】首先 6,2,3 入棧,遇到第一個操作符 +,彈出 2 和 3 執行加法,然后將 2 + 3 的結果入棧,遇到操作符 -,彈出兩個數 6 和 (2 + 3) 執行減法,然后將 (6 - (2 + 3)) 的結果入棧,3,8,2 依次入棧,遇到操作符 /,彈出 2 和 8 執行除法,然后將 8/2 入棧,遇到操作符 +,彈出 8/2 和 3 執行加法,然后將 (3 + 8/2) 入棧,遇到操作符 *,彈出 (6 - (2 + 3)) 和 (3 + 8/2) 執行乘法,然后將 (6-(2 + 3))*(3 + 8/2) 入棧,然后 2 入棧,遇到操作符 ^ 彈出 2 和 (6-(2 + 3))*(3 + 8/2) 執行異或操作,然后將 (6-(2 + 3))*(3 + 8/2)^2 入棧,然后 3 入棧,遇到操作符 +,然后彈出 3 和 (6-(2 + 3))*(3 + 8/2)^2 執行加法,然后將 (6-(2 + 3))*(3 + 8/2)^2 + 3 入棧,所以最終結果選 A。
9. 二進制數 101010 和 八進制數 166 的和為( )
A. 二進制數 10110000
B. 八進制數 236
C. 十進制數 158
D. 十六進制數 A0
【答案】D
【考點】進制轉換
【解析】先將二進制數和八進制數轉換成十進制
160 轉換成16進制是 A0,八進制是 240,二進制數是 10100000。
10. 假設有一組字符 {a,b,c,d,e,f},對應的頻率分別為 5%,9%,12%,13%,16%,45%。請問以下哪個選項是字符 a, b, c, d, e, f分別對應的一組哈夫曼編碼?( )
A. 1111,1110,101,100,110,0
B. 1010,1001,1000,011,010,00
C. 000,001,010,011,10,11
D. 1010,1011,110,111,00,01
【答案】A
【考點】哈夫曼編碼/霍夫曼編碼
【解析】記住要點: 霍夫曼編碼左 0 右 1,哈夫曼編碼的形態不唯一,但是 WPL 一定是唯一的,哈夫曼樹的形態如下:
哈夫曼樹的形態不唯一,但是結點到根節點的路徑的長度一定是唯一的,路徑的長度是唯一的所以 WPL 是唯一,備考北化刷王道數據結構以前刷到過類似的題目hhh。合并的策略一定是選擇 n 個結點中最小的兩個結點進行合并,然后再將合并的結果放入合并的集合中。B、C、D 選可以從路徑上排除,這個題比較好 。
11. 給定一棵二叉樹,其前序遍歷結果為:ABDECFG,中序遍歷結果為:DEBACFG。請問這棵樹的正確后序遍歷結果是什么?( )
A. EDBGFCA
B. EDGBFCA
C. DEBGFCA
D. DBEGFCA
【答案】A
【考點】樹的遍歷
【解析】前序遍歷順序: 根左右 中序遍歷順序: 左根右
后序遍歷: 左右根 ==> EDBGFCA。
12. 考慮一個有向無環圖,該圖包括4條有向邊:(1,2),(1,3),(2,4),和(3,4)。以下哪個選項是這個有向無環圖的一個有效的拓撲排序?( )
A. 4,2,3,1
B. 1,2,3,4
C. 1,2,4,3
D. 2,1,3,4
【答案】B
【考點】拓撲排序、有向圖
【解析】有向圖如下所示
拓撲排序: 度為 0 的點從圖中去掉。率先去掉 1 號點,(1,2),(1,3) 這兩條邊去掉,度為 0 的點是 2 和 3,可以是 2 這個點先去掉,也可以是 3 這個點去掉,最后去掉 4 這個點,所以拓撲序列是: 1, 2, 3, 4 或者 1, 3, 2, 4。
13. 在計算機中,以下哪個選項描述的數據存儲容量最小?( )
A. 字節(byte)
B. 比特(bit)
C. 字(word)
D. 千字節(kilobyte)
【答案】B
【考點】數據存儲
【解析】數據存儲的基本單位: 字節(Byte),數據的最小存儲單元: 比特(bit)。
1 Byte = 8 bit。
14. 一個班級有10個男生和12個女生。如果要選出一個3人的小組,并且小組中必須至少包含1個女生,那么有多少種可能的組合?( )
A. 1420
B. 1770
C. 1540
D. 2200
【答案】A
【考點】排列組合
【解析】
① 一個女生,2 個男生
② 兩個女生,1 個男生
③ 三個女生
最終方案數: 540 + 660 + 220 = 1420。
15. 以下哪個不是操作系統?( )
A. Linux
B. Windows
C. Android
D. HTML
【答案】D
【考點】操作系統
【解析】HTML 前端三劍客之一,超文本標記語言。
第二部分 程序閱讀
程序閱讀
程序閱讀 ①
01 #include<iostream>
02 #include<cmath>
03 using namespace std;
04
05 double f(double a,double b,double c){
06 double s=(a+b+c)/2;
07 return sqrt(s*(s-a)*(s-b)*(s-c));
08 }
09
10 int main(){
11 cout.flags(ios::fixed);
12 cout.precision(4);
13
14 int a,b,c;
15 cin>>a>>b>>c;
16 cout<<f(a,b,c)<<endl;
17 return 0;
18 }
假設輸入的所有數都為不超過1000的正整數,完成下面的判斷題和單選題:
16. (2分)當輸入為“2 2 2”時,輸出為“1.7321”( )
【答案】?
【解析】a = 2, b = 2, c = 2, s = 3, 計算結果如下
17. (2分)將第7行中的"(s-b)*(s-c)"改為"(s-c)*(s-b)"不會影響程序運行的結果( )
【答案】?
【解析】乘法交換率 = a*b = b*a,所以交換后結果并不會發送變化。
18. (2分)程序總是輸出四位小數( )
【答案】?
【解析】cou.precision(4): 保留四位小數輸出。
19. (3分)當輸入為“3 4 5”時,輸出為( )
A. 6.0000
B. 12.0000
C. 24.0000
D. 30.0000
【答案】A
【解析】a = 3, b = 4, c = 5, s = 6,根據海倫-秦九韶公式知代碼求三角形面積,根據 a, b, c 的關系得知是直角三角形,所以面積為 6,故選 A。
20. (3分)當輸入為“5 12 13”時,輸出為( )
A. 24.0000
B. 30.0000
C. 60.0000
D. 120.0000
【答案】B
【解析】a = 5, b = 12, c = 13,根據海倫-秦九韶公式知代碼求三角形面積,根據 a, b, c 的關系得知是直角三角形,所以面積為 30,故選 B。
點評: 第一道題送分題 12 分應該拿滿分,語法簡單題,未拿到滿分的同學應該好好進行自我反思為什么語法難度的閱讀題會丟分。
程序閱讀 ②
01 #include<iostream>
02 #include<vector>
03 #include<algorithm>
04 using namespace std;
05
06 int f(string x,string y){
07 int m=x.size();
08 int n=y.size();
09 vector<vector<int>>v(m+1,vector<int>(n+1,0));
10 for(int i=1;i<=m;i++){
11 for(int j=1;j<=n;j++){
12 if(x[i-1]==y[j-1]){
13 v[i][j]=v[i-1][j-1]+1;
14 }else{
15 v[i][j]=max(v[i-1][j],v[i][j-1]);
16 }
17 }
18 }
19 return v[m][n];
20 }
21
22 bool g(string x,string y){
23 if(x.size() != y.size()){
24 return false;
25 }
26 return f(x+x,y)==y.size();
27 }
28
29 int main(){
30 string x,y;
31 cin>>x>>y;
32 cout<<g(x,y)<<endl;
33 return 0;
34 }
21. (1.5分)f函數的返回值小于等于min(n,m)。( )
【答案】?
【解析】f 函數是一個典型的最長公共子序列模型,屬于動態規劃里面的內容
v[i][j]: 表示字符串 1 前 i 個字符和字符串 2 前 j 個字符,屬性值表示共有的子序列,狀態轉移方程如下
所以 f 函數最終的返回值應該小于等于兩個字符串中最小的那個長度。
22. (1.5分) f函數的返回值等于兩個輸入字符串的最長公共子串的長度。( )
【答案】?
【解析】子串: 要求連續; 子序列: 要求不連續,f 函數求的是最長公共子序列。
23. (1.5分)當輸入兩個完全相同的字符串時,g函數的返回值總是true( )
【答案】?
【解析】f 函數的返回值是字符串的長度,所以 f(x+x, y) = y.size() 是恒成立,所以 g 函數的返回值總是 true。
24. (3分)將第19行中的“v[m][n]”替換為“v[n][m]”,那么該程序( )
A. 行為不變
B. 只會改變輸出
C. 一定非正常退出
D. 可能非正常退出
【答案】D
【解析】當字符串 x 和 字符串 y 長度相等的情況情況不變,所以排除 B 和 C,當字符串 x 的長度大于或者小于字符串長度 y 導致數組越界訪問,可能導致程序異常終止。
25. (3分)當輸入為“csp-j p-jcs”時,輸出為: ( )
A. 0
B. 1
C. T
D. F
【答案】B
【解析】csp-jcsp-j p-jcs,f 函數的返回值是 5,和 p-jcs 長度相等,g 函數返回 true,bool 類型的輸出 true 自動轉化成 1。
26. (3分)當輸入為“csppsc spsccp”時,輸出為: ( )
A. T
B. F
C. 0
D. 1
【答案】D
【解析】csppsccsppsc spsccp,f 函數的返回值是 6,和 spsccp 長度相等,g 函數返回 true,bool 類型的輸出 true 自動轉化成 1。
點評: 第二道題 f 函數考察同學們對于動態規劃學習的檢驗。
程序閱讀 ③
01 #include <iostream>
02 #include <cmath>
03 using namespace std;
04
05 int solve1(int n){
06 return n*n;
07 }
08
09 int solve2(int n){
10 int sum=0;
11 for(int i=1;i<=sqrt(n);i++){
12 if(n%i==0){
13 if(n/i==i){
14 sum+=i*i;
15 }else{
16 sum+=i*i+(n/i)*(n/i);
17 }
18 }
19 }
20 return sum;
21 }
22
23 int main(){
24 int n;
25 cin>>n;
26 cout<<solve2(solve1(n))<<" "<<solve1((solve2(n)))<<endl;
27 return 0;
28 }
27. (1.5分)如果輸入的n為正整數,solve2函數的作用是計算n所有的因子的平方和 ( )
【答案】?
【解析】solve2 函數代碼解析如下:
28. (1.5分) 第13~14行的作用是避免n的平方根因子i(或n/i)進入第16行而被計算兩次 ( )
【答案】?
【解析】平方數 n 中出現 i 是 n 的因子時,必然 n/i 和 i 相同,同一個因子出現兩次但是計算只計算一次,所以該判斷題敘述正確。
29. (1.5分)如果輸入的n為質數,solve2(n)的返回值為n2+1 ( )
【答案】?
【解析】循環枚舉 i 是從 1 開始枚舉,質數的定義除了 1 和它本身外沒有其余的因子,所以 sum = n*n + 1*1,所以敘述正確。
30. (4分)如果輸入的n為質數 p 的平方,那么 solve2(n)的返回值為( )
A. p2+p+1
B. n2+n+1
C. n2+1
D. P4+2p2+1
【答案】B
【解析】n 的因子有 1, p, n,sum 統計的是 n*n + p*p + 1*1,題目說 n 是質數 p 的平方,那么 p*p = n,等價替換返回值等于 n*n + n + 1 或者 p*p*p*p + p*p + 1,兩個答案的變形都算正確,所以最終選 B。
31. (3分)當輸入為正整數時,第一項減去第二項的差值一定 ( )
A. 大于0
B. 大于等于0且不一定大于0
C. 小于0
D. 小于等于0且不一定小于0
【答案】D
【解析】特殊代值法排除,當 n 為 1 時 solve2(solve1(n))-solve1((solve2(n)))結果都為 0,因為模擬計算后發現都為 1,所以排除 A、C 兩個選項;代入一個值 n為 3 的情況,solve1(3) = 9,solve2(9) = 1*1 + 9*9 + 3*3 = 91,solve2(3) = 1*1 + 3*3 = 10,solve1(10) = 100,91 - 100 = -9,所以選 D,暑期集訓說過這種結論題一般代值大概率能找出正確答案,算是做題技巧。
32. (3分) 當輸入為“5”時,輸出為 ( )
A. 651 625
B. 650 729
C. 651 676
D. 652 625
【答案】C
【解析】solve1(5) = 25,solve2(25) = 1*1 + 5*5 + 25*25 = 651。
solve2(5) = 1*1 + 5*5 = 26,solve1(26) = 26*26 = 676。
點評: 數學知識因數分解。
第三部分 程序完善
程序完善
(1)(尋找被移除的元素)問題:原有長度為 n+1 公差為 1 等升數列,將數列輸到程序的數組時移除了一個元素,導致長度為 n 的開序數組可能不再連續,除非被移除的是第一個或最后之個元素。需要在數組不連續時,找出被移除的元素。試補全程序。
01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int find missing(vector<int>& nums){
07 int left = 0, right = nums.size() - 1;
08 while (left < right){
09 int mid = left + (right left) / 2;
10 if (nums[mid] = mid + ①){
11 ②;
12 }else{
13 ③
14 }
15 }
16 return ④;
17 }
18
19 int main(){
20 int n;
21 cin >> n;
22 vector<int> nums(n);
23 for (int i= 0; i< n; i++) cin >> nums[i];
24 int missing_number = find_missing(nums);
25 if_(missing_number == ⑤) {
26 cout << "Sequence is consecutive" << endl;
27 }else{
28 cout << "Missing number is " << ,missing numbeer << endl;
29 }
30 return 0;
31 }
二分適用條件: ① 區間單調性 ② 二分的答案滿足單調性
單調遞增區間查找 >= x 的最小值
int Find_L(int n, int num){ // n 表示 n 個數, num 查詢的數
int L = 0, R = n-1; // L:左端點, R:右端點
while(L < R){
int mid = (L+R)>>1; //中間點
if(a[mid] >= num) R = mid; //左子區間
else L = mid + 1; //右子區間
}
return L; //二分的 >= num 的最小值
}
單調遞增區間查找 <= x 的最大值
int Find_R(int n, int num){ //n:n個元素,num:查詢值
int L = 0, R = n - 1; //L:左端點 R:右端點
while(L < R){
int mid = (L + R + 1)/2; //中間點
if(a[mid] <= num) L = mid; //右區間
else R = mid - 1; //左區間
}
return R; // 二分 <= num 的最大值
}
33. ① 處應填( )
A. 1
B. nums[0]
C. right
D. left
【答案】B
【解析】等差數列公差 1 說明原序列具有連續性,連續必然滿足 nums[0] + mid == nums[mid],不連續 nums[mid] 必然大于 nums[0] + mid。
34. ②處應填( )
A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid
【答案】A
【解析】當 if 成立說明左區間連續,答案必然在右區間 [mid+1, right] ,通過不斷調整左指針 left 和右指針 right 來確定答案處于哪個區間,因此需要將 left 修改成 mid+1。
35. ③處應填( )
A. left=mid+1
B. right=mid-1
C. right=mid
D. left=mid
【答案】C
【解析】if 不成立答案處于左區間 [left, mid],只需要修改指針 right = mid。
36. ④處應填( )
A. left+nums[0]
B. right+nums[0]
C. mid+nums[0
D. right+1
【答案】A
【解析】返回的是被刪除的數,被刪除的數即不連續的位置 + 起始值。
37. ⑤處應填( )
A. nums[0]+n
B. nums[0]+n-1
C. nums[0]+n+1
D. nums[n-1]
【答案】D
【解析】如果 n 個數連續, left = right = n-1,返回的數必然是序列中的最后一個數,反之則返回的數即是被刪除的數。
這個題大多數認真學的同學都是滿分,注意認真學并不是說上課聽講,而是自己課后自己動手去模擬過二分的過程,聽老師講懂了和自己動手驗證老師上課講的內容記憶會更加深刻。
②(編輯距離) 給定兩個字符串,每次操作可以選擇刪除 (Delete)、插入 (Insert)、替換 (Replace),一個字符,求將第一個字符串轉換為第二個字符串所需要的最少操作次數。
1.#include <iostream>
2.#include <string>
3.#include <vector>
4.using namespace std;
5.
6.int min(int x,int y,int z){
7. return min(min(x,y),z);
8.}
9.
10.int edit_dist_dp(string str1,string str2){
11. int m=str1.length();
12. int n=str2.length();
13. vector<vector<int>> dp(m+1,vector<int>(n+1));
14.
15. for(int i=0;i<=m;i++){
16. for(int j=0;j<=n;j++){
17. if(i==0)
18. dp[i][j]= ①;
19. else if(j==0)
20. dp[i][j]= ②;
21. else if(③)
22. dp[i][j]= ④;
23. else
24. dp[i][j]=1+min(dp[i][j-1],min(dp[i-1][j],⑤));
25. }
26. }
27. return dp[m][n];
28.}
29.
30.int main(){
31. string str1,str2;
32. cin>>str1>>str2;
33. cout<<"Mininum number of operation:"
34. <<edit_dist_dp(str1,str2)<<endl;
35. return 0;
36.}
一、狀態表示:dp[i][j]
1. 集合:將 str1[1~i] 和 str2[1~j] 匹配的操作數量的集合
2. 屬性:最少操作次數
二、狀態計算:
1. 思想-----集合的劃分
2. 集合劃分依據:根據最后一步進行劃分
刪除操作:dp[i][0] = i;
插入操作:dp[0][i] = i;
3. 具體劃分為3類:
1. 增加:dp[i][j] = dp[i, j - 1] + 1
2. 刪除:dp[i][j] = dp[i - 1, j] + 1
3. 修改:dp[i][j] = dp[i - 1, j - 1] + 1 (str1[i] != str2[j])
4. 匹配:dp[i][j] = dp[i - 1][j - 1] (str1[i] == str2[j])
38. ① 處應填( )
A. j
B. i
C. m
D. n
【答案】A
【解析】第一個字符串長度為 0,第二個字符串長度為 j,將第一個字符串轉換成第二個字符串操作的次數是 j,這個操作是增加。
39. ② 處應填( )
A. j
B. i
C. m
D. n
【答案】B
【解析】第一個字符串長度為 i,第二個字符串長度為 0,將第一個字符串轉換成第二個字符串操作的次數是 i,這個是刪除操作。
40. ③處應填( )
A. str1[i-1]==str2[j-1]
B. str1[i]==str2[j]
C. str1[i-1]!=str2[j-1]
D. str1[i]!=str2[j]
【答案】A
【解析】匹配操作,第一個字符串和第二個字符串匹配。
41. ④處應填( )
A. dp[i-1][j-1]+1
B. dp[i-1][j-1]
C. dp[i-1][j]
D. dp[i][j-1]
【答案】B
【解析】匹配的情況不需要操作
42. ⑤處應填( )
A. dp[i][j] + 1
B. dp[i-1][j-1]+1
C. dp[i-1][j-1]
D. dp[i][j]
【答案】C
【解析】前 i-1 個字符與前 j 個字符最少操作次數、前 i 個字符與前 j-1 個字符最少操作次數、前 i-1 個字符與前 j-1 個字符最少操作三者取 min 后 + 1。
第四部分 總結
關于孩子是否適合走信奧這條路我的觀念依舊是能從中學到什么,對以后的學習生活有什么幫助,如果太看中成績,那么 99.9999% 的學生都是失敗者。
言歸正傳說一下考試試卷考點分析:
暑期集訓的內容沒有花太多的時間講動態規劃,因為想的是不太好挖空,主要太簡單,沒想到今年的題型比去年的簡單,對于系統學習的同學大部分都是 90 左右,這里的系統學習不是說考試出現的概率小就不考的誤區,程序閱讀沒學過動態規劃影響不大,暑期初賽集訓課后有認真思考的同學 65 左右。
學習建議:
① 戒驕戒躁,靜心學習
② 按照要求課后自覺上機練習(考場兩小時,課后兩三年功夫)
③ 戒掉功利主義的心態,如果只是為了保送清華北大建議放棄,打信奧能進清北,全力沖刺高考文化課妥妥也牛掰(破音)
④ 不要相信不勞而獲,很多宣傳主打一個就是夸張宣傳,比如跟著誰學零基礎包 CSP-J 獲獎(主打吹牛)、包 CSP-J 晉級(主打考級)
⑤ 系統學習
⑥ 職業規劃,未來規劃專業不讀計算機、不讀研、不選擇和互聯網相關行業打不打信奧都沒有什么關系
教學反思:
① 不講概率事件,也不會按著家長的要求去講機構的內容,不會再將整個競賽體系打亂,union 是 2023 新大綱的內容,認為考是一個小概率事件,但是確實是考了,動態規劃程序題小概率事件考了
② 將競賽體系進行順序的調整,考核不通過的學員不會講下一個階段的內容
③ 第一年參賽只能說去和已經獲獎的對手同臺競技,第一次比賽結束后續一定要好好學習,課后認真刷題(杜絕水題)
④ 和機構博弈的學員不帶,就是機構不開課,家長就說自己找了教練,教務必然會各種挽留家長(已經遇到過幾次,心累,沒有那個功夫和機構斗嘴皮子,您說的全對!每天笑哈哈,拒絕精神內耗)
⑤ 要想出成績不會再順著學員的心態數據削弱,完全掌握就是完全掌握,有些細節不注意錯就是錯,有則改之,無責加勉勵
*請認真填寫需求信息,我們會在24小時內與您取得聯系。