[help-ansiC] problemino...

[Ciocco@256]

Ciao a tutti e grazie a chi mi aiuterà! Sono un attimo in crisi, magari voi informatici di queste cose ne avete fatte a bizzeffe....

Allora, ho un vettore di lunghezza nota con dei numeri dentro
[100][150][200][300][400]
ora devo cercare tutte le combinazioni degli elementi di questo vettore a gruppi di N (con N ricevuto da tastiera), considerando che non mi servono le combinazioni ripetute, e che l'ordine non conta. Per ogni combinazione ne devo calcolare la somma. Devo scegliere infine la combinazione che si avvicina di più ad un numero massimo K, ricevuto da tastiera.

Per portarla più sul pratico, i numeri dentro il vettore sono calorie bruciate con un esercizio fisico, N è il numero di esercizi che devo fare, K sono le calorie che devo bruciare con gli N esercizi. Ogni esercizio può essere fatto solo una volta, e ovviamente l'ordine in cui si fanno gli esercizi non conta. Il numero di esercizi disponibili (cioè la lunghezza del vettore) la so.

Sto impazzendo...forse (ma molto forse) serve una ricorsione ma proprio non riesco

e spero di farcela per lunedì

Ah, come da titolo linguaggio C (ovviamente non chiedo di scrivermi il codice bello e fatto, mi basta qualche dritta )

grazie

[sottovento]

Ciao,
praticamente stai cercando C(n,k), cioe' le combinazioni senza ripetizione di n elementi presi k a k.
Come ben saprai, questo e' (n k) (scusa se lo scrivo cosi', intendo il binomiale), pertanto il loro numero e'

C(n.k) = n!/(k! * (n - k)!)

Si tratta ora di numerarle. L'algoritmo piu' semplice e' ovviamente quello ricorsivo anche se, in questo caso, non e' molto vantaggioso. Immagino pero' che, vista l'entita' dei numeri, tu non debba ricorrere a numeri grossi...
Nel caso questo succedesse, la versione iterativa sarebbe migliore, poiche' ti permetterebbe di avere un programma che puo' essere fatto ripartire il giorno dopo nel caso non si riesca a completare. (con la ricorsione, questo e' sicuramente piu' difficile).

Attualmente non ho tanto tempo, per cui sono costretto a fornirti solo una traccia per la procedura ricorsiva.

La procedura ricorsiva dovra' accettare in ingresso il vettore V degli elementi di tuo interesse, ed i due parametri interi n, k. Supponiamo ovviamente n >= k.
In uscita, avrai una sequenza di vettori (un vettore di vettori, di cui conosci la dimensione in partenza, essendo C(n,k)). In alternativa, se non vuoi allocare troppa memoria, puoi analizzare un caso alla volta mediante chiamata alla tua funzione di calcolo all'interno della funzione ricorsiva.

- Base della ricorsione: n == k. In tal caso la soluzione e' il vettore V;
- Base della ricorsione: k == 1. In tal caso hai n soluzioni, ciascuna e' un vettore di 1 elemento;
- Il caso (n-1 )== k e' facilmente risolvibile. Ti basta infatti ritornare n vettori, ciascuno con (n-1) elementi. Ottieni quindi la soluzione costruendo gli n vettori semplicemente togliendo un elemento alla volta;
- Infine, il caso rimanente (n > (k+1)). Lo risolvi con un ciclo for.
Per ogni elemento i puntato dal ciclo for, preparerai il vettore di (n-1) elementi ottenuto TOGLIENDO l'elemento corrente dal vettore di partenza e chiamando la procedura ricorsiva, passando detto vettore, n-1 e k-1. Il risultato della chiamata ricorsiva sara' una lista di vettori, a cui anteporrai l'elemento che avevi tolto prima della chiamata.

High Flying
Sottovento

[repne scasb]

La procedura ricorsiva non presenta particolare interesse; ben piu' interessante e' la procedura non ricorsiva. Allego il codice in C-- per visualizzare le combinazione di 'N' elementi presi 'K' a 'K' (algoritmo non ricorsivo indipendente da 'N' e 'K'):

#include <stdio.h>

#define N 10
#define K 4

void main(void)

{
    int table_array[N]={1,2,3,4,5,6,7,8,9,10};
    int table_pos[K],i,j;

    for(i=0;i<K;i++)
	table_pos[i]=i;

    do
    {
	for(i=0;i<K;i++)
	    printf("%d ",table_array[table_pos[i]]);
	printf("\n");

        for(i=1;i<=K;i++)
        {
	    if(table_pos[K-i]!=(N-i))
	    {
	        table_pos[K-i]++;
	        for(j=K-i+1;j<K;j++)
	    	    table_pos[j]=table_pos[j-1]+1;
		break;
	    }
	}
    } while (i!=(K+1));
}

[sottovento]

Originariamente inviato da repne scasb

La procedura ricorsiva non presenta particolare interesse; ben piu' interessante e' la procedura non ricorsiva. Allego il codice in C-- per visualizzare le combinazione di 'N' elementi presi 'K' a 'K' (algoritmo non ricorsivo indipendente da 'N' e 'K'):

...omissis...

Molto interessante. A questo punto sarebbe bello avere anche un algoritmo che mi permetta di avere una relazione d'ordine fra le combinazioni e la possibilita' di accesso alla n-esima....

[Ciocco@256]

Questo quello che ho fatto io...ma c'è un altro problema (che vi dico dopo )!!!!

mettiamo N=4 e z=10
allora, prec è l'indice precedente e alla prima chiamata vale -1, par=somma parziale delle calorie, f=passo della ricorsione -> parte da N+1 alla prima chiamata (così appena entro decremento e sono ad N), z numero elementi, k massima somma raggiungibile, vett=vettore con dentro le calorie, finale = vettore dove salvo gli indici di vettore che ho usato
/*Lo so che son stato un po confusionario...*/

int funzione(int prec, int par, int f, int z, int k, int *vett, int *finale)
{
int i, cambiato, tmp, tmp2;

f--;
if(f==1) /*Se sono all'ultimo for degli N. In pratica prima di questo passo 
         ho fissato N-1 elementi, e ora combino questi fissati con ognuno dei 
         rimanenti. Lo tratto separatamente perchè solo all'ultimo for
         posso sapere se la combinazione è la migliore.*/
    {    tmp=0;
         for(i=prec+1;i<z;i++) /*Per ogni elemento, partendo da quello
                               successivo all'ultimo dei precedenti fissati
                               fino al massimo totale degli esercizi*/
             if( (( k-(par+vett[i]) )<tot ) && ((par+vett[i])<=k) )  
                                            /*Se trovo una soluz. migliore
                                            della precedente e non supero
                                            il max calorie*/
                 {    tot=k-(par+vett[i]);  /*memorizzo la nuova differenza*/
                      finale[f]=i;          /*memorizzo l'indice*/
                      tmp=1;                /*mi ricordo che ho trovato una
                                            soluzione migliore della prec.*/
                 }
         if(tmp==1) return 1; else return 0; /*Se ho trovato una soluz. 
                                             migliore della precente, altrim.*/
    }
else /*se sono ad uno dei primi for*/
    {    tmp2=0;
         for(i=prec+1;i<=z-f;i++) /*mi fermo a z-f. Ad esempio con z=5 esercizi
                                  disponibile e n=3 esercizi alla volta, il primo
                                  degli N for annidati si dovrà fermare allo
                                  indice 2, per avere la combinazione 2-3-4 che
                                  è l'ultima. Se andassi oltre "sforerei".*/
             {    par=par+vett[i]; /*aggiungo al parziale l'elemento in cui sono*/
                  if(par<k)
                  {cambiato=funzione(i,par,f,z,k,vett,finale);
                  if(cambiato==1)    {  finale[f]=i;
                                        tmp2=1;
                                     }}
                  par=par-vett[i]; /*tolgo l'elemento usato prima per prepararmi
                                   a sommare il successivo.*/
             }
         if(tmp2==1) return 1; else return 0;
    }
}

/*Fuori da questa funzione mi trovo con gli indici scelti in finale[], a partire
da finale[1] fino a finale di [N] --> per questo finale è dichiarato come
finale[N+1], per avere indici da 0 ad N.*/

L'altro problema è che, in realtà, questo era un sottoproblema del mio
Infatti, ogni esercizio di questo vettore, è associato a + fasi di allenamento (sono #define MAXFASI), ma non a tutte...
vabbè, faccio prima a mettervi il testo intero dell'esercizio
Grazie a tutti per la pazienza!

Il file lo carico in una lista senza problemi, poi scanno la lista contando gli esercizi z di ogni fase (non già usati), alloco 2 vettori lunghi "giusti", uno per i nomi e uno per le calorie, e poi do in pasto alla funzione di sopra il vettore delle calorie (che è il vettore di cui vi avevo detto che dovevo fare tutte le combinazioni).
Ora il sottoproblema è risolto....il problema è che così trovo la soluzione migliore fase per fase, ma non è detto (quasi mai) che questa sia la soluzione migliore in generale per tutte le fasi!
- In realtà ho trovato un modo, ma è greedy, mentre a me serve avere davvero la soluzione migliore -

Una società sportiva deve organizzare un programma di allenamento per il 
potenziamento delle prestazioni fisiche dei propri atleti. Il programma prevede
 4 fasi di allenamento e per ogni fase è disponibile un certo numero di esercizi,
 ognuno dei quali caratterizzato da un determinato dispendio energetico.
Le informazione relative agli esercizi possibili, al dispendio energetico loro 
associato (numero minore o uguale a 500) ed alle fasi in cui sono impiegabili 
sono memorizzate sul file. Sul file per ogni esercizio è riportata una riga, che
 contiene il nome dell’ esercizio (senza spazio), il dispendio energetico 
associato e l’ elenco delle fasi in cui l’esercizio può essere impiegato (numeri di
 1 a 4).
Esempio di file di ingresso:
addominali_alti 200 1 2
addominali_bassi 500 1 2
glutei 250 1 3
adduttori 350 1 3 4
bicipiti 200 1 2
quadricipiti 150 2 4
trapezi 300 2
dorsali 350 3 4
pettorali 300 2 3
abduttori 200 2 3
tricipiti 100 1 3 4
deltoidi 200 1 3
femorali 400 2 3 4
Scrivere un programma in C, che legge da tastiera il valore di N (numero di 
esercizi massimo in ogni fase) e K (dispendio massimo di calorie in ogni fase) e 
che sia in grado di determinare per ciascuna fase l’esercizio/gli esercizi da 
svolgere in modo tale da avvicinarsi il più possibile al dispendio energetico 
massimo fissato, senza superarlo. Alla fine il programma deve stampare sul 
schermo, per ognuna fase, la lista degli esercizi ed il dispendio energetico loro 
associato.
Esempio di soluzione (N=3, K=800)
Fase 1
addominali_alti 200
addominali_bassi 500
tricipiti 100
Fase 2
bicipiti 200
abduttori 200
femorali 400
Fase 3
glutei 250
adduttori 350
deltoidi 200
Fase 4
quadricipiti 150
trapezi 300
dorsali 350
Osservazione: lo stesso esercizio non può essere svolto in più di una fase.

Grazie ancora...