Mensajes

Puedes marcar la raiz en el cálculo pasándola por parámetro.

Código (cpp) [Seleccionar] Expandir

int sumar(const pnodo a, const pnodo root)
{
 int suma=0;
 if(a!=NULL){
   suma=sumar(a->izq,root)+sumar(a->der,root);
   if ((a->izq!=NULL || a->der!=NULL) && a!=root) // neither leaf nor root
     suma+=a->dato;
 }
 return suma;
}

// Initial call
pnode a ;
// populate tree a with subtrees
sumar(a,a);


NEBIRE, me alegro de participar contigo.

Yo también soy partidario de escribir en pseudo-código, máxime cuando este da facilidades que los lenguajes "reales" no ofrecen, como asignación simultánea.... (En este sentido, me encanta más Python) Pero el valor inicial de una variable es algo esencial a tener explícitamente en cuenta.

Tu algoritmo se puede escribir más simple, y eso hace que el programador (no la máquina) lo entienda mejor.

Código [Seleccionar] Expandir


P : sorted(V=A[0..N)
Q : \forall  i : 0 <= i < N : (\exists j : 0 <=j < M : A[i]=V[j])

I : Q[N/n] and 0 <= k <= n <= N and N>n>0 -> V[n]!=V[n-1]
C(n) = N-n >= 0

proc bajarRepes(i/o V=A[0..N) of integer, o k integer )
n,k = 0,0
while n<N do
  V[k],k = V[n],k+1
  n=n+1
  while n<N and V[n]==V[n-1]
     n = n+1
  end
endwhile


Que efecitvamente, esta en O(n), ya que la instrucción crítica (n<N) se ejecuta un máximo de N veces. (Siendo pedantes, también está en O(n^2) , en O(n^56)  )
Erratas tenemos todos... Pero también los ingleses dicen que "el diablo está en los detalles"...

El problema es bonito, pero no trivial. Con ánimo constructivo

• La solución de Ana es correcta pero ineficiente, se dice que está en O(n^3) (3 bucles)
• La solucion de NEBIRE tiene ideas aprovechables, porque se requiere ordenar el vector, pero el paso 2 es díficil de seguir con 7 variables, algunas sin inicializar, y _creo_ que está en O(n^2), por los dos bucles. Además creo que se pide eliminar los elementos del vector de entrada, no una opia

La que propongo, ya implementada en C++, requiere ordenar el vector, cosa que se puede hacer con las rutinas de STL, en complejidad O(nlog(n)), y la que hace el proceso de "soltar" los repetidos está en O(n). En total O(nlog(n)) que es mejor que O(n^2).
Fijaos que es muy simple, aunque no tan sencillo de demostrar que sea correcta.

Fijaos en los dibujos que ilustran el invariante y podr'eis ententer como progresa el algoritmo.

Código (cpp) [Seleccionar] Expandir


/*
   P : V=A[0..N)   N>= 0
   fun dropRedundant(V=A[0..N) of int) return M:int
   Q : \forall i : 0 <=  i < N : \exists j :0 <= j < M : A[i]=V[j]
       and
       M = #i : 0 <= i < N : frec(A,0,N,A[i])= 1

   I : Q[N/n] and  0 <= M <= n <= N and
       StrictSorted(V,0,M) and Sorted(V,n,N)

   where

   frec(A,i,j,v) ::= # p : i<= p < j : A[p]=v


   I and B |- Q  (trivial, since n=N)


Snapshot invariant: (Hard)
-------------------

0     1     2    m=3    4     5     6    n=7    8           N
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  3  |   3 |  3  |  3  |  4  |     |     |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+


*/

#include <iostream>
#include <algorithm> // sort

using namespace std;
// O(n)
int dropRedundant(int V[], const int N)
{
  int m,n;
  sort(V,V+N); // O(nlog(n)
  // V sorted.
  for(n=m=0;n<N;n++) // O(n)
    if (m==0 || V[n]>V[m-1]) V[m++]=V[n];
  return m;
}

#define MAX 10000

int main(int argc, char *args[])
{
  int N,M;
  int V[MAX];
  for ( ; cin >> N; )
    {
      for(int n=0 ; n < N ;  n++ ) cin >> V[n];
      M=dropRedundant(V,N);
      cout << M << endl;
      for(int m=0;m<M;m++) cout << V[m] << " ";
      cout << endl;
    }
}



Algunos ejemplos de entreada. La primera linea  marca el numero de elementos, la segunda el vector a considerar.

Código [Seleccionar] Expandir


6
1 1 2 2 3 3
6
2 2 1 3 4 5
6
2 2 2 2 3 1

En la salida, se da la dimensión del nuevo vector y los elementos originales sin repetir

Código [Seleccionar] Expandir


3
1 2 3
5
1 2 3 4 5
3
1 2 3

Que os sirva!

[2]

...Con ese punto medio hice la forma propuesta por YreX-DwX, quedando muy similar a como estaba el programa al inicio, lo dejo abajo por las dudas:

Código [Seleccionar] Expandir


...
int sumaDyV( int *vec, int inicio, int fin ) {
   if( inicio == fin ) {
       return vec[inicio];
   }
   if ( (fin - inicio) == 1)
  {
       return sumaDyV(vec, inicio, inicio) + sumaDyV( vec, fin, fin);
   }
   else {
       return sumaDyV(vec, inicio, (inicio+fin)/2) + sumaDyV( vec, ((inicio+fin)/2)+1, fin);
   }
}

Voy a tener en cuenta usar el [i,...,j) con if ( i == j )  return 0; para subsegmentos.
Gracias!

A ti!
No obstante, ahora el caso de  YreX-DwX es redundante, no es necesario. De tu forma, si

Código [Seleccionar] Expandir

( (fin - inicio) == 1)

Entonces el tamaño del subsegmento es 2, y consecuentemente en el caso recursivo se partirá en dos submitades. Sigue valiendo el cálculo del punto medio del caso general.

Una razón más para emplear el convenio  [i..j) !

[- Si la diferencia entre inicio y fin es 1 -> return sumaDyV(v, inicio, inicio) + sumaDyV(v, fin, fin)]

Para que funcione tienes que distinguir 3 casos (te falta 1):
- Si inicio y fin son iguales -> return v[inicio]
- Si la diferencia entre inicio y fin es 1 -> return sumaDyV(v, inicio, inicio) + sumaDyV(v, fin, fin)
- Si la diferencia es mayor que 1 -> return sumaDyV(v, inicio, fin/2) + return sumaDyV(v, fin/2+1, fin)
Suerte.

Hola. Creo que ese no es el problema.

El problema es que no está computando bien el punto medio.

Código (c) [Seleccionar] Expandir

int sumaDyV( int *vec, int inicio, int fin ) {
    if( inicio == fin ) {
        return vec[inicio];
    }
    const int half = (inicio + fin)/2;
    return sumaDyV(vec, inicio, half) + sumaDyV( vec, half +1, fin);
}

Ahora queda:

Código [Seleccionar] Expandir

Dimension del vector: 5

Numero en la posicion 0: 2

Numero en la posicion 1: 2

Numero en la posicion 2: 2

Numero en la posicion 3: 2

Numero en la posicion 4: 3

Resultado: 11

Por cierto, que te recomiendo usar para subsegmentos el convenio [i..j) , semiabierto por la derecha, en vez de [i..j-1], cerrado por los dos lados, que es el que usas. Es más inmediato a la lectura de C, y permite valorar la longitud del segmento con la simple diferencia (j-i), contra las más compleja ((j-1)-i+1).
(Además, es legítimo preguntar por la suma de ls elements del vector vacío)


Lo pongo según mi versión:

Código (c) [Seleccionar] Expandir

#include <iostream>
using namespace std;
int sumaDyV( const int *vec, const int inicio, const int fin );

int main() {
    int N;
    cin>>N;
    int *vec = new int[N];
    for(int i = 0; i<N;i++)   cin>>vec[i];
    cout<<sumaDyV( vec, 0, N )<< endl;
    delete[] vec;
    return 0;
}

// Inmersion:
// P :   0 <= i <= j <= N
// Q :   n = \sum k : i<= k < j : V[k];
int sumaDyV( const int *V, const int i, const int j ) {
    if ( i == j )  return 0;
    if ((j - i) == 1)  return V[i];   
    const int half = (i + j)/2;
    return sumaDyV(V, i, half) + sumaDyV( V, half, j);
}


Ah! yo no me preocuparía de hacer "friendly" la entrada - salida... No están pedidiendo una aplicación, solo la exhibición de un algoritmo!

Dejo un ejemplo funcionan con metodo RECURSIVO. Lo deje con comentarios para puedas seguir un poco el codigo.

Código (c) [Seleccionar] Expandir


...
int suma_de_digitos_recursiva(int numero) {
char temporal[20] = {0};
int suma = 0;
int len,i;
sprintf(temporal,"%i",numero); //Aqui "copiamos" el numero a una cadena de texto para poder iterar facilmente sobre cada digitio individual del numero
printf("Prosesando el numero %s\n",temporal);
len = strlen(temporal); //Sacamos la longitud del numero
if(len == 1) { //Si la longitud del numero es solo de uno ya no hacemos nada retornamos el numero
printf("Finalizamos, el numero tiene un solo digito\n");
return numero;
}
else { //Si la longitud es mayor que uno sumamos los digitos individuales
i = 0;
while(i < len) {
suma += temporal[i] - '0';
i++;
}
printf("La suma es %i\n",suma);
return suma_de_digitos_recursiva(suma);
}
}

...

2 COMENTARIOS:

• Aunque la solución sea correcta, parece que la función recursiva tiene a su vez, un bucle, que podriamos computar también recursivamente
• Yo pienso que los protocolos de entrada-salida hay que dejarlos al margen de las funciones de cómputo. Simplemente, ayuda a separar la I/0 del procesamiento

Propongo esta:

Código (c) [Seleccionar] Expandir


/*

NOTE: In this context, we can safely take log(0)=0 as an extension of ordinary log, for which 0 is undefined


P : N >= 0
fun sumDigits(int N) dev s
Q : s = \sum i : 0 <= i <= log(N) : (N/10^i)%10

INMERSION

FINAL APPROACH

P' = P and 0<= n <= N and ac = \sum i : 0 <= i <= log(N/n) : (N/10^i)%10
fun sumDigits(int n,int ac) dev s
Q' = Q[N/n]

Init call: n=N ac=0

case n=0 : return ac
case n>0 : return sumDigits(n/10,ac+n%10)


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

int sumDigitsG(const int n, const int ac)
{
 if (n) return sumDigitsG(n/10,ac+n%10);
 return ac;
}

int sumDigits(const int N)
{
 return sumDigitsG(N,0);
}

/* Formalization for solveG omitted */

void solveG(const int N,int V[], int &num)
{
 if (N>=10) {
   V[num++]=sumDigits(N);
   solveG(V[num-1],V,num);
   return;
 }
 return;
}



int main(int argc, char **args)
{
 int V[MAX];
 int N;
 for ( ; cin >> N ; )
   {
     int num=0;
     solveG(N,V,num);
     for (int n=0; n<num ;n++)  cout << V[n] << " " ;
     cout << endl;
   }
}




Y algunos casos de prueba. Se da un número, y el programa da el vector con la suma de los digitos de ese, del que se obtiene... hasta llegar a una cigra

Código [Seleccionar] Expandir

g++ sumDigits2.cc -o main && ./main
13
4
1456
16 7
177777
36 9

Estos son algunos de los casos de prueba que utilicé, y las salidas que obtuve con mi código:


....

En todo caso, no me parece que sea una solución incorrecta para un ejercicio de nivel básico.

Mis excusas. He probado ya tus códigos y son como dices. Aunque la estrategia de "existeLetra" como flag de comienzo no la entendía.

[isalpha(' ')]

Hola dresden, gracias por responder. Así aprenderé algo también.

Mi razonamiento al estudiar tu código, sin ejecutarlo, fue el siguiente :

• creo (no estoy seguro), que scanf no procesa el espacio ' ' como carácter, por lo que nunca evaluará espacios en la cadena.. Suponiendo que si, entonces
  
• o  bien isalpha(' ') es true, en cuyo caso existeLetra es true, y es evaluado por la parte positiva del primer condicional... En ese caso, la traza '    .' (5 espacios y un punto) da al menos 5 palabras, pues incrementa nPalabras 5 veces. Es esto correcto?
• o bien isalpha(' ') es false,en cuyo caso  nunca es evaluado por la condición del if, nPalabras no se incrementa. 'hola'  daría 0 palabras.
• ocurre que efectivamente, 'hola.' se incrementará en 1. Esto implica  que isalpha('.') es true.
  

Y según el manual

isalpha()
checks for an alphabetic character; in the standard "C" locale, it is equivalent to (isupper(c) || islower(c)). In some locales, there may be additional characters for which isalpha() is true-letters which are neither upper case nor lower case.

Es decir, que en el estándar C locale, sería false. Debe ser que tu computador esté configurado a sp (Spanish) y acierta arbitrariamente, marcando isalpha(' ') false y isalpha('.') true  , pero con otra configuración, no está garantizado

... Lo que es habitual en este tipo de ejercicios, donde se suelen asumir entradas ideales.

En mi opinión, las frases "ideales" deben acabar en C,  en un carácter nulo, y no deben incluir símbolos como Comas, acentos y "puntos y Comas". La única razón es ajustarse a la esencia del Problema, que deja de ser portable en otros "locales".... Pero esto es opinable...

En lo que respecta a los casos que mandas, el segundo me llama la atención, puesto que según lo anterior '    .' (5 espacios y un blanco) debería dar 1, y te da 0, que es lo correcto.

Es realmente la salida de tu código?
No Le veo la explicación, pero puede que esté equivocado.
Debería verse

Código (c) [Seleccionar] Expandir


Total palabras: 0


Un saludo, amigo... A ver si me sacas de dudas...
Estoy solo con un móvil y no puedo probar tus códigos.

Estos son algunos de los casos de prueba que utilicé, y las salidas que obtuve con mi código:

Código (cpp) [Seleccionar] Expandir

.
0

      .
0

,;.
0

,  ;    .
0

Hola.
1

Hola      .
1

       Hola   .
1

En un lugar de la Mancha, de cuyo nombre no quiero acordarme...
12

En    lugar             , de cuyo nombre no quiero          .
7

En un lugar.
3

Como se puede ver, cuando no existen palabras o cuando hay más de un espacio entre las palabras el cálculo es correcto.

No tomé en cuenta, intencionalmente, el conteo de números dentro de la frase, porque al2000 no lo planteó como parte del problema:

Código (cpp) [Seleccionar] Expandir

Ahora vienen 7 espacios:       , con estos otros suman 12:     .
7

En todo caso, no me parece que sea una solución incorrecta para un ejercicio de nivel básico.

La solución anterior es incorrecta: en el momento en que haya más de un espacio entre palabras, o mismamente cuando no haya palabras, el cálculo es errónea.

Propongo esta.

No tengo un compilador a mano para probarlo...
Pero si metes una frase, sin punto al final, no hace falta, debe funcionar.... No metas más que 'a', 'z' y ' '

Código (cpp) [Seleccionar] Expandir




/*


 P : V[0..N) , N>= 0  
 Q : (c = # i, j: 0 <= i < j <= N : word(V, i, j))

     where
word(V,n,m) : allesnb(n, m) and (n>0 - > V[n-1]=' ') and  (m<N- > V[m]=' ')


Snapshot invariant:
-------------------






  I : Q[N/n]
      and 0 <= n <= N
     

  B : n<N


  C(n) = N - n  >= 0

  Init:
  -----
    n,c = 0,0

  Step:
  ------
    n= n + 1 (Clearly, quota decreases)


  Restore:
  --------
     c = c +\chi (V[n]! =' ' && (n=0 ||   V[n-1]==' '))


  Pseudo-code:
  ------------

  n,c= 0,0
  while  n < N
      c = c +\chi (V[n]! =' ' && (n=0 ||   V[n-1]==' '))
     n= n +1
  end
  return c

 
O(N) since while;s body is in O(1) and f_iter in O(N)
     
*/

#include <iostream>
#include <algorithm> // max,min
#include <string> // to string, to use


using namespace std;
#define MAX 100000


/* See full development and derivation above*/
int solve(const char V[], const int N)
{
 int c,n;
 for(n=c=0;n<N;n++)
      c +=(V[n]!=' ' && (!n ||   V[n-1]==' '));
 return c;
}


int main(int argc, char *arg[])
{
 int n,N;
 string V;
 for(;getline(cin, V) ;)
     cout << solve(V. c_str() ,V.length() ) << endl;
 return 0;
}



El problema es que mi modulo de agregar nodo al final me agrega un nodo pero adelante como lo soluciono? Desde ya gracias chavales

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <stdlib.h>
...
typedef struct tlista{
pnodo inicio;
int contador;
};

void inicia(tlista &lista);
void crear(pnodo &nuevo);
void agregar_inicio(tlista &lista, pnodo nuevo);
void agregar_final(tlista &lista, pnodo nuevo);
void agregar_orden(tlista &lista, pnodo nuevo);
pnodo quitar_inicio(tlista &lista);
pnodo quitar_final(tlista &lista);
pnodo quitar_nodo(tlista &lista, int valor);
bool buscar_nodo(tlista lista,int valor);
void mostrar(tlista lista);
}

Ya el planteamiento de la signatura del tipo lista que haces es incorrecto. El programador usuario del tipo de datos lista no debe preocuparse del tuoi "pnodo"... Solo necesita saber el tipo de lista y el tipo de valor. Lo otro queda oculto, y solo lo conoce el implementador.

Siguiendo tu convenio, sería algo así:

Código (c) [Seleccionar] Expandir

void inicia(tlista &lista);
void agregar_inicio(tlista &lista, int valor);
void agregar_final(tlista &lista, int valor);
void agregar_orden(tlista &lista, int valor);
void quitar_inicio(tlista &lista);
void quitar_final(tlista &lista);
void quitar_valor(tlista &lista, int valor);
void mostrar(tlista lista);