| Organització: | Secció ETSEIB, Departament LSI, UPC |
|---|---|
| Data: | 13 de maig de 2015 |
| Copyright: | Reconeixement-CompartirIgual 3.0 No adaptada de Creative Commons |
| Durada: | 30 minuts |
Dos nombres naturals són coprimers si el seu màxim comú divisor
és 1. Donat un conjunt de nombres, usarem un graf per representar la
relació coprimers dins del conjunt. El nodes del graf seran els
nombres del conjunt i hi haurà una aresta entre dos nombres (nodes) si
són coprimers. Observeu que el graf és simètric. Per exemple, el graf
corresponent al conjunt {2, 3, 4, 5, 6, 7, 8, 9} és el següent:
Graf dels nombres coprimers del 2 al 9.
Als exemples posteriors usarem la funció
crea_graf_coprimers(cjt) del mòdul coprimers que retorna el
graf dels nombres coprimers donats al conjunt cjt. Aquesta
funció no és necessària per resoldre els exercicis, però podeu usar-la
per fer experiments. Proporcionem el mòdul coprimers junt amb la
resta de material de l'examen.
Dissenyeu la funció veins_menors(g, n) que donat un graf
g de nombres coprimers i donat un node n del
graf g, retorna un conjunt (set) amb els nodes veïns
d'n que són estrictament menors que n. Recordeu que els
nodes d'aquest graf són nombres naturals.
La funció ha de passar, com a mínim, els doctests següents:
>>> from coprimers import crea_graf_coprimers >>> from ex1 import veins_menors >>> c = set(range(2, 10)) >>> g = crea_graf_coprimers(c) >>> veins_menors(g, 6) == {5} True >>> veins_menors(g, 7) == {2, 3, 4, 5, 6} True >>> veins_menors(g, 8) == {3, 5, 7} True
Disposeu de més doctests en el fitxer test1.txt.
Deseu la funció al fitxer ex1.py.
Dissenyeu la funció nodes_menors(g, n) que donat un graf g
de nombres coprimers i donat un node n del graf
g, retorna un conjunt (set) amb els nodes del graf g
que són estrictament menors que n.
La funció ha de passar, com a mínim, els doctests següents:
>>> from coprimers import crea_graf_coprimers >>> from ex2 import nodes_menors >>> c = set(range(2, 10)) >>> g = crea_graf_coprimers(c) >>> nodes_menors(g, 5) == {2, 3, 4} True >>> nodes_menors(g, 8) == {2, 3, 4, 5, 6, 7} True >>> nodes_menors(g, 2) == set() True
Disposeu de més doctests en el fitxer test2.txt.
Deseu la funció al fitxer ex2.py.
Dissenyeu la funció candidats_a_primers(g) que donat un graf
g de nombres coprimers, retorna la llista dels nodes candidats a
ser nombres primers. Aquests nodes són tots els nodes n del graf
g tals que el conjunt veïns d'n estrictament menors que n
coincideix amb el conjunt de nodes del graf g menors que
n. Observeu que la funció veins_menors permet calcular el
primer conjunt i la funció nodes_menors(g, n) el segon
conjunt. La llista ha d'estar ordenada creixentment.
La funció ha de passar, com a mínim, els doctests següents:
>>> from coprimers import crea_graf_coprimers >>> from ex3 import candidats_a_primers >>> c = set(range(2, 10)) >>> g = crea_graf_coprimers(c) >>> candidats_a_primers(g) [2, 3, 5, 7] >>> c = set(range(5, 20)) >>> g = crea_graf_coprimers(c) >>> candidats_a_primers(g) [5, 6, 7, 11, 13, 17, 19]
Disposeu de més doctests en el fitxer test3.txt.
Deseu la funció al fitxer ex3.py.