百度到一个好玩的，给大家分享一下

yangxf1217

百度到一个好玩的，给大家分享一下 [复制链接]

“五个程序员开发五个模块，每个人开发不同模块的效率不同，如何分配才能保证效率最高，请用程序写出来。”
这是c语言笔试题，如何实现呢？

小杜锅锅

够高深的了，要想想、、、、

yangxf1217

嗯，好好想想。蛮有意思的题目。

yangxf1217

没人感兴趣吗？还是都不会闹

yangxf1217

我初步设想建立五个数组M1[5]，M2[5]，M3[5]，M4[5]，M5[5]表示5个人；
数组的 M[0]-M[4]   5个位置分别表示五个人对1-5个模块的效率；
找出效率最高的排列；
效率最高当然要求，总的时间最短前提下。每个程序员花费时间也最短。
接下来怎么搞呢？

yangxf1217

对这25个数进行排序，然后从小到大，先判断前五个有没有不重合的人的5个数，如果没有有，再判断前6个有没有不重合的人的五个数；直到第一次找到不重合人的5个数为止。



快沉了，有人看没人顶。

yangking91

会有25个数中都没有不同人的5个数的情况，找不到怎么办？

yangking91

最理想的情况是5个人用时最短的模块都不同，分5种情况讨论，用枚举出所有的情况

walkwk

#include
#include

#define PROGRAMMER_NUMBER 5
#define        TASK_NUMBER 5
#define MAX_TIME 255
#define MAX_NUMBER(a,b) (a>b?a:b)

typedef enum {FALSE,TRUE} BOOL;

int Efficiency[PROGRAMMER_NUMBER][TASK_NUMBER]={{1,2,3,4,5},
                                                                                                {2,3,4,5,6},
                                                                                                {3,4,5,6,7},
                                                                                                {4,5,6,7,8},
                                                                                                {8,6,7,8,9}};

BOOL IsTaskSelected[TASK_NUMBER];

int main(int argc, char *argv[]) {
        int task_index;
        int programmer_index;
        for(task_index=0;task_index                 IsTaskSelected[task_index]=FALSE;
        printf("The least time is %d\n",SearchStep(0));
        return 0;
}

int SearchStep(int Step_index)                                //Return the best choice in each step
{
        int best_choice=MAX_TIME;
        int result;
        int task_index;
        if (Step_index         {
                for(task_index=0;task_index                 {
                        if(IsTaskSelected[task_index]==FALSE)
                        {
                                IsTaskSelected[task_index]=TRUE;
                                result=MAX_NUMBER(SearchStep(Step_index+1),Efficiency[Step_index][task_index]);
                                if(best_choice>result)
                                        best_choice=result;
                                IsTaskSelected[task_index]=FALSE;
                        }
                }
                return best_choice;
        }
        else
        {
                for(task_index=0;task_index                         if(IsTaskSelected[task_index]==FALSE)
                                return Efficiency[Step_index][task_index];                       
        }       
}

yangxf1217

原帖由 yangking91 于 2013-10-11 20:55 发表
最理想的情况是5个人用时最短的模块都不同，分5种情况讨论，用枚举出所有的情况

5个人用时最短的模块都不同,这个太特殊了，
5种情况是哪5种呢。

yangxf1217

原帖由 walkwk 于 2013-10-12 09:20 发表
#include
#include

#define PROGRAMMER_NUMBER 5
#define        TASK_NUMBER 5
#define MAX_TIME 255
#define MAX_NUMBER(a,b) (a>b?a:b)

typedef enum {FALSE,TRUE} BOOL;

int Efficiency[PROGRAMMER_NUM ...

没看明白，先干会活，待会再研究研究

exiao

paixuwenti

huo_hu

什么问题没看懂?
五个人的模块必需全部执行吗?
模块间无顺序无依赖吗?
并行调度还是分时调度?

yangxf1217

原帖由 huo_hu 于 2013-10-12 13:23 发表
什么问题没看懂?
五个人的模块必需全部执行吗?
模块间无顺序无依赖吗?
并行调度还是分时调度?

版主大人你好犀利啊！

我没看懂那个程序的流程。
五个模块都要做完。
模块间无顺序无依赖。
五个人可以同时干活。

请赐教！

yangxf1217

好像没那么简单啊

yangxf1217

高手，能简单谈下你的流程吗？小弟实在看不明白。

walkwk

总共5个人，5个任务，数组里存的是每个人完成不同任务需要的时间，因为同时开始做，所以整个项目完成的时间取决于花最多时间的那个人。所以任务是，找到一个排列，使每个任务都得到完成，并且最大时间尽可能短。

函数意义是对Step_index对应的员工进行任务分配，使得最大时间最短。方法是比对Step_index+1的结果和自己当前选择项目所需时间取最大，然后比较自己选择不同任务，选择时间最小的返回

walkwk

有种感觉，这个算法不是最优的，在自己i3的电脑上奔了3秒，如果有其他的算法可以提出

yangxf1217

高手。我看明白你的分析了，表示赞同。
          但我没看明白你的程序，感觉是我两在下象棋，我看出2步，你看出5步，结果很伤感啊。
      这个程序到底是不是最优化，真心没有能力去判断了。

我是做硬件的 求自我宽恕

yangxf1217

改天有空再想想你的程序，现在实在是不行了，想的深了就会出现一堆星星