Turmas - 1º Semestre de 2025
Turmas
1º Semestre de 2025

(Poscomp, 2011) Observe a função recursiva a seguir, desenvolvida na máquina genérica.

função xpto(n)
  se (n == 0)
    então retornar 0;
    senão retornar n * 2 - 1 + xpto(n - 1);
  fim se
fim função

Considerando-se que essa função sempre será chamada com variável n contendo inteiros positivos, o seu valor de retorno será:

a. O fatorial do valor armazenado em n.

b. O valor armazenado em n elevado ao quadrado.

c. O somatório dos n primeiros números inteiros positivos.

d. O somatório dos n primeiros números pares positivos.

e. 2 elevado ao valor armazenado em n.

Considere o programa monolítico, utilizando instruções rotuladas, sobre a máquina 2_REG, apresentado a seguir.

R01: Se a_zero então vá_para R00 senão vá_para R02;
R02: Faça adicionar_b vá_para R03;
R03: Faça subtrair_a vá_para R04;
R04: Se a_zero então vá_para R10 senão vá_para R05;
R05: Faça adicionar_b vá_para R06;
R06: Faça subtrair_a vá_para R07;
R07: Se a_zero então vá_para R11 senão vá_para R08;
R08: Faça adicionar_b vá_para R09;
R09: Faça subtrair_a vá_para R01;
R10: Faça adicionar_b vá_para R11;
R11: Faça adicionar_b vá_para R00;

Analise as seguintes assertivas sobre o programa apresentado.

1. Caso a entrada fornecida seja 4 a saída será 5.
2. Caso a entrada fornecida seja 5 a saída será 6.
3. Caso a entrada fornecida seja 6 a saída será 8.
4. Caso a entrada fornecida seja 7 a saída será 9.

Quais das assertivas apresentadas estão corretas?

a. apenas as assertivas I e II.

b. apenas as assertivas I e III.

c. apenas as assertivas II e III.

d. apenas as assertivas II e IV.

e. apenas as assertivas III e IV.

Desenvolver um programa monolítico, utilizando instruções rotuladas, sobre uma máquina genérica, que converta o número decimal fornecido pelo usuário em um número octal. Caso o usuário forneça um valor inválido para o número decimal (valor negativo), o programa deverá apresentar uma mensagem de erro.

R01: Faça ler(decimal) vá_para R02;
R02: Se (decimal < 0) então vá_para R03 senão vá_para R04;
R03: Faça escrever(erro) vá_para R00;
R04: Faça octal = 0 vá_para R05;
R05: Faça base = 1 vá_para R06;
R06: Se (decimal > 0) então vá_para R07 senão vá_para R12;
R07: Faça resto = decimal % 8 vá_para R08;
R08: Se (resto != 0) então vá_para R09 senão vá_para R10;
R09: Faça octal = octal + (resto * base) vá_para R10;
R10: Faça decimal = decimal / 8 vá_para R11;
R11: Faça base = base * 10 vá_para R06;
R12: Faça escrever(octal) vá_para R00;

Um programa monolítico é estruturado usando desvios condicionais e incondicionais, não fazendo uso explícito de mecanismos auxiliares de programação que permitam uma melhor estruturação do controle, como iteração, subdivisão e recursão, de modo que a lógica é distribuída por todo o bloco (monólito) que constitui o programa. Um programa recursivo é estruturado usando rotinas recursivas, permitindo uma estruturação hierárquica do programa e possibilitando níveis diferenciados de abstração. Traduza o programa recursivo apresentado a seguir em um programa monolítico, utilizando fluxograma, e simplifique, se possível.

função principal()
  serie1();
fim função

função serie1()
  F;
  se (T1)
    então serie2();
    senão serie1();
  fim se
fim função

função serie2()
  G;
  se (T2)
    então serie1();
    senão retornar;
  fim se
fim função

Computação é a sequencia de estados que representa a execução de um programa numa certa máquina. Considerando o programa monolítico, utilizando instruções rotuladas, sobre a máquina 4_REG apresentado a seguir, qual das computações corresponde a execução do programa, caso a entrada fornecida pelo usuário seja 2 unidades?

R01: Se nilA então vá_para R00 senão vá_para R02;
R02: Faça decA vá_para R03;
R03: Faça incB vá_para R04;
R04: Faça incD vá_para R05;
R05: Se nilA então vá_para R06 senão vá_para R02;
R06: Se nilB então vá_para R00 senão vá_para R07;
R07: Faça decB vá_para R08;
R08: Se nilB então vá_para R16 senão vá_para R09;
R09: Faça decB vá_para R10;
R10: Se nilB então vá_para R15 senão vá_para R11;
R11: Faça decB vá_para R12;
R12: Se nilB então vá_para R14 senão vá_para R13;
R13: Faça decB vá_para R06;
R14: Faça incD vá_para R15;
R15: Faça incD vá_para R16;
R16: Faça incD vá_para R00;

(R01, (2, 0, 0, 0))
(R02, (1, 0, 0, 0))
(R03, (1, 1, 0, 0))
(R04, (1, 1, 0, 1))
(R05, (1, 1, 0, 1))
(R02, (0, 1, 0, 1))
(R03, (0, 2, 0, 1))
(R04, (0, 2, 0, 2))
(R05, (0, 2, 0, 2))
(R06, (0, 2, 0, 2))
(R07, (0, 1, 0, 2))
(R08, (0, 1, 0, 2))
(R09, (0, 0, 0, 2))
(R10, (0, 0, 0, 2))
(R15, (0, 0, 0, 3))
(R16, (0, 0, 0, 4))
(R00, (0, 0, 0, 4))

(R01, (2, 0, 0, 0))
(R02, (1, 0, 0, 0))
(R03, (1, 0, 0, 0))
(R04, (1, 1, 0, 0))
(R05, (1, 1, 0, 1))
(R02, (0, 1, 0, 1))
(R03, (0, 1, 0, 1))
(R04, (0, 2, 0, 1))
(R05, (0, 2, 0, 2))
(R06, (0, 2, 0, 2))
(R07, (0, 1, 0, 2))
(R08, (0, 1, 0, 2))
(R09, (0, 0, 0, 2))
(R10, (0, 0, 0, 2))
(R15, (0, 0, 0, 2))
(R16, (0, 0, 0, 3))
(R00, (0, 0, 0, 4))

(R01, (2, 0, 0, 0))
(R02, (2, 0, 0, 0))
(R03, (1, 0, 0, 0))
(R04, (1, 1, 0, 0))
(R05, (1, 1, 0, 1))
(R02, (1, 1, 0, 1))
(R03, (0, 1, 0, 1))
(R04, (0, 2, 0, 1))
(R05, (0, 2, 0, 2))
(R06, (0, 2, 0, 2))
(R07, (0, 2, 0, 2))
(R08, (0, 1, 0, 2))
(R09, (0, 1, 0, 2))
(R10, (0, 0, 0, 2))
(R15, (0, 0, 0, 2))
(R16, (0, 0, 0, 3))
(R00, (0, 0, 0, 4))

(R01, (2, 0, 0, 0))
(R02, (2, 0, 0, 0))
(R03, (1, 1, 0, 0))
(R04, (1, 1, 0, 1))
(R05, (1, 1, 0, 1))
(R02, (1, 1, 0, 1))
(R03, (0, 2, 0, 1))
(R04, (0, 2, 0, 2))
(R05, (0, 2, 0, 2))
(R06, (0, 2, 0, 2))
(R07, (0, 2, 0, 2))
(R08, (0, 1, 0, 2))
(R09, (0, 1, 0, 2))
(R10, (0, 0, 0, 2))
(R15, (0, 0, 0, 3))
(R16, (0, 0, 0, 4))
(R00, (0, 0, 0, 4))

(R01, (2, 0, 0, 0))
(R02, (2, 0, 0, 0))
(R03, (2, 1, 0, 0))
(R04, (2, 1, 0, 1))
(R05, (1, 1, 0, 1))
(R02, (1, 1, 0, 1))
(R03, (1, 2, 0, 1))
(R04, (1, 2, 0, 2))
(R05, (0, 2, 0, 2))
(R06, (0, 2, 0, 2))
(R07, (0, 2, 0, 2))
(R08, (0, 1, 0, 2))
(R09, (0, 1, 0, 2))
(R10, (0, 0, 0, 2))
(R15, (0, 0, 0, 2))
(R16, (0, 0, 0, 3))
(R00, (0, 0, 0, 4))

Considerando que diferentes computadores podem ter diferentes arquiteturas e que os diversos tipos de linguagens de programação aparecem em abundância, a formalização dos conceitos de programa e de máquina não são baseadas em qualquer linguagem ou computador real. Assim, suas características essenciais são descritas em modelos matemáticos simples, permitindo um rápido entendimento de suas semânticas e facilitando a demonstração de resultados. Considerando esse contexto, avalie as asserções a seguir.

1. Um programa P é um programa para uma máquina M, se M possuir funções de interpretação de todas as operações e testes contidos em P.
2. Um programa P é um conjunto de operações e testes cuja execução é sequenciada no tempo através de alguma estrutura de controle, que pode ser iterativa, monolítica ou recursiva.
3. Cada identificador de operação e de teste interpretado pela máquina M, deve ser associado a uma transformação na estrutura de memória.
4. Identificadores de operação e de teste interpretados pela máquina M podem estar associados a mais de uma função.

Quais das assertivas apresentadas estão corretas?

a. apenas as assertivas I e II.

b. apenas as assertivas I e III.

c. apenas as assertivas II e III.

d. apenas as assertivas II e IV.

e. apenas as assertivas III e IV.

Desenvolver um programa recursivo, sobre uma máquina genérica, que indique se o número fornecido pelo usuário é um número perfeito. Um número é considerado perfeito se a soma de seus divisores próprios é igual ao próprio número, como por exemplo o número 6, cuja soma de seus divisores próprios (1 + 2 + 3) é igual a 6. Caso o número seja considerado perfeito, o programa deverá retornar 1, caso contrário, deverá retornar 0. Caso o número fornecido pelo usuário seja menor do que 2, o programa deverá retornar -1.

função perfeito(número, contador)
  se (contador < número) então
    resto = número % contador;
    se (resto == 0)
      então retornar contador + perfeito(número, contador + 1);
      senão retornar perfeito(número, contador + 1);
    fim se
  senão
    retornar 0;
  fim se
fim função

função principal()
  ler(número);
  se (número > 1) então
    se (número == perfeito(número, 1))
      então escrever(1);
      senão escrever(0);
    fim se
  senão
    escrever(-1);
  fim se
fim função

Desenvolver um programa iterativo, sobre uma máquina genérica, que apresente o valor de S, dado pela fórmula:

S = N! / (P! * (N - P)!)

O valor de N e P serão fornecidos pelo usuário, devendo ser números inteiros e positivos, sendo o primeiro (N) sempre maior que o segundo (P).

Caso o usuário forneça valores inválidos para N ou P, o programa deverá apresentar uma mensagem de erro.

ler(n);
se (n > 0) então
  ler(p);
  se (p > 0) então
    se (n > p) então
      dif = n - p;
      nFat = 1;
      enquanto (n > 1) faça
        nFat = nFat * n;
        n = n - 1;
      fim enquanto
      pFat = 1;
      enquanto (p > 1) faça
        pFat = pFat * p;
        p = p - 1;
      fim enquanto
      difFat = 1;
      enquanto (dif > 1) faça
        difFat = difFat * dif;
        dif = dif - 1;
      fim enquanto
      s = nFat / (pFat * difFat);
      escrever(s);
    senão
      escrever(erro);
    fim se
  senão
    escrever(erro);
  fim se
senão
  escrever(erro);
fim se