華為2011校園招聘上機(jī)題目（華南和成都）一組 第三題

時(shí)間看來

在上一貼中“2012華為杯 西南賽區(qū) 初試第三題”說了GDB不少壞話。在看了《GDB調(diào)試程序[陳皓]》后，決定再找些題目試試。

歡迎任何評(píng)論！

3.操作系統(tǒng)任務(wù)調(diào)度問題。操作系統(tǒng)任務(wù)分為系統(tǒng)任務(wù)和用戶任務(wù)兩種。其中，系統(tǒng)任務(wù)的優(yōu)先級(jí) < 50，用戶任務(wù)的優(yōu)先級(jí) >= 50且 <= 255。優(yōu)先級(jí)大于255的為非法任務(wù)，應(yīng)予以剔除�，F(xiàn)有一任務(wù)隊(duì)列task[]，長(zhǎng)度為n，task中的元素值表示任務(wù)的優(yōu)先級(jí)，數(shù)值越小，優(yōu)先級(jí)越高。函數(shù)scheduler實(shí)現(xiàn)如下功能，將task[] 中的任務(wù)按照系統(tǒng)任務(wù)、用戶任務(wù)依次存放到 system_task[] 數(shù)組和 user_task[] 數(shù)組中（數(shù)組中元素的值是任務(wù)在task[] 數(shù)組中的下標(biāo)），并且優(yōu)先級(jí)高的任務(wù)排在前面，數(shù)組元素為-1表示結(jié)束。
例如：task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99}
      system_task[] = {0, 3, 1, 7, -1}
      user_task[] = {4, 8, 2, 6, -1}

函數(shù)接口
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處理函數(shù)
    
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數(shù)組中的數(shù)據(jù)順序沒有變化。
    
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.     }

復(fù)制代碼

總結(jié)：
看到一個(gè)師弟對(duì)這個(gè)三道題目的評(píng)價(jià)“其實(shí)就是邏輯思維，根本不涉及庫函數(shù)算法神馬的。。�！�
嗯，對(duì)于我來說，著重練習(xí)的是邏輯思維，GDB調(diào)試。

編這三個(gè)練習(xí)的時(shí)候我感覺到比華為杯2012西南賽區(qū)初賽題目要順手一些。特別是對(duì)于調(diào)試也“身”有體會(huì)了。看了《GDB調(diào)試程序[陳皓]》后，感覺原來GDB還不錯(cuò)。同時(shí)，也喜歡上了在程序中加上條件編譯，這樣調(diào)試程序就更方便了。目前我的調(diào)試前后的時(shí)間各占了一半，我還會(huì)做得更好的。

喜歡GDB的打印數(shù)組 p *task_ptr[0]@9 。開始對(duì)這個(gè)的理解錯(cuò)誤，運(yùn)行結(jié)果讓我匪夷所思。原來
p task_ptr[0]@9 才是打印排了序的指針。但顯示的是指針，不容易閱讀。此時(shí)，我想起了條件編譯，感覺不錯(cuò)。

在第三個(gè)練習(xí)中，用了指針數(shù)組，用得還不太熟悉。（暫且忽略解決方法的好壞~）盡管看書的時(shí)候，指針的應(yīng)用都能理解，但和自己動(dòng)手相比差別還是大。

lqfhvk357

我也寫了個(gè)...

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]<<"：此任務(wù)為非法任務(wù)！"<<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<<"請(qǐng)輸入十個(gè)整數(shù)："<<endl;
    
66.         for(i=0; i<N; i++)
    
67.                 cin>>a[i];
    
68.         scheduler(a, N, b, c);
    
69.         return 0;
    
70. }
    

復(fù)制代碼

walleeee

優(yōu)先級(jí)相同，這個(gè)時(shí)候又有另外一些要考慮的，比如是否序列穩(wěn)定。

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. }

復(fù)制代碼

大概寫了下，不過沒考慮題目要求
另外，那個(gè)多級(jí)映射，看不懂就算了，其實(shí)該用多維線性表，我用數(shù)組方便了
核心代碼就是scheduler函數(shù)

cokeboL

要我寫的話，先計(jì)數(shù)排序把task理順了然后一次遍歷放到兩個(gè)task里。4N的時(shí)間復(fù)雜度

時(shí)間看來

回復(fù) 2# lqfhvk357


嗯，測(cè)試通過！
思想是：先把任務(wù)分類，再排序。時(shí)間復(fù)雜度我沒有計(jì)算
Tips：
編程的風(fēng)格還需要注意下：比如 = 左右兩邊的的空格 是否需要？
在CU中有帖代碼行的HTML標(biāo)簽 “<>”，不然程序貼出來有的內(nèi)容可能改變。

我嘗試將元素改成254個(gè)，將程序運(yùn)行100遍。來分析這三個(gè)程序的運(yùn)行時(shí)間，到目前為止都顯示的0.01秒。
非常感謝您的時(shí)間！

時(shí)間看來

回復(fù) 4# walleeee


嗯，看懂了。
數(shù)組第一個(gè)元素用于計(jì)數(shù)……
同一個(gè)優(yōu)先級(jí)的一個(gè)隊(duì)列/線性表……

看過內(nèi)核的就是不一樣~

我嘗試將元素改成254個(gè)，將程序運(yùn)行100遍。來分析這三個(gè)程序的運(yùn)行時(shí)間，到目前為止都顯示的0.01秒。
非常感謝您的時(shí)間！

時(shí)間看來

回復(fù) 5# cokeboL


時(shí)間復(fù)雜度，我還沒有考慮哦~

這三個(gè)程序的時(shí)間復(fù)雜度，可能大牛一眼就看出來了。我還達(dá)不到

睡覺了，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. }

復(fù)制代碼

e,3n+255

lqfhvk357

回復(fù) 9# cokeboL