［資訊學奧賽一本通題解］1317：【例5.2】組合的輸出 「v1.0」

㊀題目

時間限制: 1000 ms         記憶體限制: 65536 KB
【題目描述】
排列與組合是常用的數學方法，其中組合就是從n個元素中抽出r個元素(不分順序且r≤n)，我們可以簡單地将n個元素了解為自然數1，2，…，n，從中任取r個數。

現要求你用遞歸的方法輸出所有組合。

例如n＝5，r＝3，所有組合為：

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

【輸入】
一行兩個自然數n、r(1<n<21，1≤r≤n)。

【輸出】
所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字元的位置，所有的組合也按字典順序。

【輸入樣例】
5 3
【輸出樣例】
  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

           

㊁講解

1 算法

此題主要采用的是搜尋與回溯算法。

㊂代碼展示

#include <cstdio>

int a[100] = {0},
	b[100] = {0};
int end, num;

int ssearch( int k )
{
	int i = a[k-1]+1;
	while( i <= end )
	{
		a[k] = i;
		b[i] = 1;
		if( k == num )
		{
			int j = 1;
			while( j <= num )
			{
				printf( "  %d", a[j] );
				j++;
			}
			printf( "\n" );
		}
		
		else
		{
			ssearch( k+1 );
		}
		i++;
	}
}

int main()
{
	scanf( "%d%d", &end, &num );
	ssearch(1);
}

           

㊃其他

1 更新

作者會持續更新，敬請期待

2 聲明

請合理使用本文章中的代碼，僅供學習使用，一切所造成後果本人概不負責。

代碼歡迎在不篡改的情況下自由傳播，一經更改，傳播及需要作者的許可。

最後，感謝讀者們的支援