[C] Disposizione con ripetizione e liste

[Dav3i]

Ciao a tutti.
Ho controllato nel forum, ma non ho trovato nessun riferimento ad un esercizio di questa tipologia.
Probabilmente il quesito che sto per proporvi, per molti di voi, sarà una passeggiata ma io non so proprio da che parte girarmi.

Riporto il testo:

Quesito 5
Scrivere un programma che chiede all’utente un numero intero n positivo e poi visualizza tutte le combinazioni di lunghezza n costituite da sequenze di simboli ’+’ e ’-’. L’ordine delle combinazioni `e a piacere.

Esempio 1
Ingresso: 3
Uscita: +++ ++- +-+ +-- -++ -+- --+ ---

Esempio 2
Ingresso: 2
Uscita: ++ +- -+ --

Io ho pensato di allocare dinamicamente la memoria e man mano di aggiungere in coda le combinazioni di '+' e '-' .

#include <stdio.h>
#define N 2

typedef struct _elem {
	char symbol;
	struct _elem *next;
} elem;


elem *inserisciCoda (elem *testa, char car);

int main (int argc, char * argv[])
{
	int n;
	char car;
	int totdisp = 1, cont = 0, ctrl;
	elem *lista = NULL;
	elem *tmp;

	printf ("\n\nLunghezza della disposizione con ripetizione costituita da '+' e '-': ");
	do
		scanf ("%d", &n);
	while (n <= 0);

	while (cont < n)
	{
		totdisp = N * totdisp;
		cont ++;
	}
	printf ("\nNumero di combinazioni possibili: %d", totdisp);

	for (ctrl = 0; ctrl < totdisp; ctrl ++)
	{
		if (lista == NULL)
		{
			cont = 0;
			while (cont < n)
			{
				car = '+';
				lista = inserisciCoda(lista, car);
				cont ++;
			}
			car = ' ';
			lista = inserisciCoda(lista, car);
		}
		else
		{
                     // Non riesco a capire come posso aggiungere alla lista
                     // le combinazioni di '+' e '-' controllando ad ogni ciclo
                     // se la determinata combinazione è già presente oppure no.
                 }
	}

	printf ("\n\nCombinazioni\n");
	for (tmp = lista; tmp != NULL; tmp = tmp->next)
		printf ("%c", car);
	printf ("\n\n");

	return 0;
}

elem *inserisciCoda (elem *testa, char car)
{
	elem *tmp, *new;

	if (new = (elem *)malloc(sizeof(elem)))
	{
		new->symbol = car;
		new->next = NULL;

		if (testa == NULL)
			testa = new;
		else
		{
			for (tmp = testa; tmp->next != NULL; tmp = tmp->next);
			tmp->next = new;
		}
	}
	else
		printf ("\nERRORE: memoria non allocata per il nuovo elemento.\n");

	return testa;
}

Spero di essere stato chiaro nell'esporre il mio problema. Grazie in anticipo.

[ESSE-EFFE]

Non è chiara una cosa: nel quesito non si parla di liste, sei obbligato ad utilizzarle oppure no?

[Dav3i]

No, non sono obbligato, ma ho pensato che fosse il modo migliore per utilizzare soltanto la quantità di memoria necessaria per salvare tutte le combinazioni.
Tu avresti usato un altro metodo?

[ESSE-EFFE]

Originariamente inviato da Dav3i
No, non sono obbligato, ma ho pensato che fosse il modo migliore per utilizzare soltanto la quantità di memoria necessaria per salvare tutte le combinazioni.
Tu avresti usato un altro metodo?

A me sembra un modo per complicare un problema semplice. E poi dici "salvare tutte le combinazioni", ma il quesito non lo richiede. Se provi ad incolonnare i risultati:

+++
++-
+-+
+--
-++
-+-
--+
---

si nota che il primo carattere (a destra) cambia ogni volta, il secondo ogni due, il terzo ogni quattro. Ti basta quindi un algoritmo che faccia questo giochino partendo dalla stringa iniziale. Ovviamente poi si possono trovare altre soluzioni...

[Celebron]

la soluzione più "bella" matematicamente è un algoritmo ricorsivo con backtrack

te la caveresti con poche righe di codice

[Dav3i]

Grazie ad entrambi per le dritte: più tardi provo a riscriverlo e, nel caso, tornerò a disturbarvi.
Con un paio di cicli for teoricamente dovrei cavarmela: essendo ancora alle prime armi con la programmazione, a volte mi è difficile convertire l'algoritmo che ho in testa in linguaggio C. Di conseguenza mi complico la vita.

[Dav3i]

Niente da fare.
Ieri pomeriggio l'ho riguardato, ma non riesco a farlo funzionare.
Ho seguito il consiglio di ESSE-EFFE, ma non riesco a capire come gestire i due cicli 'for' (sempre che servano). La parte di codice che in rosso penso sia giusta (dovrebbe essere abbastanza immediato a cosa serva).

Grazie per la pazienza.

#include <stdio.h>
#define N 2


int main (int argc, char * argv[])
{
	int n;
	int riga, col;
	int a, b, ctrl;
	char car;
	int totdisp = 1;
	int cont = 0;

	printf ("\n\nLunghezza della disposizione con ripetizione utilizzando %d simboli: ", N);
	do
		scanf ("%d", &n);
	while (n <= 0);

	while (cont < n)
	{
		totdisp = N * totdisp;
		cont ++;
	}
	printf ("\nTotale combinazioni possibili: %d\n\n", totdisp);

	ctrl = totdisp;
	car = '+';
	b = 0;

	/*for (col = 0; col < totdisp; col ++)
	{
		for (riga = 0; riga < n; riga ++)
		{*/
			ctrl = ctrl / 2;
			for (a = 0; a < ctrl; a ++)
				printf ("%c", car);
			b = b + 1;
			if (b % 2 == 0)
				car = '+';
			else
				car = '-';
		/*}
		printf ("\n");
	}/*

	return 0;
}

[ESSE-EFFE]

Originariamente inviato da Dav3i
La parte di codice che in rosso penso sia giusta (dovrebbe essere abbastanza immediato a cosa serva).

Secondo me c'eri molto vicino. Una soluzione abbastanza generica potrebbe essere la seguente (evito di ripetere tutto il codice):

char car[] = "+-*/.....";

for (riga = 0; riga < totdisp; riga++)
{
    a = riga;
    for (col = 0; col < n; col++)
    {
        printf("%c", car[a % N]);
        a /= N;
    }
    printf("\n");
}

Invece una soluzione semplificata/ottimizzata valida solo per N = 2 (cioè il quesito originario):

for (riga = 0; riga < totdisp; riga++)
{
    for (col = 0; col < n; col++)
    {
        if (riga & (1 << col))
            printf("+");
        else
            printf("-");
    }
    printf("\n");
}

HTH,

[Dav3i]

for (riga = 0; riga < totdisp; riga++)
{
    for (col = 0; col < n; col++)
    {
        if (riga & (1 << col))
            printf("+");
        else
            printf("-");
    }
    printf("\n");
}

Ottimo, grazie!
Non mi è chiara la parte evidenziata in rosso, però: & e << che significato hanno?
A lezione, nel corpo di un 'if' ho sempre usato gli operatori && e/o || .
Invece << non l'ho mai visto...

[ESSE-EFFE]

Originariamente inviato da Dav3i
Non mi è chiara la parte evidenziata in rosso, però: & e << che significato hanno?

Beh quello lo trovi su qualunque libro o tutorial di C. & è l'and bit a bit (bitwise) mentre << è lo shift a sinistra (sembre bit a bit ovviamente). In questo caso "1 << col" è solo un modo per fare "2 elevato alla col" senza scomodare altre funzioni.