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

蔚落 2022-08-27 00:28 160阅读 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 条评论，160人围观）

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

相关阅读

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

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

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

相关非递归求所有组合

从\[0,NN-1\]这NN个数里面，找到所有组合例如Con(5,3) > 0 1 2 > 0 1 3 > 0 1 4 > 0 2 3 > 0 2 4

小灰灰/ 2023年07月24日 13:24/ 0 赞/ 17 阅读

相关斐波那契数列的递归算法与非递归算法

一、斐波那契数列由于斐波纳挈数列是以兔子的繁殖引入的，因此也叫“兔子数列”。它指的是这样一个数列：0,1,1,2,3,5,8,13......从这组数可以很明显看出这样一个

￡神魔★判官ぃ/ 2023年02月21日 06:58/ 0 赞/ 31 阅读

相关 js 归并算法(递归和非递归)

归并算法时间复杂度是：O(nlogn) 归并递归算法 function merge(left, right)\{ var result=\[\

怼烎@/ 2023年02月19日 07:27/ 0 赞/ 26 阅读

相关 280-归并排序算法(递归和非递归)

归并排序算法(递归和非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

深碍√TFBOYSˉ_/ 2023年01月14日 13:57/ 0 赞/ 151 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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