wsx666946 发表于 2022-6-17 19:47:14

编程求从n数中抽出r个数的所有组合方式 如1234组合为 432 431 421 312

#include<stdio.h>
void Combine(int n,int r,char a[],intb[],int R)
{
        if(r==0)
        {
                int i=0;
                for(i=0;i<R;i++)
                {
                        printf("%c ",a]);
                       
                        }
                printf("\n");
                }
        else
        {
                for(int j=n;j>=r;j--)
                {
                        b=j-1;
                        Combine(j-1,r-1,a,b,R+1);
                        }
                }
        }
int main()
{        int n=5,r=3,R=0;
        char a={1,2,3,4,5};
        int b;
        Combine(n,r,a,b,R);
}
求大佬们帮忙看看哪里不对 怎么输出不了啊{:5_100:}

人造人 发表于 2022-6-17 19:47:15

不，数组c必须初始化
#include <stdio.h>

void Combine(int n, int r, const int a, int b, int c, int R) {
    if(R >= r) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = 0; i < n; ++i) {
      if(c) continue;
      c = 1;
      b = a;
      Combine(n, r, a, b, c, R + 1);
      c = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    int c = {0};
    Combine(n, r, a, b, c, R);
}

人造人 发表于 2022-6-17 20:23:17

#include <stdio.h>

void Combine(int n, int r, char a[], int b[], int R) {
    if(r == 0) {
      int i = 0;
      for(i = 0; i < R; i++) {
            //printf("%c ", a]);
            printf("%hhd ", a]);   // 这里不是%c吧？应该是%hhd吧？
                                        // a数组中的元素类型是signed char
                                        // signed char应该用%hhd
      }
      printf("\n");
    } else {
      // 看不懂你这个for循环是在做什么
      for(int j = n; j >= r; j--) {
            b = j - 1;
            Combine(j - 1, r - 1, a, b, R + 1);
      }
    }
}

int main() {
    int n = 5, r = 3, R = 0;
    char a = {1, 2, 3, 4, 5};
    int b;
    Combine(n, r, a, b, R);
}



是要下面这样的效果吗？
#include <stdio.h>

void Combine(int n, int r, const int a, int b[], int c[], int R) {
    if(R >= r) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = 0; i < n; ++i) {
      if(c) continue;
      c = 1;
      b = a;
      Combine(n, r, a, b, c, R + 1);
      c = 0;
    }
}

int main() {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    int c = {0};
    Combine(n, r, a, b, c, R);
}


$ ./main
1 2 3
1 2 4
1 2 5
1 3 2
1 3 4
1 3 5
1 4 2
1 4 3
1 4 5
1 5 2
1 5 3
1 5 4
2 1 3
2 1 4
2 1 5
2 3 1
2 3 4
2 3 5
2 4 1
2 4 3
2 4 5
2 5 1
2 5 3
2 5 4
3 1 2
3 1 4
3 1 5
3 2 1
3 2 4
3 2 5
3 4 1
3 4 2
3 4 5
3 5 1
3 5 2
3 5 4
4 1 2
4 1 3
4 1 5
4 2 1
4 2 3
4 2 5
4 3 1
4 3 2
4 3 5
4 5 1
4 5 2
4 5 3
5 1 2
5 1 3
5 1 4
5 2 1
5 2 3
5 2 4
5 3 1
5 3 2
5 3 4
5 4 1
5 4 2
5 4 3
$

人造人 发表于 2022-6-17 20:25:07

#include <stdio.h>

void Combine(int n, int r, const int a, int b, int c, int R) {
    if(R >= r) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = 0; i < n; ++i) {
      if(c) continue;
      c = 1;
      b = a;
      Combine(n, r, a, b, c, R + 1);
      c = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    int c = {0};
    Combine(n, r, a, b, c, R);
}

人造人 发表于 2022-6-17 20:29:13

再改一下

#include <stdio.h>

void Combine(int n, int r, const int a, int b, int c, int R) {
    if(R >= r) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = 0; i < n; ++i) {
      if(c) continue;
      c = 1;
      b = a;
      Combine(n, r, a, b, c, R + 1);
      c = 0;
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    int c;
    Combine(n, r, a, b, c, R);
}

wsx666946 发表于 2022-6-17 20:40:43

人造人 发表于 2022-6-17 20:32
不，数组c必须初始化

我明白了是因为我定义字符数组的时候定义错了，应该是char a={'1','2','3','4','5'}; 或者char a="12345";

wsx666946 发表于 2022-6-17 20:42:07

人造人 发表于 2022-6-17 20:23
是要下面这样的效果吗？

我第二个循环是用数组b来存储组合数中每个数字在待组合数数组a中的下标

人造人 发表于 2022-6-17 20:50:04

wsx666946 发表于 2022-6-17 20:42
我第二个循环是用数组b来存储组合数中每个数字在待组合数数组a中的下标

那么这5个数选3个进行组合，结果是什么？
12345

这个？
$ ./main
1 2 3
1 2 4
1 2 5
1 3 2
1 3 4
1 3 5
1 4 2
1 4 3
1 4 5
1 5 2
1 5 3
1 5 4
2 1 3
2 1 4
2 1 5
2 3 1
2 3 4
2 3 5
2 4 1
2 4 3
2 4 5
2 5 1
2 5 3
2 5 4
3 1 2
3 1 4
3 1 5
3 2 1
3 2 4
3 2 5
3 4 1
3 4 2
3 4 5
3 5 1
3 5 2
3 5 4
4 1 2
4 1 3
4 1 5
4 2 1
4 2 3
4 2 5
4 3 1
4 3 2
4 3 5
4 5 1
4 5 2
4 5 3
5 1 2
5 1 3
5 1 4
5 2 1
5 2 3
5 2 4
5 3 1
5 3 2
5 3 4
5 4 1
5 4 2
5 4 3
$

wsx666946 发表于 2022-6-17 20:55:09

人造人 发表于 2022-6-17 20:50
那么这5个数选3个进行组合，结果是什么？
12345



3 4 5
2 4 5
1 4 5
2 3 5
1 3 5
1 2 5
2 3 4
1 3 4
1 2 4
1 2 3


书上的结果是这个 每次抽三个数 组合是没有顺序之分的

人造人 发表于 2022-6-17 20:59:31

wsx666946 发表于 2022-6-17 20:55
3 4 5
2 4 5
1 4 5


哦

桃花飞舞 发表于 2022-6-18 00:43:43

本帖最后由 桃花飞舞 于 2022-6-18 01:46 编辑

排列组合还有顺序之分么？没这要求吧？

傻眼貓咪 发表于 2022-6-18 08:17:50

本帖最后由 傻眼貓咪 于 2022-6-18 08:29 编辑

桃花飞舞 发表于 2022-6-18 00:43
排列组合还有顺序之分么？没这要求吧？

应该是不重复意思，比如：{1, 2, 5} 和 {5, 1, 2} 和 {2, 5, 1} 相同。
所谓的顺序应该是指位置顺序吧。

Combination 组合（位置无分顺序）和 Permutation 排列 （位置讲究顺序）

傻眼貓咪 发表于 2022-6-18 09:55:09

人造人 发表于 2022-6-17 20:59
哦

你的代码思路很厉害{:10_257:}学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。
打印条件需符合：打印下一个目标必须大于等于之前目标，便可以滤过重复性的打印了

桃花飞舞 发表于 2022-6-18 13:15:35

傻眼貓咪 发表于 2022-6-18 08:17
应该是不重复意思，比如：{1, 2, 5} 和 {5, 1, 2} 和 {2, 5, 1} 相同。
所谓的顺序应该是指位置顺序吧 ...

虽然知道这是用递归的方法做的，但是还是不懂它是怎么把原问题分解为子问题的，是先取0个看有几种解法，再取1个看有几种解法，然后再取2个看有几种解法么？原问题是在5个里取3个看有几种取法？

傻眼貓咪 发表于 2022-6-18 16:29:23

桃花飞舞 发表于 2022-6-18 13:15
虽然知道这是用递归的方法做的，但是还是不懂它是怎么把原问题分解为子问题的，是先取0个看有几种解法， ...

如果是题目只要求算出有几种解法相对简单很多，只需要用公式就可以算出，不用递归。

至于想打印所有组合，楼上人造人大佬已经题解了。

桃花飞舞 发表于 2022-6-18 16:53:18

本帖最后由 桃花飞舞 于 2022-6-18 17:19 编辑

傻眼貓咪 发表于 2022-6-18 16:29
如果是题目只要求算出有几种解法相对简单很多，只需要用公式就可以算出，不用递归。

至于想打印所有组 ...

嗯，真搞不懂楼主的方法为什么也对，b = j - 1;为什么要这么一句？从a]可以知道b是a的索引，而b = 2; b = 3; b = 4; 也就是a=3; a = 4; a = 5;搞不懂怎么会打印出10种组合出来？应该是for循环的原因，感觉复杂，只可惜看不懂人造人的代码

人造人 发表于 2022-6-18 17:10:37

傻眼貓咪 发表于 2022-6-18 09:55
你的代码思路很厉害学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。

感觉这样写不是很好，我也没有更好的方法了

$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a, int b, int R) {
    if(r <= 0) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = 0; i < n; ++i) {
      b = a;
      Combine(n - 1 - i, r - 1, a + 1 + i, b, R + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    Combine(n, r, a, b, R);
}
$ gcc-debug -o main main.c
$ ./main
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
$

人造人 发表于 2022-6-18 17:28:58

傻眼貓咪 发表于 2022-6-18 09:55
你的代码思路很厉害学习学习

可以试试另外附加一个打印条件就完成楼主要的结果了。

要么就再加一个变量，记录下一层从哪个位置开始遍历
$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a, int b, int R, size_t c) {
    if(r <= 0) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(size_t i = c; i < n; ++i) {
      b = a;
      Combine(n, r - 1, a, b, R + 1, i + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    Combine(n, r, a, b, R, 0);
}
$ gcc-debug -o main main.c
$ ./main
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
$


当然楼主那种从后往前遍历也可以
$ cat main.c
#include <stdio.h>

void Combine(int n, int r, const int a, int b, int R) {
    if(r <= 0) {
      for(size_t i = 0; i < R; ++i) {
            printf("%d ", b);
      }
      puts("");
      return;
    }
    for(ssize_t i = n - 1; i >= 0; --i) {
      b = a;
      Combine(i, r - 1, a, b, R + 1);
    }
}

int main(void) {
    int n = 5, r = 3, R = 0;
    int a = {1, 2, 3, 4, 5};
    int b;
    Combine(n, r, a, b, R);
}
$ gcc-debug -o main main.c
$ ./main
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1
$

人造人 发表于 2022-6-18 17:31:05

桃花飞舞 发表于 2022-6-18 16:53
嗯，真搞不懂楼主的方法为什么也对，b = j - 1;为什么要这么一句？从可以知道是a的索引，而b = ...

的确楼主的方法复杂了，其实不需要保存索引，直接保存值就可以
页: [1]
查看完整版本: 编程求从n数中抽出r个数的所有组合方式 如1234组合为 432 431 421 312