Solução Pilha de Dados – Noic
Browse: Home / Problemas da Semana / Informática / Avançado Informática - Semana 27 / Solução Pilha de Dados
Solução Pilha de Dados
O problema é uma função recursiva muito simples. O estado da recursão será a posição do dado da pilha que estamos olhando (onde o topo é 1) e e qual a face dele que está virada para cima ( ), e ela retornará o maior valor de um lado da sub-pilha formada por este dados e os abaixo dele. Sabendo a face de cima de um dado, sabemos qual a de baixo pelo desenho. Chamaremos faces A, B, ..., F de faces 1, 2, ..., 6, onde guarda qual o número da face no dado na posição .
Para um estado, percorreremos todas as faces que não são topo ou cima e usaremos a melhor para o lado da pilha que terá valor máximo. Chamaremos este valor de . Se o dado olhado for o último, retornamos . Olharemos o próximo dado, procurando qual de duas faces tem o mesmo valor da face de baixo do dado (seja ela ), e chamaremos a recursão agora com esta sendo a face de cima ( ).
No final, chamamos a recursão para cada uma das possíveis faces de cima do primeiro dado. Note que a melhor resposta da recursão para o primeiro dado soluciona o problema. Segue o código para melhor entendimento: