View Full Version : [C/C++] Esercizio di ricorsione
zanardi84
23-11-2011, 16:31
Salve a tutti, secondo voi è corretto il codice che posto che risolve il seguente problema?
Stabilire se l'intervallo tra due numeri interi si accavalla ad un altro intervallo dato.
La mia idea è quella di confrontare ogni numero dell'intervallo con l'intervallo fissato e, se appartiene, allora gli intervalli si accavallano. Ho pensato di usare la tecnica della ricorsione.
Il controllo che ultimo sia successivo a primo e che primoDato sia successivo a ultimoDato è fatto in una funzione precedente, quindi l'ordine è sempre corretto.
primo e ultimo sono i numeri dell'intervallo che voglio confrontare.
primoDato e ultimoDato sono i numeri dell'intervallo di riferimento.
bool trova (int primo, int ultimo, int primoDato, int ultimoDato)
{
bool sovrappone = false;
int numero;
numero = primo;
if(numero == ultimo)
{
if(numero >= primoDato && numero <= ultimoDato)
{
sovrappone = true; // si sovrappone
}
}
if(numero >= primoDato && numero <= ultimoDato)
{
sovrappone = true; // si sovrappone
}
else
{
if(numero < ultimo)
{
return trova(numero+1, ultimo, primoDato, ultimoDato);
}
}
return sovrappone;
}
Che dite?
Grazie
Puoi fare un esempio di accavallamento?
Perché altrimenti, da quello che sembra, la soluzione è banale:stordita:
Per esempio, l'intervallo [4,8] si accavalla a [2,9]?
e invece a [5,9]?
un banale confronto fra interi potrebbe essere la soluzione :stordita:
zanardi84
24-11-2011, 17:29
Puoi fare un esempio di accavallamento?
Perché altrimenti, da quello che sembra, la soluzione è banale:stordita:
Per esempio, l'intervallo [4,8] si accavalla a [2,9]?
e invece a [5,9]?
un banale confronto fra interi potrebbe essere la soluzione :stordita:
Beh, dall'algoritmo che ho scritto:
4 è compreso tra 5 e 9? NO, passo a 5.
5 è compreso tra 5 e 9? SI' -> l'intervallo si accavalla.
4 è comrpeso tra 2 e 9? SI' -> l'intervallo si accavalla.
Cosa proponi come confronto tra interi? Si può sempre usare la ricorsione (che è poi lo scopo finale di questo esercizio, nonchè mio obiettivo, visto che sino ad ora ho sempre preferito i cicli perchè più lineari da implementare.
goldorak
24-11-2011, 20:03
Considera due intervalli
[a,b] e [c,d]
Sono disgiunti se e solo se c>b oppure d<a.
In caso contrario i due intervalli si sovrappongo.
Piu' semplice di cosi' si muore.
Considera due intervalli
[a,b] e [c,d]
Sono disgiunti se e solo se c>b oppure d<a.
In caso contrario i due intervalli si sovrappongo.
Piu' semplice di cosi' si muore.
Infatti.
E' proprio perché è così semplice che non mi torna :confused:
Boh?
zanardi84
25-11-2011, 09:19
Considera due intervalli
[a,b] e [c,d]
Sono disgiunti se e solo se c>b oppure d<a.
In caso contrario i due intervalli si sovrappongo.
Piu' semplice di cosi' si muore.
In effetti funziona anche così!
E se avessi un insieme di numeri interi, univoci, quindi non ripetuti, da 1 a 100 e volessi costruire un set di sottoinsiemi, tra loro disgiunti?
Per esempio: numeri da 1 a 100. Su questo grosso insieme ho diversi altri sottoinsiemi
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
e così via.
Mi chiedo se questi insieme siano disgiunti rispetto a quelli dati e pertanto creabili:
[4, 26] o [19, 53] o [60, 100] o [64, 89]
sarei tentato di confrontare ogni intervallo con gli altri dati.
[4,26] si accavalla con [1,23] o [24,27] o [28, 45] o [50,51] o [63,90]?
Confronto [4,26] con [1,23]: si accavalla? sì, allora vuol dire che non è un intervallo che posso creare.
[64, 89] si accavalla con [1,23]? No, passo a confrontarlo con [24,27]: si accavalla? No. Proseguo. Arrivo sino a confrontare con [53,63], se non trovo un intervallo in cui si accavalla.
Se non si accavalla a nessuno, allora è un sottoinsieme creabili.
Giusto?
In effetti funziona anche così!
E se avessi un insieme di numeri interi, univoci, quindi non ripetuti, da 1 a 100 e volessi costruire un set di sottoinsiemi, tra loro disgiunti?
Per esempio: numeri da 1 a 100. Su questo grosso insieme ho diversi altri sottoinsiemi
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
e così via.
Mi chiedo se questi insieme siano disgiunti rispetto a quelli dati e pertanto creabili:
[4, 26] o [19, 53] o [60, 100] o [64, 89]
sarei tentato di confrontare ogni intervallo con gli altri dati.
[4,26] si accavalla con [1,23] o [24,27] o [28, 45] o [50,51] o [63,90]?
Confronto [4,26] con [1,23]: si accavalla? sì, allora vuol dire che non è un intervallo che posso creare.
[64, 89] si accavalla con [1,23]? No, passo a confrontarlo con [24,27]: si accavalla? No. Proseguo. Arrivo sino a confrontare con [53,63], se non trovo un intervallo in cui si accavalla.
Se non si accavalla a nessuno, allora è un sottoinsieme creabili.
Giusto?
Non ho capito :D
Hai un insieme (intervallo) di numeri interi, da 1 a 100 e vuoi costruire un set di sottoinsiemi (intervalli).
Per esempio questi:
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
e così via...
Ora vuoi verificare se un dato intervallo è disgiunto rispetto a quelli dati.
Domanda: i numeri da 0 a 100 li hai espressi nel tuo esempio come un insieme di intervalli, pertanto sono rappresentati TUTTI i numeri da 0 a 100.
Qualunque intervallo di interi tra 0 e 100 non sarà mai disgiunto dall'insieme di intervalli dell'esempio.
Mi sfugge qualcosa?
zanardi84
25-11-2011, 09:58
Non ho capito :D
Hai un insieme (intervallo) di numeri interi, da 1 a 100 e vuoi costruire un set di sottoinsiemi (intervalli).
Per esempio questi:
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
e così via...
Ora vuoi verificare se un dato intervallo è disgiunto rispetto a quelli dati.
Domanda: i numeri da 0 a 100 li hai espressi nel tuo esempio come un insieme di intervalli, pertanto sono rappresentati TUTTI i numeri da 0 a 100.
Qualunque intervallo di interi tra 0 e 100 non sarà mai disgiunto dall'insieme di intervalli dell'esempio.
Mi sfugge qualcosa?
Ho scritto male :D
Ho un insieme di numeri da 1 a 100 (ma ho messo 100 solo per limitarlo, altrimenti avrei potuto estendere il caso anche a infiniti numeri)
All'interno di questo insieme ho alcuni sottoinsiemi.
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
che come puoi vedere sono disgiunti non avendo mai elementi comuni tra loro.
Voglio costruire altri sottoinsiemi disgiunti.
Ogni sottoinsieme in realtà è una sequenza ordinata di numeri, in questo caso che mi interessa.
Posso costruire i sottoinsiemi [4, 26] o [19, 53] o [60, 100] o [64, 89], sapendo che ogni sottoinsieme deve essere disgiunto da tutti gli altri?
Ho scritto male :D
Ho un insieme di numeri da 1 a 100 (ma ho messo 100 solo per limitarlo, altrimenti avrei potuto estendere il caso anche a infiniti numeri)
All'interno di questo insieme ho alcuni sottoinsiemi.
[1,23]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
che come puoi vedere sono disgiunti non avendo mai elementi comuni tra loro.
Voglio costruire altri sottoinsiemi disgiunti.
Ogni sottoinsieme in realtà è una sequenza ordinata di numeri, in questo caso che mi interessa.
Posso costruire i sottoinsiemi [4, 26] o [19, 53] o [60, 100] o [64, 89], sapendo che ogni sottoinsieme deve essere disgiunto da tutti gli altri?
Gli 'insiemi' [x,y] chiamali intervalli, così è più coerente :)
Se gli intervalli dati sono ordinati, bene. Altrimenti li ordini.
Poi, dato l'intervallo [a,b] devi verificare se questo è disgiunto confrontando a e b con gli intervalli dati.
Qui con un po' di inventiva devi ridurre al minimo i confronti :cool:
goldorak
25-11-2011, 10:16
--------
Quindi se ho capito bene ad ogni passo dell'algoritmo hai una famiglia di sottoinsiemi disgiunti ad esempio A={S1, S2, S3,......Sn} e vuoi sapere se un dato intervallo [a,b] interseca uno qualsiasi degli Si. In caso affermativo non fai niente, in caso negativo aggiungi [a,b] all'insieme A.
Per fare questo basta un algoritmo union find.
Se A è un insieme ordinato di intervalli disgiunti sarebbe interessante un algoritmo stile ricerca binaria.
No?
:D
zanardi84
25-11-2011, 10:29
Ci sono.
Gli intervalli sono ordinati, nel senso che se [x,y] dove x è il più piccolo e y il più grande, non avrò mai x scambiato con y perchè prima di eseguire il confronto è bene introdurre una funzione di confronto e/o ordinamento.
Ho provato a tradurre in codice (molto grezzo e minimale) l'intenzione.
Come potete osservare, inserisco dal codice (perchè ai fini dell'algoritmo non mi interessa avere inserimenti o altro perchè posso benissimo farlo in un'altra funzione). Mi sembra che funzioni, o sbaglio?
#include <iostream>
using namespace std;
typedef struct intervallo
{
int primo;
int ultimo;
}INSIEME;
INSIEME sequenza[5];
bool confronto(int a, int b, int i);
int main()
{
bool sovrappone = false;
sequenza[0].primo = 81;
sequenza[0].ultimo = 86;
sequenza[1].primo = 9;
sequenza[1].ultimo = 14;
sequenza[2].primo = 1;
sequenza[2].ultimo = 5;
sequenza[3].primo = 44;
sequenza[3].ultimo = 44;
sequenza[4].primo = 6;
sequenza[4].ultimo = 8;
for (int i = 0; i < 5; i++)
{
cout << i<< endl;
sovrappone = confronto(7,8, i);
if (sovrappone == true)
{
cout << "STOP!!! LA SEQUENZA SI SOVRAPPONE" << endl;
break;
}
}
if (sovrappone == false)
{
cout << "NON SI SOVRAPPONGONO!!!" << endl;
}
return 0;
}
bool confronto(int a, int b, int i)
{
bool sovrappone = true;
if(sequenza[i].primo> b || sequenza[i].ultimo < a)
{
sovrappone = false;
}
return sovrappone;
}
Mi sembra funzionare.
L'insieme S ordinato vuol dire che presi due intervalli
Si e Sj, con j>i
i rispettivi intervalli
[Ai, Bi] e [Aj, Bj]
rispettano la condizione Bi<Aj
Più semplicemente sono in quest'ordine:
[2,6] [8,15] [22, 50] etc...
:)
Visto che da oggetto parlavi di esercizio ricorsivo, puoi costruire una funzione ricorsiva del tipo:
overlap(intervallo, insieme)
che restituisce vero o falso. Dato che l'insieme è ordinato puoi operare la ricorsione come nella ricerca binaria.
Correggetemi se ho detto stupidaggini :D
zanardi84
25-11-2011, 10:51
Mi sembra funzionare.
L'insieme S ordinato vuol dire che presi due intervalli
Si e Sj, con j>i
i rispettivi intervalli
[Ai, Bi] e [Aj, Bj]
rispettano la condizione Bi<Aj
Più semplicemente sono in quest'ordine:
[2,6] [8,15] [22, 50] etc...
:)
Visto che da oggetto parlavi di esercizio ricorsivo, puoi costruire una funzione ricorsiva del tipo:
overlap(intervallo, insieme)
che restituisce vero o falso. Dato che l'insieme è ordinato puoi operare la ricorsione come nella ricerca binaria.
Correggetemi se ho detto stupidaggini :D
Non penso che importi l'ordine degli insiemi ai fini del funzionamento perchè basta la sovrapposizione ad uno e un solo sottoinsieme per rendere non accettabile l'intervallo.
A sto punto penso che la ricorsione non abbia un'applicazione utile in questo caso, con questo metodo di confronto, o sbaglio?
Invece importa l'ordinamento.
prendi questa sequenza:
[1,19]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
L'insieme è fatto da intervalli ordinati.
Devi verificare se [20,22] sovrappone.
Che fai?
Verifichi [20,22] con TUTTI gli intervalli della sequenza?
Oppure:
[20,22] si sovrappone con [1,19]? NO
[20,22] si sovrappone con [24,27]? NO
22<24 -> FINE
Nel caso pessimo confronti sino all'ultimo intervallo.
Per questo suggerivo una ricerca binaria... :rolleyes:
zanardi84
25-11-2011, 11:09
Invece importa l'ordinamento.
prendi questa sequenza:
[1,19]
[24, 27]
[28, 45]
[50, 51]
[53, 63]
L'insieme è fatto da intervalli ordinati.
Devi verificare se [20,22] sovrappone.
Che fai?
Verifichi [20,22] con TUTTI gli intervalli della sequenza?
Oppure:
[20,22] si sovrappone con [1,19]? NO
[20,22] si sovrappone con [24,27]? NO
22<24 -> FINE
Nel caso pessimo confronti sino all'ultimo intervallo.
Per questo suggerivo una ricerca binaria... :rolleyes:
In realtà potevo avere anche questa sequenza disordinata:
[28, 45]
[24, 27]
[53, 63]
[1,19]
[50, 51]
[20,22] sovrappone?
con [28,45] no, con [24,27] no, con [53,63] no, con [1,19] no, con [50,51] no. Quindi è una sequenza che può essere inserita nell'insieme.
Mi pare una soluzione generale che può essere adattata a diverse situazioni, per esempio se ogni intervallo arrivasse da una lista non ordinata, ma ottenuta inserendo sequenzialmente in testa o in coda le coppie di ogni intervallo.
Penso che con il mio sistema, scandirei la lista una sola volta fermandomi al primo caso negativo, quindi potrebbe essere la testa della lista o la coda o anche il fondo.
Nel caso di una sequenza da ordinare dovrei prima ordinarla, se fosse una lista, poi dovrei fare la scansione. E se la coppia da ordinare fosse di due numeri molto grandi? Dovrei andare in fondo alla lista lo stesso.
Penso che valga anche per un semplice array.
O sbaglio?
Secondo me sbagli.
Il tuo algoritmo deve scorrere la lista alla ricerca di una sovrapposizione che se non c'è comporta sempre lo scorrimento di tutta la lista.
L'algoritmo di ricerca binaria su insiemi ordinati ha una complessità dell'ordine LOG(n) in ogni caso.
Significa che con un insieme di 8 elementi con 3 confronti hai finito.Sempre.
Mi pare un bel risparmio.
L'ordinamento lo fai una volta.
Oltretutto con la ricerca binaria trovi anche il punto esatto dove inserire l'intervallo che vuoi esaminare.
Sono un po' arrugginito sull'argomento complessità dell'algoritmo, quindi spero di non aver detto castronerie :rolleyes:
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.