錛?/strong>
鍒ゆ柇鐐筆鏄惁鍦ㄥ杈瑰艦涓槸璁$畻鍑犱綍涓竴涓潪甯稿熀鏈絾鏄崄鍒嗛噸瑕佺殑綆楁硶銆備互鐐筆涓虹鐐癸紝鍚戝乏鏂逛綔灝勭嚎L錛岀敱浜庡杈瑰艦鏄湁鐣岀殑錛屾墍浠ュ皠綰縇鐨勫乏绔竴瀹氬湪澶氳竟褰㈠錛岃冭檻娌跨潃L浠庢棤絀瘋繙澶勫紑濮嬭嚜宸﹀悜鍙崇Щ鍔紝閬囧埌鍜屽杈瑰艦鐨勭涓涓氦鐐圭殑鏃跺欙紝榪涘叆鍒頒簡澶氳竟褰㈢殑鍐呴儴錛岄亣鍒扮浜屼釜浜ょ偣鐨勬椂鍊欙紝紱誨紑浜嗗杈瑰艦錛?#8230;…鎵浠ュ緢瀹規槗鐪嬪嚭褰揕鍜屽杈瑰艦鐨勪氦鐐規暟鐩瓹鏄鏁扮殑鏃跺欙紝P鍦ㄥ杈瑰艦鍐咃紝鏄伓鏁扮殑璇漃鍦ㄥ杈瑰艦澶栥?/p>
浣嗘槸鏈変簺鐗規畩鎯呭喌瑕佸姞浠ヨ冭檻銆傚鍥句笅鍥?a)(b)(c)(d)鎵紺恒傚湪鍥?a)涓紝L鍜屽杈瑰艦鐨勯《鐐圭浉浜わ紝榪欐椂鍊欎氦鐐瑰彧鑳借綆椾竴涓紱鍦ㄥ浘(b)涓紝L鍜屽杈瑰艦欏剁偣鐨勪氦鐐逛笉搴旇璁$畻錛涘湪鍥?c)鍜?d) 涓紝L鍜屽杈瑰艦鐨勪竴鏉¤竟閲嶅悎錛岃繖鏉¤竟搴旇琚拷鐣ヤ笉璁°傚鏋淟鍜屽杈瑰艦鐨勪竴鏉¤竟閲嶅悎錛岃繖鏉¤竟搴旇琚拷鐣ヤ笉璁°?/p>
涓轟簡緇熶竴璧瘋錛屾垜浠湪璁$畻灝勭嚎L鍜屽杈瑰艦鐨勪氦鐐圭殑鏃跺欙紝1銆傚浜庡杈瑰艦鐨勬按騫寵竟涓嶄綔鑰冭檻錛?銆傚浜庡杈瑰艦鐨勯《鐐瑰拰L鐩鎬氦鐨勬儏鍐碉紝濡傛灉璇ラ《鐐規槸鍏舵墍灞炵殑杈逛笂綰靛潗鏍囪緝澶х殑欏剁偣錛屽垯璁℃暟錛屽惁鍒欏拷鐣ワ紱3銆傚浜嶱鍦ㄥ杈瑰艦杈逛笂鐨勬儏褰紝鐩存帴鍙垽鏂璓灞炰簬澶氳竟琛屻傜敱姝ゅ緱鍑虹畻娉曠殑浼唬鐮佸涓嬶細
count ← 0;
浠涓虹鐐癸紝浣滀粠鍙沖悜宸︾殑灝勭嚎L;
for 澶氳竟褰㈢殑姣忔潯杈箂
do if P鍦ㄨ竟s涓?nbsp;
then return true;
if s涓嶆槸姘村鉤鐨?
then if s鐨勪竴涓鐐瑰湪L涓?
if 璇ョ鐐規槸s涓ょ鐐逛腑綰靛潗鏍囪緝澶х殑绔偣
then count ← count+1
else if s鍜孡鐩鎬氦
then count ← count+1;
if count mod 2 = 1
then return true;
else return false;
鍏朵腑鍋氬皠綰縇鐨勬柟娉曟槸錛氳P'鐨勭旱鍧愭爣鍜孭鐩稿悓錛屾í鍧愭爣涓烘鏃犵┓澶э紙寰堝ぇ鐨勪竴涓鏁幫級錛屽垯P鍜孭'灝辯‘瀹氫簡灝勭嚎L銆?
鍒ゆ柇鐐規槸鍚﹀湪澶氳竟褰腑鐨勮繖涓畻娉曠殑鏃墮棿澶嶆潅搴︿負O(n)銆?/p>
鍙﹀榪樻湁涓縐嶇畻娉曟槸鐢ㄥ甫絎﹀彿鐨勪笁瑙掑艦闈㈢Н涔嬪拰涓庡杈瑰艦闈㈢Н榪涜姣旇緝錛岃繖縐嶇畻娉曠敱浜庝嬌鐢ㄦ誕鐐規暟榪愮畻鎵浠ヤ細甯︽潵涓瀹氳宸紝涓嶆帹鑽愬ぇ瀹朵嬌鐢ㄣ?
鍒ゆ柇綰挎鏄惁鍦ㄥ杈瑰艦鍐?/strong>錛?/strong>
綰挎鍦ㄥ杈瑰艦鍐呯殑涓涓繀瑕佹潯浠舵槸綰挎鐨勪袱涓鐐歸兘鍦ㄥ杈瑰艦鍐咃紝浣嗙敱浜庡杈瑰艦鍙兘涓哄嚬錛屾墍浠ヨ繖涓嶈兘鎴愪負鍒ゆ柇鐨勫厖鍒嗘潯浠躲傚鏋滅嚎孌靛拰澶氳竟褰㈢殑鏌愭潯杈瑰唴浜わ紙涓ょ嚎孌靛唴浜ゆ槸鎸囦袱綰挎鐩鎬氦涓斾氦鐐逛笉鍦ㄤ袱綰挎鐨勭鐐癸級錛屽洜涓哄杈瑰艦鐨勮竟鐨勫乏鍙充袱渚у垎灞炲杈瑰艦鍐呭涓嶅悓閮ㄥ垎錛屾墍浠ョ嚎孌典竴瀹氫細鏈変竴閮ㄥ垎鍦ㄥ杈瑰艦澶?瑙佸浘a)銆備簬鏄垜浠緱鍒扮嚎孌靛湪澶氳竟褰㈠唴鐨勭浜屼釜蹇呰鏉′歡錛氱嚎孌靛拰澶氳竟褰㈢殑鎵鏈夎竟閮戒笉鍐呬氦銆?
綰挎鍜屽杈瑰艦浜や簬綰挎鐨勪袱绔偣騫朵笉浼氬獎鍝嶇嚎孌墊槸鍚﹀湪澶氳竟褰㈠唴錛涗絾鏄鏋滃杈瑰艦鐨勬煇涓《鐐瑰拰綰挎鐩鎬氦錛岃繕蹇呴』鍒ゆ柇涓ょ浉閭諱氦鐐逛箣闂寸殑綰挎鏄惁鍖呭惈浜庡杈瑰艦鍐呴儴錛堝弽渚嬭鍥綽)銆?
鍥犳鎴戜滑鍙互鍏堟眰鍑烘墍鏈夊拰綰挎鐩鎬氦鐨勫杈瑰艦鐨勯《鐐癸紝鐒跺悗鎸夌収X-Y鍧愭爣鎺掑簭(X鍧愭爣灝忕殑鎺掑湪鍓嶉潰錛屽浜嶺鍧愭爣鐩稿悓鐨勭偣錛孻鍧愭爣灝忕殑鎺掑湪鍓嶉潰錛岃繖縐嶆帓搴忓噯鍒欎篃鏄負浜嗕繚璇佹按騫沖拰鍨傜洿鎯呭喌鐨勫垽鏂紜?錛岃繖鏍風浉閭葷殑涓や釜鐐瑰氨鏄湪綰挎涓婄浉閭葷殑涓や氦鐐癸紝濡傛灉浠繪剰鐩擱偦涓ょ偣鐨勪腑鐐逛篃鍦ㄥ杈瑰艦鍐咃紝鍒欒綰挎涓瀹氬湪澶氳竟褰㈠唴銆?
璇佹槑濡備笅錛?/p>
鍛介1錛?
濡傛灉綰挎鍜屽杈瑰艦鐨勪袱鐩擱偦浜ょ偣P1 錛孭2鐨勪腑鐐筆' 涔熷湪澶氳竟褰㈠唴錛屽垯P1, P2涔嬮棿鐨勬墍鏈夌偣閮藉湪澶氳竟褰㈠唴銆?/p>
璇佹槑錛?
鍋囪P1,P2涔嬮棿鍚湁涓嶅湪澶氳竟褰㈠唴鐨勭偣錛屼笉濡ㄨ璇ョ偣涓篞錛屽湪P1, P'涔嬮棿錛屽洜涓哄杈瑰艦鏄棴鍚堟洸綰匡紝鎵浠ュ叾鍐呭閮ㄤ箣闂存湁鐣岋紝鑰孭1灞炰簬澶氳竟琛屽唴閮紝Q灞炰簬澶氳竟鎬у閮紝P'灞炰簬澶氳竟鎬у唴閮紝P1-Q-P'瀹屽叏榪炵畫錛屾墍浠1Q鍜孮P'涓瀹氳法瓚婂杈瑰艦鐨勮竟鐣岋紝鍥犳鍦≒1,P'涔嬮棿鑷沖皯榪樻湁涓や釜璇ョ嚎孌靛拰澶氳竟褰㈢殑浜ょ偣錛岃繖鍜孭1P2鏄浉閭諱袱浜ょ偣鐭涚浘錛屾晠鍛介鎴愮珛銆傝瘉姣曘?
鐢卞懡棰?鐩存帴鍙緱鍑烘帹璁猴細
鎺ㄨ2錛?
璁懼杈瑰艦鍜岀嚎孌礟Q鐨勪氦鐐逛緷嬈′負P1,P2,……Pn錛屽叾涓璓i鍜孭i+1鏄浉閭諱袱浜ょ偣錛岀嚎孌礟Q鍦ㄥ杈瑰艦鍐呯殑鍏呰鏉′歡鏄細P錛孮鍦ㄥ杈瑰艦鍐呬笖瀵逛簬i =1, 2,……, n-1錛孭i ,Pi+1鐨勪腑鐐逛篃鍦ㄥ杈瑰艦鍐呫?
鍦ㄥ疄闄呯紪紼嬩腑錛屾病鏈夊繀瑕佽綆楁墍鏈夌殑浜ょ偣錛岄鍏堝簲鍒ゆ柇綰挎鍜屽杈瑰艦鐨勮竟鏄惁鍐呬氦錛屽樿嫢綰挎鍜屽杈瑰艦鐨勬煇鏉¤竟鍐呬氦鍒欑嚎孌典竴瀹氬湪澶氳竟褰㈠錛涘鏋滅嚎孌靛拰澶氳竟褰㈢殑姣忎竴鏉¤竟閮戒笉鍐呬氦錛屽垯綰挎鍜屽杈瑰艦鐨勪氦鐐逛竴瀹氭槸綰挎鐨勭鐐規垨鑰呭杈瑰艦鐨勯《鐐癸紝鍙鍒ゆ柇鐐規槸鍚﹀湪綰挎涓婂氨鍙互浜嗐?
鑷蟲鎴戜滑寰楀嚭綆楁硶濡備笅錛?
if 綰跨PQ鐨勭鐐逛笉閮藉湪澶氳竟褰㈠唴
then return false;
鐐歸泦pointSet鍒濆鍖栦負絀?
for 澶氳竟褰㈢殑姣忔潯杈箂
do if 綰挎鐨勬煇涓鐐瑰湪s涓?
then 灝嗚绔偣鍔犲叆pointSet;
else if s鐨勬煇涓鐐瑰湪綰挎PQ涓?
then 灝嗚绔偣鍔犲叆pointSet;
else if s鍜岀嚎孌礟Q鐩鎬氦 // 榪欐椂鍊欏凡緇忓彲浠ヨ偗瀹氭槸鍐呬氦浜?
then return false;
灝唒ointSet涓殑鐐規寜鐓-Y鍧愭爣鎺掑簭;
for pointSet涓瘡涓や釜鐩擱偦鐐?pointSet[i] , pointSet[ i+1]
do if pointSet[i] , pointSet[ i+1] 鐨勪腑鐐逛笉鍦ㄥ杈瑰艦涓?
then return false;
return true;
榪欎釜榪囩▼涓殑鎺掑簭鍥犱負浜ょ偣鏁扮洰鑲畾榪滃皬浜庡杈瑰艦鐨勯《鐐規暟鐩畁錛屾墍浠ユ渶澶氭槸甯告暟綰х殑澶嶆潅搴︼紝鍑犱箮鍙互蹇界暐涓嶈銆傚洜姝ょ畻娉曠殑鏃墮棿澶嶆潅搴︿篃鏄疧(n)銆?/p>
璁$畻綰挎鎴栫洿綰夸笌綰挎鐨勪氦鐐?/font>:
璁句竴鏉$嚎孌典負L0 = P1P2錛屽彟涓鏉$嚎孌墊垨鐩寸嚎涓篖1 = Q1Q2 錛岃璁$畻鐨勫氨鏄疞0鍜孡1鐨勪氦鐐廣?
1錛?棣栧厛鍒ゆ柇L0鍜孡1鏄惁鐩鎬氦錛堟柟娉曞凡鍦ㄥ墠鏂囪璁鴻繃錛夛紝濡傛灉涓嶇浉浜ゅ垯娌℃湁浜ょ偣錛屽惁鍒欒鏄嶭0鍜孡1涓瀹氭湁浜ょ偣錛屼笅闈㈠氨灝哃0鍜孡1閮界湅浣滅洿綰挎潵鑰冭檻銆?
2錛?濡傛灉P1鍜孭2妯潗鏍囩浉鍚岋紝鍗矻0騫寵浜嶻杞?
a) 鑻1涔熷鉤琛屼簬Y杞達紝
i. 鑻1鐨勭旱鍧愭爣鍜孮1鐨勭旱鍧愭爣鐩稿悓錛岃鏄嶭0鍜孡1鍏辯嚎錛屽亣濡侺1鏄洿綰跨殑璇濅粬浠湁鏃犵┓鐨勪氦鐐癸紝鍋囧L1鏄嚎孌電殑璇濆彲鐢?璁$畻涓ゆ潯鍏辯嚎綰挎鐨勪氦鐐?鐨勭畻娉曟眰浠栦滑鐨勪氦鐐癸紙璇ユ柟娉曞湪鍓嶆枃宸茶璁鴻繃錛夛紱
ii. 鍚﹀垯璇存槑L0鍜孡1騫寵錛屼粬浠病鏈変氦鐐癸紱
b) 鑻1涓嶅鉤琛屼簬Y杞達紝鍒欎氦鐐規í鍧愭爣涓篜1鐨勬í鍧愭爣錛屼唬鍏ュ埌L1鐨勭洿綰挎柟紼嬩腑鍙互璁$畻鍑轟氦鐐圭旱鍧愭爣錛?
3錛?濡傛灉P1鍜孭2妯潗鏍囦笉鍚岋紝浣嗘槸Q1鍜孮2妯潗鏍囩浉鍚岋紝鍗矻1騫寵浜嶻杞達紝鍒欎氦鐐規í鍧愭爣涓篞1鐨勬í鍧愭爣錛屼唬鍏ュ埌L0鐨勭洿綰挎柟紼嬩腑鍙互璁$畻鍑轟氦鐐圭旱鍧愭爣錛?
4錛?濡傛灉P1鍜孭2綰靛潗鏍囩浉鍚岋紝鍗矻0騫寵浜嶺杞?
a) 鑻1涔熷鉤琛屼簬X杞達紝
i. 鑻1鐨勬í鍧愭爣鍜孮1鐨勬í鍧愭爣鐩稿悓錛岃鏄嶭0鍜孡1鍏辯嚎錛屽亣濡侺1鏄洿綰跨殑璇濅粬浠湁鏃犵┓鐨勪氦鐐癸紝鍋囧L1鏄嚎孌電殑璇濆彲鐢?璁$畻涓ゆ潯鍏辯嚎綰挎鐨勪氦鐐?鐨勭畻娉曟眰浠栦滑鐨勪氦鐐癸紙璇ユ柟娉曞湪鍓嶆枃宸茶璁鴻繃錛夛紱
ii. 鍚﹀垯璇存槑L0鍜孡1騫寵錛屼粬浠病鏈変氦鐐癸紱
b) 鑻1涓嶅鉤琛屼簬X杞達紝鍒欎氦鐐圭旱鍧愭爣涓篜1鐨勭旱鍧愭爣錛屼唬鍏ュ埌L1鐨勭洿綰挎柟紼嬩腑鍙互璁$畻鍑轟氦鐐規í鍧愭爣錛?
5錛?濡傛灉P1鍜孭2綰靛潗鏍囦笉鍚岋紝浣嗘槸Q1鍜孮2綰靛潗鏍囩浉鍚岋紝鍗矻1騫寵浜嶺杞達紝鍒欎氦鐐圭旱鍧愭爣涓篞1鐨勭旱鍧愭爣錛屼唬鍏ュ埌L0鐨勭洿綰挎柟紼嬩腑鍙互璁$畻鍑轟氦鐐規í鍧愭爣錛?
6錛?鍓╀笅鐨勬儏鍐靛氨鏄疞1鍜孡0鐨勬枩鐜囧潎瀛樺湪涓斾笉涓?鐨勬儏鍐?
a) 璁$畻鍑篖0鐨勬枩鐜嘖0錛孡1鐨勬枩鐜嘖1 錛?
b) 濡傛灉K1 = K2
i. 濡傛灉Q1鍦↙0涓婏紝鍒欒鏄嶭0鍜孡1鍏辯嚎錛屽亣濡侺1鏄洿綰跨殑璇濇湁鏃犵┓浜ょ偣錛屽亣濡侺1鏄嚎孌電殑璇濆彲鐢?璁$畻涓ゆ潯鍏辯嚎綰挎鐨勪氦鐐?鐨勭畻娉曟眰浠栦滑鐨勪氦鐐癸紙璇ユ柟娉曞湪鍓嶆枃宸茶璁鴻繃錛夛紱
ii. 濡傛灉Q1涓嶅湪L0涓婏紝鍒欒鏄嶭0鍜孡1騫寵錛屼粬浠病鏈変氦鐐廣?
c) 鑱旂珛涓ょ洿綰跨殑鏂圭▼緇勫彲浠ヨВ鍑轟氦鐐規潵
榪欎釜綆楁硶騫朵笉澶嶆潅錛屼絾鏄鍒嗘儏鍐佃璁烘竻妤氾紝灝ゅ叾鏄綋涓ゆ潯綰挎鍏辯嚎鐨勬儏鍐甸渶瑕佸崟鐙冭檻錛屾墍浠ュ湪鍓嶆枃灝嗘眰涓ゆ潯鍏辯嚎綰挎鐨勭畻娉曞崟鐙啓鍑烘潵銆傚彟澶栵紝涓寮濮嬪氨鍏堝埄鐢ㄧ煝閲忓弶涔樺垽鏂嚎孌典笌綰挎錛堟垨鐩寸嚎錛夋槸鍚︾浉浜わ紝濡傛灉緇撴灉鏄浉浜わ紝閭d箞鍦ㄥ悗闈㈠氨鍙互灝嗙嚎孌靛叏閮ㄧ湅浣滅洿綰挎潵鑰冭檻銆傞渶瑕佹敞鎰忕殑鏄紝鎴戜滑鍙互灝嗙洿綰挎垨綰挎鏂圭▼鏀瑰啓涓篴x+by+c=0鐨勫艦寮忥紝榪欐牱涓鏉ヤ笂榪拌繃紼嬬殑閮ㄥ垎姝ラ鍙互鍚堝茍錛岀緝鐭簡浠g爜闀垮害錛屼絾鏄敱浜庡厛瑕佹眰鍑哄弬鏁幫紝榪欑綆楁硶灝嗚姳璐規洿澶氱殑鏃墮棿銆?
姹傜嚎孌墊垨鐩寸嚎涓庡渾鐨勪氦鐐?/font>:
璁懼渾蹇冧負O錛屽渾鍗婂緞涓簉錛岀洿綰匡紙鎴栫嚎孌碉級L涓婄殑涓ょ偣涓篜1,P2銆?
1. 濡傛灉L鏄嚎孌典笖P1錛孭2閮藉寘鍚湪鍦哋鍐咃紝鍒欐病鏈変氦鐐癸紱鍚﹀垯榪涜涓嬩竴姝ャ?
2. 濡傛灉L騫寵浜嶻杞達紝
a) 璁$畻鍦嗗績鍒癓鐨勮窛紱籨is錛?
b) 濡傛灉dis > r 鍒橪鍜屽渾娌℃湁浜ょ偣錛?
c) 鍒╃敤鍕捐偂瀹氱悊錛屽彲浠ユ眰鍑轟袱浜ょ偣鍧愭爣錛屼絾瑕佹敞鎰忚冭檻L鍜屽渾鐨勭浉鍒囨儏鍐點?
3. 濡傛灉L騫寵浜嶺杞達紝鍋氭硶涓嶭騫寵浜嶻杞寸殑鎯呭喌綾諱技錛?
4. 濡傛灉L鏃笉騫寵X杞翠篃涓嶅鉤琛孻杞達紝鍙互姹傚嚭L鐨勬枩鐜嘖錛岀劧鍚庡垪鍑篖鐨勭偣鏂滃紡鏂圭▼錛屽拰鍦嗘柟紼嬭仈绔嬪嵆鍙眰瑙e嚭L鍜屽渾鐨勪袱涓氦鐐癸紱
5. 濡傛灉L鏄嚎孌碉紝瀵逛簬2錛?錛?涓眰鍑虹殑浜ょ偣榪樿鍒嗗埆鍒ゆ柇鏄惁灞炰簬璇ョ嚎孌電殑鑼冨洿鍐呫?/p>

]]>