Stampare tutti gli insiemi di {1,2,3,...n} senza utilizzare array o cicli nel programma C

Data un numero positivo n, dobbiamo stampare tutti i sottinsiemi della serie {1,2,3,4,... n} senza utilizzare alcun array o ciclo.

Come facciamo con qualsiasi numero che diciamo 3 s, dobbiamo stampare tutti i sottinsiemi della集合 {1,2,3}, che saranno {1 2 3}, {1 2}, {2 3}, {1 3}, {1}, {2}, {3} {}.

Ma dobbiamo eseguire questa operazione senza utilizzare alcun ciclo o array. Pertanto, il solo metodo possibile per risolvere questo tipo di problema senza utilizzare alcun array o ciclo è la ricorsione.

Esempio

Input: 3
Output: { 1 2 3 } { 1 2 } { 1 3 } { 1 } { 2 3 } { 2 } { 3 } { }
Spiegazione: Il set sarà {1 2 3} dal quale troveremo i sottinsiemi
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 } { }

Il metodo che useremo per risolvere il problema dato-

• Iniziare da num = 2 ^ n -1 fino a 0.

• Considerare la rappresentazione binaria di num con n cifre.

• Dalla posizione più a sinistra che rappresenta 1, la seconda posizione rappresenta 2, e così via, fino alla posizione che rappresenta n.

• Stampare il numero corrispondente a quella posizione (se è impostato).

• Eseguire le stesse operazioni per tutti i valori di num fino a raggiungere 0.

Usiamo un esempio semplice per capire meglio il funzionamento del metodo-

Supponiamo che l'input sia n = 3, allora il problema inizia con num = 2 ^ 3-1 = 7　

• 7⇒ nella forma binaria

• Corrisponde al sottoinsieme⇒

Sottrarre 1 da num; num = 6

• La rappresentazione binaria di 6⇒

• Corrisponde al sottoinsieme⇒

Sottrai 1 da num; num = 5

• La rappresentazione binaria di 5⇒

• Corrisponde al sottoinsieme⇒

Sottrai 1 da num; num = 4

• La rappresentazione binaria 4⇒

• Corrisponde al sottoinsieme⇒

Allo stesso modo, itereremo fino a che num = 0 e stampiamo tutti i sottoinsiemi.

Algoritmo

Inizia
　　　Passo 1 → Nella funzione int subset(int bitn, int num, int num_of_bits)
　　　Se bitn >= 0
　　　　　　Se (num & (1 << bitn)) != 0
　　　　　　　　　Stampa num_of_bits - bitn
　　　　　　　　　subset(bitn - 1, num, num_of_bits);
　　　　　　Altrimenti
　　　　　　　　　Restituisci 0
　　　　　　Restituisci 1
　　　Passo 2 → Nella funzione int printSubSets(int num_of_bits, int num)
　　　　　　Se (num >= 0)
　　　　　　　　　Stampa "{ "
　　　　　　　　　Chiamare la funzione subset(num_of_bits - 1, num, num_of_bits)
　　　　　　　　　Stampa ""
　　　　　　　　　Chiamare la funzione printSubSets(num_of_bits, num - 1)
　　　　　　Altrimenti
　　　　　　　　　Restituisci 0
　　　　　　Restituisci 1
　　　Passo 3 → Nella funzione int main()
　　　　　　Dichiarare ed inizializzare int n = 4
　　　　　　Chiamare la funzione printSubSets(n, (int) (pow(2, n)) - 1)
Ferma

Esempio

#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);
　　　　　　}
　　　　　　//Controlla il bit successivo
　　　　　　subset(bitn - 1, num, num_of_bits);
　　　}
　　　else
　　　　　　return 0;
　　　　　　return 1;
}
//funzione per stampare i sottoinsiemi
int printSubSets(int num_of_bits, int num) {
　　　if (num >= 0) {
　　　　　　printf("{ ");
　　　　　　//Stampare i sottoinsiemi corrispondenti a
　　　　　　//la rappresentazione binaria di num.
　　　　　　subset(num_of_bits - 1, num, num_of_bits);
　　　　　　printf("}");
　　　　　　//chiamata ricorsiva della funzione per
　　　　　　//stampare il sottoinsieme successivo.
　　　　　　printSubSets(num_of_bits, num - 1);
　　　}
　　　else
　　　　　　return 0;
　　　　　　return 1;
}
//programma principale
int main() {
　　　int n = 4;
　　　printSubSets(n, (int) (pow(2, n)) - 1);
}

Risultato di 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 } }