请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

C语言的组合算法

2023-07-13

文件名称 C_SF_combination.c ,源代码如下:

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

/**
 * arr  源数据。
 * n  arr的长度。
 * start  arr的当前递归开始位置。
 * res  组合结果存放数据。
 * m  res的长度。
 * index  当前要写入res的位置。
 */
void recursion(int *arr, int n, int start, int *res, int m, int index);

// 简介:  组合算法。
// 参考来源:  https://wenku.baidu.com/view/967f37ef4328915f804d2b160b4e767f5acf8022  。
int main(void)  
{
    int n = 0, m = 0;
    printf("请输入数据的长度N (N>0) : ");
    scanf("%d", &n);
    printf("你输入一个组合的数据长度m (0<m<=N) : ");
    scanf("%d", &m);

    if (n<=0 || m<=0 || m>n) {
        printf("输入的数值不合理\n");
        return -1;
    }

    // 初始化。
    int arr[n];
    for (int i=0; i<n; i++) {
        arr[i] = (i + 1);
    }
    int res[m];
    memset(res, 0, sizeof(res));

    // 递归调用。
    recursion(arr, n, 0, res, m, 0);

    return 0;
}

// 递归。
void recursion(int *arr, int n, int start, int *res, int m, int index) {
    if (index == m) {
        // 遍历输出。
        for (int i=0; i<m; i++) {
            printf("%d", res[i]);
        }
        printf("\n");
    } else {
        // (m-index) 表示组合当前还需要填充的个数。
        for (int i=start; i<=n-(m-index); i++) {
            // 针对当前index, 遍历剩余可用的数填充递归。
            res[index] = arr[i];
            recursion(arr, n, i+1, res, m, index+1);
        }
    }
}

// "n=4 且 m=3" 的推演过程:                       
// arr = [ 1  2  3  4 ];
// res = [ 0  0  0 ];
//  
// - - - index=0 start=0 i=start=0
// 1  0  0  
//      - - - index=1 start=1 i=start=1
//      1  2  0  
//          - - - index=2 start=2 i=start=2
//          1  2  3  
//              - - - index=3 start=3
//              打印数据。
//          - - - index=2 start=2 i=start+1=3
//          1  2  4  
//              - - - index=3 start=3
//              打印数据。
//          - - - index=2 start=2 i=start+2=4
//          条件 i<=n-(m-index) 不成立而结束循环。
//      - - - index=1 start=1 i=start+1=2
//      1  x(/2)  x(/4) -> 1  3  x(/4)   ~ [注: 小括号里面的数据是前面留下的缓存数据] 。
//          - - - index=2 start=3 i=start=3
//          1  3  4  
//              - - - index=3 start=3
//              打印数据。
//          - - - index=2 start=2 i=start+1=3
//          条件 i<=n-(m-index) 不成立而结束循环。 
//      - - - index=1 start=1 i=start+2=3
//      条件 i<=n-(m-index) 不成立而结束循环。
//
//
// - - - index=0 start=0 i=start+1=1
// x(/1)  x(/3)  x(/4) -> 2  x(/3)  x(/4)
//      - - - index=1 start=2 i=start=2
//      2  3  x(/4)
//          - - - index=2 start=3 i=start=3
//          2  3  4
//              - - - index=3 start=4
//              打印数据。
//          - - - index=2 start=3 i=start+1=4
//          条件 i<=n-(m-index) 不成立而结束循环。
//      - - - index=1 start=2 i=start+1=3
//      条件 i<=n-(m-index) 不成立而结束循环。
//
//
// - - - index=0 start=0 i=start+2=2
// 条件 i<=n-(m-index) 不成立而结束循环。
//
//

// 参考来源: https://wenku.baidu.com/view/967f37ef4328915f804d2b160b4e767f5acf8022

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部