免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 5269 | 回复: 14

华为2011校园招聘上机题目(华南和成都)一组 第三题 [复制链接]

论坛徽章:
0
发表于 2012-05-26 11:59 |显示全部楼层
在上一贴中“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.     #define DEBUG 0

  4.     void scheduler(int task[], int n, int system_task[], int user_task[]);

  5.     int
  6.     main(int argc, char *argv[])
  7.     {
  8.         int n, i, j;
  9.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99};
  10.         n = sizeof(task) / sizeof(int);
  11.         int system_task[n];
  12.         int user_task[n];

  13.         scheduler(task, n, system_task, user_task);

  14.         printf("\ntask[] is :\n");
  15.         for(i = 0; i < n; i++){
  16.             printf("%d ", task[i]);
  17.         }
  18.         
  19.         printf("\n\nsystem_task[] is :\n");
  20.         for(i = 0; i < n && system_task[i] != -1; i++){
  21.             printf("%d ", system_task[i]);
  22.         }
  23.         printf("%d",system_task[i]);
  24.         
  25.         printf("\n\nuser_task[] is :\n");
  26.         for(i = 0; i < n && user_task[i] != -1; i++){
  27.             printf("%d ", user_task[i]);
  28.         }
  29.         printf("%d", user_task[i]);
  30.         printf("\n");

  31.     }

  32.     /*
  33.      *scheduler处理函数
  34.      */
  35.     void
  36.     scheduler(int task[], int n, int system_task[],int user_task[])
  37.     {
  38.         int i, j, min_val;
  39.         int min_in_task_ptr;
  40.         int *fill_ptr;
  41.         int *task_ptr[n];
  42.         int **tmp_ptr_ptr;

  43.         for(i = 0; i < n; i++){
  44.             task_ptr[i] = &task[i];
  45.         }

  46.         /*将task_ptr[]从小到大的排列*/
  47.         for(i = 0; i < n; i++){
  48.             min_val = *task_ptr[i];
  49.             min_in_task_ptr = i;
  50.             fill_ptr = task_ptr[i];

  51.             /*寻找task_ptr后面的最小值和它的指针*/
  52.             for(j = i; j < n; j++){
  53.                 if(*task_ptr[j] < min_val){
  54.                     min_val = *task_ptr[j];
  55.                     min_in_task_ptr = j;
  56.                 }
  57.             }
  58.     #if DEBUG
  59.             printf("min_val:%d min_ptr:%d ", min_val, *task_ptr[min_in_task_ptr]);
  60.             printf("min_ptr-task:%d\n", min_in_task_ptr);
  61.     #endif

  62.             /*交换指针*/
  63.             task_ptr[i] = task_ptr[min_in_task_ptr];
  64.             /*min_ptr-task怎么和我期望的有差距呢?
  65.              * 哦,task数组中的数据顺序没有变化。
  66.              * */
  67.             //task_ptr[i] = task_ptr[min_ptr - task];
  68.             task_ptr[min_in_task_ptr] = fill_ptr;
  69.     #if DEBUG
  70.             printf("%d\ttask_ptr[] is :", i);
  71.             for(j = 0; j < n; j++){
  72.                 printf("%d ", *task_ptr[j]);
  73.             }
  74.             printf("\n");
  75.     #endif

  76.         }

  77.         int count_sys = 0;
  78.         int count_user = 0;

  79.         for(i = 0; i < n; i++){
  80.             if(*task_ptr[i] < 50){
  81.                 system_task[count_sys] = task_ptr[i] - task;
  82.                 count_sys++;
  83.             } else if(*task_ptr[i] > 255){
  84.                 printf("%d", *task_ptr[i]);
  85.             } else {
  86.                 user_task[count_user] = task_ptr[i] - task;
  87.                 count_user++;
  88.             }
  89.         }
  90.         system_task[count_sys] = -1;
  91.         user_task[count_user] = -1;
  92.     }
复制代码
总结:
看到一个师弟对这个三道题目的评价“其实就是逻辑思维,根本不涉及库函数算法神马的。。。”
嗯,对于我来说,着重练习的是逻辑思维,GDB调试。

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

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

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

论坛徽章:
0
发表于 2012-05-27 12:03 |显示全部楼层
本帖最后由 lqfhvk357 于 2012-05-29 10:46 编辑

我也写了个...
  1. #define N 10

  2. #include <iostream.h>
  3. void scheduler(int task[], int n, int system_task[], int user_task[])
  4. {
  5.         int i, h;
  6.         int k_s, k_u;
  7.         k_s=0, k_u=0;
  8.         for(i=0; i<n; i++)
  9.         {
  10.                 if(task[i]<50)
  11.                 {
  12.                         system_task[k_s++]=i;
  13.                         h=k_s;
  14.                         while(h>1)
  15.                         {       
  16.                                 if(task[system_task[h-1]]<task[system_task[h-2]])
  17.                                 {
  18.                                         system_task[h-1]=system_task[h-1]+system_task[h-2],
  19.                                         system_task[h-2]=system_task[h-1]-system_task[h-2],
  20.                                         system_task[h-1]=system_task[h-1]-system_task[h-2];
  21.                                         h--;
  22.                                 }
  23.                                 else
  24.                                         break;               
  25.                         }
  26.                 }
  27.                 else if(task[i]<=255)
  28.                 {
  29.                         user_task[k_u++]=i;
  30.                         h=k_u;
  31.                         while(h>1)
  32.                         {       
  33.                                 if(task[user_task[h-1]]<task[user_task[h-2]])
  34.                                 {
  35.                                         system_task[h-1]=system_task[h-1]+system_task[h-2],
  36.                                         system_task[h-2]=system_task[h-1]-system_task[h-2],
  37.                                         system_task[h-1]=system_task[h-1]-system_task[h-2];
  38.                                         h--;
  39.                                 }
  40.                                 else
  41.                                         break;               
  42.                         }
  43.                 }
  44.                 else
  45.                         cout<<task[i]<<":此任务为非法任务!"<<endl;
  46.         }
  47.         system_task[k_s]=-1;
  48.         user_task[k_u]=-1;
  49.         cout<<"system_task:"<<endl;
  50.         for(i=0; i<k_s+1; i++)
  51.                 cout<<system_task[i]<<" ";
  52.         cout<<endl<<"user_task:"<<endl;
  53.         for(i=0; i<k_u+1; i++)
  54.                 cout<<user_task[i]<<" ";
  55. }

  56. int main()
  57. {
  58.         int  i;
  59.         int a[N];
  60.         int b[N];
  61.         int c[N];

  62.         cout<<"请输入十个整数:"<<endl;
  63.         for(i=0; i<N; i++)
  64.                 cin>>a[i];
  65.         scheduler(a, N, b, c);
  66.         return 0;
  67. }
复制代码

论坛徽章:
0
发表于 2012-05-27 15:02 |显示全部楼层
优先级相同,这个时候又有另外一些要考虑的,比如是否序列稳定。

论坛徽章:
0
发表于 2012-05-27 17:03 |显示全部楼层
本帖最后由 walleeee 于 2012-05-27 17:05 编辑
  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. // but here i use mutil-level fixed array just for
  6. // convenient. lol :-)

  7. #include <stdio.h>

  8. #define PRIORITY_MIN            0x00000000
  9. #define PRIORITY_MAX            0x000000fe
  10. #define PRIORITY_LEVEL_MAX_PROC 0x0000000f
  11. #define PRIORITY_QUEUE_ROW      PRIORITY_MAX-PRIORITY_MIN+1
  12. #define PRIORITY_QUEUE_COLUMN   PRIORITY_LEVEL_MAX_PROC+1

  13. // switch for reporting error code or just filter/ignore error.
  14. #undef USE_ERROR

  15. // error code.
  16. #define ERROR_OK                    0x00000000
  17. #define ERROR_PRIORITY_OUT_RANGE    0x00000001

  18. int Scheduler(const int *allTask, int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN])
  19. {
  20.     for(int i=0; i<PRIORITY_QUEUE_ROW; ++i)
  21.     {
  22.         priorityQueue[i][0] = 0;
  23.     }

  24.     for(int i=0; allTask[i]!=-1; ++i)
  25.     {
  26.         if(allTask[i]>=PRIORITY_MIN && allTask[i]<=PRIORITY_MAX)
  27.         {
  28.             priorityQueue[allTask[i]][++priorityQueue[allTask[i]][0]] = i;
  29.         }
  30. #ifdef USE_ERROR
  31.         else
  32.         {
  33.             return ERROR_PRIORITY_OUT_RANGE;
  34.         }
  35. #endif
  36.     }

  37.     return ERROR_OK;
  38. }

  39. void DumpPriorityQueue(const int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN], int start, int end, const char *name)
  40. {
  41.     printf("[%s] ", name);
  42.     for(int i=start; i<end; ++i)
  43.     {
  44.         for(int j=1; j<=priorityQueue[i][0]; ++j)
  45.         {
  46.             printf("%d ", priorityQueue[i][j]);
  47.         }
  48.     }
  49.     printf("\n");
  50. }

  51. int main(int argc, char **argv)
  52. {
  53.     int allTask[] = {0, 30, 155, 1, 80, 300, 170, 40, 99, -1};
  54.     int priorityQueue[PRIORITY_QUEUE_ROW][PRIORITY_QUEUE_COLUMN];

  55.     Scheduler(allTask, priorityQueue);

  56.     DumpPriorityQueue(priorityQueue, 0, 50, "sys");
  57.     DumpPriorityQueue(priorityQueue, 50, 256, "usr");

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

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2012-05-27 22:14 |显示全部楼层
要我写的话,先计数排序把task理顺了然后一次遍历放到两个task里。4N的时间复杂度

论坛徽章:
0
发表于 2012-05-28 00:14 |显示全部楼层
本帖最后由 时间看来 于 2012-05-28 00:27 编辑

回复 2# lqfhvk357


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

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

论坛徽章:
0
发表于 2012-05-28 00:21 |显示全部楼层
回复 4# walleeee


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

看过内核的就是不一样~

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

论坛徽章:
0
发表于 2012-05-28 00:23 |显示全部楼层
本帖最后由 时间看来 于 2012-05-28 12:35 编辑

回复 5# cokeboL


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

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

睡觉了,GOOD NIGHT~

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2012-05-29 00:03 |显示全部楼层
本帖最后由 cokeboL 于 2012-05-29 00:04 编辑
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. void task_sort(int task[], int task_num, int max_task_num)
  4. {
  5.         int i, j;
  6.         int *count = (int*)malloc(sizeof(int)*max_task_num);

  7.         for(i=0; i<max_task_num; i++){
  8.                 count[i]=0;
  9.         }

  10.         for(i=0; i<task_num; i++){
  11.                 count[task[i]]++;
  12.         }

  13.         for(i=0, j=0; i<task_num; j++){
  14.                 while( (count[j]-- > 0) && i<task_num ){
  15.                         task[i++] = j;
  16.                 }
  17.         }

  18.         free(count);
  19. }

  20. void Scheduler(int task[], int task_num, int max_task_num, int system_task[], int user_task[])
  21. {
  22.         int i=0, n=0;
  23.         task_sort(task, task_num, max_task_num);
  24.         while(task[n]<50){
  25.                 system_task[n]=n++;
  26.         }
  27.         system_task[n]=-1;
  28.         while(task[n]<=255){
  29.                 user_task[i++]=n++;
  30.         }
  31.         user_task[n]=-1;
  32. }

  33. int main()
  34. {
  35.        
  36.         int task[] = {0, 30, 155, 1, 80, 300, 170, 40, 99},
  37.                 system_task[20],
  38.                 user_task[20];
  39.         Scheduler(task, sizeof(task)/sizeof(int), 300, system_task, user_task);
  40.        
  41.         return 0;
  42. }
复制代码
e,3n+255

论坛徽章:
0
发表于 2012-05-29 10:35 |显示全部楼层
本帖最后由 lqfhvk357 于 2012-05-29 21:19 编辑

回复 9# cokeboL
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP