Hola me llamo Sonia y queria pediros ayuda para resolver un ejercicio gracias :)

[MAFUS]

¿Conoces las listas enlazadas? El problema se basa en ellas. Eso lo habréis visto.
En verdad es una lista circular, dónde el último elemento enlaza con el primero.
Dadas dos listas circulares de la misma longitud, usa una como referencia y muévete por la otra hasta encontrar una coincidencia, a partir de allí muévete por las dos al mismo tiempo vigilando si los elementos son los mismos. Cuando des una vuelta entera a la de referencia y hayan sido todos los elementos iguales podrás decir que las dos listas son las mismas.

[soni1345_ela]

vale, muchas gracias por el consejo

[dijsktra]

Hola Sonia.

No he tenido mucho tiempo, porque me voy a ver el partido del mundial de España-Irán    .

Echa un vistazo a esto... (No he probado, mañana edito una respuesta más elaborada, e implemento el programa principal, aunque no lo pide)

Código (c) [Seleccionar] Expandir


#define MAX 10000
#include <assert.h>

/* Static memory implementation */

typedef struct {
  int V[MAX];
  int N;
} CycleSeq, *pCycleSeq;


/* Comment: Compare cannonical forms */
int SameCycle(CycleSeq *A, CycleSeq *B)
{

  if (A->N != B->N) return 0;

  if (A->N == 0 ) return 1 ;

  // otherwise
  assert((A->N == B->N) && A->N );

  int n ;
  int mA, mB;
  for (mA=mB=0, n = 1 ; n < A->N ; n++)
    {
      if (A->V[mA]>A->V[n]) mA = n ;
      if (B->V[mB]>B->V[n]) mB = n ;
    };
  // mA mB holds minimum positions;
// count coincidences in cannonical form.
  int count;
  for(count=0; (count < A->N) && (A->V[mA]==B->V[mB]); mA=(mA+1)% A->N,mB=(mB+1)%A->N  )
    count++;
  return count == A->N;
}

[dijsktra]

Hola!
Ya lo tengo de nuevo, completo, con especificación algebraica, implementación, programa principal y todo! (no se pedía todo)



Como esto es un foro de C/C++ , empezamos por el final, la implementación...  Tened en cuenta que sólo se pedía el struct y la operación equals (Mismo Ciclo). Me ha salido más fácil que ayer!!

Código (c) [Seleccionar] Expandir


/*
CYCLE: Informally, a circular permutation, ie.

 [1,4,23,7]~[4,23,7,1]~[23,7,1,4]~[7,1,4,23]
*/
#define MAX 10000
#include <cassert>
#include <cstdlib>
#include <cstdio>

// Implementation on static memory.
typedef struct {
 int V[MAX];
 int N;
} CycleSeq, *pCycleSeq;

CycleSeq* cycle(const int V[],const int N)
{
 // Pre: assumed Def(canonical(V))
 CycleSeq *A;
 if (!(A = (pCycleSeq)malloc(sizeof(CycleSeq))))
   {
     perror("malloc");
     exit(1);
   };
 A->N = N ;
 for(int n=0; n<N ; n++) A->V[n]=V[n];
 return A;
}

int contains(const int i,const CycleSeq *A)
{
 // Pre: true O(n)
 int n;
 for (n=0 ; n<A->N && (A->V[n]!=i) ; n++);
 return (n<A->N);

}

int next(const int i,const CycleSeq *A)
{
 // Pre: contains(A,i) O(n)
 int n ;
 for ( n=0 ; A->V[n]!=i ; n++);
 return (A->V[(n+1)%A->N]);

}

/* Comment: Compare cannonical forms . (Was SameCycle)*/
int equals(const CycleSeq *A, const CycleSeq *B)
{

 if (A->N != B->N) return 0;

 if (A->N == 0 ) return 1 ;

 // e.o.c
 assert((A->N == B->N) && A->N );

 int n ;
 int mA, mB;
 for (mA=mB=0, n = 1 ; n < A->N ; n++)
   {
     if (A->V[mA]>A->V[n]) mA = n ;
     if (B->V[mB]>B->V[n]) mB = n ;
   };
 // mA mB holds minimum positions; count matches in cannonical form.
 for(n=0; (n < A->N) && (A->V[(mA+n)%A->N]==B->V[(mB+n)%A->N]); n++);
 return (n == A->N);
}

#include <iostream>
using namespace std;
#define MAX 10000

int main(int argc, char *args[])
{
 CycleSeq *B,*A;
 int V1[MAX],V2[MAX];
 int N1,N2;
 for( ; cin >> N1 && cin >>N2 ; )
   {
     for(int n=0; n<N1; n++) cin >> V1[n];
     for(int n=0; n<N2; n++) cin >> V2[n];
     A= cycle(V1,N1);
     B= cycle(V2,N2);
     cout << equals(A,B) << endl;
     free(A);
     free(B);
   }
}


Y algunos casos de prueba emepzando por los de la foto.

Protocolo de entrada.

• Linea que marca la longitud de las permutaciones ciclicas
• Componentes de la primera permucacion
• Componentes de la segunda permucacion
• Acaba cuando no se dan pares de longitudes

Protocolo de salida: 1 marca TRUE ( permutaciones ciclicas equivalentes) 0 marca FALSE

Código [Seleccionar] Expandir

5 5
6 23 4 71 9
71 9 6 23 4
1
5  5
71 9 6 23 4
6 23 4 71 9
1
5  5
6 23 4 71 9
6 23 71 4  9
0

Otros casos que no tienen que ver con esos.

Código [Seleccionar] Expandir

1 1
3 3
1
1 1
3 4
0
2 2
1 2
2 1
1
2 3
1 2
1 2 3
0
4 4
1 4 23 7
4 23 7 1
1
4  4
4 23 7 1
23 7 1 4
1
4  4
23 7 1 4
7 1 4 23
1
4  4
7 1 4 23
1 4 23 7
1
4  4
1 4 23 7
23 7 1 4
1
4 4
23 7 1 4
23 1 7 4
0

y Ahora.... Para los que busquen algo "pure mathematical", sin C... aquí os dejo la especifiación ecuacional del tipo Ciclic... No se si tiene fallos...

Código [Seleccionar] Expandir

CYCLE: Informally, a circular permutation, ie.

 [1,4,23,7]~[4,23,7,1]~[23,7,1,4]~[7,1,4,23]


 Algebraic Spec:
 ---------------

 TAD CYCLE is

 uses SEQ;

 carrier Cycle;

 ops
 ---

 cycle : Seq -> Cycle   [non free cons]

 partial next : Int Cycle -> Int   [ obs ]

 aux ops
 --------

 contains : Int Cycle -> Bool  [obs]

 partial canonical  : Seq -> Seq  // extends TAD SEQ, but safe

 var
 ---
 n:Int, c:Cycle , s: Seq

 axioms
 ------

 contains(n,c) -> Def(next(n,c))

 nonRepeated(s) -> Def(canonical(s))

 Def(canonical(s)) -> Def(cycle(s))

 contains(n,cycle(s)) = contains(n,s)

 // canonical form of a a seq.
length(s) = length(cannonical(s))

 let
   M = length(s)
 in
   (M==0 ||
          let
             ms,ms' = min(s) , min(canonical(s))
          in  
          \forall i : 0<= i < M : s.at[(ms+i)%M]=cannonical(s).at[(ms'+i)%M])

 cycle(seq) = cycle(cannonical(seq))  

Y unos breves apuntes  sobre la implementación, expresando el invariante de representación y la función de abstracción.

A lo mejor estas cosas no parecen imporantes, pero sirven para guiarme en como hago las cosas luego en C.

Código [Seleccionar] Expandir

 Impl:
 -----

   int V[MAX];
   int N;

 INV : N<=MAX && \forall : 0 <= i < N : frec(V[i],V)=1

 ABSTRACTION : (V1,N1) ~ (V2,N2)

    N1=N2 and
    (N1 = 0 ||
    let A = min i : 0 <= i < N1 : V1[i]
        B = min i : 0 <= i < N2 : V2[i]
    in
    \forall : 0 <= i < N1 : V1[(A+i) mod N1)] = V2[(B+i) mod N1)] )