Todos os exercícios nesta página têm o propósito de revisão dos conceitos de variáveis, laços (for e while), seleções (if, elif, else), funções (def e return) e listas.
Membros das turmas NA1 e NB{4,5} deverão submeter códigos em Python para todos os exercícios nesta página em um único arquivo .py via
Tidia
até 05/05 às 19h – sob a entrada E6.
Exercícios
(01)Produto Palindrômico Máximo.
Um inteiro não negativo é um palíndromo se sua sequência de dígitos (decimais) for a mesma quando lida da esquerda para a direita, e da direita para a esquerda.
O produto de dois inteiros $m,n\geq 0$ é palindrômico se $mn$ for um palíndromo.
Dado um inteiro $k\geq 1$, determine um produto palindrômico de valor máximo, em que $m$ e $n$ contém $k$ dígitos (decimais).
Exemplo: para $k=2$, temos que $91\,*\,99=9009$ é o maior produto palindrômico formado por números de $2$ dígitos.
Solução:
Observe que, dependendo do valor de $k$, pode não haver um palíndromo que é produto de dois valores em $[10^{k-1}..10^k-1]$.
Neste caso, devolvemos $-1$.
def is_palindrome (m: int) -> bool:
k, n = m = 0
while k > 0:
n = n * 10 + k % 10
k = k // 10
return m == n
def max_palindrome_prod (k: int) -> int:
beg, end, pal = 10**(k-1), 10**k-1, -1
for m in range (beg, end):
for n in range (i+1, end+1):
mn = m * n
if is_palindrome (mn) and pal < mn:
pal = mn
return pal
$\square$
(02)Caminhos em Reticulados.
Considere uma grade $2\times 2$. Partindo do canto superior esquerdo, com cada passo podendo ser dado uma posição à direita ou abaixo, existem $6$ rotas (caminhos distintos) até o canto inferior direito (veja figura).
Dado um inteiro $n\geq 0$, determine quantas rotas (como acima) existem em uma grade $n\times n$.
Solução:
O problema consiste em, dadas $2n$ possíveis direções, escolher $n$ que serão à direita. Em outras palavras, queremos
determinar o número de subconjuntos com $n$ elementos à partir de um conjunto de $2n$ elementos. A resposta é: $\binom{2n}{n}$.
from math import prod
def couting_paths (n: int) -> int:
return prod (range (n+1, 2*n+1)) // prod (range (1, n+1))
$\square$
(03)Segmento Máximo de Zeros.
Escreva uma função que recebe uma lista $A[0\,..n-1]$ de inteiros, calcula o comprimento $m$ do mais longo segmento de zeros em $A$, e devolve a tripla $(m,i,j)$,
em que $m=j-i$ e todos os elementos em $A[i\,..j-1]$ são iguais a zero.
Solução:
def longest_zero_segment (A: [int]) -> (int, int, int):
n = len (A)
i, j, k, l = n, n, 0, 0
while k < n:
while k < n and A[k] != 0: k += 1
l = k
while k < n and A[k] == 0: k += 1
if k-l > j-i:
i, j = l, k
return (j-i, i, j)
$\square$
(04)Problema de Josephus.
Imagine uma roda de $n$ pessoas. Suponha que as pessoas estão numeradas de $1$ a $n$ no sentido horário. Começando com a pessoa de número $1$, percorra a roda no sentido horário e elimine cada $m$-ésima pessoa enquanto a roda tiver duas ou mais pessoas. Escreva uma função que calcule o número do sobrevivente.
Exemplo: para $n=5$ e $m=3$, temos que
$$\langle 1,2,3,4,5\rangle
\quad\to\quad
\langle 1,2,4,5 \rangle
\quad\to\quad
\langle 2,4,5 \rangle
\quad\to\quad
\langle 2,4 \rangle
\quad\to\quad
\langle 4\rangle
$$
resultando no sobrevivente de número $4$.
Solução:
def josephus (n: int, m: int) -> int:
C, p = [i+1 for i in range(n)], 0
while len (C) > 1:
p = (p + m-1) % len (C)
del C[p]
return C[0]
$\square$
(05)Números Distintos.
Dada uma lista $A[0\,..n-1]$ de números inteiros, determine quantos números distintos existem em $A$.
Solução:
def distincts (A: [int]) -> int:
if (n := len (A)) == 0: return 0
A.sort()
j, m = 0, 1
for i in range (1, n):
if A[j] != A[i]:
j, m = i, m+1
return m
$\square$
(06)Número de Segmentos.
Escreva uma função que recebe duas listas $S[0\,..m-1]$ e $T[0\,..n-1]$, com $0\leq m\leq n$, e devolve o número
de ocorrências de $S$ como segmento em $T$. Lembre-se que $S$ ocorre como um segmento em $T$ se existe $0\leq k\leq n-m$
tal que $S[0\,..m-1] = T[k\,..n+k-1]$.
Por exemplo, se
$$
S = [0,1,0] \qquad\text{e}\qquad
T = [\underline{0,1,0},2,3,0,4,5,\underline{0,1,0},6,7,8,9,0,3,10,2,
\underline{0,1,\underline{0,}}\underline{1,0}],
$$
$S$ ocorre $4$ vezes como segmento em $T$.
Solução:
def naive_pattern_matching (S: [int], T: [int]) -> int:
c, m, n = 0, len (S), len (T)
for i in range(n-m+1):
j = 0
while j < m and S[j] == T[i+j]: j += 1
if j == m: c += 1
return c
O algoritmo acima claramente consome tempo $\Theta(nm)$. Para algoritmos mais avançados e melhores
que resolvem a mesma tarefa em tempo $O(n+m)$, procure pelos algoritmos \textsc{Knuth-Morris-Pratt}
e \textsc{Boyer-Moore}.
$\square$
(07)Sub-listas.
Uma sub-lista de uma lista $L$ é o que sobra depois que alguns dos elementos de $L$ são apagados. Por exemplo, $[12,13,10,3]$
é uma sub-lista de $[11,12,13,11,10,9,7,3,3]$, mas não de $[11,12,10,11,13,9,7,3,3].$ Escreva uma função (eficiente) que decide
se uma lista $A[0\,..m-1]$ é sub-lista de $L[0\,..n-1].$
Solução:
def is_sublist (A: [int], B: [int]) -> bool:
i, j, m, n = 0, 0, len (A), len (B)
while i < m and j < n:
if A[i] == B[j]: i+= 1
j += 1
return i == m
$\square$
(08)Ordenação Indireta.
Escreva uma função que recebe uma lista $A[0\,..n-1]$ de números reais positivos e devolve uma lista $B[0\,..n-1]$ de índices em $\{0,1,\ldots,n-1\}$ tal que
$$
A[B[0]] \leq A[B[1]] \leq A[B[2]] \leq \cdots \leq A[B[n-1]].
$$
Solução:
Vamos utilizar o algoritmo de ordenação por seleção (selection sort) por simplicidade.
def ind_selection_sort (A : [int]) -> [int]:
n = len (A)
B = list (range (n))
for i in range (n-1):
k = i
for j in range (i+1, n):
if A[B[j]] < A[B[k]]: k = j
B[i], B[k] = B[k], B[i]
return B
“See, if y’all haven’t the same feeling for this, I really don’t give a damn. If you ain’t feeling it, then dammit this ain’t for you!" (desconheço a autoria; agradeço a indicação)
