[C/C++] Esercizio di ricorsione

[zanardi84]

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

[Mommolo]

Puoi fare un esempio di accavallamento?
Perché altrimenti, da quello che sembra, la soluzione è banale

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

[zanardi84]

Originariamente inviato da Mommolo

Puoi fare un esempio di accavallamento?
Perché altrimenti, da quello che sembra, la soluzione è banale

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

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]

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.

[Mommolo]

Originariamente inviato da goldorak

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

Boh?

[zanardi84]

Originariamente inviato da goldorak

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?

[Mommolo]

Originariamente inviato da zanardi84

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
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]

Originariamente inviato da Mommolo

Non ho capito
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

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?

[Mommolo]

Originariamente inviato da zanardi84

Ho scritto male

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

[goldorak]

--------

[Mommolo]

Originariamente inviato da goldorak

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?

[zanardi84]

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;
}

[Mommolo]

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

[zanardi84]

Originariamente inviato da Mommolo

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

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?

[Mommolo]

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...

[zanardi84]

Originariamente inviato da Mommolo

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...

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?

[Mommolo]

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