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

1. 璁句簩緇存暟緇?/span>a[1..m, 1..n] 鍚湁m*n 涓暣鏁般€?/span>

銆€銆€(1) 鍐欏嚭綆楁硶(pascal榪囩▼鎴?/span>c鍑芥暟)錛氬垽鏂?/span>a涓墍鏈夊厓绱犳槸鍚︿簰涓嶇浉鍚岃緭鍑虹浉鍏充俊鎭?/span>(yes/no)錛?/span>

銆€銆€(2) 璇曞垎鏋愮畻娉曠殑鏃墮棿澶嶆潅搴︺€傘€愬崕涓悊宸ュぇ瀛?/span> 1999 浜?/span> 錛?/span>10鍒嗭級銆?/span>

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

銆€銆€[棰樼洰鍒嗘瀽]鍒ゆ柇浜岀淮鏁扮粍涓厓绱犳槸鍚︿簰涓嶇浉鍚岋紝鍙湁閫愪釜姣旇緝,鎵懼埌涓€瀵圭浉絳夌殑鍏冪礌錛屽氨鍙粨璁轟負涓嶆槸浜掍笉鐩稿悓銆傚浣曡揪鍒版瘡涓厓绱犲悓鍏跺畠鍏冪礌姣旇緝涓€嬈′笖鍙竴嬈★紵鍦ㄥ綋鍓嶈錛屾瘡涓厓绱犺鍚屾湰琛屽悗闈㈢殑鍏冪礌姣旇緝涓€嬈★紙涓嬮潰絎竴涓驚鐜帶鍒跺彉閲?/span>p鐨?/span>for寰幆錛夛紝鐒跺悗鍚岀i+1琛屽強浠ュ悗鍚勮鍏冪礌姣旇緝涓€嬈★紝榪欏氨鏄驚鐜帶鍒跺彉閲?/span>k鍜?/span>p鐨勪簩灞?/span>for寰幆銆?/span>

銆€銆€int JudgEqual(ing a[m][n],int m,n)

銆€銆€//鍒ゆ柇浜岀淮鏁扮粍涓墍鏈夊厓绱犳槸鍚︿簰涓嶇浉鍚岋紝濡傛槸錛岃繑鍥?/span>1錛涘惁鍒欙紝榪斿洖0銆?/span>

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

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

銆€銆€{ for(p=j+1;p<n;p++) //鍜屽悓琛屽叾瀹冨厓绱犳瘮杈?/span>

銆€銆€if(a[i][j]==a[i][p]) {printf(鈥?/span>no鈥?/span>); return(0); }

銆€銆€//鍙鏈変竴涓浉鍚岀殑錛屽氨緇撹涓嶆槸浜掍笉鐩稿悓

銆€銆€for(k=i+1;k<m;k++) //鍜岀i+1琛屽強浠ュ悗鍏冪礌姣旇緝

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

銆€銆€if(a[i][j]==a[k][p]) {printf(鈥?/span>no鈥?/span>); return(0); }

銆€銆€}// for(j=0;j<n-1;j++)

銆€銆€printf(yes鈥?/span>); return(1); //鍏冪礌浜掍笉鐩稿悓

銆€銆€}//綆楁硶JudgEqual緇撴潫

銆€銆€錛?/span>2錛変簩緇存暟緇勪腑鐨勬瘡涓€涓厓绱犲悓鍏跺畠鍏冪礌閮芥瘮杈冧竴嬈★紝鏁扮粍涓叡m*n涓厓绱狅紝絎?/span>1涓厓绱犲悓鍏跺畠m*n-1涓厓绱犳瘮杈冿紝絎?/span>2涓厓绱犲悓鍏跺畠m*n-2 涓厓绱犳瘮杈冿紝鈥︹€︼紝絎?/span>m*n-1涓厓绱犲悓鏈€鍚庝竴涓厓绱?/span>(m*n)姣旇緝涓€嬈?/span>,鎵€浠ュ湪鍏冪礌浜掍笉鐩哥瓑鏃舵€葷殑姣旇緝嬈℃暟涓?/span> (m*n-1)+(m*n-2)+鈥?/span>+2+1=錛?/span>m*n錛?/span>(m*n-1)/2銆傚湪鏈夌浉鍚屽厓绱犳椂,鍙兘絎竴嬈℃瘮杈冨氨鐩稿悓,涔熷彲鑳芥渶鍚庝竴嬈℃瘮杈冩椂鐩稿悓,璁懼湪(m*n-1)涓綅緗笂鍧囧彲鑳界浉鍚?/span>,榪欐椂鐨勫鉤鍧囨瘮杈冩鏁扮害涓猴紙m*n錛?/span>(m*n-1)/4錛屾€葷殑鏃墮棿澶嶆潅搴︽槸O(n4)銆?/span>