【正文】 。 return 1。 } 折半法 (二分法 )查數 對已排 序數據序列 (小到大或大到小 )的查找 算法： 值區(qū)間不斷折半縮小，直到找到要查的數 例 a[9]={1,2,3,6,8,9,10,12,14} 0 1 2 3 4 5 6 7 8 要求查 x=2 a的有值區(qū)間 0~8 折半 (0+8)/2=4 a[4]=8 不是 a的區(qū)間分為 0~3 5~8 判別有值區(qū)間 0~3 a的有值區(qū)間 0~3 折半 (0+3)/2=1 a[1]=2=x 是 折半法流程 輸入數組 a 輸入 x top=0, mid=0 bot=N1 xa[bot]||xa[top] top=bot mid=(top+bot)/2 x==a[mid] xa[mid] break bot=mid1 top=mid+1 x==a[mid] 輸出 mid,x 打印無此數 1 0 1 1 1 1 0 0 0 0 a[0]~a[N1]:小到大排序 x:為查找的數 top:查找區(qū)間下標下界 bot:查找區(qū)間下標上界 mid:查找區(qū)間折半下標 define N 10 include void main() {int a[N],top=0,bot=N1,mid=0,x,i。 for(i=0。iN。i++) scanf(%d,amp。a[i])。 scanf(%d,amp。x)。 if(x=a[0]amp。amp。x=a[N1]) while(top=bot) {mid=(top+bot)/2。 if(x==a[mid]) break。 else if(xa[mid]) bot=mid1。 else top=mid+1。 } if(x==a[mid]) printf(a[%d]=%d\n, mid,a[mid])。 else printf(no number)。 } ?輸入一個字符串 str，再輸入一個字符 c，將字符串 str 中出現的所有字符 c 刪除。 include void main() {char c,str[80]。 int i,j=0。 gets(str)。 scanf(%c, amp。c)。 for(i=0。str[i]!=0。i++) if(str[i]!=c) {str[j]=str[i]。j++。} str[j]=39。\039。 puts(str)。 } ?在字符串中找子字符串 。 如子字符串存在 , 輸出 YES。 否則 , 輸出 NO. include main() {char s[100],c[20]。 int i,j,flag。 gets(s)。gets(c)。 for(i=0。s[i]!=39。\039。i++) {flag=1。 for(j=0。c[j]!=39。\039。j++) if(s[i+j]!=c[j]){flag=0。break。} if(flag) break。 } if(flag) printf(YES\n)。 else printf(NO\n)。 } abcdefghy efg 又如 ,計算一個字符串中子字符串出現的次數。 include void main() {int i, n=1,m。 scanf(%d,amp。m)。 for(i=m1。i=1。i) n=(n+1)*2。 printf(%d,n)。 } ?猴子吃桃問題。猴子第一天搞下若干個桃子 ,當即吃了一半 ,還不過癮 ,又多吃了一個。第二天又將剩下的桃子吃掉一半 ,又多吃一個。以后每天都吃了前一天剩下的一半零一個。到 m天只剩一個桃子了。問共摘多少個挑子 ? ?年齡問題。有 n人坐在一起 ,問第 n個人多少歲 ?他說比第 n1個人大2歲。問第 n1個人多少歲 ?他說比第 n2個人大 2歲 ,……, 問第 3個人多少歲 ?他說比第 2個人大 2歲。 問第 2個人多少歲 ?他說比第 1個人大2歲。 最后問第 1個人 ,他說 10歲。求第 5個人的歲數？ 用遞歸函數表示 int age(int n) {int c。 if(n==1) c=10。 else c=age(n1)+2。 return(c)。} void main() {int n。 scanf(%d,amp。n)。 printf(%d\n ,age(n))。 } include void main() {int i,n,m=10。 scanf(%d,amp。n)。 for(i=1。in。i++) m=m+2。 printf(%d\n ,m)。 } 類似有 : 球體自由落地 搬磚頭 圍圈報數 兌換硬幣 ?打印揚輝三角 include void main( ) { int i,j,n。char c。 scanf(%d,amp。n)。 for(i=1。i=n。i++) {c=39。139。1。 for(j=1。j=2*n1。j++) if(j=ni) printf( )。 else if(j=n) {c=c+1。 printf(%c,c)。} else if(jn+i) {c=c1。 printf(%c,c)。} printf(\n)。 } } 1 121 12321 1234321 123454321 如打印 A ABA ABCBA ABCDCBA ?輸入 a,b使 a=bn的 n, n為最大的整數 include long pown(long b,int n)/*求 bn*/ {int i。 long g=1。 if (n==0) return 1。 for(i=1。i=n。i++) g=g*b。 return g。 } void main( ) { int n。 long a,b。 scanf(%ld%ld,amp。a,amp。b)。 n=0。 while(apown(b,n)) n++。 printf(%d\n,n)。 } 摸擬袖珍計算器 求 最大公約數和最小公倍數 輸入某年某月某日轉成這一年的第幾天 計算時間 (小時 :分 :秒 ) 計算分段函數 由于上機考試要進行服務器整理 ,練習系統使用截止日期為 6月 4日。 6月 5日開始停止使用。 找矩陣的鞍點 (元素值在該行上最大 , 在該列上最小 ) 解法一： i行 ,在 i行找到最大元素的列 j=col col列找到最小元素的行 k =row i==row,則鞍點為 row行 col列 輸入 a i=0。in。i++ col=0 j=1。jn。j++ a[i][col]a[i][j]) col=j 1 0 j k=1。kn。k++ a[row][col]a[k][col] row=k 1 k row==i 輸出 i,col 輸出 NO row=0 i 1 1 停 0 0 1 void main() {int i,j,k,row,col,flag=0,n。 int a[6][6]。 scanf(%d,amp。n)。 for(i=0。in。i++) for(j=0。jn。j++) scanf(%d,amp。a[i][j])。 for(i=0。in。i++) {col=0。 for(j=1。jn。j++) if(a[i][col]a[i][j])col=j。 row=0。 for(k=1。kn。k++) if(a[i][col]a[k][col])row=k。 if(row==i) {flag=1。break。} } if(flag) printf(i=%d,j=%d,row,col)。 else printf(NO)。 } 解法二： 對每個元素判別是否鞍點 i行 j列的元素 aij i行求出列最大值 max j列求出列最小值 min max==min==aij 則鞍點為 i行 j列 include void main() {int n,i,j,p,max,min,a[6][6]。 scanf(%d,amp。n)。 for(i=0。in。i++) for(j=0。jn。j++) scanf(%d,amp。a[i][j])。 for(i=0。in。i++) for(j=0。jn。j++) {max=a[i][0]。 for(p=1。pn。p++) if(maxa[i][p]) max=a[i][p]。 min=a[0][j]。 for(p=1。pn。p++) if(mina[p][j]) min=a[p][j]。 if(max==minamp。amp。max==a[i][j]) {printf(%d %d\n,i,j)。 return。} } printf(no\n)。} …… a ij …… …… ……