Forum Ubuntu-it

Codice: Seleziona tutto

fact(3)

Codice: Seleziona tutto

fact(2)
fact(3)

Codice: Seleziona tutto

fact(1)
fact(2)
fact(3)

Codice: Seleziona tutto

pop(top(stack)) = 1;  
return n*fact(n-1);   prende il valore di 1. 


Stack attuale:
fact(2)  <---------- ora si riprende l'esecuzione di questa chiamata, prima interrotta! 
fact(3)

Codice: Seleziona tutto

pop(top(stack)) = 2
return n*fact(n-1);   prende il valore di 1*2. 


Stack attuale:
fact(3)  <---------- ora si riprende l'esecuzione di questa chiamata, prima interrotta! 

Codice: Seleziona tutto

pop(top(stack)) = 3
return n*fact(n-1);   prende il valore di 1*2*3. 


Stack attuale:

Codice: Seleziona tutto

fact(3)
...fact(x).0
...if(x)
.....fact(x).1
........fact(x).2
.............fact(x).3

Codice: Seleziona tutto

#include <stdio.h>

/*
unsigned int fact(int n)     
{
	if ( n <= 1 )
		return 1;
	else
	{
		return n * fact( n-1 );
	}       
}
*/ 

unsigned int fact(int n)
{
	int stack[1024];
	int top = -1;
	int accumulator = 1;

	if ( n == 0 )
		return 1;
	
	printf("PUSH n: %d\n", n);
	stack[++top] = n;
	
	beginning:
	if (n <= 1)
	{
		printf("Raggiunto il caso base n = 1\n");
		
		while ( top >= 0 )
		{
			n = stack[top--];
			printf("POP %d\n", n);
			printf("RETURN %d * %d = %d\n", accumulator, n, accumulator * n);			
			accumulator *= n;
		}

		printf("RETURN %d\n", accumulator);
		return accumulator;
	}
	else
	{
		printf("PUSH n - 1: %d\n", n - 1);	
		n -= 1;	
		stack[++top] = n;
		goto beginning;
	}	
}    
      
int main (void)
{
	int x = 3;
	
	printf("%d! = %u\n", x, fact(x));
	
    return 0;
}

Codice: Seleziona tutto

$ gcc -Wall -W -O2 fact.c -o fact
$ ./fact
PUSH n: 3
PUSH n - 1: 2
PUSH n - 1: 1
Raggiunto il caso base n = 1
POP 1
RETURN 1 * 1 = 1
POP 2
RETURN 1 * 2 = 2
POP 3
RETURN 2 * 3 = 6
RETURN 6
3! = 6

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void combinations (int v[], int start, int n, int k, int maxk)
{
	int i;
	
	if (k > maxk)
	{
		for (i = 1; i <= maxk; i++)
			printf ("%i ", v[i]);
		printf ("\n");
		return;
	}

	for (i = start; i <= n; i++)
	{
		v[k] = i;
		combinations (v, i+1, n, k+1, maxk);
	}
}

int main (int argc, char *argv[])
{
	clock_t c_start, c_end;
	double TempoImpiegato;  
	int n, k;
	int *v;        
	
	if (argc != 3)
	{
		printf ("Uso: %s n k\n", argv[0]);
		exit (1);
	}
	n = atoi (argv[1]);
	k = atoi (argv[2]);
	
	v = (int*)calloc(n + 1, sizeof(int));
	if ( !v )
	{
		printf("Errore: memoria insufficiente.\n");
		return -1;		
	}
        
	c_start = clock();
	
	combinations (v, 1, n, 1, k);
        
	c_end = clock();
	TempoImpiegato = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("Tempo impiegato -> %5.5f secondi\n\n", TempoImpiegato);
	
	free(v);
	
	return 0;
}

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define true 1
#define false 0

typedef  int * ksubset;
   
/* Calcola il coefficiente binomiale "n sopra r" */
int BinCoef(int n, int r)
{
	int i, b;
	
	if ( (r < 0) || (n < r) )
		return 0;
		
	if ( (2 * r) > n )
		r = n - r;
	b = 1;
	if (r > 0)
		for(i = 0; i <= (r - 1); i++)
			b = (b * (n - i))/(i + 1);
			
	return b;
}

void kSubsetLexUnrank(int r, ksubset T, int n, int k)
{
	int x,i,y;
	
	x = 1;
	for(i = 1; i <= k; i++)
	{
		y = BinCoef(n - x, k - i);
		while (y <= r)
		{
			r = r - y;
			x = x + 1;
			y = BinCoef(n - x, k - i);
		}
		T[i] = x;
		x = x + 1;
	}
}

int main(int argc, char *argv[])
{
	int n, k;
	int NN, r, j;
	ksubset T;
	clock_t c_start, c_end;
	double TempoImpiegato;   
	
	if(argc != 3)
	{
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}
	n = atoi(argv[1]);
	k = atoi(argv[2]);  
	if (k < 0)
	{
		fprintf(stderr,"k deve essere > 0\n");
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}
	if (k > n)
	{
		fprintf(stderr,"k deve essere <= n\n");
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}

	T = (int *)calloc(k + 1, sizeof(int)); 
	if ( !T )
	{
		printf("Errore: memoria insufficiente.\n");
		return -1;
	}
	NN = BinCoef(n, k);
    
    printf("n = %d k = %d Numero combinazioni = %d\n\n", n, k, NN);
    
    c_start = clock();
    for(r = 0; r < NN; r++)
    {
		kSubsetLexUnrank(r, T, n, k);
		for (j = 1; j <= k; j++)
			printf(" %d",T[j]);
		printf("\n");
	}
	
	c_end = clock();
	TempoImpiegato = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("Tempo impiegato -> %5.5f secondi\n\n", TempoImpiegato); 
	
	free(T);
		
	return 0;
}

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define true 1
#define false 0

typedef  int * ksubset; 

/* Calcola il coefficiente binomiale "n sopra r" */
int BinCoef(int n, int r)
{
	int i, b;
	
	if ( (r < 0) || (n < r) )
		return 0;
		
	if ( (2 * r) > n )
		r = n - r;
	b = 1;
	if (r > 0)
		for(i = 0; i <= (r - 1); i++)
			b = (b * (n - i))/(i + 1);
			
	return b;
}

void kSubsetLexSuccessor(ksubset T, int * flag, int n, int k, ksubset U)
{
	int i, j;
	
	(*flag) = true;
	
	for(i = 1; i <= k; i++)
		U[i] = T[i];
	i = k;
	
	while ( (i >= 1) && (T[i] == (n - k + i)) )
		i = i - 1;
	if (i == 0) 
		(*flag) = false;
	else
	{
		for (j = i; j <= k; j++)
			U[j] = T[i] + 1 + j - i;
		for (j = 1; j <= k; j++)
			T[j] = U[j];
	}
}

int main(int argc, char *argv[])
{
	int n, k, j;
	int flag;
	int NN;
	ksubset T;
	ksubset U;
	clock_t c_start, c_end;
	double TempoImpiegato;   
	
	if(argc != 3)
	{
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}
	n = atoi(argv[1]);
	k = atoi(argv[2]);  
	if (k < 0)
	{
		fprintf(stderr,"k deve essere > 0\n");
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}
	if (k > n)
	{
		fprintf(stderr,"k deve essere <= n\n");
		fprintf(stderr,"Uso: %s n k\n", argv[0]);
		return -1;
	}
	
	T = (int *)calloc(k + 1, sizeof(int)); 
	if ( !T )
	{
		printf("Errore: memoria insufficiente.\n");
		return -1;
	}	
	
	U = (int *)calloc(k + 1, sizeof(int)); 
	if ( !U )
	{
		printf("Errore: memoria insufficiente.\n");
		free(T);
		return -1;
	}	
	
	NN = BinCoef(n, k);
    
    printf("n = %d k = %d Numero combibazioni = %d\n\n", n, k, NN);
    
	c_start = clock();
	for (j = 1; j <= k; j++)
		T[j] = j;
	flag = true;
	while (flag)
	{
		for (j = 1; j <= k; j++)
			printf(" %d", T[j]);
		printf("\n");
		kSubsetLexSuccessor(T, &flag, n , k, U);
	}
	
	c_end = clock();
	TempoImpiegato = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("Tempo impiegato -> %5.5f secondi\n\n", TempoImpiegato);   	
	
	free(T);
	free(U);
		
	return 0;
}

Codice: Seleziona tutto

ulimit -s

Codice: Seleziona tutto

ulimit -a

Codice: Seleziona tutto

core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 29952
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 29952
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited