救命！某大公司程序员笔试题！答中有重奖！超难算法

Question

zeroleonhart(莱昂哈特) 老兄,你说的方法我也用过了,最后不是有人多拿了.就是有人不够.这个问题决不是那么简单的,不然别人不会拿这个来问我的

Answer 1

我的算法的结果：
一年级：c,d,e,h,i,b,a,f,g每人一个，每种水果200个
二年级：c,d,j,e,h,i,b,a每人一个，每种水果100个
五年级：c,d,j,e,h,i每人一个，每种水果200个
三年级：b,f,g,a,c每人一个,每种水果200个
六年级：d200,j200,e150+a50,b100+f100，d,j每人一个，另外两种水果在e和a，b和f之间选择
四年级：g,h,i每人一个，每种水果100个，至此全部发完

Answer 2

zeroleonhart(莱昂哈特) 的方法已经符合要求了，不知道楼主还有什么要求？
a   b   c   d   e   f   g   h   i   j
550 600 700 700 650 500 500 600 600 5001 200 9
2 100 8
3 200 5
4 100 3
5 200 6
6 200 4c   d   e   h   i   b   a   f   g   j   年级
700 700 650 600 600 600 550 500 500 500
500 500 450 400 400 400 350 300 300 500 1
j   c   d   e   h   i   b   a   f   g
500 500 500 450 400 400 400 350 300 300
400 400 400 350 300 300 300 250 300 300 2
j   c   d   e   h   i   b   f   g   a
400 400 400 350 300 300 300 300 300 250
200 200 200 150 100 300 300 300 300 250 3
i   b   f   g   a   j   c   d   e   h
300 300 300 300 250 200 200 200 150 100
200 200 200 300 250 200 200 200 150 100 4
g   a   i   b   f   j   c   d   e   h
300 250 200 200 200 200 200 200 150 100 
100 50  0   0   0   0   200 200 150 100 5
c   d   e   h   g + a   i + b + f   j
200 200 200 200 100 100 100 50 50   0
0   0   0   0   0   0   0   0   0   0   6

Answer 3

估计他要的是程序不是算法...
这段程序是最最最土的。但一样能得出结果
$food=array(
'a'=>550,
'b'=>600,
'c'=>700,
'd'=>700,
'e'=>650,
'f'=>500,
'g'=>500,
'h'=>600,
'i'=>600,
'j'=>500
);
$student=array();
function get_food($index)
{
global $student,$food;
//该拿几个
if($index<200) $num=9;
elseif($index<300) $num=8;
elseif($index<500) $num=5;
elseif($index<600) $num=3;
elseif($index<800) $num=6;
else $num=4;

foreach($food as $k=>$v){
if($v>0){
$food[$k]--;
$student[$index].=$k;
$num--;
if($num==0) break;
}
}
while($num>0){
for($i=0;$i<$index;$i++){
foreach($food as $k=>$v){
if($v>0 && false===strpos($student[$i],$k)){
for($j=0;$j<strlen($student[$i]);$j++){
if(false===strpos($student[$index],$student[$i][$j])){
$student[$index].=$student[$i][$j];
$student[$i]=substr($student[$i],0,$j).substr($student[$i],$j+1).$k;
$food[$k]--;
$num--;
break 3;
}
}
}
}
}
}
}for($i=0;$i<1000;$i++){
get_food($i);
}
foreach($student as $k=>$v){
echo sprintf("%04d",$k+1).":{$v}<br>";
}
exit;

Answer 4

问题最大的难点在于 ：到最后出现这样的情况，其中某水果没了，某水果还很多。
导致某人拿同一水果。解决办法：相信每个小朋友都是聪明的，他们会按照以下方法去取水果。
原则一：从最多的水果开始挑选。
原则二：每人要求个数少的优先挑选。具体实现：
排列水果 从多到少：  sortapple()
悠闲挑选水果顺序：  3 4 5 6 8 9
算法时间： (1000)*(200*9+100*8+200*5+100*3+200*6+200*4) = 100万次
算法优化： sortapple()函数 个人认为还有更好的办法。
poyi_820921() 是不是去笔面试 ：）

Answer 5

我觉得要是没要求运行时间 Gdj的那段最土的代码 就行`````````

Answer 6

同意Hylas(羽心)的观点
原则一：优先拿剩下的水果数多的
原则二：让要求分到水果种类多的学生先拿。个人感觉算法时间不会有百万级那么大，应该是1000*（10个数排序的算法时间）

Answer 7

DEMO地址，http://www.mit9.com/fp.rar
任一指定班级人数，任一指定班每人应该分得水果数，任一指定每种水果数目
欢迎各位同僚指点一二

Answer 8

atwdsgood(东流水) ,你做做就知道有意思了

Answer 9

TO:Hylas(羽心)
同意你嘀观点，，但有一点跟你有点差别
解决办法：相信每个小朋友都是聪明的，他们会按照以下方法去取水果。
原则一：从最多的水果开始挑选。
原则二：个数要求多嘀年级优先挑选。具体实现：
排列水果 从多到少：  sortapple()
个数要求多嘀年级挑选，挑一次sorapple()一次，保证不出现剩下嘀水果品种不能满足年级要求嘀个数
悠闲挑选水果顺序：  9，8，6，5，4，3
算法时间：约为 M（学生人数）*N（水果种类数）

Answer 10

C++的代码：#include <iostream.h>#define FRUIT_KINDS 10
#define GRADES 6void fruit_order(int);int grade_students[GRADES]={200,100,200,100,200,200};
int grade_fruits[GRADES]={9,8,5,3,6,4};char fruit_name[FRUIT_KINDS]={'a','b','c','d','e',
        'f','g','h','i','j'};
int fruits[FRUIT_KINDS]={550,600,700,700,650,
        500,500,600,600,500};
int main()
{    int temp;//水果的数量先排序 
    int k=FRUIT_KINDS-1;
    for (int i=0;i<k;i++) {
        for(int j=i+1;j<FRUIT_KINDS;j++) {
                if (fruits[i]<fruits[j]) {
                   temp=fruits[i];
                   fruits[i]=fruits[j];
                   fruits[j]=temp;
                   temp=fruit_name[i];
                   fruit_name[i]=fruit_name[j];
                   fruit_name[j]=temp;
                }
        }
    }
                   
    //output
            for (k=0;k<FRUIT_KINDS;k++) {
                cout<< fruit_name[k] <<":" << fruits[k] << ",";
                }
            cout << endl;
            
    
//外循环是年级，内循环是人数，里面第三层循环是每年级可拿的水果数  
    for(int i=0;i<GRADES;i++) {
            
            k=grade_fruits[i]-1;            for (int j=0;j<grade_students[i];j++) {
                for (int x=0;x<=k;x++) {
                    fruits[x]--;
                    }
                fruit_order(grade_fruits[i]);                    
            }
            
            //output
            for (k=0;k<FRUIT_KINDS;k++) {
                cout<< fruit_name[k] <<":" << fruits[k] << ",";
                }
            cout << endl;
    }    
}
void fruit_order(int bs)
{
     int i,j,temp;
     
     for (i=bs-1;(i>=0) && (fruits[i]<fruits[i+1]);i--) {
           for(j=FRUIT_KINDS-1;j>=i+1;j--) 
           {
            if (fruits[i]<fruits[j])
            {
               temp=fruits[i];
               fruits[i]=fruits[j];
               fruits[j]=temp;
               temp=fruit_name[i];
               fruit_name[i]=fruit_name[j];
               fruit_name[j]=temp;
            }
           }
     }
}          执行结果：
c:700,d:700,e:650,b:600,h:600,i:600,a:550,f:500,g:500,j:500, //未拿时
c:500,d:500,e:450,b:400,h:400,i:400,j:363,g:363,a:362,f:362, //一年级拿后
c:400,d:400,e:350,h:308,j:307,g:307,a:307,f:307,i:307,b:307, //二年级拿后
c:230,d:230,a:230,g:230,h:230,e:230,b:230,i:230,j:230,f:230, //三年级拿后
j:200,f:200,d:200,c:200,g:200,a:200,b:200,i:200,h:200,e:200, //四年级拿后
d:80,c:80,g:80,a:80,j:80,f:80,b:80,i:80,h:80,e:80, //五年级拿后
d:0,c:0,g:0,a:0,j:0,f:0,b:0,i:0,h:0,e:0, // 六年级都给拿光了