华为2011校园招聘上机题目（华南和成都）一组 第三题

时间看来

在上一贴中“2012华为杯 西南赛区 初试第三题”说了GDB不少坏话。在看了《GDB调试程序[陈皓]》后，决定再找些题目试试。

欢迎任何评论！

3.操作系统任务调度问题。操作系统任务分为系统任务和用户任务两种。其中，系统任务的优先级 < 50，用户任务的优先级 >= 50且 <= 255。优先级大于255的为非法任务，应予以剔除。现有一任务队列task[]，长度为n，task中的元素值表示任务的优先级，数值越小，优先级越高。函数scheduler实现如下功能，将task[] 中的任务按照系统任务、用户任务依次存放到 system_task[] 数组和 user_task[] 数组中（数组中元素的值是任务在task[] 数组中的下标），并且优先级高的任务排在前面，数组元素为-1表示结束。
例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99}
      system_task[] = {0, 3, 1, 7, -1}
      user_task[] = {4, 8, 2, 6, -1}

函数接口
void scheduler(int task[], int n, int system_task[], int user_task[])

1.     #include <stdio.h>
   
2.     #include <stdlib.h>
   
3. 
   
4.     #define DEBUG 0
   
5. 
   
6.     void scheduler(int task[], int n, int system_task[], int user_task[]);
   
7. 
   
8.     int
   
9.     main(int argc, char *argv[])
   
10.     {
    
11.         int n, i, j;
    
12.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99};
    
13.         n = sizeof(task) / sizeof(int);
    
14.         int system_task[n];
    
15.         int user_task[n];
    
16. 
    
17.         scheduler(task, n, system_task, user_task);
    
18. 
    
19.         printf("\ntask[] is :\n");
    
20.         for(i = 0; i < n; i++){
    
21.             printf("%d ", task[i]);
    
22.         }
    
23.         
    
24.         printf("\n\nsystem_task[] is :\n");
    
25.         for(i = 0; i < n && system_task[i] != -1; i++){
    
26.             printf("%d ", system_task[i]);
    
27.         }
    
28.         printf("%d",system_task[i]);
    
29.         
    
30.         printf("\n\nuser_task[] is :\n");
    
31.         for(i = 0; i < n && user_task[i] != -1; i++){
    
32.             printf("%d ", user_task[i]);
    
33.         }
    
34.         printf("%d", user_task[i]);
    
35.         printf("\n");
    
36. 
    
37.     }
    
38. 
    
39.     /*
    
40.      *scheduler处理函数
    
41.      */
    
42.     void
    
43.     scheduler(int task[], int n, int system_task[],int user_task[])
    
44.     {
    
45.         int i, j, min_val;
    
46.         int min_in_task_ptr;
    
47.         int *fill_ptr;
    
48.         int *task_ptr[n];
    
49.         int **tmp_ptr_ptr;
    
50. 
    
51.         for(i = 0; i < n; i++){
    
52.             task_ptr[i] = &task[i];
    
53.         }
    
54. 
    
55.         /*将task_ptr[]从小到大的排列*/
    
56.         for(i = 0; i < n; i++){
    
57.             min_val = *task_ptr[i];
    
58.             min_in_task_ptr = i;
    
59.             fill_ptr = task_ptr[i];
    
60. 
    
61.             /*寻找task_ptr后面的最小值和它的指针*/
    
62.             for(j = i; j < n; j++){
    
63.                 if(*task_ptr[j] < min_val){
    
64.                     min_val = *task_ptr[j];
    
65.                     min_in_task_ptr = j;
    
66.                 }
    
67.             }
    
68.     #if DEBUG
    
69.             printf("min_val:%d min_ptr:%d ", min_val, *task_ptr[min_in_task_ptr]);
    
70.             printf("min_ptr-task:%d\n", min_in_task_ptr);
    
71.     #endif
    
72. 
    
73.             /*交换指针*/
    
74.             task_ptr[i] = task_ptr[min_in_task_ptr];
    
75.             /*min_ptr-task怎么和我期望的有差距呢？
    
76.              * 哦，task数组中的数据顺序没有变化。
    
77.              * */
    
78.             //task_ptr[i] = task_ptr[min_ptr - task];
    
79.             task_ptr[min_in_task_ptr] = fill_ptr;
    
80.     #if DEBUG
    
81.             printf("%d\ttask_ptr[] is :", i);
    
82.             for(j = 0; j < n; j++){
    
83.                 printf("%d ", *task_ptr[j]);
    
84.             }
    
85.             printf("\n");
    
86.     #endif
    
87. 
    
88.         }
    
89. 
    
90.         int count_sys = 0;
    
91.         int count_user = 0;
    
92. 
    
93.         for(i = 0; i < n; i++){
    
94.             if(*task_ptr[i] < 50){
    
95.                 system_task[count_sys] = task_ptr[i] - task;
    
96.                 count_sys++;
    
97.             } else if(*task_ptr[i] > 255){
    
98.                 printf("%d", *task_ptr[i]);
    
99.             } else {
    
100.                 user_task[count_user] = task_ptr[i] - task;
     
101.                 count_user++;
     
102.             }
     
103.         }
     
104.         system_task[count_sys] = -1;
     
105.         user_task[count_user] = -1;
     
106.     }

复制代码

总结：
看到一个师弟对这个三道题目的评价“其实就是逻辑思维，根本不涉及库函数算法神马的。。。”
嗯，对于我来说，着重练习的是逻辑思维，GDB调试。

编这三个练习的时候我感觉到比华为杯2012西南赛区初赛题目要顺手一些。特别是对于调试也“身”有体会了。看了《GDB调试程序[陈皓]》后，感觉原来GDB还不错。同时，也喜欢上了在程序中加上条件编译，这样调试程序就更方便了。目前我的调试前后的时间各占了一半，我还会做得更好的。

喜欢GDB的打印数组 p *task_ptr[0]@9 。开始对这个的理解错误，运行结果让我匪夷所思。原来
p task_ptr[0]@9 才是打印排了序的指针。但显示的是指针，不容易阅读。此时，我想起了条件编译，感觉不错。

在第三个练习中，用了指针数组，用得还不太熟悉。（暂且忽略解决方法的好坏~）尽管看书的时候，指针的应用都能理解，但和自己动手相比差别还是大。

lqfhvk357

我也写了个...

1. #define N 10
   
2. 
   
3. #include <iostream.h>
   
4. void scheduler(int task[], int n, int system_task[], int user_task[])
   
5. {
   
6.         int i, h;
   
7.         int k_s, k_u;
   
8.         k_s=0, k_u=0;
   
9.         for(i=0; i<n; i++)
   
10.         {
    
11.                 if(task[i]<50)
    
12.                 {
    
13.                         system_task[k_s++]=i;
    
14.                         h=k_s;
    
15.                         while(h>1)
    
16.                         {       
    
17.                                 if(task[system_task[h-1]]<task[system_task[h-2]])
    
18.                                 {
    
19.                                         system_task[h-1]=system_task[h-1]+system_task[h-2],
    
20.                                         system_task[h-2]=system_task[h-1]-system_task[h-2],
    
21.                                         system_task[h-1]=system_task[h-1]-system_task[h-2];
    
22.                                         h--;
    
23.                                 }
    
24.                                 else
    
25.                                         break;               
    
26.                         }
    
27.                 }
    
28.                 else if(task[i]<=255)
    
29.                 {
    
30.                         user_task[k_u++]=i;
    
31.                         h=k_u;
    
32.                         while(h>1)
    
33.                         {       
    
34.                                 if(task[user_task[h-1]]<task[user_task[h-2]])
    
35.                                 {
    
36.                                         system_task[h-1]=system_task[h-1]+system_task[h-2],
    
37.                                         system_task[h-2]=system_task[h-1]-system_task[h-2],
    
38.                                         system_task[h-1]=system_task[h-1]-system_task[h-2];
    
39.                                         h--;
    
40.                                 }
    
41.                                 else
    
42.                                         break;               
    
43.                         }
    
44.                 }
    
45.                 else
    
46.                         cout<<task[i]<<"：此任务为非法任务！"<<endl;
    
47.         }
    
48.         system_task[k_s]=-1;
    
49.         user_task[k_u]=-1;
    
50.         cout<<"system_task:"<<endl;
    
51.         for(i=0; i<k_s+1; i++)
    
52.                 cout<<system_task[i]<<" ";
    
53.         cout<<endl<<"user_task:"<<endl;
    
54.         for(i=0; i<k_u+1; i++)
    
55.                 cout<<user_task[i]<<" ";
    
56. }
    
57. 
    
58. int main()
    
59. {
    
60.         int  i;
    
61.         int a[N];
    
62.         int b[N];
    
63.         int c[N];
    
64. 
    
65.         cout<<"请输入十个整数："<<endl;
    
66.         for(i=0; i<N; i++)
    
67.                 cin>>a[i];
    
68.         scheduler(a, N, b, c);
    
69.         return 0;
    
70. }
    

复制代码

walleeee

优先级相同，这个时候又有另外一些要考虑的，比如是否序列稳定。

walleeee

1. // the original priority scheduler design is not right.
   
2. // it should not be design as that, it's slow. i think
   
3. // the scheduler should use mutil-level list/queue to
   
4. // store process, which in scheuler list.
   
5. 
   
6. // but here i use mutil-level fixed array just for
   
7. // convenient. lol :-)
   
8. 
   
9. #include <stdio.h>
   
10. 
    
11. #define PRIORITY_MIN            0x00000000
    
12. #define PRIORITY_MAX            0x000000fe
    
13. #define PRIORITY_LEVEL_MAX_PROC 0x0000000f
    
14. #define PRIORITY_QUEUE_ROW      PRIORITY_MAX-PRIORITY_MIN+1
    
15. #define PRIORITY_QUEUE_COLUMN   PRIORITY_LEVEL_MAX_PROC+1
    
16. 
    
17. // switch for reporting error code or just filter/ignore error.
    
18. #undef USE_ERROR
    
19. 
    
20. // error code.
    
21. #define ERROR_OK                    0x00000000
    
22. #define ERROR_PRIORITY_OUT_RANGE    0x00000001
    
23. 
    
24. int Scheduler(const int *allTask, int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN])
    
25. {
    
26.     for(int i=0; i<PRIORITY_QUEUE_ROW; ++i)
    
27.     {
    
28.         priorityQueue[i][0] = 0;
    
29.     }
    
30. 
    
31.     for(int i=0; allTask[i]!=-1; ++i)
    
32.     {
    
33.         if(allTask[i]>=PRIORITY_MIN && allTask[i]<=PRIORITY_MAX)
    
34.         {
    
35.             priorityQueue[allTask[i]][++priorityQueue[allTask[i]][0]] = i;
    
36.         }
    
37. #ifdef USE_ERROR
    
38.         else
    
39.         {
    
40.             return ERROR_PRIORITY_OUT_RANGE;
    
41.         }
    
42. #endif
    
43.     }
    
44. 
    
45.     return ERROR_OK;
    
46. }
    
47. 
    
48. void DumpPriorityQueue(const int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN], int start, int end, const char *name)
    
49. {
    
50.     printf("[%s] ", name);
    
51.     for(int i=start; i<end; ++i)
    
52.     {
    
53.         for(int j=1; j<=priorityQueue[i][0]; ++j)
    
54.         {
    
55.             printf("%d ", priorityQueue[i][j]);
    
56.         }
    
57.     }
    
58.     printf("\n");
    
59. }
    
60. 
    
61. int main(int argc, char **argv)
    
62. {
    
63.     int allTask[] = {0, 30, 155, 1, 80, 300, 170, 40, 99, -1};
    
64.     int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN];
    
65. 
    
66.     Scheduler(allTask, priorityQueue);
    
67. 
    
68.     DumpPriorityQueue(priorityQueue, 0, 50, "sys");
    
69.     DumpPriorityQueue(priorityQueue, 50, 256, "usr");
    
70. 
    
71.     return 0;
    
72. }

复制代码

大概写了下，不过没考虑题目要求
另外，那个多级映射，看不懂就算了，其实该用多维线性表，我用数组方便了
核心代码就是scheduler函数

cokeboL

要我写的话，先计数排序把task理顺了然后一次遍历放到两个task里。4N的时间复杂度

时间看来

回复 2# lqfhvk357


嗯，测试通过！
思想是：先把任务分类，再排序。时间复杂度我没有计算
Tips：
编程的风格还需要注意下：比如 = 左右两边的的空格 是否需要？
在CU中有帖代码行的HTML标签 “<>”，不然程序贴出来有的内容可能改变。

我尝试将元素改成254个，将程序运行100遍。来分析这三个程序的运行时间，到目前为止都显示的0.01秒。
非常感谢您的时间！

时间看来

回复 4# walleeee


嗯，看懂了。
数组第一个元素用于计数……
同一个优先级的一个队列/线性表……

看过内核的就是不一样~

我尝试将元素改成254个，将程序运行100遍。来分析这三个程序的运行时间，到目前为止都显示的0.01秒。
非常感谢您的时间！

时间看来

回复 5# cokeboL


时间复杂度，我还没有考虑哦~

这三个程序的时间复杂度，可能大牛一眼就看出来了。我还达不到

睡觉了，GOOD NIGHT~

cokeboL

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. void task_sort(int task[], int task_num, int max_task_num)
   
5. {
   
6.         int i, j;
   
7.         int *count = (int*)malloc(sizeof(int)*max_task_num);
   
8. 
   
9.         for(i=0; i<max_task_num; i++){
   
10.                 count[i]=0;
    
11.         }
    
12. 
    
13.         for(i=0; i<task_num; i++){
    
14.                 count[task[i]]++;
    
15.         }
    
16. 
    
17.         for(i=0, j=0; i<task_num; j++){
    
18.                 while( (count[j]-- > 0) && i<task_num ){
    
19.                         task[i++] = j;
    
20.                 }
    
21.         }
    
22. 
    
23.         free(count);
    
24. }
    
25. 
    
26. void Scheduler(int task[], int task_num, int max_task_num, int system_task[], int user_task[])
    
27. {
    
28.         int i=0, n=0;
    
29.         task_sort(task, task_num, max_task_num);
    
30.         while(task[n]<50){
    
31.                 system_task[n]=n++;
    
32.         }
    
33.         system_task[n]=-1;
    
34.         while(task[n]<=255){
    
35.                 user_task[i++]=n++;
    
36.         }
    
37.         user_task[n]=-1;
    
38. }
    
39. 
    
40. int main()
    
41. {
    
42.        
    
43.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99},
    
44.                 system_task[20],
    
45.                 user_task[20];
    
46.         Scheduler(task, sizeof(task)/sizeof(int), 300, system_task, user_task);
    
47.        
    
48.         return 0;
    
49. }

复制代码

e,3n+255

lqfhvk357

回复 9# cokeboL