Imprimer {1,2,3Toutes les sous-ensembles de ..., sans utiliser d'array ou de boucle dans le programme C

Donné un entier positif n, nous devons imprimer un ensemble {1,2,3,4,... n} tous les sous-ensembles.

comme nous disons pour tout nombre3 comme pour s, nous devons imprimer l'ensemble {1,2,3Tous les sous-ensembles de {1 2 3}. {1 2}. {2 3}. {1 3}. {1}. {2}. {3}. {}.

Mais nous devons exécuter cette opération sans utiliser aucun boucle ou tableau. Par conséquent, seule la récursion est une méthode possible pour résoudre ce type de problème, sans utiliser aucun tableau ou boucle.

Exemple

Input:　3
Entrée:　}　1　2　3　}{　1　2　}{　1　3　}{　1　}{　2　3　}{　2　}{　3　}{　}
Explication : l'ensemble sera {1　2　3à partir duquel nous trouverons les sous-ensembles
Input:　4
Entrée:　}　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　}{　}

Sortie:　{-

• Nous utiliserons pour résoudre le problème donné 2 À partir de num = -1^ n

• Commencer par 0.

• En considérant la représentation binaire de num ayant n bits.1Commencer par le bit le plus à gauche, le deuxième bit représente2Ensuite, etc., jusqu'à ce que le bit représentant n soit le n-ième.

• Imprimer le nombre correspondant à ce bit (si il est défini).

• Exécuter les étapes ci-dessus pour toutes les valeurs de num jusqu'à ce qu'elles soient égales à 0.

Laissez-nous utiliser un exemple simple pour comprendre en détail le fonctionnement de la méthode.-

Supposons que l'entrée n = 3Donc, le problème passe de num = 2 ^ 3-1 = 7Début　

• 7⇒représentation binaire

• Sous-ensemble correspondant⇒

Enlever de num1；num = 6

• 6représentation binaire⇒

• Sous-ensemble correspondant⇒

Enlever de num1；num = 5

• 5représentation binaire⇒

• Sous-ensemble correspondant⇒

Enlever de num1；num = 4

• représentation binaire4⇒

• Sous-ensemble correspondant⇒

De même, nous itérerons jusqu'à ce que num = 0 et imprimerons tous les sous-ensembles.

Algorithme

Début
　　　Étape　1　→ Dans la fonction int subset(int bitn, int num, int num_of_bits)
　　　Si bitn >= 0
　　　　　　Si (num & (1　<< bitn)) != 0
　　　　　　　　　Imprimer num_of_bits　-　bitn
　　　　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　　　　Sinon
　　　　　　　　　Retourner 0
　　　　　　Retourner　1
　　　Étape　2　→ Dans la fonction int printSubSets(int num_of_bits, int num)
　　　　　　Si (num >= 0)
　　　　　　　　　Imprimer "{ "
　　　　　　　　　Appeler la fonction subset(num_of_bits　-　1, num, num_of_bits)
　　　　　　　　　Imprimer ""
　　　　　　　　　Appeler la fonction printSubSets(num_of_bits, num　-　1)
　　　　　　Sinon
　　　　　　　　　Retourner 0
　　　　　　Retourner　1
　　　Étape　3　→ Dans la fonction int main()
　　　　　　Déclarer et initialiser int n =　4
　　　　　　Appeler la fonction printSubSets(n, (int) (pow(2,　n))　-1)
Arrêter

Exemple

#include <stdio.h>
#include <math.h>
//　Cette fonction imprime récursivement le
//　sous-ensemble correspondant au binaire
//　représentation de num.
int subset(int bitn, int num, int num_of_bits) {
　　　if　(bitn　>=　0)　{
　　　　　　//　Imprimer le nombre dans le sous-ensemble donné uniquement
　　　　　　//　si le bit correspondant
　　　　　　//　est défini dans num.
　　　　　　if　((num　&　(1　<<　bitn))　!=　0)　{
　　　　　　　　　printf("%d　",　num_of_bits　-　bitn);
　　　　　　}
　　　　　　//　Vérifier le bit suivant
　　　　　　subset(bitn　-　1,　num,　num_of_bits);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//fonction pour imprimer les sous-ensembles
int　printSubSets(int　num_of_bits,　int　num)　{
　　　if　(num　>=　0)　{
　　　　　　printf("{　");
　　　　　　//　Imprimer les sous-ensembles correspondants à
　　　　　　//　la représentation binaire de num.
　　　　　　subset(num_of_bits　-　1,　num,　num_of_bits);
　　　　　　printf("}");
　　　　　　//　appeler récursivement la fonction pour
　　　　　　//　Imprimer le sous-ensemble suivant.
　　　　　　printSubSets(num_of_bits,　num　-　1);
　　　}
　　　else
　　　　　　return　0;
　　　　　　return　1;
}
//programme principal
int　main()　{
　　　int　n　=　4;
　　　printSubSets(n,　(int)　(pow(2,　n))　-1);
}

Résultat de la sortie

{　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　}{　}