parent = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
'Zoe':'Mary'}
Este es el diccionario principal mencionado en la pregunta. Mi tarea es:
Averigüe si los 2 nombres ingresados son ancestros. Por ejemplo, el padre de Amy es Ben, el padre de Ben es Howard, por lo que Howard y Amy están relacionados como antepasados.
A continuación se muestra mi código:
def is_ancestor(name1,name2,pdict):
for name in pdict:
parent = pdict.get(name2)
parent2 = pdict.get(parent)
if(name1 == parent2):
return True
else:
return False
Esto funcionará para el caso de ejemplo que mencioné anteriormente. Pero, ¿y si la pregunta es 'Amy' y 'Howard'? Debería devolver True ya que el padre de 'Amy' es 'Tom', el padre de Tom es Ben y el padre de Ben es Howard. Así que Amy y Howard son ancestros. Pero mi código se detendrá después de recibir a Tom y Ben. ¿Cómo mantenerlo en bucle hasta que encuentre una respuesta correcta?
A continuación se muestra la pregunta exacta:
La persona A es un antepasado (indirecto) de la persona B si se considera que la persona B es uno de los muchos descendientes de la persona A.
En el árbol de ascendencia del ejemplo dado arriba, Howard es un antepasado de Amy, pero Amy no es un antepasado de Tom.
Y esa persona misma NO es su propio antepasado. Su tarea es escribir una función,
is_ancestor(name1,name2,pdict), que abarca tres argumentos.Los primeros dos argumentos son los nombres de personas (cadenas), mientras que el tercer argumento es
El diccionario principal mencionado anteriormente.La función debe devolver el valor booleano ‘Verdadero 'si la primera persona en la lista de argumentos es un antepasado de la segunda persona,
y "Falso" si la primera persona en la lista de argumentos no es un
antepasado de la segunda persona.
4 respuestas
Puede usar la recursión en lugar de un bucle.
def is_ancestor(name1, name2, pdict):
parent = pdict.get(name2, None)
if not parent:
return False
elif parent == name1:
return True
else:
return is_ancestor(name1, parent, pdict)
parents = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
'Zoe':'Mary'}
print(is_ancestor("Amy", "Ben", parents))
print(is_ancestor("Ben", "Amy", parents))
print(is_ancestor("Howard", "Amy", parents))
La función obtiene el padre de name2. Si no se encuentra ningún padre, hemos alcanzado el caso base y devolvemos False. De lo contrario, verificamos si el padre encontrado es el que estamos buscando. Si es así, devolvemos True. Si no, buscamos si el padre de esa persona es el antepasado que estamos buscando. Esto seguirá recurriendo hasta que lleguemos al antepasado que estamos buscando o golpeemos a una persona sin padre en el diccionario.
Que te equivocaste
Lo que sucede en su código es que solo está verificando a los padres, y no más. Debes seguir atravesando la cadena, hasta que encuentres un antepasado o te quedes sin nombres
La solución
Aquí hay un enfoque simple para el problema:
def is_ancestor(name1,name2,pdict):
child = name1
while True:
if child not in pdict:
return False
if pdict[child] == name2:
return True
child = pdict[child]
Explicación
Aquí verifica si el niño que está revisando tiene un padre. Si no, devuelve False si es así, luego verifica si ese padre es la persona que estás buscando. Si no es así, establezca ese hijo como padre y repita el proceso.
Puedes hacer algo como esto:
parent = {
'Amy':'Ben',
'May':'Tom',
'Tom':'Ben',
'Ben':'Howard',
'Howard':'George',
'Frank':'Amy',
'Joe':'Bill',
'Bill':'Mary',
'Mary':'Philip',
'Simon':'Bill',
'Zoe':'Mary',
}
def is_ancestor(name1, name2, pdict):
while name1 in pdict:
name1 = pdict[name1]
if name1 == name2:
return True
return False
assert is_ancestor('Amy', 'Amy',parent) == False
assert is_ancestor('Amy', 'Ben',parent) == True
assert is_ancestor('Ben', 'Amy',parent) == False
assert is_ancestor('Amy', 'Howard',parent) == True
assert is_ancestor('Howard', 'Amy', parent) == False
assert is_ancestor('Amy', 'George', parent) == True
assert is_ancestor('George', 'Amy', parent) == False
Aquí está tu respuesta usando la recursividad:
def is_ancestor(name1, name2, pdict):
try:
if pdict[name1] == name2:
return True
else:
return is_ancestor(pdict[name1], name2, pdict)
except KeyError:
return False
Primero, verifica si ha encontrado un antepasado directo; de lo contrario, verifica la próxima generación recurriendo a la misma función. La excepción KeyError se activa si no se encuentra el ancestro, lo que indica que name2 no es un ancestro de name1.
Preguntas relacionadas
Nuevas preguntas
python
Python es un lenguaje de programación multipropósito, de tipificación dinámica y de múltiples paradigmas. Está diseñado para ser rápido de aprender, comprender y usar, y hacer cumplir una sintaxis limpia y uniforme. Tenga en cuenta que Python 2 está oficialmente fuera de soporte a partir del 01-01-2020. Aún así, para preguntas de Python específicas de la versión, agregue la etiqueta [python-2.7] o [python-3.x]. Cuando utilice una variante de Python (por ejemplo, Jython, PyPy) o una biblioteca (por ejemplo, Pandas y NumPy), inclúyala en las etiquetas.