1. 题目描述

现有n个数,从中任选k个数,打印所有可能的选取方法的k个数的和

2. 解题

用两种方法来解这个题,不过都是递归。

第一种方法比较直观,比较符合人的思路。从n个数中选k个数,那就把n个数从前往后一个数一个数的考虑,第一个数选和不选分两种情况,每种情况都往后递归,然后第二个数也分选和不选两种情况,注意往后递归的时候如果选了这个数k就要减1,没选这个数k就不用减1。而每往后递归一次n就要减1。然后就是边界条件的设定,有两个,一个是k等于0了,就说明这一个分支已经选够了k个数,直接打印就行了。还有一个边界条件是现在n的值等于k了,说明前面的元素选的比较少,我还需要k个元素但现在就只剩k个元素了,所以后面的k个元素必须都选上,一个循环全加起来然后输出就行了。

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

// 现有n个数,从中任选k个数求和,打印所有可能的选取方法的和

void NSelectK_1(int* arr, int n, int k, int sum) {
    if (k == n) {  // 如果还差k个数,而数组剩余元素个数n=k,就把剩余n个元素全加起来
        for (int i = 0; i < n; i++) {
            sum += arr[i];
        }
        printf("---%d\n", sum);
        return;
    }

    if (k == 0) {  // 如果k=0说明当前的sum就是k个数的和
        printf("---%d\n", sum);
        return;
    }

    NSelectK_1(arr + 1, n - 1, k, sum);
    NSelectK_1(arr + 1, n - 1, k - 1, sum + *arr);
}

int main() {
    int n, k;

    printf("n:");
    scanf("%d", &n);
    printf("k:");
    scanf("%d", &k);

    int* arr = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    NSelectK_1(arr, n, k, 0);

    system("pause");
    return 0;
}

第二种方法稍有不同,可以想到对于第一种方法来说,相当于一个数一个数的分情况,选和不选,然后选够k个数就打印。而第二种方法相当于只选k次数,每次必选一个,只用区分每一次选在哪。具体还是看代码把:

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

// 现有n个数,从中任选k个数求和,打印所有可能的选取方法的和

void NSelectK_2(int* arr, int n, int k, int sum, int start) {
    int i;
    if (k == 0)
    {
        printf("%d\n", sum);
        return;
    }
    for (i = start; i < n; i++)
    {
        NSelectK_2(arr, n, k - 1, sum + arr[i], i + 1);
    }
}

int main() {
    int n, k;

    printf("n:");
    scanf("%d", &n);
    printf("k:");
    scanf("%d", &k);

    int* arr = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    NSelectK_2(arr, n, k, 0, 0);

    system("pause");
    return 0;
}
Last modification:November 10th, 2019 at 10:21 am