1a prova 2016

Prévia do material em texto

Algoritmos e Programação - Prova 1 - 2016
1. (2 pontos) O que é impresso pelo código abaixo?
def f(l):
def g(a,b):
return b*2+a
if len(l)<=1: return l
return g(l[:1],l[1:2])+f(l[2:])
print f("abcdef")
print f(range(1,6))
2. (2 pontos) O que é impresso pelo código abaixo?
d={}
for a,b in [(1,2),(1,4),(2,2),(3,0),(4,2),(1,5),(5,1)]:
if a in d:
d[a]=d[a]+[b]
else:
d[a]=[b]
for a in range(5):
if a in d:
print len([1 for b in d[a] if b in d])
3. (6 pontos) Empacotamento de círculos é um método pelo qual se tenta prencher um retângulo
com círculos de tamanhos variados sem que estes se intersectem. Um método simples consiste em
gerar pontos aleatórios dentro do retângulo e computar a distância d ao círculo mais próximo. Se
o ponto cair dentro de algum círculo gerado anteriormente, é ignorado. Caso contrário, é gerado
um círculo naquela posição com raio menor que d. O código Python listado parcialmente a seguir
implementa essa idéia, e uma figura exemplo gerada pelo programa é mostrada na figura abaixo.
from random import random
from math import *
def ponto_aleatorio(xmax,ymax):
u"""Retorna uma tupla da forma (x,y) representando um ponto
aleatório sujeito a 0 <= x <= xmax e 0 <= y <= ymax."""
...
def raio_aleatorio (x, y, xmax, ymax, rmin, rmax):
u"""Retorna um raio aleatório entre rmin e rmax para um círculo
centrado em x,y de forma que o círculo esteja todo contido dentro
do retângulo dado por 0 <= x <= xmax e 0 <= y <= ymax."""
...
def distancia_lista(p,l):
u"""Retorna a distância entre um ponto p dado por uma tupla
da forma (x,y) e o círculo mais próximo dentre os círculos
armazenados na lista l. Cada círculo em l é representado
por uma tupla da forma (x,y,r) onde x,y são as coordenadas do centro
e r é o raio. Se p está dentro de algum círculo de r, a função
retorna 0. Se l está vazia, retorna um número grande."""
...
circulos = []
def setup():
size(1000,1000)
def draw():
p = ponto_aleatorio(1000,1000)
d = distancia_lista(p,circulos)
if d>2:
x,y = p[0],p[1]
r = raio_aleatorio(x,y,1000,1000,2,d)
ellipse(x,y,2*r,2*r)
circulos.append((x,y,r))
Pede-se escrever o código das funções ponto_aleatorio(), raio_aleatorio() e
distancia_lista().
Algumas observações:
(a) Lembre que a distância entre dois pontos com coordenadas (x1, y1) e (x2, y2) é√
(x1 − x2)2 + (y1 − y2)2.
(b) A função random() retorna um número em ponto flutuante entre 0 e 1.
(c) Embora não seja necessário lembrar das funções do Processing para resolver a questão, você
pode achar útil a seguinte recapitulação:
i. A função setup() é chamada automaticamente para inicializar o ambiente Processing.
ii. A função size(w,h) especifica que a janela de desenho tem largura w e altura h.
iii. A função draw() é chamada automaticamente aproximadamente 30 vezes por segundo.
iv. A função ellipse(x,y,w,h) desenha uma elipse centrada em x,y, largura w e altura
h.