Newsgroup: it.arti.musica.strumenti.chitarra
Titolo: [OT] c'è qualche nerd di programmazione ricorsiva in C?

cdo. avrei un esercizio da risolvere ma non riesco... 

 cdo. avrei un esercizio da risolvere ma non riesco...
Mmh... spara, io ho dato Programmazione 1 e bisognava programmare in C, 
quindi *forse* (magari stai dando Algoritmi 88 e non credo di poterti 
aiutare :D) una mano te la posso dare

 cdo. avrei un esercizio da risolvere ma non riesco...
in c particolarmente no, ma programmo in Java ,C# e qualcosina in c++,
magari una mano riesco a dartela lo stesso

 cdo. avrei un esercizio da risolvere ma non riesco...
Dicci, dicci
-- 
Don't misuse your strings. Tap 'em.
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 cdo. avrei un esercizio da risolvere ma non riesco...
sarebbe?

 cdo. avrei un esercizio da risolvere ma non riesco...
Problema: abbiamo un intero m ed un array Y di n interi e vogliamo 
determinare se esiste un insieme di indici i1,.ik in [0,n-1+ tale che 
Y*i1++Y*i2++.+Y*ik+=m. Chiamiamo un tale insieme di indici i1,.ik una 
soluzione per m in Y ed una rappresentazione di questa soluzione è un array 
R di n booleani tale che, per ogni j in [0,n-1], R[j]=true se j è nella 
soluzione i1,.ik e altrimenti è false. Non si fa nessuna ipotesi sull'intero 
m e sugli interi contenuti in Y.
scrivere una funzione *ricorsiva* con questo prototito: bool F(int m, int 
*Y, int n, bool *R) che restituisca true se e solo se esiste una soluzione 
in Y, e R dev'essere una rappresentazione di questa soluzione. altrimenti 
deve restituire false.
iterativamente l'ho fatto senza particolari problemi, ma ricorsivamente non 
mi viene... 


Se ho compreso la richiesta c'e' un problema di logica. La soluzione in Y 
potebbe essere + di una e quindi R dovrebbe essere un array di array.
Es.
m=7
Y=1,2,3,4,5,6,7
R1=T,T,F,T,F,F,F
R2=F,F,T,T,F,F,F
R3=T,F,F,F,F,T,F
ecc.
Come pensi di gestirlo? Diventa una funzione ricorsiva in un calcolo 
combinatorio (una cosa da mal di testa per m e Y grandi )
-- 
 ************** (.)_(.)  **************
 Un amico č uno che sa tutto di te e,
 nonostante questo, gli piaci
(E. Hobbard) 

 combinatorio (una cosa da mal di testa per m e Y grandi )
se una soluzione esiste basta che R la rappresenti, non serve che le 
rappresenti tutte.
crive
-- 


 combinatorio (una cosa da mal di testa per m e Y grandi )


 combinatorio (una cosa da mal di testa per m e Y grandi )


scusate per i messaggi multipli, colpa di newsland o della connessione 
presumo..


 ha scritto nel messaggio

come hai fatto l'algoritmo iterativo?

 Y*i1++Y*i2++.+Y*ik+=m.
questa non l'ho capita, c'è un errore di battitura? se "no", allora
non so esserti d'aiuto :D

 non so esserti d'aiuto :D
scusate, il copia incolla ha fatto cazzate, č cosě:
Y[i1]+Y[i2]+...+Y[ik]=m
-- 


The Philosopher ha scritto:


ho seguito questa idea:
parto con l'array bool R con tutti zeri,
inizio un ciclo che aumenta di 1 l'array R tramite una funzione 
ausiliaria(considerando l'array R come se fosse un numero binario che ad 
ogni ciclo aumenta di 1). 
all'interno di questo ciclo ce n'è un altro che fa la somma dei valori di
Y 
che corrispondono alle posizioni di R in cui c'è un 1.
appena trovo che questa somma==m, ho finito.
in pratica R (con per esempio n=3) cambia in questo modo:
000
001
010
011
100
101
111
in questo modo valuta tutte le possibili combinazioni di indici.
iterativamente è anche semplice, ma ricorsivamente temo di dover usare un 
metodo diverso
-- 


 restituire false.
In soldoni tu gli passi un'array di Booleani e la funzione ti dice se è 
una "soluzione" o meno? (dove con "soluzione" intendo che se sommi i 
vari Y[i] con R[i]=true ottieni m)
In questo caso io di ricorsivo ci metterei solo la somma dei vari Y[i] 
o.0' (ma sinceramente non  capisco il perchè della ricorsività o.0')
Ma credo di aver capito male il problema...
P.S. una funzione ricorsiva è una funzione che richiama se stessa, 
ora... cosa cazzo te ne fai di richiamare una funzione che ti dice se 
il vettore R è una "soluzione" in una funzione che ti dice se il 
vettore R è una "soluzione"? Non riesco a capire :S
(non ce l'ho con te eh, ce l'ho col problema :D)


sarebbe bello capire il perchè di certe cose che complicano solo la
vita...
l'idea di partire dall'array R e vedere se man mano trovo una
soluzione è quella che ho usato per la parte iterativa.
per la ricorsiva credo si debba usare un approccio diverso ma non
riesco bene a capire quale :-D

 (non ce l'ho con te eh, ce l'ho col problema :D)
Forse mi è venuta un'idea. Consideri il vettore R come se fosse un 
numero in base binaria. Come dicevi tu, un buon metodo è (se n=3) fare 
in modo che R diventi:
1 000
2 001
3 010
4 011
5 100
6 101
7 110
8 111
Ora, chiamiamo increase(int *R) una funzione che fa passare R dalla 
configurazione i alla configurazione i+1 (se non sai come fare, ma 
credo tu lo sappia, pensa R come appunto un numero in base 2 ed il 
gioco è fatto)
bool F(int m, int *Y, int n, bool *R)
{
    if(/*qua ci metti un ciclo che somma i vari valori Y[i] in base ai 
rispettivi valori di R[i]*/ == m) return 0;
    increase(*R);
    return bool F(m, *Y, n, *R);
}
Questa funzione restituisce true se esiste una soluzione *R. Per sapere 
a quale passaggio l'hai trovata basta trovare il numero in base 2 
rappresentato da *R (e incrementarlo di uno se non vuoi che il primo 
passaggio sia considerato il passaggio 0).
Spero di essere stato utile (e di aver capito il rpoblema -.-)

 m e sugli interi contenuti in Y.
Non capisco la formula. Immagino che intendi
Y[i1] + Y[i2] + ... + Y[ik] == m
giusto? Hai vincoli di complessita' particolari? Ovvero la soluzione
brutale e' accettabile oppure devi in qualche modo visitare astutamente
l'albero e abbassare il caso medio o ancora abbassare la complessita'
del caso pessimo?
La difficolta' che stai incontrando e' che quell'esercizio ti invita ad
usare funzioni ricorsive in modo *molto* poco funzionale. Il problema
principale e' che quel prototipo non ti facilita nel mantenere lo stato
(intuitivamente "quanto hai sommato fino a quel momento").
In realta', mi verrebbe da chiedermi se il testo dell'esercizio e'
formulato male, in quanto sembra costringerti all'uso di variabili
globali o a truccacci abbastanza zozzi per mantenere lo stato.
-- 
-riko


questa soluzione ha senso, ma è praticamente la soluzione iterativa
con un ciclo for trasformato in ricorsione. ora, la cosa andrebbe
anche bene, se non fosse per il fatto che ho dimenticato di citare la
parte del testo dell'esame in cui il prof dice esplicitamente:
Realizzare la funzione ricorsiva F_RIC. Questa funzione deve seguire
lo schema classico delle funzioni ricorsive. Non deve seguire l’idea
suggerita per l’esercizio iterativo. (per "idea suggerita" intende il
fatto che chiedeva di realizzare anche la funzione che tu hai chiamato
increase)
mah....
(scusa per la dimenticanza, son giorni che penso a come risolvere il
problema senza usare increase e quindi non mi è neanche venuto in
mente di citarvela)

 -riko
l'esercizio in se è anche formulato comprensibile, nel senso che ho un
array di numeri e un array di bool, trovo gli indici di Y in cui ci
sono gli elementi che sommati mi danno m, e R deve avere un 1 nelle
posizioni buone, e 0 in quelle non buone.
in effetti ora che penso a quello che dici, cioè all'albero, forse
qualche idea mi può venire...
ma non so neanche come formulare il caso base della ricorsione... cioè
si potrebbe fermare quando n<0, oppure quando m==0.. ora ci penso

 si potrebbe fermare quando n<0, oppure quando m==0.. ora ci penso
Hai bisogno di entrambi i casi, ovviamente. Uno e' un problema di
correttezza (sicuramente, a seconda di quello che e' n, finisce che ti
devi fermare che finisci lo spazio). L'altro ti dice se ce l'hai fatta.
Questo e' l'algoritmo che ti serve in Prolog:
solve(0, [], []).
solve(0, [_V|Vs], [0|Ms]) :-
    solve(0, Vs, Ms).
solve(N, [], []) :-
    N \== 0,
    !, fail.
solve(Tot, [V|Vs], [M|Ms]) :-
    (M=0, solve(Tot, Vs, Ms))
    ;
    (M=1, Tot1 is Tot - V, solve(Tot1, Vs, Ms)).
Se vuoi te lo do anche in C, ma credo che se vuoi ragionarci sopra,
questo qui ti guida diretto alla soluzione. Solo attenzione; per sua
stessa natura questo qua sopra e' stateless, in C sei stateful: occhio a
quello che scrivi nel buffer.
-- 
-riko


scusa, avevo postato la correzione dell'errore su un altro post,
usando google faccio fatica a seguire bene i lthread (sono fuori casa)

non conosco prolog, puoi anche scrivere in pseudo codice o in C se hai
cazzi ovviamente, mi basta capire un po' il ragionamento da fare, ci
sto pian piano arrivando ma faccio fatica :-)
adesso comunque guardo questo codice che hai scritto! e intanto grazie!


ecco:



la cosa che mi riesce difficile capire è:
se io arrivo che m==0 ho capito che ce l'ho fatta, allora
probabilmente al ritorno delle chiamate ricorsive devo mettere gli 1 e
gli 0 nell'array R, perchè non posso fare questo all'andata visto che
non so mai se sto percorrendo il cammino giusto (ipotizzando la
soluzione come un albero con 0 = ramo sinistro e 1 = ramo destro


non dando specifiche sul contenuto dell'array, ammettiamo che
m= 3
Y= [1,1,1,1,1]
il risultato sarebbe
R = [0,0,1,0,0]?
oppure
R = [1,1,1,0,0]? se fosse cosi' si spiegherebbe la ricorsività, che a
quel punto ti serve perche' una volta finite le elaborazioni, devi
tornare "all' indietro" nell'array di booleani e settare a true tutte
le posizioni precedenti al primo ritorno true della stessa funzione
chiamata ricorsivamente ;)
non so se mi sono stato spiegato.


R = [1,1,1,0,0,0] è la risposta corretta,
ma se ho
Y = [1,1,0,1,1,1] e m=3, la soluzione sarebbe
R = [1,1,0,1,0,0]
come faccio a settare quello zero tra gli uni che vanno bene?


hum , no, se tu avessi
Y = [1,1,0,1,1,1] e m=3
la soluzione sarebbe
R = [1,1,1,1,0,0]
se e' come mi hai detto che la risposta sarebbe corretta....


eh forse non mi sono spiegato bene:
se fosse come dici tu dovrei prendere le posizioni dove c'è 1 in R,
cioè dalla prima alla quarta, prendere i rispettivi numeri che stanno
in quelle posizioni in Y e sommarli, e verrebbe 1+1+0+1, che
effettivamente fa 3, quindi in questo esempio va bene anche la tua
soluzione, ma se invece di 0 in terza posizione metti un -10 avresti
1+1+(-10)+1, che fa -7.
certo che potevo pensare ad un esempio migliore prima :-D
quindi nel caso di Y = 1,1,-10,1,1,1
una soluzione è R= 1,1,0,1,0,0
ma anche questa è una soluzione per Y con R=  0,0,0,1,1,1.


hum ok ho capito, allor a'e molto piu' complicato di quanto pensassi.
eppure noj sono convinto che la soluzione valida sia quella che
intendi tu, ovvero, facciamo un'ipotesi
Y = 1,1,-10,1,10,2,3
quidni se e' coem dici tu ora la soluzione sarebbe
R = 1,1,1,1,1,0,0
in quanto il +10 e il -10 si annullano e concorrono comunqeu a fare la
somma di 3 , valore ipotetico di m...
insomma, mi sembra un po troppo complicato come ragionamento, dover
tenere conto di quali numeri "concorrono" e quali no ad arrivare alla
somma = m, visto che andando avanti questi potrebbero aggiungersi in
virtu' di valori precedentemente scartati...boh
comunqe ho scritto un programmino c++ al volo (con tanto di errorino
finale che ora non mi va di corregere:D) con funzione ricorsiva per
trovare nua soluzione del tipo
m= 3
Y = 1,1,1,1,1,1
R = 0,0,1,0,0,0
se ti serve, te lo mando.


se vuoi manda pure! l'indizirro è valido
solo che una soluzione del genere l'ho trovata anch'io ma vediamo
pure!
la soluzione come la intendo io è credo giusta, perchè è esattamente
il ragionamento che ho fatto per la versione iterativa, solo che in
quel caso valutare tutte le possibilità è molto facile, e ci si può
fermare subito appena si trova una soluzione...
o il prof non si è spiegato bene oppure booooooooh, cha casino..

 soluzione come un albero con 0 = ramo sinistro e 1 = ramo destro
In realta' IMHO *puoi* farlo all'andata, a patto che quando cambi branch
cambi anche quel marcatore. Comunque si, questa cosa dell'albero con i
rami etichettati puo' di fatto esserti molto utile per capire come
farlo.
Certo, il punto critico e' esattamente quello da te individuato: devi
stare *molto* attento a non cambiare in modo errato lo stato.
Usando Prolog ho "barato" poiche' di fatto le "copie" implicite le fa,
appunto implicitamente lui. Quindi vedi come e' coinciso?
Poi se non lo conosci nemmeno un pochetto mi rendo conto che non ti e'
di grande aiuto.
-- 
-riko

 adesso comunque guardo questo codice che hai scritto! e intanto grazie!
Allora, in Python viene cosi':
def solve(m, Y, R, i):
    #print m, Y, R
    if m == 0:
        return True
    if i == len(Y):
        return False
    R[i] = not R[i]
    if solve(m-Y[i], Y, R, i+1):
        return True
    else:
        R[i] = not R[i]
        return solve(m, Y, R, i+1)
Nota bene, qui non stiamo usando i puntatori e un indice n che ci dice
quanto rimane ma dei vettori di cui ci portiamo dietro nell'indice i il
punto a cui siamo arrivati.
Io poi ho anche la versione C, se vuoi vederla. Ma devi un po' dirmi tu
cosa preferisci.
-- 
-riko

 Y[i1]+Y[i2]+...+Y[ik]=m
Si lo avevo intuito, non avevo letto tutto il thread.
-- 
-riko

On 19 Lug, 18:04, 
r...@despammed.com
 (Enrico Franchi) wrote:

ho provato a tradurre in C questa soluzione che hai postato, ma non
funziona (evidentemente ho sbagliato io perchè non conosco bene
neanche il python)
se vuoi postare la versione in C mi faresti un favore!
una cosa, nel tuo codice incrementi i fino a che non diventa == alla
dimensione dell'array.
nella soluzione che devo realizzare (cioè che avrei dovuto realizzare
all'esame) ho ha disposizione solo il valore dim (che rappresenta la
dimensione dell'array), quindi la fine della ricorsione arriva quando
dim == 1.
non capisco bene poi il perchè di R[i]= not R[i], cioè cambi il valore
di R[i], ma come mai?
scusa per lo sbattimento sai, e grazie ancora per l'aiuto!

 scusa per lo sbattimento sai, e grazie ancora per l'aiuto!
Ma figurati... questo esercizio me lo riciclo per i miei il prossimo
semestre. HAW HAW HAW HAW. Solo che temo che non riusciranno a farlo.
-- 
-riko

 volta e' abbastanza poco testata.
Se vuoi provare a "romperlo":
<
http://github.com/rik0/rk-exempla/blob/master/algorithms/c/recursive_ex
ample.c>
-- 
-riko


ahahahahhah poveri!!! io non sono di certo un asso in questa materia,
ma IMHO questo esercizio è uno dei più tosti che ho trovato nei vari
appelli che ho fatto (e ne ho fatto taaaaaanti ahahha), più che altro
perchè in sede d'esame vuoi per il tempo, vuoi per l'agitazione e il
fatto che noi dobbiamo scrivere le soluzioni su carta, non mi sarebbe
mai venuta l'intuizione giusta!
sei stato gentilissimo comunque!
ps: ma insegni questa materia?

 ps: ma insegni questa materia?
Non so quale sia "questa materia". :)
La dicitura ufficiale e' di collaboratore didattico... in un certo senso
quindi "insegno", ma di fatto e' piu' simile al ruolo di un
esercitatore-laboratorio. Lo ho fatto per Algoritmi, lo ho fatto (e
probabilmente lo faro') per Programmazione 1.
-- 
-riko

 perfetto!!!
scusa tornato ora dalla piscina, vedo che hai risolto e forse anche in
modo piu' semplice di come avevo fatto io (che non sono neanche sicuro
di cosa ho fatto precisamente ehhehe)
ciao!
ps: w i nerd informatici

 probabilmente lo faro') per Programmazione 1.
eccomi! rispondo in ritardo perchè son sotto a studiare per l'orale!
la materia è proprio programmazione 1!!


questa versione è in effetti uguale all'altra, intuitivamente forse l' *R = 
1 rende l'idea un po' più semplice..
se ho capito bene il ragionamento che si fa è questo:
ad una qualsiasi chiamata della funzione mi trovo in un punto dell'array 
che, passati i casi base, setto a 1 (è questo il punto che non capisco del 
tutto)
poi, se il test mi ritorna 1 vuol dire che le chiamate successive hanno 
avuto successo, e in quel caso mi va bene l'1 che avevo settato prima nella 
attuale posizione,
in caso contrario setto a 0 la mia attuale posizione (perchè appunto il test 
non ha avuto successo, e faccio la chiamata con m (senza diminuirlo, perchè 
evidentemente se il test ha dato 0, vuol dire che devo passare l'm senza 
diminuirlo di *Y).
veramente io devo avere dei limiti per quanto riguarda la ricorsione, perchè 
non mi è proprio facile capire il ragionamento che si fa per settare la 
posizione attuale..
nel senso che io (sbagliando) avrei fatto prima il test, e in base all'esito 
avrei settato *R a 1, ma così non credo funzioni...
invece si parte dal presupposto che passati i casi base si setta *R=1
quanta confusione ho un testa? ahahehh 

 ciao, f.
lo voglio!
è comprensibile da una mente arretrata come la mia? ;-) 

 ciao, f.
venerdì vado in cerca! grazie del consiglio! 

 "Goedel Escher Bach, un'Eterma Ghirlanda Brillante", Douglas Hofstadter.
Io ce l'ho autografato!!! Tiè! :D
Mi ricordo uno stralcio della conversazione: (tra l'altro parla un 
italiano migliore del mio :S)
Io "Io e un mio amico abbiamo provato a fare quell'esercizio sulla 
definizione delle potenze, abbiamo definito tutte le potenze di primi"
Lui "sisi"
Io "Poi abbiamo provato con le potenze di 10"
Lui "noooo! No,no,no,no lasciate perdere!"
Dev'essere veramente una cosa tosta se dopo 30 anni se la ricorda 
ancora così brutta :D

 quanta confusione ho un testa? ahahehh 
La ricorsione per molti e' estremamente ostica. Aiuta avere una solida
comprensione del principio di induzione ed essere familiari con il fare
dimostrazioni per induzione. Potresti anche dimostrare per induzione che
il codice mostrato fa quello che ti aspetti. 
In generale credo sia anche un problema in Italia il fatto che in molti
posti si insegni a programmare in C o in Java invece che in qualche
linguaggio come scheme. Una volta ho anche scovato un tizio (svizzero,
pero') che non credeva manco fosse possibile che esistesse la
ricorsione.
-- 
-riko

 la materia è proprio programmazione 1!!
Ok! Dove?
In bocca al lupo, comunque. 
-- 
-riko

 In bocca al lupo, comunque.
fatto stamattina, ovviamente mi ha chiesto un esercizio che non avevo capito 
tanto bene... diciamo che è stato buono e finalmente ho passato 'sto 
esame!!!! :-D
(ora dovrò iniziare a pensare a prog2 aiuto ahahhahaah) 

 esame!!!! :-D
Scommetto che il programma doveva restituire una parola che iniziava 
per S e una per F e ha restituito "Segmentation Fault" :D

 (ora dovrò iniziare a pensare a prog2 aiuto ahahhahaah) 
Beh, in bocca al lupo!
-- 
-riko

 senza quello li.
infatti mi mancano praticamente solo gli esami che venivano bloccati da 
prog1.. a parte algoritmi e calcolo e qualcos'altro..

 per S e una per F e ha restituito "Segmentation Fault" :D
ahahaahaha maledetto segmentation fault!!!