Complexidade de algoritmo

Páginas: 36 (8801 palavras) Publicado: 3 de junho de 2014
Relatório
MATEMÁTICA DISCRETA

Bruno Alves | Rui Freitas | José Gomes

Enunciado:
Pretende-se controlar o tráfego de alunos no ISEP. Em particular, quer-se
saber qual o intervalo de tempo em que o acréscimo de alunos nas instalações
do ISEP é máximo, e qual é esse acréscimo.
De modo a resolver este problema, é efetuado um controlo do número de
alunos que entram/saem durante um certoperíodo de tempo. A cada 5
minutos, é recolhida a informação N, que corresponde à diferença entre o
número de alunos que entraram e saíram das instalações durante os últimos 5
minutos.
Como exemplo, seja a sequência seguinte o resultado da medição durante 1
hora:

[29, -32, -9, -25, 44, 12, -61, 51, -9, 44, 74, 4]

O problema de determinar qual o acréscimo máximo de alunos no ISEP,durante essa hora, consiste agora em determinar qual a subsequência
contígua, da sequência anterior, cuja soma das suas entradas é máxima. Neste
caso, a resposta seria a subsequência
[51, -9, 44, 74, 4]
com soma igual a 164. Isto significa que, ao final deste período de 25 minutos,
o ISEP tinha mais 164 alunos nas suas instalações.
Este problema motiva o que se enuncia em seguida, sendo oponto de partida
para o trabalho que se propõe:
Dada uma sequência de inteiros, encontre uma subsequência contígua
cuja soma dos seus valores é máxima.
Façamos ainda a seguinte consideração. Uma subsequência vazia é
considerada como tendo a soma 0. Assim, se todos os elementos da sequência
inicial são negativos, o resultado deve ser a subsequência vazia.

Questão 1:
E: Construa umalgoritmo que resolve o problema do enunciado e que
consiste numa solução de força bruta, ou seja, o algoritmo deve examinar
todas as subsequências contíguas da sequência inicial e devolver o seguinte:
unia subsequência com soma máxima e o valor da sua soma. No relatório,
apresente o algoritmo em pseudocódigo.

R:

function MaxSubSeq(seq):
int size = seq.length()
lista tmp
lista maiorint soma, somaMax = 0
Para i de 0 até size, passo 1
tmp.clear()
Para j de i até size, passo 1
tmp.add(seq.get(j))
soma = getSoma(tmp)
Se (soma > somaMax) Então
somaMax = soma
maior.clear()
maior.addAll(tmp)
FimSe
Fim Para
Fim Para
Escreve “Subsequência com soma máxima:” maior
Escreve “Valor da soma:” somaMax
fuctionEnd

function int getSoma(tmp):
int soma = 0
Para i de 0 atétmp.length(), passo 1
soma = soma +tmp.get(i)
Fim Para
Retorna soma
functionEnd

Questão 2:
E: Para o algoritmo construído em (1), calcule uma estimativa O, em
termos do comprimento do input, para o número de vezes que cada linha é
executada, descrevendo ainda o tipo de operação(ões) primitiva(s) que é(são)
efetuada(s) nessa linha. Conclua, indicando uma estimativa O, qual é acomplexidade do algoritmo.

R:
Nº Operações

function MaxSubSeq(seq):
int size = seq.length()

1A

lista tmp

1

lista maior

1

int soma, somaMax = 0

1A

Para i de 0 até size, passo 1

(n + 1)AouI + (n + 1)C
n

tmp.clear()
Para j de i até size, passo 1

((n(n+1)/2) + n)AouI + (n + 1)C

tmp.add(seq.get(j))

(n(n+1)/2)

soma = getSoma(tmp)

(n(n+1)/2)

Se(soma > somaMax) Então

(n(n+1)/2) C

somaMax = soma

(n(n+1)/2) (A)

maior.clear()

(n(n+1)/2)

maior.addAll(tmp)

(n(n+1)/2)

FimSe
Fim Para
Fim Para
Escreve “Subsequência com soma máxima:” maior

1

Escreve “Valor da soma:” somaMax

1

fuctionEnd

function int getSoma(tmp):
int soma = 0
Para i de 0 até tmp.length(), passo 1

(n(n+1)/2) A
((n(n+1)/2) (n(n+1)/2) +n)AouI + (n +

1)C
soma = soma +tmp.get(i)

(n(n+1)/2) (n(n+1)/2) (Op+A)

Fim Para
Retorna soma
functionEnd

(n(n+1)/2) R

Questão 3:
E: Construa uma rotina que gere aleatoriamente listas de tamanho n
com inteiros entre [-n, n]. No relatório, apresente o algoritmo em pseudocódigo.

R:

fuction lista random(int n):
lista tmp
int x
Para i de 1 até/igual n, passo 1
x =...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Complexidade de algoritmos
  • Complexidade de Algoritmos
  • Complexidade de Algoritmos
  • Complexidade de algoritmos
  • Complexidade de algoritmo
  • Complexidade algoritmos
  • Complexidade algoritmo
  • Complexidade Algoritmos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!