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

• 1MD - Transportar 1 Missionário para a direita
• 2MD - Transportar 2 Missionários para a direita
• 1CD - Transportar 1 Canibal para a direita
• 2CD - Transportar 2 Canibais para a direita
• CMD - Transportar 1 Canibal e 1 Missionário para a direita
• 1ME - Transportar 1 Missionário para a esquerda
• 2ME - Transportar 2 Missionários para a esquerda
• 1CE - Transportar 1 Canibal para a esquerda
• 2CE - Transportar 2 Canibais para a esquerda
• CME - Transportar 1 Canibal e 1 Missionário para a esquerda

Teste de Mesa e Estados

0. (3, 3, 1, 0, 0, 0) - CMD
1. (2, 2, 0, 1, 1, 1) - 1ME
2. (2, 3, 1, 1, 0, 0) - 2CD
3. (0, 3, 0, 3, 0, 1) - 1CE
4. (1, 3, 1, 2, 0, 0) - 2MD
5. (1, 1, 0, 2, 2, 1) - CME
6. (2, 2, 1, 1, 1, 0) - 2MD
7. (2, 0, 0, 1, 3, 1) - 1CE
8. (3, 0, 1, 0, 3, 0) - 2CD
9. (1, 0, 0, 2, 3, 1) - 1CE
10.(2, 0, 1, 1, 3, 0) - 2CD
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.