資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在C程式中不使用陣列或迴圈列印{1,2,3,…n}的所有子集
給定一個正整數n，我們必須列印集合{1, 2, 3, 4,… n}的所有子集，而不使用任何陣列或迴圈。
例如，如果給定一個數字3，我們必須列印集合{1, 2, 3}的所有子集，它們將是{1 2 3}、{1 2}、{2 3}、{1 3}、{1}、{2}、{3} {}。
但是，我們必須在不使用任何迴圈或陣列的情況下執行此操作。因此，僅遞迴是解決此類問題而不使用任何陣列或迴圈的可能方法。
示例
Input: 3
Output: { 1 2 3 }{ 1 2 }{ 1 3 }{ 1 }{ 2 3 }{ 2 }{ 3 }{ }
Explanation: The set will be {1 2 3} from which we will find the subsets
Input: 4
Output: { 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }我們將用來解決給定問題的方案 −
- 從num = 2^n -1 到0開始。
- 考慮num的二進位制表示，它有n位。
- 從最左邊的位開始，它表示1，第二位表示2，依此類推，直到第n位表示n。
- 如果位被設定，則列印對應於該位的數字。
- 對num的所有值執行上述步驟，直到它等於0。
讓我們使用一個簡單的示例詳細瞭解所述方法是如何工作的 −
假設輸入n = 3，因此問題從num = 2^3 - 1 = 7開始
- 7的二進位制表示 ⇒
| 1 | 1 | 1 |
- 相應的子集 ⇒
| 1 | 2 | 3 |
從num中減去1；num = 6
- 6的二進位制表示 ⇒
| 1 | 1 | 0 |
- 相應的子集 ⇒
| 1 | 2 |
從num中減去1；num = 5
- 5的二進位制表示 ⇒
| 1 | 0 | 1 |
- 相應的子集 ⇒
| 1 | 3 |
從num中減去1；num = 4
- 4的二進位制表示 ⇒
| 1 | 0 | 0 |
- 相應的子集 ⇒
| 1 |
類似地，我們將迭代直到num = 0並列印所有子集。
演算法
Start
Step 1 → In function int subset(int bitn, int num, int num_of_bits)
If bitn >= 0
If (num & (1 << bitn)) != 0
Print num_of_bits - bitn
subset(bitn - 1, num, num_of_bits);
Else
Return 0
Return 1
Step 2 → In function int printSubSets(int num_of_bits, int num)
If (num >= 0)
Print "{ "
Call function subset(num_of_bits - 1, num, num_of_bits)
Print "}"
Call function printSubSets(num_of_bits, num - 1)
Else
Return 0
Return 1
Step 3 → In function int main()
Declare and initialize int n = 4
Call fucntionprintSubSets(n, (int) (pow(2, n)) -1)
Stop示例
#include <stdio.h>
#include <math.h>
// This function recursively prints the
// subset corresponding to the binary
// representation of num.
int subset(int bitn, int num, int num_of_bits) {
if (bitn >= 0) {
// Print number in given subset only
// if the bit corresponding to it
// is set in num.
if ((num & (1 << bitn)) != 0) {
printf("%d ", num_of_bits - bitn);
}
// Check the next bit
subset(bitn - 1, num, num_of_bits);
}
else
return 0;
return 1;
}
//function to print the subsets
int printSubSets(int num_of_bits, int num) {
if (num >= 0) {
printf("{ ");
// Printint the subsets corresponding to
// the binary representation of num.
subset(num_of_bits - 1, num, num_of_bits);
printf("}");
// recursively calling the function to
// print the next subset.
printSubSets(num_of_bits, num - 1);
}
else
return 0;
return 1;
}
//main program
int main() {
int n = 4;
printSubSets(n, (int) (pow(2, n)) -1);
}輸出
{ 1 2 3 4 }{ 1 2 3 }{ 1 2 4 }{ 1 2 }{ 1 3 4 }{ 1 3 }{ 1 4 }{ 1 }{ 2 3 4 }{ 2 3 }{ 2 4 }{ 2 }{ 3 4 }{ 3 }{ 4 }{ }
更新於: 2019年11月20日
918 次檢視
廣告