Determinación del objeto ponderado inconsistentemente

Dados N objetos numerados del 1 al N de los cuales todos tienen el mismo peso excepto un solo objeto que no se conoce de antemano. También se nos dan comparaciones Q, en cada una de las cuales se coloca un número igual de objetos en ambos lados de una balanza, y se nos dice el lado más pesado.
La tarea es encontrar el objeto ponderado inconsistentemente o determinar si los datos no son suficientes.
Ejemplos :

Input : N = 6
Q = 3
1 2 = 5 6
1 2 3 > 4 5 6
3 4 < 5 6
Output : 4
Explanation: Object 4 is lighter than all other objects.

Input : N = 10
Q = 4
1 2 3 4 < 7 8 9 10
1 = 9
2 3 4 > 1 5 10
6 = 2
Output : Insufficient data

Se dice que excepto un solo elemento, el resto de los elementos son del mismo peso. Entonces, si observamos con atención, se puede decir que:

En una comparación ‘=’, ninguno de los objetos en ambos lados tiene un peso inconsistente.
Si un objeto aparece en el lado más pesado en una comparación y en el lado más liviano en otra, entonces no es el objeto ponderado inconsistentemente. Esto se debe a que, si un objeto aparece en el lado más pesado, entonces tiene el peso máximo y si aparece en el lado más liviano, tiene el peso mínimo. Dado que un solo elemento no puede ser máximo y mínimo al mismo tiempo. Entonces, este caso nunca ocurrirá.
El objeto ponderado de manera inconsistente debe aparecer en todas las comparaciones no balanceadas (‘>’ o ‘<‘).

Podemos usar las tres observaciones anteriores para reducir los candidatos potenciales para el objeto ponderado inconsistentemente. Consideraremos solo aquellos objetos que están en el lado más pesado o en el lado más liviano; si solo hay un objeto de este tipo, entonces es el requerido. Si no existe tal objeto, consideraremos todos aquellos objetos que no aparecen en ninguna comparación. Si solo hay un objeto de este tipo, entonces es el objeto ponderado inconsistentemente. Si no se presenta ninguno de estos escenarios, los datos son insuficientes.
A continuación se muestra la implementación del enfoque anterior:

Python3

# Python program to determine the
# inconsistently weighted object
 
# Function to get the difference of two lists
def subt(A, B):
    return list(set(A) - set(B))
 
# Function to get the intersection of two lists
def intersection(A, B):
    return list(set(A).intersection(set(B)))
 
# Function to get the intersection of two lists
def union(A, B):
    return list(set(A).union(set(B)))
 
# Function to find the inconsistently weighted object
def inconsistentlyWeightedObject(N, Q, comparisons):
    # Objects which appear on the heavier side
    heavierObj = [i for i in range(1, N + 1)]
     
    # Objects which appear on the lighter side
    lighterObj = [i for i in range(1, N + 1)]
    equalObj = [] # Objects which appear in '=' comparisons
     
    # Objects which don't appear in any comparison
    objectNotCompared = [i for i in range(1, N + 1)]
     
    for c in comparisons:
        objectNotCompared = subt(objectNotCompared, union(c[0], c[2]))
         
        if c[1] == '=':
            equalObj = union(equalObj, union(c[0], c[2]))
        elif c[1] == '<':
            # Removing those objects which do
            # not appear on the lighter side
            lighterObj = intersection(lighterObj, c[0])
             
            # Removing those objects which do
            # not appear on the heavier side
            heavierObj = intersection(heavierObj, c[2])
        else:
            # Removing those objects which do
            # not appear on the lighter side
            lighterObj = intersection(lighterObj, c[2])
             
            # Removing those objects which do
            # not appear on the heavier side
            heavierObj = intersection(heavierObj, c[0])
     
    L_iwo = subt(union(heavierObj, lighterObj), equalObj) # Potential candidates
 
    if len(L_iwo) == 1:
        return L_iwo[0]
    elif not len(L_iwo):
        if len(objectNotCompared) == 1:
            return objectNotCompared[0]
        else:
            return 'Insufficient data'
    else:
        return 'Insufficient data'
 
 
# Driver code
N = 6
Q = 3
comparisons = [ [[1, 2], '=', [5, 6]], [[1, 2, 3], '>', [4, 5, 6]],
                                        [[3, 4], '<', [5, 6]] ]
print(inconsistentlyWeightedObject(N, Q, comparisons))

Producción:

Publicación traducida automáticamente

Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Python3

Deja una respuesta Cancelar la respuesta