数据结构进阶实训八 数组，规律

Data structure advanced training course notes and algorithm exercises

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

---

题目1

荷兰国旗
现有n个红蓝白三种不同颜色的小球，乱序排列在一起；
请通过两两交换任意两个球，使得从左到右的球依次：红球、白球、蓝球

1.1 算法设计思想

把题目理解为这样的问题：
一个循环，把红色球和剩余的球交换，那么红球就排序好了，就是两两交换问题；
另一个循环，把剩下没排序好的白球和蓝球也排序好，也是两两交换；
程序的时间复杂度取决于长度取决于第一个循环，O(n)

1.2 源代码

#define RED 0
#define WHITE 1
#define BLUE 2

void swap(int *p, int *q){
  int temp;
  temp = *p;
  *p = *q;
  *q = temp;
}

void sort(int array[], int start, int end, int collor){
  int i=start, j=end;
  while(i < j){
    while(array[i]==collor){
      i++;
    }
    while(array[j]!=collor){
      j--;
    }
    swap(&array[i], &array[j]);
    i++;
  }
}

void main(){
  int ball[20]={1,2,2,0,1,0,1,2,0,0,0,1,2,1,0,1,2,0,0,1};
  int i, num_red=0;
  printf("There are 20 red, blue and white balls in three different colors, \
  arranged together in disorder:\n");
  for(i=0; i<20; i++){
    if(ball[i]==RED){
      num_red++;
      printf("Red  ");
    }
    if(ball[i]==WHITE)
      printf("White  ");
    if(ball[i]==BLUE)
      printf("Blue  ");
  }
  printf("\n");
  sort(ball, 0, 20, RED); // 把红色球排好序
  sort(ball, num_red, 20, WHITE); // 把白色球排好序
  printf("\nAfter sorting: \n");
  for(i=0; i<20; i++){
    if(ball[i]==RED)
      printf("Red  ");
    if(ball[i]==WHITE)
      printf("White  ");
    if(ball[i]==BLUE)
      printf("Blue  ");
  }
  printf("\n");
}

1.3 运行情况截图

---

---

题目2

完美洗牌算法
有一个长度为2n的数组{a1,a2,a3,…an,b1,b2,b3, …bn},
希望“排序”后，变为{a1, b1, a2, b2, a3, b3,…an, bn}。
要求：尽可能高效。能否在时间复杂度为O(n)，空间复杂度为O（1）的解法

2.1 算法设计思想

依次考察每个位置的变化规律
a1: 0 -> 不变
a2: 1 -> 2
a3: 2 -> 4
a4: 3 -> 6
…
an: n-1 -> 2n-2
b1: n -> 1
b2: n+1 -> 3
b3: n+2 -> 5
…
bn-1: 2n-2 -> 2n-3
bn: 2n-1 -> 不变
可以得出下标的变化规律：
j=(i * 2) % (n2 -1)
所以将值赋给辅助数组即可

2.2 源代码

void perfect_shuffle(char *a[],int n) {
  int n2 = n * 2, i, j;
  char *b[20];
  for (i = 1; i < n2-1; i++) {
    j=(i * 2) % (n2 -1);
    b[j] = a[i];
  }
  for (i = 1; i < n2-1; i++) {
    a[i] = b[i];
  }
}

2.3 运行情况截图

---

---

题目3

买票找零问题
在一场激烈的球赛开始之前，售票工作正在紧张地进行中，每张球票为50元。
现有2n个人排队购票，其中有n个人手持50元的钞票，
另外的n个人手持100元的钞票，假设开始售票时，售票处没有零钱。
要求：问这2n个人有多少种排队方式，不至于使售票处出现找不开钱的局面呢

3.1 算法设计思想

找规律递推的方法；
要求持50元n人，100元n人，多少种排队方式，那么排在最后的一定是持100元的人，所以和持50元n人，100元n-1人的排队方式相同；
发现规律，持50元n-1人，100元n-1人和持50元n-1人，100元n-2人的排队方式相同；
所以这就可以从最小的1开始求了，然后累加到n，得到最后结果

3.2 源代码

#define N 100

int arrange(int n){ 
  int array[N][N];
  int i, j;
  // 当100元和50元人数不相等，100元0人，则只有1中解决方案
  for(i=0; i<n; i++){
    array[i][0]=1;
  }
  // 若50元人数小于100元人数，则没有解决方案
  // 则二维数组的上三角的值都为0，不用初始化赋值
  // 开始递推，填满下三角矩阵数组
  for(i=1; i<=n; i++){
    for(j=0; j<=i; j++)
      array[i][j]=array[i-1][j]+array[i][j-1];
  }
  return array[n][n];
}

3.3 运行情况截图

---