【算法】组合数问题非递归解法

蔚落 2022-08-27 00:28 122阅读 0赞

**描述**

找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)个数的所有组合。

**输入**

输入n、r。

**输出**

按特定顺序输出所有组合。  
特定顺序：每一个组合中的值从大到小排列，组合之间按逆字典序排列。

**样例输入**

5 3

**样例输出**

543
    542
    541
    532
    531
    521
    432
    431
    421
    321

<span style="font-size:18px;">#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX_LEN 1000
    
    int cmp(const void *a,const void *b);
    int main()
    {
    	int i = 0;
    	int j = 0;
    	int n = 0;
    	int r = 0;
    	int k = 0;
    	int data[10];
    	int num[10] = {1,2,3,4,5,6,7,8,9};
    	int result[MAX_LEN];
    
    	scanf("%d %d",&n,&r);
    	memset(result,0,sizeof(result));
    
    	for (i = 0; i < (1<<n); i++)
    	{
    		int m = 0;
    		int numdex = 0;
    
    		memset(data,0,sizeof(data));
    
    		for (j = 0; j < n; j++)
    		{
    			if (i & (1<<j))
    			{
    				data[numdex++] = num[j];
    			}
    		}
    
    		if (numdex == r)
    		{
    			int tmp = 0;
    
    			for (m = numdex-1; m >= 0; m--)
    			{
    				tmp = tmp * 10 + data[m];
    			}
    
    			result[k++] = tmp;
    		}
    	}
    
    	qsort(result,k,sizeof(result[0]),cmp);
    
    	for (k = k-1; k >= 0; k--)
    	{
    		printf("%d\n",result[k]);
    	}
    
    	return 0;
    }
    
    int cmp(const void *a,const void *b)
    {
    	return *((int *)a) - *((int *)b);
    }
    </span>

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题解】29. 组合的递归解法

> 这是一道中等难度的题 > > https://leetcode.cn/problems/combinations/ 题目给定两个整数 `n` 和 `

青旅半醒/ 2024年03月22日 18:54/ 0 赞/ 14 阅读

相关老鼠迷宫问题递归解法

迷宫如下： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

痛定思痛。/ 2022年11月15日 11:46/ 0 赞/ 130 阅读

相关 Java青蛙跳台阶的递归和非递归解法

递归版： int Fib(int n) { if (1 == n || 2 == n) return n;

川长思鸟来/ 2022年09月25日 11:20/ 0 赞/ 186 阅读

相关【算法】组合数问题非递归解法

描述找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)个数的所有组合。输入输入n、r。输出按特定顺序输出所有组合。特定

蔚落/ 2022年08月27日 00:28/ 0 赞/ 123 阅读

相关二分查找的非递归与递归算法

一.引入: 假设一个已经\[排好序的数组a\[n\] ,若要搜索其中某个元素x,一般想到的是逐个查找,倘若x刚好在a\[n\],则最坏的情况需要n次比较,如若x不在数组a中,

电玩女神/ 2022年08月18日 12:21/ 0 赞/ 201 阅读

相关递归图形输出问题通用解法

ACM学了有一段时间了，有一类题目遇到过了很多次，但很少做出来，这类题目就是递归图形输出。找了一些大神博客学习了一下，在这里做个总结。那什么是递归图形输出问题呢？顾名思

青旅半醒/ 2022年06月01日 05:55/ 0 赞/ 148 阅读

相关二分查找（非递归算法和递归算法）

非递归算法： package mytest; public class test { public static int Bina

水深无声/ 2022年05月29日 06:17/ 0 赞/ 201 阅读

相关汉诺塔问题递归解法

思路先移动最底层到其上的部分到辅助位置，再移动最底层到要求位置，将辅助位置的移动到最终位置。 ![在这里插入图片描述][watermark_type_ZmF

灰太狼/ 2022年04月24日 12:44/ 0 赞/ 182 阅读

相关递归求组合数和递推求一般性问题的practice

考新郎 Time Limit: 1000 ms Memory Limit: 32768 KiB [Submit][] [Statistic][] [Discuss][]

梦里梦外;/ 2022年03月30日 03:19/ 0 赞/ 192 阅读

相关非递归&递归汉诺塔算法实践

汉诺塔算法是很多公司的面试题，经常会让手写，这里总结了一下 ![汉诺塔][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

比眉伴天荒/ 2021年12月07日 10:17/ 0 赞/ 304 阅读