Waipapa Pt e Jack’s Blowhole

fotos, nova zelândia, viagens, praias, southland, trilhas

2010

31

jan

Este artigo é parte da série Diários da Nova Zelândia

Ao sair de Bluff era hora de começar a subir a Ilha Sul pela costa leste, e o extremo sudeste da Ilha Sul foi uma das regiões que mais gostei principalmente porque há muito para ver. São muitos rochedos, baías e paisagens, mas sem muitas trilhas. Coisa pra turista mesmo, embora a atividade turística por aqui seja bem menor devido à distância das cidades maiores.

Ao sair pela região vimos algo muito engraçado e bizarro. Como aqui venta muito, as árvores acabam crescendo deitadas, olha só:

Árvores que crescen deitadas em southland

O primeiro lugar que paramos chama-se Waipapa Pt, que não seria tão famoso se aqui não tivesse acontecedio o naufrágio do SS Tararua, o que acaba sendo o pior naufrágio que já aconteceu na Nova Zelândia.

Depois do acontecido fizeram um farol para evitar esse tipo de acidente.

Esta região é de navegação perigosa por causa dos longos e baixos rochedos que acompanham a costa e são invisíveis à noite.

Depois de passar um tempinho ali fomos conhecer o Jack’s Blowhole, que ficava em Jack’s Bay. Esse tal de Jack deve ser muito egocêntrico por descobrir o tal do buraco. Trata-se de um lugar muito simpático com meia dúzia de casas e povoado por fazendeiros simples.

Chama-se blowholes o que conhecemos por gargantas, que são entradas de mar para dentro da costa por baixo da terra, que acabam acontecendo por inssitência das ondas seguido por um desfalecimento da terra em algum ponto interior da caverna.

Detalhe que a trilha que chega até o buraco não foi originalmente feita pelo Departamento de Conservação do governo, mas sim pelos moradores locais que confiam que você deposite NZ$1 para usar a trilha e NZ$2 para acampar um dia no local. Só porque eles querem mesmo…

A trilha é muito bonita. A sensação de andar em pastos sobre estes rochedos é bem interessante. Ficamos um tempo tacando pedras para tentar acertar o mar sem sucesso e concluímos. “Se alguém se jogar aqui certamente não cai na água.”

No caso do Jack’s Blowhole o mar encontrou uma passagem de 200m para dentro da costa em um rochedo de 55m de altura, ficando com uma cratera de 65m de largura. Coisa de louco ficar olhando para ondas quebrando com tamanha violência pra dentro do buraco.

Invercagill e Bluff

fotos, nova zelândia, viagens, bluff, invercagill, mirantes, stewart island

2010

10

jan

Este artigo é parte da série Diários da Nova Zelândia

Enfim chegamos em Invercagill (diz-se “Invercágo”), a última cidade de tamanho considerável da Nova Zelândia. Esta cidade possui avenidas largas, prédios antigos e uma população pequena. Reza a lenda que o governo até lhe pagará um salário se você resolver vir morar por aqui.

Ela fica um pouco antes do vilarejo de Bluff, este sim o extremo sul da Ilha Sul. Neste ponto ainda não havíamos utilizado os esquis que o Beto comprou por NZ$10, e estava na hora de tentar passar eles pra frente.

Em tentativas inocentes, nenhuma loja de materiais usados os aceitaram dizendo que eles eram velhos demais. Sem restar o que fazer com eles, Beto e Bernardo deram uma de típicos brasileiros. Sentaram para conversar em um banquinho, ficaram alguns instantes, levantaram e ops… foram embora esquecendo os esquis. Como que alguém esquece um trambolho daqueles em um banco?

Preste atenção e verá o resultado da gafe: os pobres esquis encostados e abandonados no banco.

Sem muito o que ver na cidade chuvosa de Invercagill, já no final da tarde fomos para Bluff, ainda mais ao sul. Basta seguir a estrada por dentro dos trapiches até o vilarejo de três ruas que é Bluff. A segunda inocência do dia foi a de que conseguiríamos arranjar um lugar para acampar por ali, e foi que novamente tivemos de dormir no carro. Eu nesta viagem foi a segunda vez, pois o Beto já tinha optado por isso antes, enquanto o Bernardo dormia a maioria dos dias.

Foi para mim foi, de longe, a noite mais desconfortável dessa viagem.

Pela manhã fomos até o mirante para dar uma olhada e, como de prache, a paisagem é muito boa.

Mirante do extremo sul da Nova Zelândia em Bluff

Pode-se ver Invercagill e toda a extensão da Ilha Sul, além do porto de Bluff.

Vista para a ilha sul do mirante de Bluff

E na vista para o sul pode-se ver a Stewart Island, a terceira maior Ilha da Nova Zelândia. Segundo a lenda esta é a âncora do barco do herói que pescou a Ilha Norte, enquanto a Ilha Sul seria o barco. É um reduto de pássaros raros, pois lá ainda não existem predadores levados pelo homem que reproduziram-se livremente. Como o ferry para lá somente acontece a cada semana, decidimos cortar esta pequena ilha de nossa viagem.

Vista para a Steward Island do mirante de Bluff

Agora a viagem estava teoricamente pela metade. Restava voltar ao norte pela costa leste da Ilha Sul, e pela costa oeste da Ilha Norte até Auckland. Alcançados o extremo norte e o extremo sul, era hora de voltar.

Contorcionismo Pelas Fendas de Clifden Caves

fotos, nova zelândia, viagens, cavernas, clifden caves, southland

2010

9

jan

Este artigo é parte da série Diários da Nova Zelândia

Saindo de Milford Sound o plano era ir agora até o extremo sul do país para depois voltar ao norte pela costa leste. A caminho de Invercagill - a última cidade de tamanho considerável, deparamo-nos com o aviso turístico “Clifden Caves”. O Beto havia muito tempo queria explorar algumas cavernas, e assim como todo o resto de nossas atividades - trilhas, escaladas em geleiras, rally em terras perdidas - não tínhamos nenhum equipamento, e isso até agora não era muita desvantagem.

A entrada parece bastante turística e fácil, o que muda poucos metros adentro. A amplitude simplesmente acaba, aparentando o fim da caverna. Aí olhando um pouquinho melhor para as paredes só à base de luz de lanterna de dínamo e LED de celular pode-se ver algumas flechas refletoras que indicam o caminho. “Não é possível, será que tem que entrar aqui mesmo?”. O negócio era tentar.

Os túneis e malabarismos continuavam adentro. Cada nova fenda era um exercício de contorcionismo, isso sem falar nas escadas por cima dos lagos subterrâneos e a iluminação precária que tínhamos. Um cara um pouco mais gordo não iria muito longe.

Dentro de uma grnde fenda em Clifden Caves

Infelizmente a maioria das fotos não ficaram muito boas devido à escuridão intensa. Tentamos fotografar algumas estalactites e estalagmites, artrópodes fluorescentes e lagos, só que nada ficou muito bom. Vídeos são impossíveis com as câmeras que tínhamos.

Enfim, passamos um bom tempo indo de fenda em fenda sem saber o quanto teríamos de ir, e parecia que a caverna não acabava nunca mais. Do nada a luz surge por uma passagem estreita, e lá estava a saída. Saímos no meio de um pasto com paisagem recompensadora.

A Grandeza de Milford Sound

fotos, nova zelândia, viagens, fiordland, milford sound

2009

31

dez

Este artigo é parte da série Diários da Nova Zelândia

O “sound” do título é algo para o qual eu não encontrei uma tradução adequada, então vale explicar. Chamam-se “sounds” as entradas do mar por vales e montanhas, geralmente configuradas de maneira fechada e até meio labiríntica.

Não entendeu? Dê uma olhada no mapa de satélite do Milford Sound e do Queen Charlotte Sound, este último onde cruza o Ferry entre a Ilha Norte e a Ilha Sul. O extremo sudoeste da Nova Zelândia é composto pelo Parque Nacional Fiordland, um dos maiores complexos de “sounds” do mundo, e o maior parque da Nova Zelândia.

Este parque não é acessível na maioria de sua extenão, sendo extremamente recortado e inabitado. São várias as menções que o meio ambiente aqui permanece inalterado desde o povoamento do país - embora minha formação me force a duvidar um pouco disso.

Como dito no post anterior, a estrada de Queenstown até Milford Sound é lindíssima, e cruza-se diversos pontos de filmagem de O Senhor dos Anéis. Esta planície por exemplo.

Não imagino um acesso fácil via terra para os “sounds” que não seja a estrada com os túneis. Esta região é cercada por paredões de montanhas por todos os lados, e fico pensando como isso era feito pelos Mäori nativos da região, que comprovadamente já haviam passado por ali. A estrada para este acesso também possui o maior túnel da Nova Zelândia.

Paredão de acesso para os Sounds de Fiordland

Ao chegar no final da estrada, infelizmente não há muito dos “sounds” para ver se você não pagar um caríssimo passeio de barco pela água. De qualquer modo, há uma pequena e simpática trilha, e um pequeno museu de história natural.

Cachoeiras descem de todos o lados das montanhas que simplesmente emergem da água sem nenhuma praia. A região de fato parece bastante inóspita e intocada. A umidade é tamanha que ainda em pleno meio-dia há uma névoa fina por cima da água acompanhada de uma névoa bem mais grossa por entre os altos becos.

Final da Trilha da Cachoeira em Milford Sound

É uma sensação minimalística olhar para o fundo dos becos. Dizem que quando chove a paisagem fica ainda mais bonita por aumentar o fluxo de água que desce das inúmeras cachoeiras.

Aliás, eu estou nas duas fotos acima. Se você prestar atenção pode me ver. Entendeu o porquê da sensação minimalística?

Fiordland, Te Anau e Henry Creek

fotos, nova zelândia, viagens, acampamento, fiordland, henry creek, milford sound, te anau

2009

28

dez

Este artigo é parte da série Diários da Nova Zelândia

A estrada de Queenstown até Milford Sound foi a mais bonita que fiz pela Nova Zelândia, passando por vários túneis, bosques, montanhas e planícies. Boa parte da filmagem de Senhor dos Anéis foi feita nesta região, então pode-se imaginar como que é o negócio.

Fomos até Te Anau, a última cidadezinha antes de Milford Sound. O clima interiorano e o olhar torto dos moradores para nós deram um clima memorável e bastante estranho daqueles filmes estadunidenses. Sei que não é tanto, mas esta cidade também me passou uma ideia muito forte de isolamento, talvez por ter uma estrada somente de ida até ela.

Acampamos em Henry Creek, que é mais um acampamento bastante escondido (ainda mais à noite), coisa comum pela Ilha Sul.

Este acampamento fica à beira do Lago Te Anau, que dá nome à cidade que passamos. É o maior lago da Nova Zelândia. Chegamos lá à noite, sendo meio assustador devido à área de camping ser bem no meio da mata. Fomos dar uma volta pela borda do lago no meio da madrugada congelante e admirar o céu bastante visível nesta região um pouco mais afastada, e pela manhã admiramos o visual da água cristalina.

Vista do Lago Te Anau no acampamento Henry Creek

Quatro Dias em Queenstown

fotos, nova zelândia, viagens, acampamento, queenstown, southland

2009

27

dez

Este artigo é parte da série Diários da Nova Zelândia

Até este ponto da viagem o negócio foi basicamente no meio do mato e da neve, e principalmente o Bernardo estava sentindo muita falta de uma cidadezinha. Foi lá que vimos neve caindo pela primeira vez, e como o Beto já havia programado faz um tempão que gostaria de pular de bungie-jump, tivemos de esperar o agendamento do salto dele para o outro dia.

Queenstown é mais ou menos uma rua cheia de lojas de esportes radicais. Em um final de semana você facilmente pode gastar NZ$3.000 em somente uma quadra dentre passeios de moto, lanchas, esqui, saltos e tudo mais que esse povo inventa pra fazer dinheiro fácil dos pobres turistas. É também um reduto de brasileiros. Andando pelas ruas e supermercados vemos com frequência o português fluindo em meio à expressões em inglês que não são lá tão difíceis de traduzir, mas a galera não traduz por falta de identidade com a língua mesmo.

A paisagem da cidade é linda. Com os alpes ao fundo e à beira do lago Wakatipu, possui uma população reduzida de 10.000 habitantes. Tudo isso dá um certo ar bucólico e simpático, mas ao mesmo tempo com toda a praticidade de uma cidade moderna. Esta foto o Beto tirou de cima da colina onde está construído um dos Bungie-Jumps, e a atração principal deste é justamente ser sobre a cidade. Nesta colina também está a famosa pista de carrinho de rolimã.

Acampamos em Twelve Mile Delta, uma saída de terra para o lago transformada em uma pseudo clareira de acampamento a uns 40 minutos da cidade. Foi lá que filmaram a batalha dos Oliphants de O Senhor dos Anéis.

Pôr do sol de cima da colina em Queenstown

Ficamos indo e voltando deste acampamento todos os quatro dias principalmente para não pagar nenhum tipo de hospedagem - assim como fizemos por toda a Nova Zelândia. Mas aqui houve um episódio ainda mais engraçado. Como não estávamos encontrando um lugar para tomar banho, e os lugares em geral não nos deixavam somente tomar banho sem que pagássemos a hospedagem por inteiro, simplesmente entramos em um Hostel qualquer, cumprimentamos o pessoal da portaria, e fomos tomar banho.

Queenstown é o típico lugar em que se deve cozinhar dentro da barraca.

Cozinhando de dentro da barraca em Queenstown

Esta cidade também possui muitas lojas de souvenires, com todo tipo de cacareco para trazer para casa. Uma observação importante também é que tudo, em geral, é muito mais caro.

Não tenho muito mais para falar sobre Queenstown do que aqueles que visitam a cidade querendo morar lá ou gastar as calças. Desde que sou meio contra à espetacularização do esporte não posso considerar bungie-jumps e lanchas como esportes radicais. Passei grande parte do tempo na biblioteca lendo tudo o que pude sobre a Índia, esperando os meninos frequentarem estes lugares.

Doa-se cachorrinho: Joaquim Ferdinando

especismo, fotos, cachorros, doação

2009

19

dez

Este alegre e vitaminado vira-latinha foi atropelado em frente à casa dos meus pais e teve uma patinha dianteira quebrada. Ele foi levado ao veterinário e está se recuperando muito bem. Como estava de coleira e bem tratado acreditamos que ele já devia ter um dono, e rodamos a vizinhança inteira perguntando mas ninguém o reconheceu.

Se você reconhece o Joaquim nas imediações do Orleans, Campo Comprido e Gabineto ou quer adotá-lo, entre em contato:

Atenção: O Joaquim já foi doado
Obrigado a todos pela divulgação.

É meio difícil tirar umas fotos do Joaquim porque ele ficou tão grato e feliz por ser socorrido que não para quieto. Ele é novinho, de porte médio para pequeno e muito bonzinho, pois é super dócil, brincalhão, não late e fica feliz com qualquer pessoa.

Substituição de Trechos em Strings com C

estudos, bcc, c/c++

2009

28

nov

É fato comum nestes últimos anos que, especialmente adolescentes e jovens, utilizem habitualmente a palavra tipo como advérbio, aposto, vocativo, artigo, entre outros não previstos para tal palavra.

Preocupado com a deficiência no vernáculo português que tal hábito representa, o professor da turma A de Ocina de Computação solicita a seus alunos que escrevam um programa que ajude pessoas com tal vício de linguagem a se recuperarem.

Para tanto, implemente um programa em linguagem C que leia diversas linhas de texto (cada linha é terminada pelo caractere ‘\n’) até encontrar o sinal ‘EOF’. Ao final da leitura o programa deve imprimir as linhas lidas eliminando todas as ocorrências da palavra tipo.

Entretanto, as linhas devem ser impressas na ordem inversa à leitura. Devem ser eliminadas apenas as ocorrências da palavra tipo, ou seja, variações como: tipos, logotipo, tipografia, etc não devem ser afetados.

Pode acontecer que a frase que sem sentido, especialmente se a palavra tipo estava empregada corretamente. Mas isso é aceitável e não precisa ser levado em consideração.

Entrada:

Professor, tipo eu tenho uma dúvida tipo sobre o trabalho
O tipo de problema depende dos tipos de dados
Uma tipografia trabalha com tipos
Pô meu, tipo, tenho uma parada que é do tipo, sacou?

Saída:

Pô meu,, tenho uma parada que é do, sacou?
Uma tipografia trabalha com tipos
O de problema depende dos tipos de dados
Professor, eu tenho uma dúvida sobre o trabalho

Programa:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define LINHA 50
 
char* le_frase() {
	int i = 0, j = LINHA;
	char c, *str;
 
	str = malloc (sizeof(char) * j);
	while ((c = getc(stdin)) && (c != '\n')) {
		if (c == EOF) return 0;
		if (i >= j) str = realloc (str, j *= 2);
		str[i++] = c;
	}
	str[i] = '';
 
	return str;
}
 
int e_letra (char c) {
	if ((65 <= c) && (c <= 122))
		return 1;
	return 0;
}
 
int busca_palavra (char *frase, char *palavra) {
	int i = 0, j = 0;
	int t = strlen(palavra);
 
	for (i = 0; i < strlen(frase); i++) {
		if (frase[i] == palavra[j]) {
			j++;
			if ((j == t) && (!e_letra(frase[i+1])) && (!e_letra(frase[i-t])))
				return i-t+1;
		} else j = 0;
	}
 
	return -1;
}
 
char* remove_palavra (int pos, char *frase, char *palavra) {
	int i, j = 0;
	int tp = strlen(palavra);
	int tf = strlen(frase);
 
	char *nfrase = malloc(sizeof(char) * tf);
	if (pos >= 0) {
		for (i = 0; i < pos; i++)
			nfrase[j++] = frase[i];
		for (i = pos + tp; i < tf; i++)
			nfrase[j++] = frase[i];
	} else {
		strcpy(nfrase,frase);
	}
 
	nfrase[j] = '';
 
	return nfrase;
}
 
char* strtolower (char *str) {
	int i = 0;
 
	while (str[i]) {
		if ((65 <= str[i]) && (str[i] < 97))
			str[i] += 97-65;
		i++;
	}
 
	return str;
}
 
int main () {
	char *frase;
	//char palavra[sizeof(int) * 3] = "tipo";
 
	while ((frase = le_frase())) {
		printf("%s\n",frase);
		printf("%s\n",remove_palavra (busca_palavra(strtolower(frase),palavra), frase, palavra));
		free(frase);
	}
 
	return 0;
}

Problema das Probabilidades de Coincidência de Aniversários

estudos, bcc, c/c++, estatística, probabilidades, programação

2009

27

nov

Há um problema em estatística bastante interessante, e que consiste resumidamente em uma simples pergunta:

Quantas pessoas precisaremos para que haja ao menos uma coincidência de aniversários entre elas?

3374833183_a1d7064442 Problema das Probabilidades de Coincidência de Aniversários

Esta pergunta desafia nosso senso comum, afinal, uma coincidência de aniversários parece ser algo tão raro, e ao mesmo tempo sabemos que outras milhares de pessoas nascem no mesmo dia em que fazemos aniversário.

Na dúvida simulamos por força bruta, ou seja: Repetimos as possibilidades milhares de vezes até encontrar uma resultado razoável.

Podemos fazer isso através do seguinte programa em C:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int numeroAleatorio(int max, int min, int seed) {
	int numero;
	srand(seed*time(NULL));
 	numero = rand();
	while (numero > max) numero = (numero % (max+1)) + min;
	return numero;
}
 
int buscaAniversariantes(int n) {
	int i, j, coincidencias = 0, dias = 365;
	int aniversariantes[n];
 
	for (i = 1; i <= n; i++) {
		aniversariantes[i] = numeroAleatorio(dias,1,i);
	}
 
	for (i = 1; i <= n-1; i++) {
		for (j = i+1; j <= n; j++) {
			if (aniversariantes[i] == aniversariantes[j]) coincidencias++;
		}
	}
 
	return coincidencias;
}
 
int main() {
	int pessoas;
 
	printf("Número de pessoas: ");
	scanf("%d",&pessoas);
 
	printf("Coincidências: %d \n",buscaAniversariantes(pessoas));
 
	return 0;
}

Vejamos então uma simulação para cada quantidade (sem empregar força bruta).

Número de pessoas: 10; Coincidências: 0
Número de pessoas: 20; Coincidências: 0 
Número de pessoas: 30; Coincidências: 0 
Número de pessoas: 40; Coincidências: 1 
Número de pessoas: 50; Coincidências: 7 
Número de pessoas: 60; Coincidências: 6

Se repetirmos estas execuções diversas vezes, podemos concluir que a partir de 60 pessoas é praticamente impossível não termos ao menos uma coincidência de datas de aniversário. A grosso modo: Não fique achando que a data do seu aniversário é muito sua.

Busca em Largura nos Tubos de Ligeirinho de Curitiba

estudos, algoritmos, bcc, c/c++, curitiba, transporte

2009

27

nov

1376102471_5fb4a7a5c8 Busca em Largura nos Tubos de Ligeirinho de Curitiba

Enunciado:

Considerando o transporte coletivo de Curitiba, mais restritamente os Ligeirinhos e seus respectivos Tubos, o obejtivo desse trabalho é desenvolver um sistema capaz de identificar dois melhores caminhos entre dois Tubos:

o caminho com o menor número de Tubos; e
o caminho com o menor número de Ligeirinhos.

A entrada deve ser feita pela entrada padrão (stdin). O arquivo será composto por uma linha com os Tubos inicial e final que se deseja procurar o menor caminho, e uma lista de rotas dos Ligeirinhos e seus Tubos, uma por linha, como no exemplo abaixo:

2 12
1 2 3 4 5 #
5 6 2 7 8 #
2 9 10 11 5 12 #

O # no final de cada linha é para facilitar a leitura. Considere que o número do Ligeirinho começa em 1. Este processo já está implementado no arquivo main.c disponibilizado.

A saída deve ser feita pela saída padrão (stdout). O arquivo será composto por duas linhas: a primeira com o caminho composto pelo menor número de Tubos; e a segunda com o caminho composto pelo menor número de Ligeirinhos. Cada Tubo destes caminhos deve ser mostrado entre parênteses e cada Ligeirinho entre “-”. Por exemplo um conteúdo do arquivo de saída válido.

(2)-1-(3)-1-(4)-1-(5)-3-(12)
(2)-3-(9)-3-(10)-3-(11)-3-(5)-3-(12)

Solução:

1. Introdução

São inúmeras as estruturas que podem ser representadas através de grafos em nosso cotidiano, e da mesma forma são inúmeras as aplicações - muitas vezes implícitas - de algoritmos que efetuem buscas de determinados dados nestas estruturas.

Uma forma interessante e elucidativa de imaginar um grafo são as possibilidades de percorrimento de rotas reais, tais como estradas, pontes ou linhas de ônibus.

No presente trabalho foi proposto como modelo a utilização do famoso, inovador e sofrido sistema de transporte de Curitiba com suas futurísticas estações tubo. Dentre tantas possíveis conexões, qual o menor caminho e o menor número de conexões que podem ser feitas entre dois tubos do sistema integrado?

2. Métodos e Discussões

Utilizou-se a linguagem C e o compilador GCC para a elaboração de um programa que recebe uma listagem de dados que consistem no ponto inicial, final e as rotas dos ônibus.

Toma-se o custo de percorrimento como constante entre cada aresta da estrutura, o que é especialmente ideal ao considerar as voltas e desvios de algumas linhas de ligeirinhos. Justamente esta consideração é a que promove o uso do algoritmo de busca em largura, pois a solução encontrada será sempre a melhor [3], além de ser mais adequada para grafos menores [2].

Aproveitaram-se as funções da biblioteca fornecida pela especificação do trabalho, sendo que o esforço de implementação girou mais sobre as funções `caminho_minimo_tubos` e `caminho_minimo_linhas`.

Uma forma conveniente de tratar este conjunto de dados é através da construção de uma lista de adjacência [2] para então empregar a busca. Esta busca funciona de modo exastivo examinando todas as possibilidades de caminho nível a nível [1].

busca em largura (Início , Alvo)
  entra (Fila, Início)
  enquanto (a Fila não for vazia)
	Nó := sai (Fila)
     se (Nó = Alvo)
	retorna Nó
     para cada (Filho em Expande(Nó))
	 se (não visitado(Filho))
	        marca como visitado (Filho)
	        entra (Fila, Filho)

Já para o menor número de conexões de um ponto a outro empregou-se um algoritmo de cálculo do fecho transitivo. Novamente faz-se um processo exaustivo que detecta todos os vértices que podem ser alcançados a partir do vértice de origem, e os percorre de acordo com a função já utilizada anteriormente.
Retorna-se então a menor rota que passa pelo menor número de trocas.

Como o trabalho deve utilizar a função de escrita de lista já proposta, foi feita uma segunda função para inserção de elementos na lista, `insere_final`. Esta função extra percorre toda a lista no ato da inserção para viabilizar a utilização da `escreve_caminho`, colocando os elementos na ordem devida.

3. Conclusão:

O algoritmo de busca em largura mostra-se eficiente para a tarefa de encontrar o menor número de linhas e tubos entre dois pontos de Curitiba. Suposições ideais são feitas para simplificar o processo e, dependendo da cisrcusntância, é empregado o encontro do fecho transitivo através de `calcula_fecho`.

O que comumente é feito em distâncias reais é a conversão das distâncias do grafo em valores unitários, sempre iguais, e desta maneira pode-se empregar o algoritmo de busca em largura de maneira eficiente e uniforme para encontrar o menor caminho [7].

Embora talvez para uma aproximação real este algoritmo possa não ser o mais adequado, a circunstância é válida devido ao exercício de trabalhar com buscas em árvores de dados, servindo também de uma introdução para a ampliação de conceitos de busca em grafos.

Código fonte: Download.

Referências:

[1] Wikipedia: Breadth-first search - Acessado em 06/12/09
[2] SEDGEWICK, Robert - Algorithms in C
[3] Prof. Paulo Feofiloff: Grafos: Busca em largura - Acessado em 06/12/09
[4] Prof. Paulo Feofiloff: Algoritmos para grafos: listas de adjacência - Acessado em 06/12/09
[5] INF-UFSC: Busca em grafos - Acessado em 06/12/09
[6] Wikipedia: Floyd–Warshall algorithm
[7] Wikipedia: Uniform-cost search

Waipapa Pt e Jack’s Blowhole

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

Invercagill e Bluff

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

Contorcionismo Pelas Fendas de Clifden Caves

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

A Grandeza de Milford Sound

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

Fiordland, Te Anau e Henry Creek

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

Quatro Dias em Queenstown

Este artigo é parte da série Diários da Nova Zelândia

Artigos Relacionados

Doa-se cachorrinho: Joaquim Ferdinando

Artigos Relacionados

Substituição de Trechos em Strings com C

Artigos Relacionados

Problema das Probabilidades de Coincidência de Aniversários

Artigos Relacionados

Busca em Largura nos Tubos de Ligeirinho de Curitiba

Artigos Relacionados