Esercizi e sorgenti dei programmi

Visualizzazione di tutte le stringhe binarie di lunghezza n

L'algoritmo STRINGHEBINARIE, dato un intero n>0, consente di generare tutte le 2n stringhe binarie di lunghezza n. La pseudo-codifica dell'algoritmo è la seguente:

STRINGHEBINARIE(n)

  1. per ogni i = 0, 1, 2, ..., n−1:
  2.    si = 0
  3. fine-ciclo
  4. i = 0
  5. fintanto che i < n ripeti:
  6.    i = 0
  7.    fintanto che i < n e si ≠ 0 ripeti:
  8.      si = 0
  9.      i = i+1
  10.    fine-ciclo
  11.    se i < n allora si = 1
  12.    scrivi la stringa S = (s0, s1, ..., sn−1)
  13. fine-ciclo

#include <stdlib.h>
#include <stdio.h>
#define MAX 100

void stampaArray(int A[], int n) {
   int i;
   for (i=0; i<n; i++) 
      printf("%d ", A[i]);
   printf("\n");
   return;
}

int main(void) {
   int S[MAX], i, n;
   long c=0;

   printf("Numero di elementi: ");
   scanf("%d", &n);

   for (i=0; i<n; i++) 
      S[i] = 0;
   
   i = 0;
   while (i<n) {
      i = 0;
      while (i < n && S[i] != 0) {
         S[i] = 0;
         i++;
      }
      if (i < n)
         S[i] = 1;
      printf("%6ld: ", c++);
      stampaArray(S, n);
   }
   return(0);
}