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

时间看来

回复 9# 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, j;
    
29.         task_sort(task, task_num, max_task_num);
    
30.         printf("task[]:\n");
    
31.         for(j = 0; j < task_num; j++){
    
32.                 printf("%d  ", task[j]);
    
33.         }
    
34.         printf("\n");
    
35. 
    
36.         while(task[n]<50){
    
37.                 system_task[n]=n++;
    
38.         }
    
39.         system_task[n]=-1;
    
40.         printf("system_task:\n");
    
41.         for(j = 0; j < task_num; j++){
    
42.                 printf("%d  ", system_task[j]);
    
43.         }
    
44.         printf("\n");
    
45. 
    
46.         while(task[n]<=255){
    
47.                 user_task[i++]=n++;
    
48.         }
    
49.         user_task[n]=-1;
    
50.         printf("user_task:\n");
    
51.         for(j = 0; j < task_num; j++){
    
52.                 printf("%d  ",user_task[j]);
    
53.         }
    
54.         printf("\n");
    
55. }
    
56. 
    
57. int main()
    
58. {
    
59. 
    
60.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99},
    
61.                 system_task[20],
    
62.                 user_task[20];
    
63.         Scheduler(task, sizeof(task)/sizeof(int), 300, system_task, user_task);
    
64. 
    
65.         return 0;
    
66. }
    

复制代码

g++编译后，您程序的运行结果是：
task[]:
0  1  30  40  80  99  155  170  300  
system_task:
0  1  2  3  -1  104126944  -1075139896  13049472  -163754450  
user_task:
4  5  6  7  1  -1  2691008  103209324  -1  

gcc编译后输出是：
task[]:
0  1  30  40  80  99  155  170  300  
system_task:
0  1  2  3  -1  0  0  0  -163754450  
user_task:
4  5  6  7  1  0  0  0  -1  

说明，你排序后，改变了task[]的内容，再定位时，得到的位置数据是不正确的。
没弄明白7后面的1是怎么来的？？？？但“user_task[n]=-1;”我想你的本意是“user_task=-1;”

cokeboL

回复 10# lqfhvk357


    那有怎么样~

cokeboL

回复 11# 时间看来


      
    写了没调试，49行的user_task[n]改成 user_task

    我比较懒惰，内核要管理进程根据时间来改变进程优先级，肯定要保存原来的顺序；
   
   但是这个题目没有，所以我就省去一步；
   
   如果要保持顺序，就加个key。

draytek58

1. #include <stdio.h>
   
2. 
   
3. void scheduler(const int task[], int n, int system_task[], int user_task[])
   
4. {
   
5.         int i, j, k, p, q;
   
6. 
   
7.         p = q = 0;
   
8. 
   
9.         for (i = 0; i < n; ++i)
   
10.                 if (task[i] < 50) {
    
11.                         for (j = 0; j < p && task[system_task[j]] < task[i]; ++j);
    
12.                         for (k = p; k > j; --k)
    
13.                                 system_task[k] = system_task[k - 1];
    
14.                         system_task[j] = i;
    
15.                         ++p;
    
16.                 } else if (task[i] <= 255) {
    
17.                         for (j = 0; j < q && task[user_task[j]] < task[i]; ++j);
    
18.                         for (k = q; k > j; --k)
    
19.                                 user_task[k] = user_task[k - 1];
    
20.                         user_task[j] = i;
    
21.                         ++q;
    
22.                 }
    
23.        
    
24.         system_task[p] = user_task[q] = -1;
    
25. }
    
26. 
    
27. int main(void)
    
28. {
    
29.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99};
    
30.         size_t n = sizeof(task) / sizeof(unsigned int);
    
31.         int system_task[n], user_task[n], i;
    
32. 
    
33.         scheduler(task, n, system_task, user_task);
    
34. 
    
35.         for (i = 0; i < n; ++i)
    
36.                 printf("%d ", task[i]);
    
37.         printf("\n");
    
38. 
    
39.         for (i = 0; system_task[i] != -1; ++i)
    
40.                 printf("%d ", system_task[i]);
    
41.         printf("%d\n", system_task[i]);
    
42. 
    
43.         for (i = 0; user_task[i] != -1; ++i)
    
44.                 printf("%d ", user_task[i]);
    
45.         printf("%d\n", user_task[i]);
    
46. 
    
47.         return 0;
    
48. }
    

复制代码

调试用 gdb 就得了，不必printf

时间看来

回复 14# draytek58


嗯，用插入排序。
不过“for (j = 0; j < p && task[system_task[j]] < task; ++j);”，用<的话，相同优先级的进程会产生点小问题。把task[]里优先级相同的，且先出现的，排到了system_task[]， user_task[]的后面去了。