鏁版嵁緇撴瀯絎簲绔犵畻娉曡璁￠[5]_璺ㄨ€冪綉

1錛庤緙栧啓瀹屾暣鐨勭▼搴忋€傚鏋滅煩闃?/span>A涓瓨鍦ㄨ繖鏍風(fēng)殑涓€涓厓绱?/span>A[i,j]婊¤凍鏉′歡:A[i,j]鏄i琛屼腑鍊兼渶灝忕殑鍏冪礌,涓斿張鏄j鍒椾腑鍊兼渶澶х殑鍏冪礌錛屽垯縐頒箣涓鴻鐭╅樀鐨勪竴涓┈闉嶇偣銆傝緙栫▼璁＄畻鍑?/span>m*n鐨勭煩闃?/span>A鐨勬墍鏈夐┈闉嶇偣銆?/span> 銆?a target="_blank">涓婃搗澶у 2000 涓?/span> 錛?/span>20鍒嗭級(jí)銆戙€愪腑縐戦櫌鑷姩鍖栨墍 1997銆?/span>

銆€銆€銆愬弬鑰冪瓟妗堛€?/span>

銆€銆€[棰樼洰鍒嗘瀽] 瀵繪壘椹瀺鐐規(guī)渶鐩存帴鐨勬柟娉?/span>,鏄湪涓€琛屼腑鎵懼嚭涓€涓渶灝忓€煎厓绱?/span>,鐒跺悗媯€(gè)鏌ヨ鍏冪礌鏄惁鏄厓绱犳墍鍦ㄥ垪鐨勬渶澶у厓绱?/span>,濡傛槸,鍒欒緭鍑轟竴涓┈闉嶇偣,鏃墮棿澶嶆潅搴︽槸O(m*(m+n)).鏈畻娉曚嬌鐢ㄤ袱涓緟鍔╂暟緇?/span>max鍜?/span>min,瀛樻斁姣忓垪涓渶澶у€煎厓绱犵殑琛屽彿鍜屾瘡琛屼腑鏈€灝忓€煎厓绱犵殑鍒楀彿,鏃墮棿澶嶆潅搴︿負(fù)O錛?/span>m*n+m錛夛紝浣嗘瘮杈冩鏁版瘮鍓嶇綆楁硶浼?xì)澧炲姞锛屼篃澶氫娇鐢ㄥ悜閲徑I洪棿銆?/span>

銆€銆€int m=10, n=10;

銆€銆€void Saddle(int A[m][n])

銆€銆€//A鏄?/span>m*n鐨勭煩闃?/span>,鏈畻娉曟眰鐭╅樀A涓殑椹瀺鐐?/span>.

銆€銆€{int max[n]={0}, //max鏁扮粍瀛樻斁鍚勫垪鏈€澶у€煎厓绱犵殑琛屽彿,鍒濆鍖栦負(fù)琛屽彿0;

銆€銆€min[m]={0}, //min鏁扮粍瀛樻斁鍚勮鏈€灝忓€煎厓绱犵殑鍒楀彿,鍒濆鍖栦負(fù)鍒楀彿0;

銆€銆€i, j;

銆€銆€for(i=0;i<m;i++) //閫夊悇琛屾渶灝忓€煎厓绱犲拰鍚勫垪鏈€澶у€煎厓绱?/span>.

銆€銆€for(j=0;j<n;j++)

銆€銆€{if(A[max[j]][j]<A[i][j]) max[j]=i; //淇敼絎?/span>j鍒楁渶澶у厓绱犵殑琛屽彿

銆€銆€if(A[i][min[i]]>A[i][j]) min[i]=j; //淇敼絎?/span>i琛屾渶灝忓厓绱犵殑鍒楀彿.

銆€銆€}

銆€銆€for (i=0;i<m;i++)

銆€銆€{j=min[i]; //絎?/span>i琛屾渶灝忓厓绱犵殑鍒楀彿

銆€銆€if(i==max[j])printf(鈥?/span>A[%d][%d]鏄┈闉嶇偣錛屽厓绱犲€兼槸%d鈥?/span>,i,j,A[i][j]); //鏄┈闉嶇偣

銆€銆€}

銆€銆€}// Saddle

銆€銆€[綆楁硶璁ㄨ] 浠ヤ笂綆楁硶鍋囧畾姣忚錛堝垪錛夋渶澶氬彧鏈変竴涓彲鑳界殑椹瀺鐐癸紝鑻ユ湁澶氫釜椹瀺鐐?/span>,鍥犱負(fù)涓€琛?/span>(鎴栦竴鍒?/span>)涓彲鑳界殑椹瀺鐐規(guī)暟鍊兼槸鐩稿悓鐨勶紝鍒欏彲鐢ㄤ簩緇存暟緇?/span>min2錛岀涓€緇存槸琛屽悜閲忥紝鏄悇琛岃鍙鳳紝絎簩緇存槸鍒楀悜閲忥紝瀛樻斁涓€琛屼腑鏈€澶у€肩殑鍒楀彿銆傚鏈€澶у€間篃鍚屾牱澶勭悊錛屼嬌鐢ㄥ彟涓€浜岀淮鏁扮粍max2錛岀涓€緇存槸鍒楀悜閲忥紝鏄悇鍒楀垪鍙鳳紝絎簩緇村瓨璇ュ垪鏈€澶у€煎厓绱犵殑琛屽彿銆傛渶鍚庣敤綾諱技涓婇潰鏂規(guī)硶錛屾壘鍑烘瘡琛?/span>(i)鏈€灝忓€煎厓绱犵殑姣忎釜鍒楀彿錛?/span>j錛夛紝鍐嶅埌max2鏁扮粍涓壘璇ュ垪鏄惁鏈夋渶澶у€煎厓绱犵殑琛屽彿錛?/span>i錛夛紝鑻ユ湁錛屽垯鏄┈闉嶇偣銆?/span>