ListaExercícioRecursão

Prévia do material em texto

<p>1 ============================================</p><p>2 LISTA DE EXERCÍCIOS RECURSIVIDADE 16/10/2023</p><p>3 ============================================</p><p>4</p><p>5 1. Dentro da programação, no que diz respeito à recursividade, marcar C para as</p><p>afirmativas Certas, E para as Erradas e, após, assinalar a alternativa que</p><p>6 apresenta a sequência CORRETA:</p><p>7</p><p>8 (_) Nem sempre a natureza recursiva do problema garante que um algoritmo recursivo</p><p>seja a melhor opção para resolvê-lo. O algoritmo recursivo para obter a sequência de</p><p>Fibonacci é um ótimo exemplo disso.</p><p>9 (_) Em programação, a recursividade é um mecanismo útil e poderoso que permite a uma</p><p>função chamar a si mesma direta ou indiretamente, ou seja, uma função é dita</p><p>recursiva se ela contém pelo menos uma chamada explícita ou implícita a si própria.</p><p>10 (_) Por usarem moderadamente a pilha, o que requer alocações e desalocações de</p><p>memória, os algoritmos recursivos tendem a ser mais rápidos que os equivalentes</p><p>iterativos, e também são mais fáceis de ser depurados durante a fase de</p><p>desenvolvimento.</p><p>11</p><p>12 A E - C - E.</p><p>13 B C - E - C.</p><p>14 C C - C - E.</p><p>15 D E - E - C.</p><p>16 E C - C - C.</p><p>17</p><p>18 2. Analise o código abaixo escrito em C.</p><p>19</p><p>20 int main() {</p><p>21 int a = 0;</p><p>22 while(a < 100) {</p><p>23 if((a % 2) == 0) {</p><p>24 a++;</p><p>25 }</p><p>26 else {</p><p>27 a = a + 3;</p><p>28 }</p><p>29 }</p><p>30 return</p><p>31 }</p><p>32</p><p>33 Assinale, a seguir, um conceito ou estrutura de programação que NÃO foi utilizado no</p><p>código.</p><p>34</p><p>35 A Variável.</p><p>36 B Recursividade.</p><p>37 C Estrutura condicional.</p><p>38 D Estrutura de repetição.</p><p>39</p><p>40 3. Considere a seguinte função f, programada recursivamente em linguagem C:</p><p>41</p><p>42 int f(int m, int n) {</p><p>43 if (m < n)</p><p>44 return 0;</p><p>45 else</p><p>46 return 1 + f(m - n, n);</p><p>47 }</p><p>48</p><p>49 Qual função matemática de inteiros positivos m e n é implementada por f ?</p><p>50</p><p>51 A Quociente da divisão de m por n.</p><p>52 B Resto da divisão de m por n.</p><p>53 C Multiplicação de m por n.</p><p>54 D Adição de m com n.</p><p>55 E Potenciação com base m e expoente n.</p><p>56</p><p>57</p><p>58 4. Uma grande vantagem da utilização da recursividade é o baixo consumo de memória.</p><p>59 C Certo</p><p>60 E Errado</p><p>61</p><p>62 5. Recursividade é o mecanismo de programação no qual uma definição de função</p><p>refere-se à própria função sendo definida. Em resumo, pode ser definida como uma</p><p>função que chama a si mesma, de forma direta ou indireta. Qual a saída que o</p><p>pseudocódigo abaixo produzirá?</p><p>63</p><p>64 funcao nomedafuncao(n)</p><p>65 __inicio</p><p>66 ______ se (n == 0) então faça</p><p>67 __________inicio</p><p>68 ______________ retorne 1;</p><p>69 ___________ fim</p><p>70 _____senão</p><p>71 ________ inicio</p><p>72 ___________retorne n*nomedafuncao(n-1);</p><p>73 ________fim</p><p>74 )))fim</p><p>75</p><p>76 nomedafuncao(5);</p><p>77</p><p>78 A 0</p><p>79 B 1</p><p>80 C 24</p><p>81 D 120</p><p>82</p><p>83 6. Considere a função abaixo para num=10.</p><p>84</p><p>85 Quantas chamadas recursivas ocorrem, desconsiderando a primeira chamada da função?</p><p>86</p><p>87 int fat(int num) {</p><p>88 if (num==1) return num;</p><p>89 else return(num * fat(num-1));</p><p>90 }</p><p>91</p><p>92 A 8</p><p>93 B 9</p><p>94 C 10</p><p>95 D 11</p><p>96</p><p>97 7. Observe o algoritmo abaixo, que se refere a uma função recursiva.</p><p>98</p><p>99 algoritmo "ALG777"</p><p>100</p><p>101 var N, R, K : inteiro</p><p>102 W: logico</p><p>103</p><p>104 funcao F(M:inteiro):inteiro</p><p>105</p><p>106 inicio</p><p>107 K <- K + 1</p><p>108 se M < 2 entao</p><p>109</p><p>110 retorne 2</p><p>111 senao</p><p>112 retorne M * F(M-1)</p><p>113 fimse</p><p>114 fimfuncao</p><p>115</p><p>116 inicio</p><p>117 k <- 0</p><p>118 se K mod 2 = 1 entao</p><p>119 W <- FALSO</p><p>120 N <- 3</p><p>121 senao</p><p>122 W <- VERDADEIRO</p><p>123 N < - 4</p><p>124 fimse</p><p>125 escreval(W,F(N):8,K:4)</p><p>126 fimalgoritmo</p><p>127</p><p>128 Após a execução, os valores de W, F(N) e K serão, respectivamente:</p><p>129</p><p>130 A FALSO, 12 e 3.</p><p>131 B FALSO, 48 e 4.</p><p>132 C VERDADEIRO, 12 e 4.</p><p>133 D VERDADEIRO,48 e 4.</p><p>134 E VERDADEIRO, 12 e 3.</p><p>135</p><p>136 8. Quando uma função é definida em termos de si mesma fica caracterizado o uso</p><p>137 A da iteratividade.</p><p>138 B da recursividade.</p><p>139 C da interatividade.</p><p>140 D do acesso direto a Banco de Dados.</p><p>141 E de DLLs.</p><p>142</p><p>143 9. Qual é o problema com a implementação recursiva da sequência de Fibonacci a seguir?</p><p>144</p><p>145 #include <stdio.h></p><p>146</p><p>147 int fibonacci(int n) {</p><p>148 return fibonacci(n - 1) + fibonacci(n - 2);</p><p>149 }</p><p>150</p><p>151 int main() {</p><p>152 int n;</p><p>153 printf("Digite o valor de n para calcular o termo de Fibonacci: ");</p><p>154 scanf("%d", &n);</p><p>155</p><p>156 if (n < 0) {</p><p>157 printf("O número de Fibonacci não está definido para valores negativos.\n");</p><p>158 } else {</p><p>159 int result = fibonacci(n);</p><p>160 printf("O %do termo de Fibonacci é: %d\n", n, result);</p><p>161 }</p><p>162</p><p>163 return 0;</p><p>164 }</p><p>165</p><p>166 A) A implementação não calcula a sequência de Fibonacci.</p><p>167 B) A implementação entra em um loop infinito e causa um estouro de pilha quando n é</p><p>maior que 1.</p><p>168 C) A implementação calcula a sequência de Fibonacci corretamente para todos os</p><p>valores de n.</p><p>169 D) A implementação não compila devido a erros de sintaxe.</p><p>170</p><p>171 10. Qual é o propósito principal do código abaixo, que utiliza a função hanoi para</p><p>resolver o problema da Torre de Hanói com 4 discos?</p><p>172</p><p>173 #include <stdio.h></p><p>174</p><p>175 void hanoi(int n, char origem, char auxiliar, char destino) {</p><p>176 if (n == 1) {</p><p>177 printf("Mova o disco 1 de %c para %c\n", origem, destino);</p><p>178 return;</p><p>179 }</p><p>180 hanoi(n - 1, origem, destino, auxiliar);</p><p>181 printf("Mova o disco %d de %c para %c\n", n, origem, destino);</p><p>182 hanoi(n - 1, auxiliar, origem, destino);</p><p>183 }</p><p>184</p><p>185 int main() {</p><p>186 int n = 4; // Número de discos</p><p>187 hanoi(n, 'A', 'B', 'C'); // Chamada à função para resolver o problema</p><p>188 return 0;</p><p>189 }</p><p>190</p><p>191 A) Calcular o número total de movimentos necessários para resolver o problema.</p><p>192 B) Imprimir os passos para mover 4 discos da Torre A para a Torre C.</p><p>193 C) Classificar os discos em ordem crescente com base em seus tamanhos.</p><p>194 D) Criar uma matriz de discos em C e inseri-los em uma pilha.</p><p>195</p><p>196 11. Proceda com o download deste código</p><p>https://github.com/leoneDuarte/torre_hanoi/tree/master.</p><p>197 Faça a execução passo a passo do código do exercício 10. Anote os passos.</p><p>198 Agora, aplique-os no código do download.</p><p>199</p><p>200</p><p>201</p>