首页 > 代码库 > Lotto(DFS处理)

Lotto(DFS处理)


题目再现

题目内容:
给定N个数字,再从中选定M个数字出来。
将每一种组合内的数字由小到大排列之后,
将全部组合依照字典序排列。
请你找出第X组的第Y个数字。
给定的数字为1~N。
范例1 (N,M,X,Y) = (5,2,8,2)
全部组合按顺序排列为:
    (1 2), (1 3), (1 4), (1 5), (2 3),
    (2 4), (2 5), (3 4), (3 5), (4 5)
所以第8组第2个数字为4。

输入格式: 第一行有一个数字T代表有多少组測资。 每一组測资有一行, 第一行四个数字N、M、X、Y, 意义如题目所述。 測资范围: T < 1000 1 < N < 12 1 < M < N 0 < X <= C(N, M) 0 < Y <= N 输出格式: 对于每一笔測资,找出第X组第Y个数字。

将全部測资的答案加总后再输出。 输入例子: 2 5 2 8 2 6 3 7 3 输出例子: 10 时间限制:500ms内存限制:32000kb


算法实现

这个题能够通过DFS获取全部的序列,通过box数组记录序列信息,在获取序列的时候使用计数器推断须要找的位置。

#include <stdio.h>
#include <string.h>

int book[12], box[12];
int times;
long long sum = 0;

void dfs(int step, int n, int m, int x, int y){
    int i;

    if(step >= m){

        times ++;
        if(times == x){
            sum += box[y - 1];
        }
        return;
    }

    for(i = 1; i <= n; i ++){
        if(book[i - 1] == 0){
            if(step >= 1 && box[step - 1] > i){
                continue;
            }
            box[step] = i;
            book[i - 1] = 1;
            dfs(step + 1, n, m, x, y);
            book[i - 1] = 0;
        }
    }
}

int main(){
    int T;
    int N, M, X, Y;

    scanf("%d", &T);
    while(T --){
        memset(book, 0, sizeof(book));
        times = 0;
        scanf("%d %d %d %d", &N, &M, &X, &Y);
        dfs(0, N, M, X, Y);
    }

    printf("%lld", sum);

    return 0;
}

拓展阅读

小谈深度优先搜索


博客名称:王乐平博客

博客地址:http://blog.lepingde.com

CSDN博客地址:http://blog.csdn.net/lecepin


技术分享

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

Lotto(DFS处理)