天天看點
傳回

【算法】算法的藝術（一）

火車托運費的計算

　　　設乘坐火車托運作李時按下列式子收費：

　　　                 0                (0<=x<=20）

　　　　應交費用y =    (x–20) * 2         (20<x<=40)

                     (x–40) * 5 + 40     (x>40)

　　　編一個程式用來計算應交金額。

　　執行個體解析：

　　　這是第三章中的一個例題（當時是用switch處理的），是一個選擇結構的執行個體，收費情況共分三種。

　　　本題可以采用三種方法來程式設計：

　　　(1) 用三個單獨的if語句，每個if語句處理一種情況；

　　　(2) 用嵌套的if語句處理，需兩個if語句；

　　　(3) 用switch語句。

方法一：用單獨的if語句

     
  1.  #include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  int x, y;       
    5.       
  5.  　　scanf(“%d”, &x);       
    6.       
  6.  if(x <= 20)       
    7.       
  7.  　　　 y = 0;       
    8.       
  8.  if(x > 20 && x <= 40)       
    9.       
  9.  　　　 y = (x-20)*2;       
    10.       
  10.  if(x > 40)       
    11.       
  11.  　　　 y = (x–40)*5 + 40;       
    12.       
  12.  　　printf(“y = %d\n”, y);       
    13.       
  13.  　　getch();       
    14.       
  14.  return 0;       
    15.       
  15.  }       
    16.

注意：

if(x > 40)一行，不能寫成else，原因請參看第3章3.13中的if語句常見錯誤。

方法二：用嵌套的if語句

     
  1.  #include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  　　int x, y;       
    5.       
  5.  　　scanf(“%d”, &x);       
    6.       
  6.  　　if(x <= 20)       
    7.       
  7.  y = 0;       
    8.       
  8.  else if(x <= 40)  //在x>=20不成立的情況下，若x<=40       
    9.       
  9.  y = (x-20)*2;       
    10.       
  10.  　　else  //在前面兩個條件都不成立的情況下       
    11.       
  11.  y = (x–40)*5 + 40;       
    12.       
  12.  　　printf(“y = %d\n”, y);       
    13.       
  13.  　　getch();       
    14.       
  14.  　　return 0;       
    15.       
  15.  }       
    16.

方法三：用switch語句

     
  1.  　#include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  　　　int x, y;       
    5.       
  5.  　　　scanf(“%d”, &x);       
    6.       
  6.  　　　switch(x/20)         
    7.       
  7.  　　　{       
    8.       
  8.  　　　　　case 0:   y = 0;  break;       
    9.       
  9.  　　　    case 1:   y = (x-20)*2;  break;       
    10.       
  10.  　　　    default:  y = (x–40)*5 + 40;       
    11.       
  11.  　　　 }       
    12.       
  12.  　　　printf(“y=%d\n”, y);       
    13.       
  13.  　　　getch();       
    14.       
  14.  　　　return 0;       
    15.       
  15.  }       
    16.

找小偷

　　　警察局抓了a、b、c、d 共4名盜竊嫌疑犯，但隻有一人是小偷。審訊中，a不承認自己是小偷，b說c是小偷，c指認d為小偷，d說c冤枉他。已知4人中有3人說的是真話，請問誰是小偷？

　　　執行個體解析：

　　　本執行個體的目的是讓讀者學會把邏輯值當整數來使用。

　　　C中的邏輯值要麼為1，要麼為0。将幾個關系（或邏輯）表達式相加，由結果可以知道其中有幾個表達式是成立的。

　　　由題意知，4個人都是嫌疑犯，是以我們定義一個變量x，使之分别取值1、2、3、4，分别代表a、b、c、d是小偷的4種情況。

　　　對于x的每一個取值，我們判斷下面的4個表達式有幾個成立。

　　　(1)  x != 1        //小偷不是a

　　　(2)  x == 3       //小偷是c

　　　(3)  x == 4       //小偷是d

　　　(4)  x != 4        //小偷不是d

　　　判斷的方法是：将4個表達式的值相加，若等于3，表示三個人說的是真話，符合題意，輸出結果，否則，不符合題意，跳過。

　　　下面是程式代碼：

     
  1.  #include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  　　　 int x;       
    5.       
  5.  　　　 for(x = 1; x <= 4; x++)       
    6.       
  6.  　　　   if((x!=1) + (x==3) + (x==4) + (x!=4) == 3)       
    7.       
  7.  　　　 　　　  printf(“%c是小偷！\n”, x+64);       
    8.       
  8.  　　　 getch();       
    9.       
  9.  　　　 return 0;       
    10.       
  10.  }       
    11.

判斷整數能被3、5、7中的哪些數整除

　　　鍵盤輸入一個整數，判斷能被3、5、7中的幾個數整數，并且指出這幾個數。

　　　這個題目可以用3個if語句分别檢查能否被3、5、7整除，但這種最普通的算法效率較低。

　　　這裡我們介紹一種簡單的方法，利用執行個體3所介紹的技巧：将幾個關系表達式相加，可以知道有幾個表達式是成立的。

　　　求解：s = (x%3==0) + (x%5 == 0) + (x%7 == 0)

　　　（1）若s 值為3，則x可同時被3個數整除

　　　（2）若s為2，則隻能同時被其中2個數整除。

　　　（3）若s為1，則隻能被其中1個數整除。

　　　（4）若s為0，則不能被其中任何數整除。

　　　但是，這樣設計有一個問題，當s = 2或s = 1時，我們隻知道x可以被幾個數整數，但能被哪些數整除卻不能确定。

　　　為此，我們這樣設計：用一個位元組的後三位分别表示能否被3、5、7整除。若x能被3整除，我們讓最後一位為1，若能被5整除，讓倒數第2位為1，若能被7整除，讓倒數第3位為1。共有8種可能：

　　　（1）00000000

　　　（2）00000001

　　　（3）00000010

　　　（4）00000011

　　　（5）00000100

　　　（6）00000101

　　　（7）00000110

　　　（8）00000111

　　　通過檢查該位元組的值，可以得到本執行個體所要的結論。

　　　程式代碼如下：

     
  1.  #include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  　　　int x;       
    5.       
  5.  　　　char s;       
    6.       
  6.  　　　scanf(“%d”, &x);       
    7.       
  7.  s = (x%3==0) + (x%5==0)*2 + (x%7==0)*4;         
    8.       
  8.  　　　switch(s)       
    9.       
  9.  　　　{       
    10.       
  10.  　　　  case 0:   printf(“none\n”); break;       
    11.       
  11.  　　　  case 1:   printf(“3\n”);     break;       
    12.       
  12.  　　　  case 2:   printf(“5\n”);     break;       
    13.       
  13.  　　　  case 3:   printf(“3,5\n”);   break;       
    14.       
  14.  　　　  case 4:   printf(“7\n”);     break;       
    15.       
  15.  　　　  case 5:   printf(“3,7\n”);   break;       
    16.       
  16.  　　　  case 6:   printf(“5,7\n”);   break;       
    17.       
  17.  　　　  case 7:   printf(“3,5,7\n”); break;       
    18.       
  18.  　　　  default:  printf(“error!\n”);         
    19.       
  19.  　　　}       
    20.       
  20.  　　　return 0;       
    21.       
  21.  }       
    22.

找假貨

　　　有5箱産品，每箱20件，但其中有幾箱裡全是假貨。已知正品每件100克，假貨比正品輕10克，問能否用天平隻稱一次，找出所有裝假貨的箱子？

　　　本題可以先這樣考慮：每箱取出一件産品，共取5件，一起放在天平上稱一次，如果總重490克，說明比正常情況少了10克，其中必定有一件是假貨，推斷出隻有一箱假貨。如果比正常少20克，則有兩箱假貨，如果少30克，有三箱假貨……

　　　但是，這樣隻能知道有幾箱假貨，不知道哪箱是假貨。為此，我們給每個箱子加上權重：即每個箱子取出的産品數目不同。

　　　我們想到，可以在5個箱子中分别取1、2、3、4、5件産品，但這樣的算法依然存在問題：當總重470克時，有可能1、2号箱是假貨，還有可能3号箱是假貨，還是不能确定哪些箱是假貨。

　　　正确的取法應該是：分别在5個箱子中取1、2、4、8、16件産品，這樣就不會出現分辨不清的情況了。例如若總重430克，少了70克，則一定是前三箱是假貨。

     
  1.  #include <stdio.h>       
    2.       
  2.  int main()       
    3.       
  3.  {       
    4.       
  4.  int w[5] = {100,90,100,90,90}; //分别是5個箱子裡一件産品的重量       
    5.       
  5.  int sum = 0, i, k = 1, m;       
    6.       
  6.  for(i = 0; i < 5; i++ )         
    7.       
  7.  　　　{       
    8.       
  8.  　　　   sum += w[i]*k;         
    9.       
  9.  　　　   k *= 2;         
    10.       
  10.  　　　 }       
    11.       
  11.  　　　 m = (100*31 – sum)/10 ;        // 計算其中有多少件假貨       
    12.       
  12.  　　　 k = 16;                           //  k先取第5箱的權重       
    13.       
  13.  for(i = 5; i >= 1; i--)       
    14.       
  14.  　　　 {       
    15.       
  15.  if(m >= k)       
    16.       
  16.  　　　　　　{       
    17.       
  17.  　　　    　　　 printf(“第%d箱是假貨\n”, i);       
    18.       
  18.  　　　    　　　 m -= k;         
    19.       
  19.  　　　  　　　 }                         
    20.       
  20.  　　　   　　k /= 2;  // k變為下一個要處理箱的權重       
    21.       
  21.  　　　　　 }         
    22.       
  22.  　　　getch();       
    23.       
  23.  return 0;       
    24.       
  24.  　　　}       
    25.

　　　上面代碼的最後一段也可以采用位操作來完成：

     
  1.  m = (100*31 – sum)/10 ; // 計算其中有多少件假貨       
    2.       
  2.  for(i = 1; i <= 5; i++)         
    3.       
  3.  {       
    4.       
  4.  if(m & 1)       
    5.       
  5.     　　printf(“第%d箱是假貨\n”, i);       
    6.       
  6.  　　　  m >>= 1;             
    7.       
  7.  }           
    8.

計算某天是一年中的第幾天

　　　鍵盤輸入一個年月日，計算該日期在該年中是第幾天。

　　　這也是第三章中的一個例題（參看例3.3），在例3.3中是用switch語句來程式設計的，這裡我們用循環的方法。

　　　程式設計思路是：用一個數組存放12個月份的天數（實際上第12月的資料無用），假設month=5，則需要先把前4個月的天數（即下面數組的第1~4個元素）加起來，再加上5月份的日期（即day），若是閏年，再加1。

     
  1.  #include<stdio.h>       
    2.       
  2.  int main( )       
    3.       
  3.  {       
    4.       
  4.  int  year, month, day;       
    5.       
  5.  int m[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};         
    6.       
  6.  int  i, n = 0;       
    7.       
  7.      scanf(“%d%d%d”, &year, &month, &day);       
    8.       
  8.  for(i = 1; i < month; i++)       
    9.       
  9.  　　 　　  n += m[i];       
    10.       
  10.  　　　n += day;       
    11.       
  11.  if((year%4==0 && year%100 != 0 || year%400 == 0 ) && month>=3 )       
    12.       
  12.  　　 　　  n++;       
    13.       
  13.  　　 printf(“%d\n”, n);       
    14.       
  14.  　　 getch();       
    15.       
  15.  return 0;       
    16.
算法 資料結構 mystery
上一篇: 記賬本開發日報（九）
下一篇: windows核心基礎與異常處理

繼續閱讀