2007-05-26

用C實做二元搜尋數

二元搜尋(Binary Search)
  從一個排序過的序列中找尋數值所在的位置(index)。  假設一個陣列大小為10,存放已排序好的數列如圖所示,搜尋數值16所在位址。

  1. 初始min為柱標0
  2. 初始max為柱標n-1
  3. 以min到max為搜尋範圍,每次都比較中間數值是否為搜尋之key,如果是就回傳其所在位址
  4. 如果中間值(mid)小於key,表示key存在於範圍mid+1到max之間,因此修改min為mid,並繼續下一次比較
  5. 如過中間值(mid)大於key,表示key存在於範圍min到mid-1之間,因此修改max為mid,並繼續下一次比較
  6. 重複3, 4, 5 步驟直到min大於max為止,此時還未找到key所在位址,表示key不存在于數列之中,因此回傳-1表示搜尋失敗
參考程式如下:
#include <stdio.h>

int binary_search(int arr[], int n, int key) {
int min = 0 ;
int max = n-1 ;
int mid ;
while(max >= min) {
mid=(min+max)/2 ;
if(arr[mid] == key)
return mid ;
else if(key < arr[mid])
max = mid-1 ;
else

min = mid+1 ;
}
return -1 ;
}

int main() {
int arr[10] = {1, 5, 7, 10, 12, 13, 16, 19, 20, 30} ;
printf("%d\n", binary_search(arr, 10, 13)) ;
system("pause") ;
return 0 ;
}

2007-05-25

【5/24】計概實習參考解答

題目:運用遞迴觀念設計一函數,該函數接受兩個參數:一個整數型態陣列、一個整數(表示陣列大小),並回傳總和

#include <stdio.h>

int sum(int a[], int x) {
if(x<=1) {
return a[x-1] ;
}
else

return a[x-1] + sum(a, x-1) ;
}
int main() {
int test1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ;
printf("%d\n", sum(test1, 10)) ;
system("pause") ;
return 0 ;
}

2007-05-16

簡單猜數字遊戲

猜數字遊戲之【終極密碼】

遊戲中用到亂數,相關學習可以到美麗C世界參考

#include <stdio.h>

int main() {
int input ;
int ans ;
int min=0, max=1000 ;
srand(time(NULL));
ans = rand()%1000 ;


while(1) {
printf("%d 到 %d, 猜一數字", min, max) ;
scanf("%d", &input) ;
if(input < min input > max) {
printf("賣來亂...\n");
continue ;
}
if(ans == input)
break ;
else if(input < ans)
min = input ;
else

max = input ;
}
printf("恭喜猜對了!! ans: %d\n", ans) ;
system("pause") ;
return 0 ;
}

2007-05-10

氣泡排序法(由小到大)

#include <stdio.h>
#include
<time.h>

#define
MAX 5

int main() {
int i, j, k, flag = 1;
int number[MAX] ;
int temp ;


srand((unsigned)time(NULL)) ;
printf("排序前: ");
for(i = 0; i < MAX; i++) {
number[i] = rand()%100 ;
printf("%3d", number[i]) ;
}
printf("\n") ;


for(i = 0; i < MAX-1; i++) {
for(j = 0; j < MAX-i-1; j++) {
if(number[j+1] < number[j]) {
temp = number[j+1] ;
number[j+1] = number[j] ;
number[j] = temp ;
}
}

printf("第 %d 次排序:", i+1);
for(k = 0; k < MAX; k++)
printf("%d ", number[k]);
printf("\n");
}
system("pause") ;
return 0 ;
}

2007-05-01

Java is Everywhere

  今天上物件導向時,老師要大家回去看的影片...。現在Java的應用確實無所不在,從手機、PDA、醫療產品、金融交易系統、交通運輸系統...等,處處可以看到Java的應用,Java的重要性已經無法否認!
  不過還是得跟各位學弟說:研究電機相關領域的你們,只需要一套C語言就可以打遍天下了,學會一套程式語言的重要性,不在於你可以把某套語言技巧發揮到淋漓盡致,而是要你能夠從學習這套語言的過程中建立起邏輯思考模式、未來學習其他語言能夠快速上手。各位如果以後走IC設計大概會碰到兩套硬體描述語言:VerilogVHDL,此時有C語言基礎的你們應該都可以很快速的上手才是,我想這才是要你們學習C語言的主要目的!