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 2ⁿ stringhe binarie di lunghezza n. La pseudo-codifica dell'algoritmo è la seguente:

STRINGHEBINARIE(n)

• Input: Un intero positivo n
• Output: Le stringhe binarie S = (s₀, s₁, ..., s_n−1) di lunghezza n

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

Codifica in linguaggio C

#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);
}

Codifica in linguaggio Python 3.x

s = list()
n = int(input("Numero di elementi: "))
for i in range(n):
  s.append(0)
i = 0
while i < n:
  i = 0
  while i < n and s[i] != 0:
    s[i] = 0
    i = i+1
  if i < n: s[i] = 1
  print(s, end="\r")
print()