Elementos de Programação
Amílcar Sernadas, Cristina Sernadas e Jaime Ramos

Programação Imperativa

Nos exercícios que se seguem, as únicas funções primitivas sobre listas que deve utilizar são: First, Last, Rest, Append, Prepend, Length, [[.]] e{}.
Cada exercício sobre listas pode (e deve) ser resolvido de várias maneiras:
 - recorrendo à função Length para determinar a guarda do While;
 - utilizando variável de progresso em lista;
 - ...

Defina imperativamente em Mathematica as funções abaixo descritas.

somaNat: recebe um número natural n e devolve a soma de todos os naturais até n.

somaNat[6]

quadrados: recebe um número natural n e devolve a lista dos quadrados perfeitos até n.

quadrados[6]

quadradosinv: recebe um número natural n e devolve a lista dos quadrados perfeitos até n, por ordem decrescente.

quadradosinv[6]

prodLista: recebe uma lista de inteiros e devolve o produto dos seus elementos.

prodLista[{1,2,3,4}]

contemPrimoQ:recebe uma lista de naturais l e devolve True sse l contém pelo menos um número primo.

contemPrimoQ[{1,2,3,4}]

contemPrimoQ[{4,6,8,10}]

pertenceQ: recebe uma lista de inteiros l e um inteiro k e devolve True sse k ocorre em l.

pertenceQ[{3,4,5,6,7,5},8]

pertenceQ[{3,4,5,6,7,5},7]

junta: recebe duas listas e devolve a sua concatenação.

junta[{1,2,3},{9,8,7}]

indicesPar: recebe uma lista de inteiros l e devolve a lista dos elementos de l em posições pares.

indicesPar[{2,3,4,4,5}]

retiraPares: recebe uma lista de inteiros l e devolve a lista dos elementos pares de l.

retiraPares[{2,3,4,4,5}]

retiraNeg: recebe uma lista de inteiros l e devolve a lista resultante de retirar todos os números negativos de l.

retiraNeg[{3,-2,1,-7}]

supremo: recebe uma lista de inteiros e devolve o seu supremo.
(Note que o supremo do conjunto vazio é -∞.)

supremo[{}]

supremo[{1,-3,6,-27}]

posicoesMaximo: recebe uma lista de inteiros e devolve a lista das posições onde ocorre o maior elemento.

posicoesMaximo[{2,7,6,5,7}]

conta: recebe como argumentos uma lista de inteiros l e um inteiro k e devolve o número de vezes que k ocorre em l.

conta[{1,2,3,1,2,3},2]

lposicoes: recebe como argumentos uma lista de inteiros l e um inteiro k e devolve a lista das posições em que k ocorre em l.

lposicoes[{1,2,3,1,2,3},2]

caracteristicaPrimos: recebe uma lista de naturais l e devolve uma lista com True nas posições onde ocorre em l um número primo e False nas outras.

caracteristicaPrimos[{1,2,3,4,5,6,7,8,9}]

apaga1: recebe uma lista l e um número inteiro k e devolve a lista que resulta de se apagar de l a primeira ocorrência de k (caso exista).

apaga1[{1,2,3,2,1,2},1]

apaga: recebe uma lista l e um número inteiro k e devolve a lista que resulta de se apagar de l todas as ocorrências de k.

apaga[{1,2,3,2,1,2},1]

seleccao: recebe uma lista e um predicado e devolve a lista dos elementos que verificam esse predicado.

seleccao[{1,2,3,4,5,6},PrimeQ]

mapeia: recebe uma função f e uma lista l e devolve a lista dos resultados de aplicar f aos elementos de l.

mapeia[Function[x,2^x],{3,5,7,8}]

mapeia[Function[x,EvenQ[x]],{3,5,7,8}]

primalg: recebe um inteiro k e devolve o primeiro algarismo de k.

primalg[2]

primalg[6535]

inverteLista: recebe uma lista e devolve a mesma lista mas invertida. 
Apresente duas soluções para a referida função: uma usando recursão à esquerda e outra usando recursão à direita.

inverteLista[{1,2,3,4}]

ligualQ: recebe duas listas e devolve True se as listas forem iguais e False caso contrário.

ligualQ[{1,2,3},{1,2,3}]

ligualQ[{1,2,3},{2,1,3}]

Os exercícios seguintes são de um nível de dificuldade mais elevado; caso considere necessário, utilize algumas das funções acima definidas.

permutacao: recebe duas listas l e w e devolve True se w for uma permutação de l e False caso contrário.

permutacao[{1,2,3},{2,1,3}]

permutacao[{1,2,3},{1,2,2,3}]

intercala: recebe duas listas l e w e devolve a lista resultante de intercalar os elementos de l e w.

intercala[{3,2,1},{5,6,7}]

intercala[{3,2,1},{4}]

intercala[{},{5,6,7}]

indPrimos: recebe uma lista de listas de inteiros l={l1,l2,...,lk} e devolve a lista w={w1,w2,...,wk}, em que wi é composta pelas posições dos números primos em li.

indprimos[{{1,2,3,4,5},{2,4,3,5},{4,6,8,9},{}}]

separaMult3e5: recebe uma lista de inteiros l e devolve um par formado por duas listas: a dos múltiplos de 5 que ocorrem em l e a dos múltiplos de 3 que ocorrem em l.

separaMult3e5[{1,2,3,4,5,9,15}]

potencia: recebe um dígito k (que não zero) e devolve o menor natural n tal que 2^n começa por k.

potencia[2]

potencia[3]

repete: recebe uma lista l e devolve uma lista em que o primeiro elemento de l aparece uma vez, o segundo elemento duas vezes, ... .

repete[{a,b,c}]

Ciclos encaixados

temPrimoQ: recebe uma lista de listas de inteiros e devolve True sse alguma das suas sublistas tem um número primo.

temprimoQ[{{4},{3},{1,4,6}}]

temprimoQ[{{4},{8},{1,4,6}}]

prodMatriz: recebe uma matriz e devolve o produto de todos os seus elementos.

prodMatriz[{{3,2,1},{2,1,2}}]

mediaColunasParesMatriz: recebe uma matriz e devolve a média dos elementos das colunas pares da matriz.

mediaColunasPares[{{1,2,3,6},{4,3,2,1},{1,6,7,6}}]

indPrimos: recebe uma lista de listas de inteiros {l1,l2,...,lk} e devolve a lista de listas {w1,w2,...,wk} em que cada wi contém as posições dos números primos em li.

indprimos[{{1,2,3,4,5},{2,4,3,5},{4,6,8,9},{}}]

transposta: recebe uma matriz e devolve a sua transposta.

transposta[{{1,2,3},{9,8,7},{5,7,9},{4,6,8}}]

Problemas

Defina uma função produtoMatrizes que recebe como argumentos duas matrizes e devolve a sua matriz produto.  Verifique que a dimensão das matrizes recebidas é tal que é possivel realizar o seu produto (se não o for, retorne uma mensagem de erro adequada).
Sugestão: use um procedimento auxiliar para multiplicar a linha de indice i de uma matriz pela coluna de indice j da outra matriz.

produtoMatrizes[{{2,3},{8,7},{6,2}},{{4,5},{1,9}}]

Considere o problema de calcular a área por baixo do gráfico duma função f (o integral de f) num intervalo [a,b].
Defina uma função aproximaIntegral que receba como argumentos a função f, os extremos do intervalo de integração e um parâmetro n e calcula uma aproximação do integral da função nesse intervalo.

A ideia básica consiste em dividir o intervalo [a,b] em n sub-intervalos consecutivos, com n suficientemente grande para se obter a aproximação desejada

		[a, b] = [(Subscript[x, 0]), (Subscript[x, 1])] ⋃ ... ⋃ [(Subscript[x, n-1]), (Subscript[x, n])]

e aproximar a função em cada um dos intervalos [(Subscript[x, i-1]), (Subscript[x, i])] por f((Subscript[x, i-1])).

Nestas condições, o valor do integral é aproximado por

		(∑_(i=1)^n)((Subscript[x, i]) -(Subscript[x, i-1]))f((Subscript[x, i])).

Escolhendo todos os intervalos com os mesmo comprimento

		d=((b-a)/n)
		
tem-se que (Subscript[x, i])= (Subscript[x, i-1]) + d, ou então, (Subscript[x, i])= a + i d, e chega-se a 

		(∑_(i=1)^n) d f(a+(i-1)d).
		
ou seja 
		d (∑_(i=1)^n) f(a+(i-1)d)

g=Function[x,(1+x)^-1];

aproximaIntegral[g,0,1.5,5]

aproximaIntegral[g,0,1.5,500000]

Defina uma função bisseccao que calcula uma raíz de uma equação não linear num intervalo [a,b] com aproximação pelo menos e, usando o método da bissecção a seguir descrito.

O Método da Bissecção é um método iterativo para encontrar raízes de funções baseado no Teorema do Valor Intermédio.  Pretende-se encontrar uma solução da equação f(x)=0, admitindo que f é contínua em [a,b] e que f(a)f(b)<0.

Tome-se (Subscript[a, 0])=a, (Subscript[b, 0])=b, (Subscript[I, 0])=[(Subscript[a, 0]),(Subscript[b, 0])] e repita-se iterativamente o seguinte processo.

Seja (Subscript[x, i])o ponto médio do intervalo (Subscript[I, i]).  Uma das três condições seguintes verifica-se:
1) f((Subscript[a, i]))f((Subscript[x, i]))<0, e existe uma raíz de f em [(Subscript[a, i]),(Subscript[x, i])];
2) f((Subscript[a, i]))f((Subscript[x, i]))>0, e existe uma raíz de f em [(Subscript[x, i]),(Subscript[b, i])];
3) f((Subscript[a, i]))f((Subscript[x, i]))=0, e (Subscript[x, i]) é uma raíz de f.

No terceiro caso, não é preciso fazer mais nada.  Nos outros dois casos, defina-se (Subscript[a, i+1])e (Subscript[b, i+1])como sendo (Subscript[a, i])e (Subscript[x, i])(primeiro caso) ou (Subscript[x, i])e (Subscript[b, i])(segundo caso), tome-se (Subscript[I, i+1])=[(Subscript[a, i+1]),(Subscript[b, i+1])] e repita-se o processo.

Aplicando este procedimento sucessivamente, é calculada uma sequência de intervalos (Subscript[I, 0])⊃(Subscript[I, 1])⊃(Subscript[I, 2])⊃... onde a raíz r∈(Subscript[I, k]) para todo o k.  O procedimento termina quando a amplitude do intervalo for menor do que o erro pretendido e.  Note que a amplitude do intervalo se reduz a metade a cada iteração.

f=Function[x,E^-x-Sin[x]];

bisseccao[f,0.25,0.75,0.000001]

Exercícios de Exame

Defina imperativamente as seguintes funções.

(Exame 21/01/2002 - Versão A) 
exame1 que recebendo como argumento uma matriz quadrada de números inteiros calcula a lista dos pares {i,j} tais que a soma da linha i é igual à soma da coluna j.
Sugestão: defina uma função auxiliar eqsum tal que eqsum[i,j] seja True no caso de a soma da linha i ser igual à soma da coluna j e False no caso contrário.

exame1[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 21/01/2002 - Versão B) 
exame2 que recebendo como argumento uma matriz quadrada de números inteiros calcula a lista dos números (2^i)*(3^j) tais que o produto da linha i é igual ao produto da coluna j. Sugestão: defina uma função auxiliar eqprod tal que eqprod[i,j] seja True se o produto da linha i for igual à soma da coluna j e False no caso contrário.

exame2[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 06/02/2002 - Versão A) 
exame3 que recebendo como argumento uma matriz de números inteiros calcula a lista dos pares {i,x} tais que a soma dos elementos da linha i é igual a x.
Sugestão: defina uma função auxiliar sum tal que sum[i] seja a soma da linha i.

exame3[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 06/02/2002 - Versão B) 
exame4 que recebendo como argumento uma matriz de números inteiros calcula a lista dos pares {j,y} tais que o produto dos elementos da coluna j é igual a y.
Sugestão: defina uma função auxiliar prod tal que prod[j] seja o produto da coluna j.

exame4[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 22/01/2003 - Versão A) 
triangularSuperiorQ que recebendo como argumento uma matriz quadrada de números inteiros determina se a matriz é triangular superior (isto é, todos os elementos abaixo da diagonal principal são nulos).

triangularSuperiorQ[{{3,4,5},{0,3,2},{0,0,4}}]

triangularSuperiorQ[{{3,4,5},{0,3,2},{0,3,4}}]

(Exame 22/01/2003 - Versão B) 
triangularInferiorQ que recebendo como argumento uma matriz quadrada de números inteiros determina se a matriz é triangular inferior (isto é, todos os elementos acima da diagonal principal são nulos).

triangularInferiorQ[{{3,0,0},{5,3,0},{2,3,4}}]

triangularInferiorQ[{{3,4,0},{5,3,0},{2,3,4}}]

(Exame 07/02/2003 - Versão Ax) 
exame5 que recebendo como argumento uma matriz quadrada de números inteiros calcula o produto de todos os elementos pares acima da diagonal principal.

exame5[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 07/02/2003 - Versão Ay) 
exame6 que recebendo como argumento uma matriz quadrada de números inteiros calcula a soma de todos os elementos ímpares acima da diagonal principal.

exame6[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 07/02/2003 - Versão Bx) 
exame7 que recebendo como argumento uma matriz quadrada de números inteiros calcula a soma de todos os elementos pares abaixo da diagonal principal.

exame7[{{3,4,5},{5,3,2},{2,3,4}}]

(Exame 07/02/2003 - Versão By) 
exame8 que recebendo como argumento uma matriz quadrada de números inteiros calcula o produto de todos os elementos ímpares abaixo da diagonal principal.

exame8[{{3,4,5},{5,3,2},{2,3,4}}]