P3 ED

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Universidade Federal Fluminense - Pólo Universitário de Rio das Ostras 
Professor: Dalessandro Soares Vianna Data: 30/10/2012 
Disciplina: Estrutura de Dados Prova: P3 
Nome do Aluno: ................................................................................................................................ 
 
Questão 1 (2,5): Faça uma função que imprima na tela todas as combinações de {0,1}, de 
tamanho n, que possuam valores 1 apenas na primeira metade, ou seja, na segunda metade da 
combinação só podem haver valores 0. 
 
Questão 2 (2,5): Deseja-se, trabalhando com notas de $8,00, $7,00, $3,00 e $1,00, dar o troco 
com o menor número de notas possível. Para isso, uma função deve ser implementada, a qual 
deve receber, entre outras coisas, o valor do troco e a quantidade máxima de notas de cada 
valor. 
 
Questão 3 (2,5): Faça uma função que receba um grafo como entrada e o transforme (remova 
e insira arestas) em um ciclo hamiltoniano com a seguinte característica: cada vértice j do 
grafo, exceto o primeiro, deve estar conectado apenas com o vértice j-1; o primeiro vértice 
deve estar conectado apenas com o último vértice. 
 
Questão 4 (2,5): Faça uma função que imprima o melhor caminho, existente em um 
determinado grafo, entre uma origem e um destino. O custo de um caminho em um grafo é 
determinado pelo custo da menor aresta neste caminho. Ex.: se existe um caminho 1 – 3 – 4 – 
5 e o custo das arestas deste caminho são (1,3): 5; (3,4): 3; (4,5): 8, então o custo do caminho 
seria 3 pois é o valor da menor aresta – aresta (3,4).