Mensajes

Hola!

Basado en el trabajo de  YreX-DwX, ahora creo que si he dado con una respuesta a tu problema. Un interprete de expresiones en notación polaca inversa.

En algún lado de la Wikipedia he leído que una de sus propiedades es que el empleo de paréntesis se hace innecesario con independencia de la precedencia de los operadores. Cada secuencia (correcta) determina una y solo una expresión valida...

Para no repeterlo aquí, lo podéis ver en el correo modificado anterior:

https://foro.elhacker.net/programacion_cc/ayuda-t499837.0.html;msg2206082#msg2206082

Tengo otra duda, porque yo tengo que ingresar la ecuacion en notacion polaca al programa. Como puedo hacer para ir guardando el primer numero, el segundo y su signo? He visto que lo hacian con pilas pero mi profesor me dijo que lo trate de hacer de otra forma pero no me sale una idea

Las pilas por debajo están simuladas con vectores... O sea, que expones los vectores que se ocultarían en la implementación de una pila normalemente...

EDITO
En esta versión implemento un analizador de notación polaca inversa.
Esto es, primero los operandos y después el operador. Como en (3 4 -)

Código (cpp) [Seleccionar] Expandir


/*

An stack can be simulated by a vector

+-----+
|     |
+-----+ N
|  2  |
+-----+
|  1  |
+-----+
|  +  |
+-----+ 0


*/
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

#define MAX 100000
#define DEBUG

int polish (const char V[][25], const int N)
{
  int n,top;
  int S[MAX];
  for( n=top=0;n<N;n++)
  {
#ifdef DEBUG
    int i;
    for(  i=n ; i < N ; i++) printf("%s ",V[i]);
    printf("\n\n");
#endif

    if (strtol(V[n],NULL,10))
      S[top++]=atoi(V[n]);
    else
      {
assert(top>1);
const int a = S[--top];
const int b = S[--top];
if (!strcmp(V[n],"+"))
  S[top++] = a + b;
else if (!strcmp(V[n],"-"))
  S[top++] = a - b;
else if (!strcmp(V[n],"*"))
  S[top++] = a * b;
else if (!strcmp(V[n],"/"))
       {
assert(!b);
S[top++] = a / b;
       }
      }
#ifdef DEBUG
    for(  i=0 ; i < top-1 ; i++) printf("%d ",S[i]);
    printf("%d\n\n",S[top-1]);
#endif
  };
  assert(top==1);
  return S[--top];
}


int main(int argc, char* args[])
{
  char V[MAX][25];

  int N;
  for(N=0;scanf("%s",V[N])==1 && strcmp(V[N],"\n");N++);
  printf("%d\n",polish(V,N));
  return 0;

}

Y un ejemplo de ejecuci'on. Para la expresi'on en notaci'on polaca

Código [Seleccionar] Expandir


3 4 + 7 * 9 10 5 6 + * - -

En la ejecución se da la evoluición de la cadena de entrada y del estado de la pila...

Código [Seleccionar] Expandir

3 4 + 7 * 9 10 5 6 + * - -

3

4 + 7 * 9 10 5 6 + * - -

3 4

+ 7 * 9 10 5 6 + * - -

7

7 * 9 10 5 6 + * - -

7 7

* 9 10 5 6 + * - -

49

9 10 5 6 + * - -

49 9

10 5 6 + * - -

49 9 10

5 6 + * - -

49 9 10 5

6 + * - -

49 9 10 5 6

+ * - -

49 9 10 11

* - -

49 9 110

- -

49 101

-

52

Más sencillo aún:

Pero qué....

• CalgaryCorpus ya ha comentado que no es necesario operar con enteros.
• El programa solo acaba si la palabra tiene las 25 letras al menos una vez cada una! (Asumiendo que k=1 al principio, cosa que no se expresa)
• Si acaba, el programa da siempre la misma solución ABCDEFG..Z

Intente realizar como el mencionado pero no pude me puedes orientar un poco mas porfavor

Copia el programa, estúdialo y dale curso en tu computador...
Te sale ? Que parte te confunde?
Sobre todo, distingue lo esencial (el algoritmo) de lo accesorio (la entrada/salida de datos).

si son char, en el scanf no capturas con %d capturas con %c

te recomiendo buscar el algoritmo de ordenamiento de burbuja, es el mas simple de los algoritmos de organizacion

A ver, según entiendo yo, si dice "según se lee la letra se acomoda", no se trata de ordenar, sino de insertar en un vector ordenado una letra. Pero el mayor problema, veo yo, tiene que ver con el hecho de capturar caracteres de la entrada estandard. Eso es otro problema, porque la entrada buferada exige que le des al intro, y a la vez el intro es un caracter (que a t'i no te vale para tu proposito).


Propuesta:

Código (c) [Seleccionar] Expandir

/*
P : N>0 and sorted(A,0,N-1) and V=A
Q : perm(V,A) and sorted(V,0,N)


I : perm(V,A) and sorted(V,0,n) and sorted(V,n, N)
and (0<n<N-1 - > V[n-1]<V[n+1]) and 0 <= n <= N-1

!B : n==0 || V[n]>=V[n-1]

 B : n > 0 && V[n]<V[n-1]

|- I and !B -> Q

Quote:

 C(n) = n >= 0

|- I -> C(n) >= 0

Invariant snapshot:
-------------------

0                 n           N
+-----+-----+-----+-----+-----+
|  0  |  1  |  3  |  2  |  4  |
+-----+-----+-----+-----+-----+

Init:
-----
n = N- 1

|- P -> I[n/N-1]

Step:
----
 n= n- 1

|- I and B and n=T -> (n<T)[n/n-1]

Restore:
--------

 V[n],V[n-1]=V[n-1],V[n]

Pseudocode:
-----------

  n=N-1
  while n>0 and V[n]<V[n-1] do
    V[n],V[n-1]=V[n-1],V[n]
    n=n-1
  done

*/

void *insertChar(char V[], int N)
{
 for(int n=N-1 ; (n && V[n]<V[n-1]);n--)
   {
     const int An=V[n];  /* To do swapping */
     V[n]=V[n-1];
     V[n-1]=An;
   }
 return V;
}



#include <stdio.h>
#include <string.h>


#define MAX 100000
int main(int argc, char* args[])
{
 int N;
 char V[MAX];
 memset(V,0, MAX);

  for(N=0 ; (scanf("%c",&c)==1) && c!='\n' ; )
    {
      V[N++]=c;
      printf("%d %c %s\n",strlen(V),c,insertChar(V,N));
    }
 return 0;
}

Ejemplp:

Código [Seleccionar] Expandir


gcc char.cc -o char && ./char
enunlugardelamancha
1 e e
2 n en
3 u enu
4 n ennu
5 l elnnu
6 u elnnuu
7 g eglnnuu
8 a aeglnnuu
9 r aeglnnruu
10 d adeglnnruu
11 e adeeglnnruu
12 l adeegllnnruu
13 a aadeegllnnruu
14 m aadeegllmnnruu
15 a aaadeegllmnnruu
16 n aaadeegllmnnnruu
17 c aaacdeegllmnnnruu
18 h aaacdeeghllmnnnruu
19 a aaaacdeeghllmnnnruu


Pero es que nadie va a responder a nuestra programadora argentina?  

hoal quiero apsar este algoritmos a recursivo e ayudan? solo tengo esto

Código (cpp) [Seleccionar] Expandir

int vertir-un-numero(int n)
{
tpila pila;
init_stack(pila);
while(n>0){
push_stack(pila,n%10);
n/=10;
}
for(int i=0;empty_stack(pila)==false;i++)
n+=pop_stack(pila)*pow(10.0,i);
return n;
}

Antes de dar la solución, aprecio un fallo de eficiencia... No es necesario en el segundo bucle expresar pow(10.0,i)... puedes poner

Código (c) [Seleccionar] Expandir


for(int i=0,power=1;empty_stack(pila)==false;i++)
{
n+=pop_stack(pila)*power;
power *=10 ;
}


Y te ahorras la función pow que trabaja con floats, algo que es "peligroso" en computación.


Lo normal es que te den el iterativo y tengas que hacer el recursivo. Si la función recursiva es lineal (con una sola llmada) entonces hay truco fácil. (Un poco largo para explicar aquí)

Lo que yo hago en estas lineas es dar el programa al que se aplica el truco. Es una función lineal no final, es decir, después de la llamada hay quqe hacer algo más, que en la veris'on iterativa realiza el segundo bucle...

Allá va:

Código (cpp) [Seleccionar] Expandir


int invertir_un_numeroG(const int N,int &power);

/*
P : A[0..log(N)) and N = \sum i : 0 <= i < log(N) : A[i]*10^i
Q : M = \sum i : 0 <= i < log(N) : A[i]*10^(log(N)-i)
*/
int invertir_un_numero(const int N)
{
 int power;
 return invertir_un_numeroG(N,power);
}


/* P' : P
  Q' : Q and power=10^log(N)
*/
int invertir_un_numeroG(const int N,int &power)
{
 if (N==0) { power = 1 ; return 0 ; }
 int result;
 result = invertir_un_numeroG(N/10,power);
 result += N%10 * power ;
 power *= 10;
 return result;
}

#include <iostream>

using namespace std;

int main(int argc, char* args[])
{
 int N;
 for( ; cin >> N ; )
   cout << invertir_un_numero(N) << endl;
 return 0;
}


Y algunos casos de prueba

Código [Seleccionar] Expandir

bash-2.04$ ./main
45
54
4678
8764
12345678
87654321

Sí, siempre se debe usar un while...[...]

La respuesta de RayR es muy acertada.

Como norma general, hay que poner while. Sólo analizando un caso particular puedes poner if con seguridad, pero tampoco se gana tanto en eficiencia...

Si te lia tu "intuición operacional", (ya que, si es difícil la programación secuencial, la concurrente es inabordable por la explosión de estados) de te recomiendo el siguiente esquema en pseudo lenguaje

Código [Seleccionar] Expandir


(one thread)
<await B(var) -> S>

(other thread)
<var = e>

Se traduce en C a lo que refleja el código :

Código [Seleccionar] Expandir


(one thread)
pthread_Mutex_lock(l)
while !b do pthread_cond_wait(l, c) ;
S
pthread_Mutex_unlock(l)

(other thread)
pthread_Mutex_lock(l)
var=e
pthread_cond_signal(c)
pthread_Mutex_unlock(l)

Por último, antes de manejar variables de condición en C, estudia teoría de monitores en papel y pseudo código! Las variables de condición y mutex asociados no se pueden comprender sin ellos. Fueron creados para implementar esa idea, aunque el lenguaje C no los implementa directamente. java, por ejemplo, si, pero se una forma muy limitada).

la gente las utiliza sin saber su razón de ser
(Perdón por la imprecision, pero estoy escribiendo dese un móvil)

Asi sólo con datos de tiempos, y no en una gráfica es dificil de ver....

Haz una ultima prueba, con distros aleatorias y k = 1.

Si interpolaramos en una gráfica  las mediciones, deberíamos ver que las medidas de cada una se acercan a 3 rectas... (por eso es linear. Desde la teoría de la complejidad, da igual que una vaya el doble, el triple, o k-veces más rápido, los factores constantes dan igual...)

Pero si se interpolan las curvas y vemos que alguna da una parabola, algo no va bien, pues en los tres casos, n_paired, k_paired, y zoz?paired son lineales...  Si, en el doble bucle interior tambien se comporta lineal, ya que al ser la instrucción critica se ejecuta un máximo de N veces...

La que no debería ser una recta es la del  lower_bound...

Un buen trabajo ! Enhorabuena

Los elementos del vector sí están ordenados (y no se repiten), sólo que son generados al azar. Pongo el algoritmo acá abajo:

Se invoca con el vector ya del tamaño apropiado; se carga con valores al azar, se ordena y se eliminan los duplicados:

Sí sí, es que quería mantener una atmósfera de misterio...
Y ejecutando la misma prueba para cada una de las tres funciones, en Visual Studio, ha resultado:

Curioso, al menos a mí me lo parece.
Jé, nuevo desafío... ¿quién me lo explica?

Un momento, amigo...

Código [Seleccionar] Expandir

Elementos al azar (uniform distribution) desde 1 hasta 2147483647

Las pruebas quedan invalidadas... Si pones elementos al azar, entonces ya no estarán ordenados estrictamente creciente, y los algoritmos no funcionarán en absoluto... Es conforme a esa precondición que programamamos el algoritmo... De nada sirve ir muy rápido si no computa las cosas que se espera.

Si los elementos están al azar, no ordenados, entonces, el algoritmo solo puede ser O(N^2). Por supuesto, este no vale, hay que cambiarlo.

Tu mensaje esta lleno de cosas interesantes....

...
Si te fijas en esta línea:

Código [Seleccionar] Expandir

it = std::lower_bound(it, j, s); it queda posicionado en la posición buscada o en una más allá del límite s, esperando en el mejor lugar para la próxima iteración. Y lower_bound es un binary search, logarítmico, que es mejor que avanzar secuencialmente, o mejor dicho, creí que debería serlo.

La clave está en que estamos juzgando el caso peor, y tu distribución std::iota (junto con el valor k) puede entrar en ese caso.

Como tu dices, binSearch es logaritmico, pero fijate, debido a la distrbución std::iota (junto con el valor k) trabajas mucho  para avanzar solamente 1 posición, cosa que se consigue en el mío en O(1) m=m+1.
Imaginate k=2

Código [Seleccionar] Expandir


1  5  6........................................................... 1000000000 (Arbitrariamente grande,N)

trabajas mucho (del orden de O(log(N)) para pasar del 1 al 5, del 5 al 6

Yo también probé con una solución (aparentemente) muy inferior a la versión con lower_bound, donde lo reemplazo por un estúpido find, haciendo ahora sí una solución (prácticamente) O(N2), pero no, curiosamente:

Código (cpp) [Seleccionar] Expandir

size_t n_pares(const std::vector<int>& v, int k)
{
    assert(std::is_sorted(v.begin(), v.end()) && "v debe estar ordenado.");
    assert(v.size() && "v no puede venir vacio.");

    auto n{ 0u };
    auto it = v.begin();

    for (auto i = v.begin(), j = v.end(); i != j; ++i)
    {
        it = std::find(it, j, *i + k);

        if (it != j) {
            ++n;
            ++it;
        }
        else {
            it = i + 1;
        }
    }

    return n;
}

Ahora los resultados son hasta ligeramente mejores que los de los de k_paired. Joder.


UN mundo muy ingrato.

Je,je,je... Tiene toda la explicacion... En este caso, la naturaleza de iota, k, y el problema, constituyen el caso mejor para find... No tienen que moverse casi nada, estan preguntando por el elmeento siguiente y los datos de entrada están al principio, no da "saltos" como el binsearch. con k=4

Código [Seleccionar] Expandir


1  5  6........................................................... 1000000000 (Arbitrariamente grande,N)


Del 1 al 5, la busqueda se detiene en el primero. Idem para 5  a 6...

A nadie engañamos diciendo que es en O(N^2) en el caso peor... Pero este, era el mejor caso posible...