Ordenação Utilizando Filas de Prioridade

Implemente os algoritmos Insertion-Sort e Selection-Sort utilizando um TAD Fila de Prioridade que também deve ser desenvolvido.

Classes:

Fila:

import java.util.ArrayList;

abstract class Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public Fila(){
}

abstract public void InsereItem(int Chave, Object Elemento);

abstract public Item RemoveMin();

abstract public int MinKey();

abstract public Object MinElement();

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Item:

public class Item {

private int Chave;
private Object Elemento;

public Item(int Chave, Object Elemento){
this.Chave = Chave;
this.Elemento = Elemento;
}

public void setChave(int Chave){
this.Chave = Chave;
}

public void setElemento(int Elemento){
this.Elemento = Elemento;
}

public int getChave(){
return Chave;
}

public Object getElemento(){
return Elemento;
}

}

Sort:

import java.util.ArrayList;

public class Sort {

private Fila fila;
private ArrayList<Item> Array;

public Sort(ArrayList<Item> Array, Fila fila){
this.Array = Array;
this.fila = fila;
}

public ArrayList<Item> SortList(){
ArrayList<Item> ArrayOrdenado = new ArrayList<Item>();

for(int i = 0; i < Array.size(); i++)
fila.InsereItem(Array.get(i).getChave(), Array.get(i).getElemento());

int Tamanho = fila.Size();

for(int i = 0; i < Tamanho; i++)
ArrayOrdenado.add(fila.RemoveMin());

return ArrayOrdenado;
}

}

Selection-Sort:

import java.util.ArrayList;

public class SelectionSort extends Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public SelectionSort(){
}

public void InsereItem(int Chave, Object Elemento){
Array.add(new Item(Chave, Elemento));
}

public Item RemoveMin(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
Array.remove(menor);
return menor;
}

public int MinKey(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
return menor.getChave();
}

public Object MinElement(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
return menor.getElemento();
}

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Insertion-Sort:

import java.util.ArrayList;

public class InsertionSort extends Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public InsertionSort(){
}

public void InsereItem(int Chave, Object Elemento){
Array.add(new Item(Chave, Elemento));

int posicao = 1;
if(Array.size() >= 1){
while(posicao < Array.size()){
for(int i = posicao; i > 0; i--){
if(Array.get(i).getChave() < Array.get(i - 1).getChave())
SwapElements(Array.get(i), Array.get(i - 1));
}
posicao++;
}
}
}

public Item RemoveMin(){
Item temp = Array.get(0);
Array.remove(temp);
return temp;
}

public int MinKey(){
return Array.get(0).getChave();
}

public Object MinElement(){
return Array.get(0).getElemento();
}

private void SwapElements(Item Elemento1, Item Elemento2){
int index1 = Array.indexOf(Elemento1);
int index2 = Array.indexOf(Elemento2);

Array.set(index1, Elemento2);
Array.set(index2, Elemento1);
}

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Main:

import java.util.ArrayList;


public class Main {

public static void main(String Args[]){

SelectionSort Sel = new SelectionSort();
InsertionSort Ins = new InsertionSort();

ArrayList<Item> ArraySel = new ArrayList<Item>();

ArraySel.add(new Item(5, "Elemento 5"));
ArraySel.add(new Item(4, "Elemento 4"));
ArraySel.add(new Item(2, "Elemento 2"));
ArraySel.add(new Item(3, "Elemento 3"));
ArraySel.add(new Item(1, "Elemento 1"));

Sort SelSort = new Sort(ArraySel, Sel);

ArrayList<Item> ArrayIns = new ArrayList<Item>();

ArrayIns.add(new Item(10, "Elemento 10"));
ArrayIns.add(new Item(9, "Elemento 9"));
ArrayIns.add(new Item(8, "Elemento 8"));
ArrayIns.add(new Item(7, "Elemento 7"));
ArrayIns.add(new Item(6, "Elemento 6"));

Sort InsSort = new Sort(ArrayIns, Ins);

ArrayList<Item> ArrayRetornoSel = SelSort.SortList();

for(int i = 0; i < ArrayRetornoSel.size(); i++)
System.out.printf("%d ", ArrayRetornoSel.get(i).getChave());

System.out.printf("\n");

ArrayList<Item> ArrayRetornoIns = InsSort.SortList();

for(int i = 0; i < ArrayRetornoIns.size(); i++)
System.out.printf("%d ", ArrayRetornoIns.get(i).getChave());

}

}

TAD Árvore Binária

Objetivo: Escreva um programa que leia uma seqüência de números e monte uma Árvore Binária.

O programa deve ter as seguintes opções:

• Ler números digitados pelo usuário e montar a Árvore Binária ordenada;
• Remover um determinado elemento da árvore;
  Obs: Para simplificar permita remover somente "folhas".
• Verificar se a árvore está vazia;
• Percorrer a árvore pelos modos: preorder, inorder e posorder;
• Exibir a árvore na tela, de modo que a estrutura binária da árvore possa ser visualizada, ou seja, de maneira que possamos conferir a estrutura da árvore;
• Retornar a altura da árvore.

Classes:

Árvore:

import java.util.ArrayList;

public class Arvore {

// Atributo
private Elemento Raiz;

// Construtor recebe um Elemento Raiz para criar a árvore
public Arvore(Elemento Raiz){
this.Raiz = Raiz;
}

// Método SET
public void setRaiz(Elemento Raiz){
this.Raiz = Raiz;
}

// Método GET
public Elemento getRaiz(){
return this.Raiz;
}

// Método para inserir um novo elemento na árvore
public void InserirElemento(int Valor){

// O caminhamento na arvore vai começar a partir da raiz
Elemento ElementoAux = Raiz;

// Cria um novo elemento com o valor a ser inserido
Elemento NovoElemento = new Elemento(Valor);

// Inicia o caminhamento na árvore
while(ElementoAux != null){

// Verifica se o valor a ser inserido é maior que o valor do elemento atual
if(Valor > ElementoAux.getValor()){
// Verifica se elemento direito é diferente de nulo
if(ElementoAux.getElementoDireito() != null) // Se sim, pega o elemento direito para continuar a busca
ElementoAux = ElementoAux.getElementoDireito();
else{ // Se não, insere o elemento como o elemento direito
ElementoAux.setElementoDireito(NovoElemento);
ElementoAux = null;
}
// Valor a ser inserido menor que o valor do elemento atual
} else {
// Verifica se elemento esquero é diferente de nulo
if(ElementoAux.getElementoEsquerdo() != null) // Se sim, pega o elemento esquerdo para continuar a busca
ElementoAux = ElementoAux.getElementoEsquerdo();
else{ // Se não, insere o elemento como o elemento esquerdo
ElementoAux.setElementoEsquerdo(NovoElemento);
ElementoAux = null;
}
}
}
}

// Método para fazer o caminhamento "PreOrder"
public void PreOrder(Elemento Elemento){
if(Elemento != null){
System.out.printf("%d ", Elemento.getValor());
if(Elemento.Interno()){
PreOrder(Elemento.getElementoEsquerdo());
PreOrder(Elemento.getElementoDireito());
}
}
}

// Método para fazer o caminhamento "PostOrder"
public void PostOrder(Elemento Elemento){
if(Elemento != null){
if(Elemento.Interno()){
PostOrder(Elemento.getElementoEsquerdo());
PostOrder(Elemento.getElementoDireito());
}
System.out.printf("%d ", Elemento.getValor());
}
}

// Método para fazer o caminhamento "InOrder"
public void InOrder(Elemento Elemento){
if(Elemento != null){
if(Elemento.Interno()){
InOrder(Elemento.getElementoEsquerdo());
}
System.out.printf("%d ", Elemento.getValor());
if(Elemento.Interno()){
InOrder(Elemento.getElementoDireito());
}
}
}

// Método para remover um elemento
// Recebe como parâmetro um elemento e o valor a ser removido
public boolean Remover(Elemento Elemento, int Valor){
// Verifica se elemento é diferente de nulo
if(Elemento != null){
// Verifica se o valor do elemento é igual ao valor a ser removido
if(Elemento.getValor() == Valor){
// Verifica se o elemento é um elemento externo
if(!Elemento.Interno()) // Se sim, retorna verdadeiro, pois pode ser removido
return true;
else // Se não, retorna falso, pois não pode ser removido
return false;

// Se valor do elemento atual for diferente do valor a ser removido...
} else {

// Verifica se o elemento atual é um elemento interno
if(Elemento.Interno()){

boolean flag; // Flag para verificar se foi removido o elemento

flag = Remover(Elemento.getElementoEsquerdo(), Valor); // Chama a função remover recursivamente enviando o elemento esquerdo

// Verifica se foi removido o elemento
if(flag){
Elemento.setElementoEsquerdo(null); // Remove a ligação com o elemento
return false;
} else {

flag = Remover(Elemento.getElementoDireito(), Valor); // Chama a função remover recursivamente enviando o elemento direito

// Verifica se foi removido o elemento
if(flag){
Elemento.setElementoDireito(null); // Remove a ligação com o elemento
return false;
} else
return false;
}
}
}
}
return false;
}

// Método chamado para calcular Altura da árvore
public int Altura(){
return CalculaAltura(this.Raiz, 0);
}

// Método para calcular a Altura da árvore
// Recebe como parâmetro um elemento e a altura atual da contagem
private int CalculaAltura(Elemento Elemento, int Altura){
// Verifica se elemento é diferente de nulo
if(Elemento != null){

// Verifica se elemento atual é um elemento interno
if(Elemento.Interno()){
int AlturaAux1, AlturaAux2;
// Chama o método para Calcular altura recursivamente, enviando o elemento esquerdo e a altura atual + 1
AlturaAux1 = CalculaAltura(Elemento.getElementoEsquerdo(), Altura + 1);

// Chama o método para Calcular altura recursivamente, enviando o elemento direito e a altura atual + 1
AlturaAux2 = CalculaAltura(Elemento.getElementoDireito(), Altura + 1);

// Verifica qual dos lados teve a maior altura e retorna
if(AlturaAux1 > AlturaAux2)
return AlturaAux1;
else
return AlturaAux2;

// Se elemento atual é um elemento externo, apenas retorna a altura recebida
} else {
return Altura;
}
}
return 0;
}

// Método Auxiliar do método para imprimir
// Método Cria um Array onde cada posição do array representa um nível da arvore.
private ArrayList<object> BuscaPai(){

// Cria um array de niveis
ArrayList<object> ArrayNiveis = new ArrayList<object>();

// Cria um array auxiliar para fazer o laço
ArrayList<object> ArrayAux = new ArrayList<object>();
ArrayAux.add(this.Raiz); // Inicia o array com o elemento Raiz

ArrayNiveis.add(ArrayAux); // Adiciona no array de niveis o array contendo o elemento raiz

// Percorre o array auxiliar
while(ArrayAux.size() >= 1){

// Cria um array para receber o array do método BuscaFilhos
ArrayList<object> Array = new ArrayList<object>();

// Recebe o array do método BuscaFilhos
Array = BuscaFilhos(ArrayAux);

// Adiciona o array recebido no array de níveis
ArrayNiveis.add(Array);

// Verifica se o conteudo do array recebido tem algum elemento válido, não nulo
boolean Flag = false;
for(int i = 0; i < Array.size(); i++){
if(Array.get(i) != null){
Flag = true; // Existe elemento válido
break;
}
}

// Se existe elemento válido, seta o array auxiliar com o array recebido pelo método BuscaFilhos
if(Flag)
ArrayAux = Array;
else{ // Se não existe elemento válido, remove esse último array do array de níveis
ArrayNiveis.remove(ArrayNiveis.indexOf(Array));
break;
}
}

// Retorna o array de níveis para a impressão
return ArrayNiveis;
}

// Método Auxiliar do Método BuscaPai
// Método cria um array de filhos de acordo com o array passado
private ArrayList<object> BuscaFilhos(ArrayList<object> Array){

// Cria um novo array de filhos
ArrayList<object> ArrayNovo = new ArrayList<object>();

// Percorre o array passado, adicionando no novo array o filho da esquerda e da direita
for(int i = 0; i < Array.size(); i++){
// Recupera o elemento do array
Elemento ElementoAux = (Elemento)Array.get(i);

// Verifica se elemento é diferente de nulo
if(ElementoAux != null){ // Se sim, adiciona o elemento esquerdo e direito no novo array
ArrayNovo.add(ElementoAux.getElementoEsquerdo());
ArrayNovo.add(ElementoAux.getElementoDireito());
} else { // Se não, adiciona dois valores nulos no novo array, indicando que não tem filhos
ArrayNovo.add(null);
ArrayNovo.add(null);
}
}

// Retorna o novo array de filhos para a função BuscaPai
return ArrayNovo;
}

// Método para imprimir a árvore
public void Imprimir(){

// Chama a função BuscaPai que retornará o array de níveis da arvore
ArrayList<object> Array = BuscaPai();

// Verifica o tamanho do array da ultima posição do array de níveis
ArrayList<object> ArraySize = (ArrayList<object>) Array.get(Array.size() - 1);

// Cria uma variavel de tamanho
int Tamanho = ArraySize.size();

// Percorre o array de níveis
for(int i = 0; i < Array.size(); i++){

// Recupera o array da posição atual do array de niveis
ArrayList<object> Array2 = (ArrayList<object>) Array.get(i);

// Divide o tamanho pela metade, que é o número de espaços que serão utilizados para o nivel atual
Tamanho = Tamanho/2;

if(i == Array.size() - 1)
System.out.printf(" ");

for(int j = 0; j < Array2.size(); j++){

int Espacos; // Variavel que conterá quantos "\t" serão necessários para desenhar o nível atual

if(j == 0) // Se for o primeiro índice do FOR, recebe o próprio tamanho
Espacos = Tamanho;
else // Se não, recebe o tamanho * 2
Espacos = Tamanho * 2;

// Percorre o número de espaços tabulando a impressão
for(int k = 1; k <= Espacos; k++)
System.out.printf("\t");

// Verifica se é o último nível que está sendo impresso na tela
if((i == Array.size() - 1) && (j != 0))
System.out.printf("\t "); // Se sim, insere alguns espaços depois da tabulação

// Recupera o elemento para recuperar o valor
Elemento NovoElemento = (Elemento)Array2.get(j);

// Se elemento diferente de nulo...
if(NovoElemento != null)
System.out.printf("%d", NovoElemento.getValor()); // Imprime o valor do elemento
else
System.out.printf("-"); // Imprime um traço
}
System.out.printf("\n"); // Pula de linha a cada nível
}

}

}

Elemento:

public class Elemento {

// Atributos
private int Valor;
private Elemento ElementoDireito;
private Elemento ElementoEsquerdo;

// Contrutor recebe um valor como parâmetro
public Elemento(int Valor){
this.Valor = Valor;
this.ElementoDireito = null;
this.ElementoEsquerdo = null;
}

// Métodos SET
public void setValor(int Valor){
this.Valor = Valor;
}

public void setElementoEsquerdo(Elemento ElementoEsquerdo){
this.ElementoEsquerdo = ElementoEsquerdo;
}

public void setElementoDireito(Elemento ElementoDireito){
this.ElementoDireito = ElementoDireito;
}

// Métodos GET
public int getValor(){
return this.Valor;
}

public Elemento getElementoEsquerdo(){
return this.ElementoEsquerdo;
}

public Elemento getElementoDireito(){
return this.ElementoDireito;
}

// Método para verificar se nodo é interno
public boolean Interno(){
if((ElementoEsquerdo != null) || (ElementoDireito != null))
return true;
return false;
}

}

Main:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

public static void main(String Args[]){

int Opcao;

Scanner input = new Scanner(System.in);

// Cria um novo elemento que será o elemento Raiz
Elemento elemento = new Elemento(25);

// Cria a nova árvore, enviando o elemento Raiz
Arvore arvore = new Arvore(elemento);

// Insere os elementos na árvore
arvore.InserirElemento(15);
arvore.InserirElemento(20);
arvore.InserirElemento(10);
arvore.InserirElemento(13);
arvore.InserirElemento(30);
arvore.InserirElemento(28);
arvore.InserirElemento(35);
arvore.InserirElemento(14);

Opcao = 1;

while((Opcao >= 0) && (Opcao <= 7)){
Menu();
Opcao = input.nextInt();

if((Opcao >= 0) && (Opcao <= 7)){
int Valor;
switch(Opcao){
case 1 : ;
System.out.printf("\nDigite o valor do elemento a ser inserido: ");
Valor = input.nextInt();
arvore.InserirElemento(Valor);
break;
case 2 : System.out.printf("\nDigite o valor do elemento a ser removido: ");
Valor = input.nextInt();
arvore.Remover(arvore.getRaiz(), Valor);
break;
case 3 : System.out.printf("\nAltura da árvore: %d", arvore.Altura());
break;
case 4 : System.out.printf("\nPreOrder: ");
arvore.PreOrder(arvore.getRaiz());
break;
case 5 : System.out.printf("\nPostOrder: ");
arvore.PostOrder(arvore.getRaiz());
break;
case 6 : System.out.printf("\nInOrder: ");
arvore.InOrder(arvore.getRaiz());
break;
case 7 : arvore.Imprimir();
break;
}

}

}

}

private static void Menu(){
System.out.printf("\n");
System.out.printf("\n");
System.out.printf("0 - Sair\n");
System.out.printf("1 - Inserir Elemento\n");
System.out.printf("2 - Remover Elemento\n");
System.out.printf("3 - Verificar Altura\n");
System.out.printf("4 - Caminhamento PreOrder\n");
System.out.printf("5 - Caminhamento PostOrder\n");
System.out.printf("6 - Caminhamento InOrder\n");
System.out.printf("7 - Imprimir Árvore\n");
System.out.printf("Digite Sua Opção: ");
}

}

TAD Sequência com Arranjo Circular

Implemente o TAD sequência baseado em um arranjo variável usado de forma circular de maneira que as inserções no início e no fim da sequência executem em tempo constante.

Classes:

Posição:

public class Posicao
{
// indice no vetor
private int indice;

// referencia para o elemento
private Object elemento;

// construtor
public Posicao(int indice, Object elemento)
{
this.indice = indice;
this.elemento = elemento;
}

// retorna indice
public int index()
{
return indice;
}

// retorna elemento
public Object element()
{
return elemento;
}
}

Interador:

public class Iterador
{
// armazena elementos
private Posicao[] elementos;

// controla posicao no array
private int pos;

// construtor
public Iterador(Posicao[] elementos)
{
this.elementos = elementos;
pos = 0;
}

// retorna objeto corrente do array
public Posicao object()
{
return elementos[pos];
}

// verifica se tem proximo elemento
public boolean hasNext()
{
if(pos == elementos.length)
return false;

return true;
}

// move para o proximo elemento
public Posicao nextObject()
{
if(hasNext())
return elementos[pos++];

return null;
}

// volta ao começo
public void reset()
{
pos = 0;
}
}

Sequência:

public class Sequencia
{
// no. max. de elementos
private final int MAX_ELEMENTOS = 100;

// array de posicoes
private Posicao[] sequencia;

// variaveis de controle
private int first;
private int last;
private int N;

// construtor
public Sequencia()
{
sequencia = new Posicao[MAX_ELEMENTOS];
first = 0;
last = 0;
N = MAX_ELEMENTOS;
}

// insere elemento na primeira posicao
public void insertFirst(Object o)
{
// calcula possivel indice
int pos = first - 1;

// verifica se menor que limite
if(pos < 0)
pos = N - 1; // circular

// verifica se sequencia esta cheia
if(pos == last)
{
aumentar();
// chama funcao novamente apos aumentar
insertFirst(o);
}
else
{
// cria nova posicao
Posicao posicao = new Posicao(pos, o);

// insere na posicao candidata
sequencia[pos] = posicao;
// atualiza indice da primeira posicao
first = pos;
}
}

// insere elemento na ultima posicao
public void insertLast(Object o)
{
// cria nova posicao
Posicao posicao = new Posicao(last, o);

// insere na ultima posicao
sequencia[last] = posicao;

int pos;

// atualiza indice da ultima posicao
pos = (last + 1) % N;

// verifica se sequencia esta cheia
if(pos == first)
aumentar();
else
last = pos; // atualiza indice da ultima posicao
}

// duplica tamanho da sequencia
public void aumentar()
{
// cria nova sequencia com dobro do tamanho
Posicao[] temp = new Posicao[2*sequencia.length];

// contadores auxiliares
int pos = first;
int i = 0;

// copia todos os elementos para nova sequencia
while(pos != last)
{
temp[i] = new Posicao(i, sequencia[pos].element());
i++;
pos = (pos + 1) % N;
}

// atualiza indices
first = 0;
last = i;
sequencia = temp;
N = sequencia.length;
}

public int size()
{
return (N - first + last) % N;
}

public Iterador elements()
{
// cria array de elementos a serem retornados
Posicao[] elementos = new Posicao[size()];

// contadores auxiliares
int pos = first;
int i = 0;

// copia todos os elementos para array de saida
while(pos != last)
{
elementos[i] = sequencia[pos];
i++;
pos = (pos + 1) % N;
}

// cria iterador auxiliar e passa elementos
Iterador iterador = new Iterador(elementos);

// retorna iterador
return iterador;
}

// insere elemento antes de posicao p
public void insertBefore(Posicao p, Object o)
{
// indice para ultima posicao (valor corrente)
int pos = last;

// desloca todos os elementos depois de p
do
{
sequencia[pos] = new Posicao(pos, sequencia[pos-1].element());
pos--;

// verifica limite inferior
if(pos < 0)
pos = N-1;
}
while(pos > p.index());

// insere novo elemento
sequencia[pos] = new Posicao(pos, o);

// atualiza indice para ultimo elemento
last = (last + 1) % N;

// verifica necessidade de crescimento
if(size() == N)
aumentar();
}

}

Testa Sequência:

public class SequenciaApp
{
public static void main(String args[])
{
Posicao p = null;
Iterador it;
Sequencia seq = new Sequencia();

seq.insertLast("Bola");
seq.insertLast("Caixa");
seq.insertLast("Chave");
seq.insertFirst("Lapis");

it = seq.elements();
while(it.hasNext())
{
p = it.nextObject();
System.out.println((String)p.element());
}

seq.insertBefore(p, "Controle Remoto");
System.out.println();

it = seq.elements();
while(it.hasNext())
{
p = it.nextObject();
System.out.println((String)p.element());
}
}
}

Algoritmos e Estruturas de Dados I - Será?

interface estruturaLinear {
// verifica se a estrutura tem elementos
public boolean estaVazia();
// devolve a quantidade de elementos da estrutura
public int tamanho();
// insere um elemento no início da estrutura
public void inserir(Object p0);
// insere um elemento no fim da estrutura
public void inserirCauda(Object p0);
// remove um elemento do início da estrutura
public Object remover();
// remove um elemento do fim da estrutura
public Object removerCauda();
}

/****************/

public class ArrayCircularList implements estruturaLinear {
protected Object[] array;
protected int start,end,number;

public void pArrayList(int maxsize){
array = new Object[maxsize];
start = end = number = 0;
}
public boolean estaVazia(){
return number == 0;
}
public boolean isFull(){
return number >= array.length;
}
public int tamanho(){
return number;
}
public void inserir(Object o){
if(number < array.length){
array[start = (++start % array.length)] = o;
number++;
}
}
public void inserirCauda (Object o){
if(number < array.length){
array[end] = o;
end = (--end + array.length) % array.length;
number++;
}
}
public Object remover(){
if(estaVazia())
return null;
number--;
int i = start;
start = (--start + array.length) % array.length;
return array[i];
}
public Object removerCauda(){
if(estaVazia())
return null;
number--;
return array[end = (++end % array.length)];
}
}

Algoritmos e Estruturas de Dados I - Aula 02

Apostila 03 : Vetores, Listas e Sequências - Download
Apostila 04 : Árvores - Download
Apostila 05 : Filas de Prioridade - Download

Atividades terça, 25 de agosto de 2009:

FIFO Ganho (ou Perda) de Capital

Quando um lote de ações de uma companhia é vendido, o ganho de capital (ou, às vezes, a perda) é a diferença entre o preço de venda do lote e o preço originalmente pago por ele. Essa regra é fácil de entender para um único lote, mas se vendermos múltiplos lotes comprados em tempos diferentes temos de identificar os lotes sendo vendidos. Um método usado para identificar que lotes são vendidos é usar uma estrutura que suporte o protocolo FIFO, na qual os lotes vendidos são aqueles que temos há mais tempo (este é o método usado em vários softwares de finanças pessoais). Por exemplo, suponha que compramos 100 lotes a $20 cada no dia 1, 20 lotes a $24 no dia 2, 200 lotes a $36 no dia 3 e vendemos 150 lotes no dia 4 a $30 cada. Aplicando o protocolo FIFO, significa que dos 150 lotes vendidos, 100 foram comprados no dia 1, 20 foram comprados no dia 2 e 30 foram comprados no dia 3. O ganho de capital neste caso seria 100.10+20.6+30.(-6), ou $940.

Escreva um programa que recebe como entrada uma sequência de transações da forma

• compre x lotes a y cada
  ou
• venda x lotes a y cada

assumindo que as transações ocorrem em dias consecutivos e que os valores x e y são inteiros. Dada esta sequência de entradas, a saída deve ser o ganho total (ou perda) de capital para a sequência completa, usando o protocolo FIFO para identificar os lotes.

Baixar Possível Resolução

Para baixar o JCreator clique aqui.

Algoritmos e Estruturas de Dados I - Aula 01

Apostila 01 : Análise de Algoritmos - Download
Apostila 02 : Pilhas, Filas e Deques - Download