对《培養與鍛鍊程式設計的邏輯腦(第二版)》的笔记(2)

利用一個變數，暫存其中一個數字，以便對調。

1. void swap_int()
2. {
3. int a=0,b=1;
4. //交換a與b
5. int temp=a;
6. a=b;
7. b=temp;
8. cout<<a<<''<<b;
9. }

1. void swap_int(int&a,int&b)
2. {
3. int temp=a;
4. a=b;
5. b=temp;
6. }

範例：平面上距離最近的兩個點（ Closest Pair ）

第一層枚舉第一個點，第二層枚舉第二個點。為了避免重複枚舉相同的一對點，第二層只枚舉索引值更高的點。

1. void closest_pair()
2. {
3. float point[10][2]=
4. {
5. {3,3},{1,5},{4,6},{2,8},{9,9},
6. {2,1},{7,2},{6,5},{9,4},{5,9}
7. };
8. //距離最近的兩個點的距離
9. float d=1e9;
10. //枚舉第一點
11. for(int i=0;i<10;i++)
12. //枚舉第二點
13. for(int j=i+1;j<10;j++)
14. {
15. //計算第一點到第二點的距離
16. float dx=point[i][0]-point[j][0];
17. float dy=point[i][1]-point[j][1];
18. float dij=sqrt(dx*dx+dy*dy);
19. //記錄最短的距離
20. if(dij<d)d=dij;
21. }
22. cout<<"距離是"<<d;
23. }

可以把計算距離的程式碼，抽離出來成為一個函式。好處是程式碼變得清爽許多，增加程式碼可讀性。壞處是大量呼叫函式，導致執行速度變慢。

1. struct Point{float x,y;};
2. //計算兩點之間的距離
3. float dist(Point a,Point b)
4. {
5. float dx=a.x-b.x;
6. float dy=a.y-b.y;
7. return sqrt(dx*dx+dy*dy);
8. }
9. void closest_pair()
10. {
11. Point point[10]=
12. {
13. {3,3},{1,5},{4,6},{2,8},{9,9},
14. {2,1},{7,2},{6,5},{9,4},{5,9}
15. };
16. float d=1e9;
17. for(int i=0;i<10;i++)
18. for(int j=i+1;j<10;j++)
19. //記錄最短的距離
20. d=min(d,dist(point[i],point[j]));
21. cout<<"距離是"<<d;
22. }

魚與熊掌不可兼得，這兩種程式碼各有優缺點，沒有絕對的好壞。程式員必須自行取捨。

範例：反轉字串

兩個枚舉，一個從頭到尾，一個從尾到頭，步調相同，逐步對調字元。雖然是兩個枚舉，卻只有一個迴圈。

1. void reverse_string()
2. {
3. char s[15]="HelloWorld!";
4. //兩個枚舉，一個從頭到尾，一個從尾到頭。
5. for(int i=0,j=12;i<j;i++,j--)
6. swap(s[i],s[j]);
7. cout<<"反轉之後的字串是"<<s;
8. }

1. void reverse(char*s)
2. {
3. int n=strlen(s);
4. for(int i=0;i<n/2;i++)
5. swap(s[i],s[n-1-i]);
6. }

範例：尋找總和為 10 的區間

假設陣列元素只有正數。

兩個枚舉，枚舉區間左端以及枚舉區間右端，都是從頭到尾，保持一左一右，視情況輪流枚舉。雖然是兩個枚舉，卻只有一個迴圈。

1. void find_interval()
2. {
3. int array[5]={3,6,1,7,2};
4. int sum=0;
5. for(int i=0,j=-1;j<5;)//枚舉區間[i,j]
6. {
7. if(sum>10)
8. {
9. //總和太大，區間左端往右縮短。
10. sum-=array[i];
11. i++;
12. }
13. else if(sum<10)
14. {
15. //總和太小，區間右端往右伸長。
16. j++;
17. sum+=array[j];
18. }
19. else if(sum==10)
20. {
21. //總和剛好，
22. //區間左端往右縮短，
23. //亦得區間右端往右伸長。
24. //任選一種皆可。
25. //sum-=array[i];
26. //i++;
27. j++;
28. sum+=array[j];
29. }
30. if(sum==10)
31. cout<<'['<<i<<','<<j<<']';
32. }
33. }

1. void find_interval(int array[],int n,int num)
2. {
3. int sum=0;
4. for(int i=0,j=0;j<=n;)//枚舉區間[i,j)
5. {
6. if(sum>num)
7. sum-=array[i++];
8. else
9. sum+=array[j++];
10. if(sum==num)
11. cout<<'['<<i<<','<<j-1<<']';
12. }
13. }

讀者可以想想看：陣列元素若有零、有負數，是否要調整枚舉方式？

範例：尋找陣列之中的特定數字，陣列已經由小到大排序

找到其中一個特定數字：首先找到陣列中央的數字，依其數字大小，繼續搜尋左半段或者右半段。

1. void find_number()
2. {
3. int array[15]=
4. {
5. 2,3,5,7,11,
6. 13,17,19,23,29,
7. 31,37,41,43,47
8. };
9. int left=0,right=15-1;
10. while(left<=right)
11. {
12. int mid=(left+right)/2;
13. if(array[mid]<29)
14. left=mid+1;//繼續搜尋剩下的右半段
15. else if(array[mid]>29)
16. right=mid-1;//繼續搜尋剩下的左半段
17. else if(array[mid]==29)
18. {
19. //找到了其中一個數字
20. cout<<mid<<':'<<array[mid];
21. return;
22. }
23. }
24. cout<<"找不到29";
25. }

找到所有特定數字：讀者請自行嘗試。