2008-KooXoo-NKU-笔试-3

2007.10.30.晚上，NKU的笔试考题，我因为人太多，未参加笔试，题目是后来BBS上看到的。

 

题目大致如此：

Kooxoo每个月招聘1-6人，问一年(12个月)招聘人数刚好是55的概率。

 

类似题目联想：

《程序员面试宝典》在循环，递归那章讲了一个类似的题目，问一个人打靶，连开x枪打中y环的概率是多少。

 

问题思路：

遍历+减枝，设计良好的出口。

 

问题解答：计算出所有可能的解有多少个。用count/6^12即可得出概率。

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 12 //size of problem

#define SUM 55
#define MIN_NUM 1
#define MAX_NUM 6

int result[MAX_SIZE]; //save one result
long long int count = 0;

void show_result()
{
    int i;
    for(i = 0; i < MAX_SIZE; i ++)
        printf("%d ", result[i]);
    printf("\n");
}

void check(int left_sum, int left_size)
{
    if((left_sum < left_size) || (left_sum < MIN_NUM) || (left_sum > left_size*MAX_NUM))
        return;
    if(left_size == 1 && left_sum > MAX_NUM)
        return;
    if(left_size == 1)
    {
        result[left_size-1] = left_sum;
        //show_result();

        count ++;
    }
    else
        int i;
        for(i = MAX_NUM; i >= MIN_NUM; i --)
        {
            result[left_size-1] = i;
            check(left_sum - i, left_size - 1);
        }
    }
}
int main()
{
    check(SUM, MAX_SIZE);
    printf("All %lld results\n", count);
    return 1;
}