REVISÃO DE ALGORITMOS AVANÇADOS pronto

Prévia do material em texto

Revisão de Algoritmos Avançados – 25.09.2017
 
Descreva o funcionamento de uma árvore binária e qual sua finalidade principal (1.5) 
A árvore binária é uma árvore onde todos os nós são valores, todo nó a esquerda contêm uma sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os nós da sub-árvore a direita contêm somente valores maiores ao nó raiz. (Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo da aplicação). Os valores são relevantes na árvore de busca binária. O objetivo desta árvore é estruturar os dados de forma flexível permitindo pesquisa binária
Comente qual a aplicabilidade dos algoritmos de ordenação. (0,5) 
Algoritmos de ordenação são normalmente aplicados em listas que possuem uma relação de vizinhança em todos os nodos: como listas duplamente encadeadas e vetores; A entrada do algoritmo é um conjunto desordenado e a saída é o mesmo conjunto, porém ordenado. 
Dê exemplos de algoritmos recursivos exemplifique o trecho de código que remete a recursividade 
Recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma
Exemplo 1:
def fatorial(n):
 if n == 1:
 return n
else
 return n * fatorial(n-1)
c =int(input ("Digite um numero"))
#print("O numero e: ",c)
print("O fatorial do numero e: ",fatorial(c))
Exemplo 2:
def fibonacci (num):
 if num <=1:
 return num
 else:
 return fibonacci (num -1) + fibonacci(num -2)
x= int(input("Digite um numero para calcular seu fibonacci:"))
resultado=fibonacci (x-1)
print ("O fibonacci de %d é %d" % (x,resultado))
Construa em python ou c++ qualquer algoritmo que use recursividade (1.5) 
 def fat(n):
 if n == 1:
 return n
 return n * fat(n-1)
print("Fatorial de 0: ", fat(0))
print("Fatorial de 1: ", fat(1))
print("Fatorial de 3: ", fat(3))
Comente o funcionamento de pelo menos dois algoritmos de ordenação (1.5) 
 
Funcionamento do algoritmo Insertion Sort
Consiste em cada passo a partir do segundo elemento selecionar o próximo item da sequência e colocá-lo no local apropriado de acordo com o critério de ordenação.
Funcionamento do algoritmo Selection Sort
A ordenação por seleção ou selection sort consiste em selecionar o menor item e colocar na primeira posição, selecionar o segundo menor item e colocar na segunda posição, segue estes passos até que reste um único elemento.
 
Funcionamento do algoritmo Quick Sort:
A ideia básica é dividir o problema de ordenar um conjunto com nitens em dois problemas menores. Os problemas menores são ordenados independentemente e os resultados são combinados para produzir a solução final. 
Funcionamento do algoritmo Mergesort
Esse algoritmo divide o problema em pedaços menores, resolve cada pedaço e depois junta (merge) os resultados. O vetor será dividido em duas partes iguais, que serão cada uma divididas em duas partes, e assim até ficar um ou dois elementos cuja ordenação é trivial.
 Funcionamento do algoritmo Shell Sort
o método Shell Sort é uma extensão do algoritmo de ordenação por inserção. Ele permite a troca de registros distantes um do outro, diferente do algoritmo de ordenação por inserção que possui a troca de itens adjacentes para determinar o ponto de inserção. A complexidade do algoritmo é desconhecida, ninguém ainda foi capaz de encontrar uma fórmula fechada para sua função de complexidade e o método não é estável.
 
Construa um programa em python ou c++ para retirar a média aritmética de vetor de 1000 posições. (2.5) 
 numero = [0] * 1000
soma = 0
for i in range(1000):
 numero[i] =int(input("Digite o numero:"))
 soma = soma + numero [i]
else:
 print ("Os números são:", numero)
 print ("A média dos números é:",soma/1000)
#tem uma forma mais simples de fazer porem não sei como , ai vai ter que ser digitado um por um 
Transforme um texto com 1200 caracteres e mostre quais as palavras com maior ocorrência 
 
 AcordaBrasil =ESCREVE O TEXTO AQUI 
 texto=AcordaBrasil[0:1199]
print (texto)
from collections import Counter
texto = texto.split(' ')
texto2=Counter(texto)
print ('As palavras mais usadas no texto são:',texto2.most_common()[5:7])#esse final está com gambiarra