Resolução de Problemas - Canibais e Missionários

Afluentes: Inteligência Artificial

Estrutura de Dados

Estrutura de Dados do problema dos Canibais e Missionários

LadoEsquerdo (
	Canibais = inteiro
	Missionarios = inteiro
	Canoa = booleano
)

Na forma de Vetor:

(C, M, J)
(3, 3, T)

Observações:

• C = Canibais
• M = Missinários
• J = Jangada (não deu pra colocar C de Canoa)
  • T (ou True), a canoa está do lado esquerdo, se do lado direito, então F (False)
• Para saber como está do lado direito, basta calcular:
  • C2 = 3 - C
  • M2 = 3 - M
  • e J = F

Restrições

• Max2 - Máximo de passageiros na canoa é 2 pessoas
• !C>M - Nao pode ter mais canibais que missionários
• 1P - Mínimo de passageiros numa canoa é 1 pessoa

Regras / Métodos

• 1M-AB - Transportar 1 Missionario de A para B
• 2M-AB - Transportar 2 Missionarios de A para B
• 1C-AB - Transportar 1 Canibal de A para B
• 2C AB - Transportar 2 Canibais de A para B
• CM-AB - Transportar 1 Canibal e 1 Miss. de A para B
• 1M-BA - Transportar 1 Missionario de B para A
• 2M-BA - Transportar 2 Missionarios de B para A
• 1C-BA - Transportar 1 Canibal de B para A
• 2C-BA - Transportar 2 Canibais de B para A
• CM-BA - Transportar 1 Canibal e 1 Miss. de B para A

Teste de Mesa e Estados

0. (3, 3, 1, 0, 0, 0) - CM-AB
1. (2, 2, 0, 1, 1, 1) - 1M-BA
2. (2, 3, 1, 1, 0, 0) - 2C-AB
3. (0, 3, 0, 3, 0, 1) - 1C-BA
4. (1, 3, 1, 2, 0, 0) - 2M-AB
5. (1, 1, 0, 2, 2, 1) - CM-BA
6. (2, 2, 1, 1, 1, 0) - 2M-AB
7. (2, 0, 0, 1, 3, 1) - 1C-BA
8. (3, 0, 1, 0, 3, 0) - 2C-AB
9. (1, 0, 0, 2, 3, 1) - 1C-BA
10.(2, 0, 1, 1, 3, 0) - 2C-AB
11.(0, 0, 0, 3, 3, 1)

Algoritmo

Principal

Inicio
	Enquanto Não TERMINOU Fazer
		Operação = LerDoTeclado
		Se VALIDA(Operacao) Entao
			Se Operacao == 1M-AB Então
				LadoA.Missionario--
				LadoB.Missionario++
				LadoA.Canoa = Falso
				LadoB.Canoa = Verdadeiro
			Senão
				... // Demais operações
			Fim Se
		Fim Se
	Fim Enquanto
Fim

TERMINOU

Inicio
	Se (LadoB.Canibais == 3) e (LadoB.Missionarios == 3) Então
		Retorna Verdadeiro
	Senão
		Retorna Falso
	Fim Se
Fim

VALIDA

Inicio (operação)
	Se (operacao == 1M-AB) Então
		Se LadoA.Missionarios == 0 Então
			Retorna Falso
		Fim Se
		Se (LadoA.Missionarios - 1 < LadoA.Canibais) Então
			Retorna Falso
		Fim Se
	Senão
		... // Demais Operações
	Fim Se
	Retorna Verdadeiro
Fim

Programa

Desenvolver um programa com base na Estrutura de Dados definida e algoritmos apresentados.