5 votos

Comprobar si un intervalo contiene puntos enteros

Quiero hacer un no-complejo (para algoritmos de implementación) condición lógica para comprobar si algunos de los verdaderos intervalo contiene un número entero de puntos.

Deje $x$ ser un intervalo de con límites $l, r$;

Deje $LI(x)$ ser un predicado que se aplica en el caso de $x$'s el límite izquierdo es incluyente e $RI(x)$ ser un predicado que se aplica en el caso de $x$'s el límite derecho incluyente.

Por último, vamos a $P(x)$ ser un predicado que se aplica en el caso de $x$ contiene al menos un punto entero.

He aquí lo que he producido hasta el momento:

$P(x) \equiv (\lfloor l \rfloor + 1 < r) \lor (RI(x) \land (r \in \mathbb Z) ) \lor (LI(x) \land (l \in \mathbb Z))$

Es insuficiente o superfluo? Cualquiera puede hacer un mejor fórmula? Gracias!

9voto

leftaroundabout Puntos 1343

Me gustaría ir con $$ P = (|x|>1) \vee(\lceil l\rceil \leq r \wedge LI) \vee (l \leq \lfloor r\rfloor \wedge RI) $$ Comprobación $|x|>1$ en primer lugar, que es, $r-l>1$, es una buena idea para cuando la aplicación de este como un algoritmo, es probable que esta condición será verdad que la mayoría del tiempo de todos modos, y con una buena rama de predicción del algoritmo sólo cuesta una resta y una comparación, lo que lo hace muy rápido.


El único problema es que no funciona para $x=\,].9,1.1[$... necesitas un extra lógico sumando, $$ P = (|x|>1) \vee (LI \wedge \lceil l\rceil \leq r) \vee (RI \wedge l \leq \lfloor r\rfloor ) \vee (\lceil r\rceil - \lfloor l\rfloor =2) $$ ok, ahora es más largo que el original de su propuesta... no es tan agradable. Todavía debe ser más rápido como un algoritmo, sin embargo.


$LI \wedge \lceil l\rceil \leq r$ significa que: si el borde izquierdo de valor es inclusiva, es suficiente para saber si el número junto al lado derecho de la $l$ está en el intervalo, es decir, saber que este número no es más que el derecho de $r$.

3voto

HappyEngineer Puntos 111

Edit: la fijación de condiciones para que el conjunto abierto mediante propuesta en los comentarios.

Dado que el intervalo de $x$ no está vacía, el intervalo abierto $(l,r)$ contiene un entero si y sólo si:

$$\lfloor l \rfloor + 2 \leq \lceil r \rceil$$

De lo contrario, la única manera para que un entero en el intervalo es que si uno de los límites es cerrado, y que el valor es un entero. Que es:

$$(LI(x) \land \lfloor l \rfloor = l) \lor (RI(x) \land \lceil r \rceil=r)$$

Yo uso el piso y el techo está aquí sólo para ser lindo - por lo que sólo necesitamos calcular $\lceil r \rceil$$\lfloor l \rfloor$.

Así que la expresión completa es: $$(\lfloor l \rfloor + 2 \leq \lceil r \rceil) \lor$$ $$(LI(x) \land \lfloor l \rfloor = l) \lor $$ $$(RI(x) \land \lceil r \rceil=r)$$

Si usted necesita la condición de que $x$ no está vacío, entonces $\land$ la expresión anterior con $$l\lt r \lor (l = r \land LI(x) \land RI(x))$$

0voto

Tal Puntos 617

(X) \ \ rfloor \ neq \ lfloor r (x) \ rfloor) \ vee (LI (x) \ wedge \ lfloor l (x) \ rfloor = l (x) X) \ wedge \ lfloor r (x) \ rfloor = r (x)) $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X