Ayuda Lista Enlazada

[robluis]

Alguien me puede ayudar a realizar este programa en c++ utilizado listas enlazadas gracias!!

Un verdugo es mandado a exterminar a n prisioneros de guerra. El exterminio lo ejecuta de la siguiente manera: los prisioneros forman un círculo alrededor del verdugo, el verdugo elige a quien fusilar primero, el verdugo cuenta, a partir del lugar donde estaba su última víctima, k prisioneros en orden de las manecillas del reloj y luego fusila al k-esimo prisionero después de su última víctima (a los muertos no los cuenta), y repite este proceso hasta que solo quede un prisionero.
El último prisionero podrá ser liberado.
El verdugo tiene un amigo entre los n prisioneros, escribe un programa que dado, n, k y la ubicación de su amigo, le diga a quien fusilar primero, para asegurar que su amigo sea el que quede libre.

[xiruko]

aqui no se hacen tareas!

aunque esta guapo el ejercicio me lo apunto para hacerlo cuando acabe examenes.. xD

[s00rk]

aqui no se hacen tareas!

aunque esta guapo el ejercicio me lo apunto para hacerlo cuando acabe examenes.. xD

De hecho el ejercicio se ve interesante igual luego intentare hacerlo, aunque como ya te dijeron aqui no se hacen tareas, pon lo que llevas de codigoy asi poder ayudarte en lo que podamos.

[flony]

lindo ejercicio lo anoto

[s00rk]

Bueno al final ya lo hice aunque por alguna razon no me anda bien en algunos casos aun asi ahi quien puda ayudar o nose >__<

Código (cpp) [Seleccionar] Expandir



#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct _nodo
{
   int dato;
   struct _nodo *siguiente;
} tiponodo;

typedef tiponodo *pnodo;
typedef tiponodo *Lista;

void agregarPrisionero(Lista *l, int v);
void mostrarPrisioneros(Lista lista);
void fusilarPrisioneros(Lista *lista, int k, int n);
int getAmigo(int n, int k);

int main()
{
   int n, k;
   cout << "Total de Prisioneros? ";
   cin >> n;
   cout << "Cada cuantos Prisioneros fusila? ";
   cin >> k;
   Lista lista = NULL;
   cout << "Su amigo es el numero " << getAmigo(n, k) << endl;
   for(int i = 0; i < n; i++)
       agregarPrisionero(&lista, i);
   cout << "Mostar Prisioneros: " << endl;
   mostrarPrisioneros(lista);
   //for(int x = 0; x < (n-1); x++)
   fusilarPrisioneros(&lista, k, n);
   cout << "Mostar Sobreviviente: " << endl;
   mostrarPrisioneros(lista);
   return 0;
}

int getAmigo(int n, int k)
{
   int v = -1, tam = n, y = 1;
   int amigo[n];
   amigo[0] = 0;
   for(int x = (n-1); x > 0; x--)
   {
       amigo[x] = y;
       y++;
   }

   while(tam > 1)
   {
       for(y = 0; y < k; y++)
       {
           v++;
           while(v == n || amigo[v] == n)
           {
               if(v == n)
                   v = 0;
               else
                   v++;
           }
       }
       amigo[v] = n;
       tam--;
   }

   for(int x = 0; x < n; x++)
       if(amigo[x] != n)
           return amigo[x];

   return 0;
}

void agregarPrisionero(Lista *lista, int v)
{
   pnodo nodo;
   nodo = (pnodo)malloc(sizeof(tiponodo));
   nodo->dato = v;
   if(*lista == NULL)
       *lista = nodo;
   else
       nodo->siguiente = (*lista)->siguiente;
   (*lista)->siguiente = nodo;
}

void fusilarPrisioneros(Lista *lista, int k, int n)
{
   pnodo nodo;
   nodo = *lista;

   for(int x = 0; x < (k-2); x++)
   {
       *lista = (*lista)->siguiente;
   }
   if(*lista == (*lista)->siguiente)
   {
       free(*lista);
       *lista = NULL;
   }else{
       nodo = (*lista)->siguiente;
       (*lista)->siguiente = nodo->siguiente;
       free(nodo);
   }
   if(n > 2)
   {
       *lista = (*lista)->siguiente;
       fusilarPrisioneros(lista, k, n-1);
   }
}

void mostrarPrisioneros(Lista lista)
{
   pnodo nodo = lista;
do{
  cout << nodo->dato << " ";
  nodo = nodo->siguiente;
} while(nodo != lista);
cout << endl;
}


[botella]

El ejercicio está muy bueno, yo te diría que te olvides de la lista enlazada y lo plantees primero. Igual, sabé que un prisionero apunta al de al lado y así sucesivamente, cada vez que matás a uno, el de la izquiera pasa a apuntar al siguiente luego del muerto, (el más próximo que queda vivo a la derecha). Al muerto le das un free para liberar la memoria que tenía con malloc.  El último prisionero apunta al primero. Plantealo en papel tranquilo, no es muy dificil.

Una vez que tenés bién la estructura de datos, de los prisioneros apuntandosé, tenés que hacer la función que mate al prisionero. De ahí en más empezas a buscar el algoritmo para no matar al amigo. Sabés listas?, si no sabés mandame un mp con tu e-mail que te puedo enviar las primitivas de listas y unos tutoriales. Saludos.