Newsgroup: it.comp.lang.c
Titolo: nn riesco a trovare l'errore

ciao a tutti, ho questo algoritmo che dato un arrai cn righe e colonne 
ordinate in ordine crescente, mi dice se un elemento è presente o meno 
nell'array. l'array è di questo tipo;
4  5   6
7  10  11
9  21  22
questo è l'algoritmo..solo che il progrmma esce cn un errore..va in 
crash e nn capisco perchè. inoltre vorrei sapere cm si passano gli 
array di 2 dimensioni creati dinamicamente ad una funzione. devo 
passare per forza la seconda dimensione??
#include <stdio.h>
#include <stdlib.h>
typedef enum {falso, vero} boolean;
void appartiene(int *a[3], int riga, int colonna, int elemento, int n, 
boolean *trovato);
int main()
{
	int **a, n, riga, colonna, elemento, i, j;
	boolean trovato, *p;
printf("Inserisci la dimensione di A\n");
scanf("%d", &n);
a=(int**)malloc(n*sizeof(int*));
for(i=0;i<n;i++)
a[i]=(int*)malloc(n*sizeof(int));
printf("inserire gli elementi nell'array\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
     printf("a[%d][%d] = ", i, j);
     scanf("%d", &a[i][j]);
}
printf("l'elemento da cerca e': \n");
scanf("%d", &elemento);
trovato = falso;
p=&trovato;
riga = 1;
colonna = n;
appartiene(*a[3], riga, colonna, elemento, n, p);
if (trovato == vero)
printf("L'elemento è stato trovato nella posizione a[%d][%d]\n", riga, 
colonna);
else
printf("L'elemento nn è presente\n");
	return 0;
}
void appartiene(int *a[3], int riga, int colonna, int elemento, int n, 
boolean *trovato)
{
     if(a[riga][colonna] == elemento)
     trovato = vero;
     else if (a[riga][colonna] < elemento)
     {
          if (riga <n)
          appartiene(a, riga+1, colonna, elemento, n, trovato);
          else
          trovato = falso;
     }
     else if (colonna >1)
          appartiene(a, riga, colonna-1, elemento, n, trovato);
     else
     trovato = falso;
}
-- 
Renato Zero
Provaci a riemergere, da quei sogni che il tuo silenzio ha ucciso...che 
ne sai, dell'origine, delle lacrime, se non ha mai pianto...provaci, a 
scommettere, che al traguardo tu non sarai secondo...agile è 
quest'anima,  non puoi vincerla, non la puoi ingannare più......PROVA A 
PRENDERMI......

appartiene(*a[3], riga, colonna, elemento, n, p);
appartiene(a, riga, colonna, elemento, n, p);

risolto..adesso funziona....solo un altra curiosità...è strano, ma se 
lo faccio per qualunque numero funziona....se lo faccio per il 9 nn 
funziona!!! è stranissimo!! mi aiuti a capire perchè?
questo è il codice esatto:
#include <stdio.h>
#include <stdlib.h>
typedef enum {falso, vero} boolean;
void appartiene(int *a[3], int riga, int colonna, int elemento, int n, 
boolean *trovato);
int main()
{
    int **a, n, riga, colonna, elemento, i, j;
    boolean trovato;
printf("Inserisci la dimensione di A\n");
scanf("%d", &n);
a=malloc(n*sizeof(int*));
for(i=0;i<n;i++)
a[i]=malloc(n*sizeof(int));
printf("inserire gli elementi nell'array\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
     printf("a[%d][%d] = ", i, j);
     scanf("%d", &a[i][j]);
}
printf("l'elemento da cerca e': \n");
scanf("%d", &elemento);
trovato = falso;
riga = 0;
colonna = n-1;
appartiene(a, riga, colonna, elemento, n, &trovato);
    return 0;
}
void appartiene(int *a[3], int riga, int colonna, int elemento, int n, 
boolean *trovato)
{
     if(a[riga][colonna] == elemento)
     {
     *trovato = vero;
     printf("L'elemento e' stato trovato nella posizione a[%d][%d]\n", 
riga, colonna);
     }
     else if (a[riga][colonna] < elemento)
     {
          if (riga <n)
          appartiene(a, riga+1, colonna, elemento, n, trovato);
          else
          {
          *trovato = falso;
          printf("L'elemento non e' stato trovato\n");
          }
     }
     else if (colonna >1)
          appartiene(a, riga, colonna-1, elemento, n, trovato);
     else
     {
     *trovato = falso;
     printf("L'elemento non e' stato trovato\n");


funziona!!! è stranissimo!! mi aiuti a capire perchè?
Non è stranissimo, è semplicemente il tuo programma che non funziona.
Se "funziona" per n-1 numeri e non funziona per 1 numero, allora *non
funziona* perché c'è sicuramente qualcosa di errato.  Dotati di un
buon compilatore/debugger, esegui il codice passo passo e vedi dov'è
il problema.

 funziona!!! è stranissimo!! mi aiuti a capire perchè?
Giusto un paio di consigli per fare emergere il problema.
Cerca di semplificare il codice, serve proprio che appartiene() sia 
ricorsiva?
Usando l'aritmetica dei puntatori potresti fare una sola malloc, visto 
che per una matrice di int nxn puoi usare un array di dimensioni n*n ed 
accedere con:  *(a + ((n*r)+c))).
(E magari fare anche una free() alla fine, meglio non fidarsi)
Alla luce di quanto sopra il prototipo di appartiene() è giusto?
Butta via le scanf() (origine di ogni male :) ) e fai in modo che il tuo 
programma legga un file:
3           <-- dimensione
4  5   6
7  10  11
9  21  22
e restituisca una matrice (e la dimensione!!!)
Vedrai che dopo aver lavorato un po' in questa direzione ti troverai un 
con un programma funzionante.
Mi associo ad Andrea sul debugger: vedere cosa accade ad ogni passo e 
come cambiamo i valori delle singole variabili è la cosa migliore per 
capire cosa c'e' che non va!
Remo D.

Usando l'aritmetica dei puntatori potresti fare una sola malloc, [...]
Non è necessario complicarsi la vita.  Il C offre già abbastanza
"pitfalls", perché andare a cercare rogne ?
Se serve una matrice, si allochi una matrice.

 Se serve una matrice, si allochi una matrice.
Per fortuna c'e' piu' di un modo per spellare un gatto. Magari se gli 
indichi una strada da percorrere riesce a trovare la Via!

 funziona!!! è stranissimo!! mi aiuti a capire perchè?
La cosa sensata e' usare un debugger o visto la dimensione
minuta del programma debuggare sulla carta, facendoti una tabellina
dei valori e aggiornandoli passo passo.
Personalmente la mia mente si rifiuta di leggere il tuo programma perche'
e' inutilmente complicato.
Non ha nessun senso usare la ricorsione come la  stai usando tu.
La ricorsione avrebbe senso se tu la utilizzassi
per effettuare una ricerca binaria fondata sul fatto che righe
e colonne sono ordinate. Tu non fai una ricerca binaria
e quindi non serve usare la ricorsione.
Per vedere se un elemento e' contenuto nella matrice
tanto vale scandire tutti gli elementi con due banali for.
int appartiene(int *a[3],int n, int el)
{
int i,j;
for (i=0; i<n;i++)
   for (j=0; j<n;j++)
     if (a[i][j]==el) return 1;
return 0;
}
ciao,
g.

indichi una strada da percorrere riesce a trovare la Via!
Non capisco il senso delle tue parole.  La tua non è di certo
un'indicazione per trovare la Via, ma semmai gli poni qualche ostacolo
in più sulla strada.

int appartiene(int *a[3],int n, int el)
...e magari si eviti pure di dichiarare una funzione con un argomento
a dimensione fissa, se poi tale dimensione viene chiesta a run-time...

 in più sulla strada.
[dall'altra email]
 >> int appartiene(int *a[3],int n, int el)
 >
 > ...e magari si eviti pure di dichiarare una funzione con un argomento
 > a dimensione fissa, se poi tale dimensione viene chiesta a run-time...
Magari pensando a come funzionano i puntatori gli poteva venire in mente 
di verificare *a[3] nella definizione di appartiene().
Potevamo suggerirgli di leggere le C FAQ (la sezione 6) o altri commenti 
costruttivi.
La Via che puo' essere definita non è la Via! :)
Remo D.

costruttivi.
Oppure potevamo dirgli di prendere un buon debugger ed eseguire la sua
applicazione passo passo per verificare dov'è l'errore.
Ora basta col battibecco, se vuoi essere realmente costruttivo.

 Ora basta col battibecco, se vuoi essere realmente costruttivo.
OK, nessun problema.
Remo D.

 
vorrei aggiungere una piccola cosa a questa grande verita':
mai debuggare con carta e penna, non siamo dei compilatori C e potremmo 
fare facilemente degli errori di interpretazione.
sotto questo punto di vista il compilatore/debugger non puo' sbagliare, 
noi SI!
per cui fate sempre largo uso del debugger passo passo!

allora.so che l'esercizio magari può essere fatto in modo 
diverso...però io ho questo testo per questo algoritmo e devo farlo 
cosi:
"Dato un array 2D "a" di tipo intero, di dimensione nXn, in cui gli 
elementi in ogni riga ed in ogni colonna sono in ordine crescente come 
nell'esempio:
4   5   6
7   10  11
9   21  22
Si progetti un algoritmo RICORSIVO sotto forma di procedura.
ad esempio  appartiene(A, riga, colonna, elem, n, trovato)
basato sulla tecnica "divide and conquer" per determinare se un intero 
elem è presente nell'array o no!
perciò ho scritto quell'algoritmo...ora volevo sapere cosa sbagliavo!! 
per quanto riguarda il debuger quale posso usare?? provo cn codeblock 
ma si blocca...forse nn l'ho settato bene, ho nn ho scaricato il 
"debuger" apposti....nn so...se mi aiutate x favore....vi ringrazio


 elem è presente nell'array o no!
Il problema è che nel tuo programma non si capisce bene dove hai 
applicato il concetto di divide & conquer.
Se non ho capito male parti dall'angolo in alto a destra (a[0][n-1]) e 
ti sposti di una riga in basso se l'elemento da cercare è piu' grande o 
di una colonna a sinistra se l'elemento è piu' piccolo. Giusto?
Nel peggiore dei casi avrai fatto 2n confronti per scoprire che 
l'elemento non c'e'.
Per far questo, pero', la ricorsione non è utile (cioe' non semplifica 
l'algoritmo).
Un'approccio divide&conquer potrebbe essere dividere la matrice in 
quattro sottomatrici (che conservano le proprietà sull'ordinamneto) e 
lavorare separatamente sulle quattro matrici.
Se n è dispari puoi eliminare 1/4 dei valori (se l'elemento  da cercare 
è piu' piccolo del valore a[ceil(n/2)][ceil(n/2)] o 3/4 (se è piu' grande).
Se n è pari devi lavorare un po' di piu' ma puoi stabilire, per ogni 
sottomatrice, se deve essere esclusa o inclusa al passo successivo.
Implementare tutto cio' in C è abbastanza complicato e spero ci sia un 
modo piu' semplice. E' sempre una soluzione O(n) ma tutto il lavorio di 
suddivisione cancella qualunque vantaggio per n non troppo grandi.
Qualcuno ha un'altra idea?
Remo D.

io devo rispettare quello che mi dice il testo dell'esercizio..ovvero 
usare per forza la ricorsione e per forze un prototipo di funzione come 
quello che mi da l'esercizio..altrimenti la saprei fare in modi 
diversi...cmq l'ho corretto l'algoritmo e ora funziona bene...ti 


l'algoritmo).
E' ciò che gli richiede l'esercizio, però, e deve utilizzarla per
forza.  

 diversi...cmq l'ho corretto l'algoritmo e ora funziona bene...ti ringrazio
Su questo concordo ma, se ho ben capito il tuo algoritmo, non mi sembra 
che sia classificabile come "divide & conquer" e quindi NON hai 
rispettato il testo dell'esercizio!
Remo D.

che sia classificabile come "divide & conquer"[...]
Sono curioso di sapere per quale motivo per te non lo sia...


Non ricordo la definizione esatta (infatti ho detto "mi sembra) di D&Q e 
quindi mi sarebbe utile se qualcuno mi facesse notare il mio errore 
spiegando perche' l'algoritmo che Runner ha implementato è del tipo D&Q.
Nel frattempo ti descrivo il mio ragionamento cosi' puoi indicarmi dove 
sbaglio.
L'approccio D&Q prevede di dividere il problema in piu' parti ed 
applicare a ciascuna parte separatamente (e ricorsivamente) la strategia 
di soluzione. Nel suo caso, invece, ciascun passo dell'algoritmo 
trasforma una matrice nxn in una (n-1) x n o n x (n-1) e procede 
iterativamente sulla nuova matrice (il fatto che sia implementato 
ricorsivamente mi sembra solo un escamotage per soddisfare il testo del 
problema).
L'esempio classico del mergesort forse puo' aiutarmi a spiegarmi meglio: 
per fare il mergesort di una lista L, la divido in due parti, faccio il 
mergesort delle due parti separatemente e ricombino il risultato.
Mi sembra, e ti ripeto mi sembra, che l'algoritmo implementato da runner 
non sia di questo tipo.
Mi sarei aspettato un approccio simile a quello che ho descritto nel mio 
messaggio precedente in cui ho diviso la matrice in 4 matrici ed ho 
applicato lo stesso algoritmo alle quattro matrici.
A questo punto spero tu mi possa indicare dove sbaglio.
Remo D.

problema).
Sě, credo che faccia cosě, ma in ogni caso non si puň dire, a mio
parere, che questa non sia una tecnica D&C.

 parere, che questa non sia una tecnica D&C.
Secondo me non lo è per il motivo che ho scritto nel messaggio 
precedente: non scompone il problema in parti a cui ri-applicare 
l'algoritmo ma si limita a navigare sulla matrice originale, ergo non è 
D&C.
Se si trattasse di un esercizio d'esame (come suppongo sia) sarebbe 
meglio non entrare in questa discussione con il prof se non si è 
assolutamente sicuri! Fossi Runner indagherei!
Remo D.

D&C.
D&C significa esattamente ciò che significa, non altro.  La tua
definizione di D&C è un po' troppo stretta nei presupposti: anche
l'algoritmo quick-sort (tipico esempio di D&C) può applicarsi
ricorsivamente alla stessa struttura dati.  Non capisco, sinceramente,
il motivo della tua obiezione.  Quello che io ti chiedo è: data la
definizione di D&C, dimostra (scientificamente) che quell'algoritmo
non è D&C.

 D&C significa esattamente ciò che significa, non altro.
Ok. Pero' prima definiamo esattamente D&C. Va bene la definizione presa 
da Wikipedia riportata qui' sotto?
"In computer science, divide and conquer (D&C) is an important algorithm 
design paradigm. It works by recursively breaking down a problem into 
two or more sub-problems of the same (or related) type, until these 
become simple enough to be solved directly. The solutions to the 
sub-problems are then combined to give a solution to the original problem."
Meglio stabilirlo prima o alla fine del mio ragionamento mi dirai che 
"la mia definizione di D&C è troppo restrittiva" :)
Remo D.

two or more sub-problems of the same (or related) type
Ora in base a questo dimostra la tua tesi.

 Ora in base a questo dimostra la tua tesi.
OK. Supponiamo, per assurdo, che l'algoritmo di Runner sia D&C. Se 
arrivo ad una contraddizione (o ad una falsità) avro' dimostrato la mia 
tesi.
Nell'algoritmo di Runner esiste quindi un punto in cui il suo problema 
(la ricerca di un elemento x nella matrice A) viene suddiviso in sotto 
problemi (suddivisione di A in A1, A2, ... e ricerca di x in A1, A2, ...).
E questa è una falsità: l'algoritmo di Runner non ha questo 
comportamento. Esso procede eliminando, di volta in volta, una riga o 
una colonna fino a trovare x o stabilire che x non è presente.
Inoltre la definizione D&C prevede che le soluzioni dei sotto-problemi 
vengano combinate per ottenere la soluzione del problema originale.
Anche questo aspetto manca nell'algoritmo di Runner.
Da ciò segue che l'algoritmo di Runner non è D&C.
Permettimi di aggiungere che se volessimo stiracchiare la definizione di 
D&C dicendo che, in fondo, lui applica il suo algoritmo ad una matrice 
ogni volta piu' piccola, avremmo appena fatto diventare la ricerca 
lineare un algoritmo D&C il che mi sembra un attimo esegerato.
Il quicksort che hai citato, invece, è D&C visto che, una volta 
stabilito un pivot p, la lista iniziale L viene divisa in due liste L1 
ed L2 e la soluzione è del tipo:
   quicksort(L) = quicksort(L1)+p+quicksort(L2).
Fossi Runner riguarderei l'esercizio. Fossi il prof di Runner gli darei 
un 7/10 visto che c'e' andato vicino ma non ha colto l'essenza della 
richiesta di fare un algoritmo D&C.
L'algoritmo che ho proposto io è D&C perche' procede nel dividere la 
matrice in quattro parti e riapplicare l'algoritmo alle 4 parti 
separatamente.
Spero che tu voglia accettare questo mio ragionamento o, in caso 
contrario, proporne uno che dimostri che l'algoritmo di Runner è D&C.
Ciao.
Remo D.

 di fare un algoritmo D&C.
ho letto i vostri post, e vi ringrazio per le risposte.....cmq oggi il 
prof ha messo sul sito la soluzione dell'esercizio.....ed è identica a 
quella che ho fatto io!!!!! quindi due sn le cose:
o il D&C si può attuare anche in questo modo
oppure il prof ha sbagliato! ;-)
mistero.... mdr mdr mdr


 oppure il prof ha sbagliato! ;-)
Secondo me il prof si e' confuso.
Nel senso che di sicuro l'algoritmo non rientra nello spirito del D&C.
Non basta che un algoritmo sia ricorsivo per essere classificato D&C,
specialmente in un caso come questo dove la ricorsione e' sostanzialmente
inutile e maschera un procedimento di tipo greedy.
ciao,
g.

 Secondo me il prof si e' confuso.
Ovviamente sono daccordo con te :)
Se fosse un prof disponibile io ci andrei a parlare. Almeno per chiarire 
perchè lo ritiene D&C ...
Remo D.

 quella che ho fatto io!!!!! quindi due sn le cose:
Ci dai il link? (se è accessibile ai non iscritti).
Remo


ho scaricato il pdf dell'esercitazione...eccolo:
http://www.filelodge.com/files/hdd2/24946/Esercitazione%2027-04.pdf
">Esercitazione 
27-04.pdf
stà nella seconda pagina


 
Grazie. Comunque la cosa continua a non convincermi, l'esercitazione 
successiva, infatti, presenta un vero algoritmo D&C per la ricerca del 
minimo. Puoi riconoscerci gli elementi di cui abbiamo parlato 
(suddivisione, applicazione ai sottoproblemi, ricombinazione).
Grazie al cielo (o dovrei dire purtroppo!) i tempi dell'università sono 
passati da un pezzo per me!
Se mai ti dovesse capitare di discuterne col prof (o di sentire di altri 
che l'hanno fatto) faccelo sapere. A questo punto sono curioso :)
Remo D.

vi farò sapere ;-) ciao grazie
