12/07/2019, 17:57
int sub(Set *A, Set *B);
struct Set
{
char *p
int n;
}
Set empty = {NULL, 0};
//non si esclude A = B
int sub(Set *A, Set *B)
{
//soliti controlli sui parametri
//se un elemento di A non appartiene a B, A non e' sottoinsieme di B
if(condizione con chiamata ad app)
{
return 0;
}
else
{
//chiamata a sub
}
}
13/07/2019, 08:53
sublist :: Eq a => [a] -> [a] -> Maybe Ordering
sublist xs ys
| xs == ys = Just EQ
| xs `isInfixOf` ys = Just LT
| ys `isInfixOf` xs = Just GT
| otherwise = Nothing
isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
isPrefixOf [] _ = True
isPrefixOf _ [] = False
isPrefixOf (x:xs) (y:ys)= x == y && isPrefixOf xs ys
isInfixOf :: (Eq a) => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)
tails
è la funzione che prende una lista \((x_1,x_2, \dots)\) e ritorna \((x_1, (x_1, x_2), (x_1,x_2,x_3),\dots)\)).
13/07/2019, 14:15
int app(char c, Set* A);
int sub(Set *A, Set *B);
A.p != NULL && memchr(A.p, c, A.n) != NULL
int app(char c, Set* A)
{
if (A.p == NULL) { return 0; }
for (int i = 0; i < A.n; ++i) {
if (A.p[i] == c) { return 1; }
}
return 0;
}
14/07/2019, 10:33
14/07/2019, 14:56
int app(char c, Set* A)
{
// Condizione di uscita dalla ricorsione con Set vuoto
if (A == NULL || A.p == NULL || A.n == 0) { return 0; }
// Uscita dalla ricorsione per aver trovato il valore
if (c == A.p[0]) { return 1; }
// "Costruisce" un nuovo Set con un elemento in meno e richiama la funzione ricorsivamente
Set B = {A.p + 1, A.n - 1};
return app(c, &B);
}
16/07/2019, 20:29
16/07/2019, 20:35
int sub(Set* A, Set* B)
{
// Condizione di uscita dalla ricorsione con Set vuoto
if (A == NULL || A.p == NULL || A.n == 0) { return 1; }
// Verifica se A.p[0] è incluso in B, se non lo è esci dalla ricorsione..
if (app(A.p[0], B)) { return 0; }
// "Costruisce" un nuovo Set con un elemento in meno e richiama la funzione ricorsivamente
Set A2 = {A.p + 1, A.n - 1};
return sub(&A2, B);
}
17/07/2019, 10:06
//verifica se A e' un sottoinsieme di B
int sub(Set *A, Set *B)
{
assert(NULL != A && NULL != B);
if(NULL == A->p || 0 == A->n)
{
return 1;
}
if(0 == app(*(A->p), B))
{
return 0;
}
Set C = {A->p + 1, A->n - 1};//questo era il nodo da sciogliere per me
return sub(&C, B);
}
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.