Os conceitos de recursão e iteração constituem, juntamente com as noções de composição seqüencial e seleção, as ferramentas fundamentais para construção de algoritmos e programas, a partir de um conjunto apropriado de operações ou comandos básicos. Esses dois conceitos são introduzidos neste capítulo, por meio de uma série de exemplos ilustrativos, de construção de programas para cálculo de operações aritméticas simples, tais como:
A solução de qualquer problema que envolva a realização de uma ou mais operações repetidas vezes pode ser expressa, no paradigma de programação imperativo, por meio de um comando de repetição (também chamado de comando iterativo, ou comando de iteração), ou usando funções com definições recursivas.
Definições recursivas de funções são baseadas na mesma idéia subjacente a um princípio de prova fundamental em matemática — o princípio da indução. A idéia é a de que a solução de um problema pode ser expressa da seguinte forma: primeiramente, definimos a solução desse problema para casos básicos; em seguida, definimos como resolver o problema para os demais casos, em termos da solução para casos mais simples que o original.
Considere por exemplo o problema de definir a multiplicação de dois números inteiros m e n, sendo n>0, em termos da operação de adição. O caso mais simples dessa operação é aquele no qual n=0: nesse caso, o resultado da operação é igual a 0, independentemente do valor de m. De acordo com a idéia exposta acima, precisamos agora pensar em como podemos expressar a solução desse problema no caso em que n>0, supondo que sabemos determinar sua solução para casos mais simples, que se aproximam do caso básico. Neste caso, podemos expressar o resultado de m × n em termos do resultado da operação, mais simples m × (n−1); ou seja, podemos definir m × n como sendo igual a m + (m × (n−1)), para n>0.
Ou seja, a operação de multiplicação pode então ser definida indutivamente pelas seguintes equações:
| m × n = | ⎛ ⎜ ⎝ | 0 se n=0, senão m + | ⎛ ⎝ | m × (n−1) | ⎞ ⎠ | ⎞ ⎟ ⎠ |
Uma maneira alternativa de pensar na solução desse problema seria pensar na operação de multiplicação m * n como a repetição, n vezes, da operação de adicionar m, isto é:
| m × n = (m + … + m)n vezes |
Raciocínio análogo pode ser usado para expressar a operação de exponenciação, com expoente inteiro não-negativo, em termos da operação de multiplicação.
O programa a seguir apresenta duas definições alternativas, na
linguagem C, para computar o resultado da multiplicação e da
exponenciação de dois números, dados como argumentos dessas
operações. As funções mult e exp são definidas
usando-se um comando de repetição. As funções multr e
expr são definidas usando-se chamadas à própria
função que está sendo definida, razão pela qual essas
definições são chamadas de recursivas.
Usamos a letra “r” adicionada como sufixo ao nome de uma função para indicar que se trata de uma versão recursiva da definição de uma função.
|
Como vimos na Seção 2.4, a execução de um
comando de repetição consiste na execução do corpo desse
comando repetidas vezes, até que a condição associada a esse
comando se torne falsa (caso isso nunca ocorra, a repetição
prossegue indefinidamente). Para entender melhor o significado desse
comando e, portanto, o comportamento das funções mult e
exp, consideramos seguir a execução de uma chamada à
função mult — por exemplo, mult(3,2).
Note que essas definições são usadas apenas com fins didáticos, para
explicar inicialmente definições recursivas e comandos de
repetição. Essas definições não têm utilidade prática pois existe, no
caso da multiplicação, o operador predefinido (*) e, no caso da
exponenciação, a função math.pow (cf. seção 3.9).
A execução de uma chamada de
função é iniciada, como vimos na Seção
2.5, com a avaliação dos argumentos a
serem passados à função: no exemplo acima, essa avaliação
fornece os valores representados pelos literais 3 e
2, do tipo int. Esses valores são atribuídos aos
parâmetros m e n, respectivamente, e o corpo da função
mult é então executado.
Depois da execução do corpo da função mult, os parâmetros, assim
como, possivelmente, variáveis declaradas internamente no corpo da
função, deixam de existir, isto é, são desalocados. Ou seja, o tempo de vida de parâmetros e variáveis declaradas localmente é
determinado pelo bloco correspondente à função.
A execução do corpo da função mult é iniciada com a
criação da variável r, à qual é atribuído
inicialmente o valor 0. Em seguida, o comando for é
executado.
O comando for é um comando de repetição (assim como o
comando while, introduzido na Seção 2.4). A
execução do comando for usado no corpo da função
mult consiste simplesmente em adicionar (o valor contido em)
m ao valor de r, a cada iteração, e armazenar o
resultado dessa adição em r. O número de iterações
executadas é igual a n. Por último, o valor armazenado em
r após a execução do comando for é retornado, por meio
da execução do comando return r;. Consideramos, a seguir,
o comando for mais detalhadamente.
O cabeçalho de um comando for — no exemplo, a parte entre
parênteses (int i=1; i<=n; i++) — é constituído de
três partes (ou cláusulas), descritas a seguir:
for é executado, seguido pela
avaliação da terceira cláusula do cabeçalho desse
comando, e depois uma nova iteração é iniciada; caso
contrário, ou seja, se o valor for falso (em C, zero), a
execução do comando for termina.i++, que
representa o mesmo que i = i+1, incrementa o valor de
i a cada iteração.Note a ordem na execução de cada iteração em um comando
for: teste de terminação, corpo, atualização.
É instrutivo acompanhar a modificação do valor armazenado em
cada variável durante a execução da chamada
mult(3,2). Em outras palavras, acompanhar, em cada passo da
execução, o estado da computação: o estado da
computação é uma função que associa um valor a cada
variável.
A Tabela
4.1 ilustra os passos da execução da chamada
mult(3,2), registrando, a cada passo, o estado da
computação. O resultado fornecido pela avaliação de
expressões é também mostrado nessa tabela. Note que o resultado
fornecido pela cláusula de atualização de um comando for
é sempre descartado. Essa expressão é avaliada apenas com o
propósito de atualizar o valor de uma ou mais variáveis (ou seja,
é uma expressão com efeito colateral).
Tabela 4.1: Passos na execução de mult(3,2)
Comando/ Expressão
Resultado (expressão)
Estado (após execução/avaliação) mult(3,2)… m↦ 3,n↦ 2intr= 0m↦ 3,n↦ 2,r↦ 0i= 1m↦ 3,n↦ 2,r↦ 0,i↦ 1i<=nverdadeiro m↦ 3,n↦ 2,r↦ 0,i↦ 1r+=m3 m↦ 3,n↦ 2,r↦ 3,i↦ 1i++2 m↦ 3,n↦ 2,r↦ 3,i↦ 2i<=nverdadeiro m↦ 3,n↦ 2,r↦ 3,i↦ 2r+=m6 m↦ 3,n↦ 2,r↦ 6,i↦ 2i++3 m↦ 3,n↦ 2,r↦ 6,i↦ 3i<=nfalso m↦ 3,n↦ 2,r↦ 6,i↦ 3for…m↦ 3,n↦ 2,r↦ 6,i↦ 3returnrmult(3,2)6
A variável i é usada no comando for como um contador de iterações.
Considere agora a função multr definida acima. A sua
definição espelha diretamente a definição indutiva da
operação de multiplicação, em termos da adição,
apresentada anteriormente. Ou seja, multiplicar m por n (onde n é um inteiro não-negativo) fornece:
n==0);m + mult (m, n-1), no caso indutivo (isto é, se
n!=0).Vejamos agora, mais detalhadamente, a execução de uma chamada
multr(3,2). Cada chamada da função multr cria novas
variáveis, de nome m e n. Existem, portanto, várias
variáveis com nomes (m e n), devido às chamadas
recursivas. Nesse caso, o uso do nome refere-se à variável local
ao corpo da função que está sendo executado. As execuções das
chamadas de funções são feitas, dessa forma, em uma estrutura de
pilha. Chamamos, genericamente, de estrutura de pilha uma
estrutura na qual a inserção (ou alocação) e a retirada
(ou liberação) de elementos é feita de maneira que o último
elemento inserido é o primeiro a ser retirado.
Como a execução de chamadas de funções é feita na forma de uma estrutura de pilha, em cada instante da execução de um programa, o último conjunto de variáveis alocados na pilha corresponde às variáveis e parâmetros da última função chamada. No penúltimo espaço são alocadas as variáveis e parâmetros da penúltima função chamada, e assim por diante. Cada espaço de variáveis e parâmetros alocado para uma função é chamado de registro de ativação dessa função.
O registro de ativação de cada função é desalocado (isto é, a área de memória correspondente na pilha é liberada para uso por outra chamada de função) no instante em que a execução da função termina. Como o término da execução da última função chamada precede o término da execução da penúltima, e assim por diante, o processo de alocação e liberação de registros de ativação de chamadas de funções se dá como em uma estrutura de pilha.
As variáveis que podem ser usadas no corpo de uma função são apenas os parâmetros dessa função e as variáveis internas aí declaradas (chamadas de variáveis locais da função), além das variáveis externas, declaradas no mesmo nível da definição da função, chamadas de variáveis globais.
Variáveis declaradas internamente a uma função são criadas cada vez que uma chamada a essa função é executada, enquanto variáveis globais são criadas apenas uma vez, quando a execução do programa é iniciada ou anteriormente, durante a carga do código do programa na memória.
No momento da criação de uma variável local a uma função, se não foi especificado explicitamente um valor inicial para essa variável, o valor nela armazenado será indeterminado, isto é, será o valor já existente nos bytes alocados para essa variável na pilha de chamadas de funções.
Na Figura 4.2, representamos a estrutura de pilha
criada pelas chamadas à função multr. Os nomes m e
n referem-se, durante a execução, às variáveis mais ao
topo dessa estrutura. Uma chamada recursiva que vai começar a ser
executada é circundada por uma caixa. Nesse caso, o resultado da
expressão, ainda não conhecido, é indicado por “…”.
Tabela 4.2: Passos na execução de multr(3,2)
Comando/ Expressão
Resultado (expressão)
Estado (após execução/avaliação) multr(3,2)…
m↦ 3 n↦ 2 n== 0falso
m↦ 3 n↦ 2 returnm+multr(m,n-1)…
m↦ 3 m↦ 3 n↦ 2 n↦ 1 n== 0falso
m↦ 3 m↦ 3 n↦ 2 n↦ 1 returnm+multr(m,n-1)…
m↦ 3 m↦ 3 m↦ 3 n↦ 2 n↦ 1 n↦ 0 n== 0verdadeiro
m↦ 3 m↦ 3 m↦ 3 n↦ 2 n↦ 1 n↦ 0 return0
m↦ 3 m↦ 3 n↦ 2 n↦ 1 returnm+ 0
m↦ 3 n↦ 2 returnm+ 3multr(3,2)6
Uma chamada de função corresponde então nos seguintes passos, nesta ordem:
Cada expressão usada em uma chamada em computação, correspondente a cada parâmetro, é chamada de parâmetro real. O resultado obtido pela avaliação de cada parâmetro real é chamado de argumento.
Por exemplo, na chamada mult(3+1,2), 3+1 e 2
são parâmetros reais. Os argumentos são 4 e 2,
obtidos pela avaliação das expressões 3+1 e 2,
respectivamente.
No nosso exemplo, é criado registro de ativação contendo espaço
para os parâmetros m e n.
No nosso exemplo mult(3+1,2), o argumento 4 (obtido
pela avaliação do parâmetro real 3+1) é atribuído ao
parâmetro m.
Essa atribuição do argumento ao parâmetro é chamada em computação de passagem de parâmetro, no caso uma passagem de parâmetro por valor. O significado disso é o já explicado: o parâmetro real é avaliado, resultado em um valor, chamado de argumento, e copiado para o parâmetro. O parâmetro é também chamado de parâmetro formal.
É preciso, é claro, que o resultado da função fique disponível para ser usado, ou seja armazenado em uma variável que exista depois que o espaço de memória alocado para o registro de ativação tiver sido liberado, após a chamada à função.
As definições de exp e expr seguem o mesmo padrão
de computação das funções mult e multr,
respectivamente. A definição de expr é baseada na
seguinte definição indutiva da exponenciação:
mn = (1 se m=0, senão m × mn−1)
|
Uma característica importante da implementação de funções, e de algoritmos em geral, é a sua eficiência. A definição alternativa da função de exponenciação apresentada na Figura 4.1 ilustra bem como implementações de uma mesma função, baseadas em algoritmos distintos, podem ter eficiência diferente. Essa nova definição é uma implementação de mn baseada na seguinte definição indutiva:
|
int exp2 (int m, int n) { if (n == 0) return 1; else if (n % 2 == 0) { // n é par int x = exp2(m, n/2); return x*x; } else return m * exp2(m, n-1); }
Figura 4.1: Implementação mais eficiente da operação de exponenciação
A avaliação de exp2(m, n) produz o mesmo resultado que a
avaliação de exp(m, n) e de expr(m, n), mas de
maneira mais eficiente — em termos do número de operações
necessárias, e portanto em termos do tempo de execução. Para
perceber isso, observe que a avaliação de exp2(m, n) é
baseada em chamadas recursivas que dividem o valor de n por 2 a cada chamada; a avaliação de exp(m, n), por outro
lado, diminui o valor de n de 1 a cada iteração (assim
como expr(m, n) diminui o valor de n de 1 a cada chamada
recursiva).
Por exemplo, as chamadas recursivas que ocorrem durante a
avaliação da expressão exp2(2,20) são, sucessivamente,
as seguintes:
|
A diferença em eficiência se torna mais significativa quando o
expoente n é maior. São realizadas da ordem de log2(n)
chamadas recursivas durante a execução de exp2(m, n) —
uma vez que n é em média dividido por 2 em chamadas
recursivas —, ao passo que a execução de exp(m, n)
requer n iterações.
Um exercício interessante é aplicar a mesma técnica usada na
definição de exp2 (ou seja, usar divisão por 2 caso o
segundo operando seja par) para obter uma definição mais
eficiente para a multiplicação (procure resolver esse
exercício antes de ver sua solução, no Exercício
Resolvido 2).
Questões sobre eficiência de algoritmos são importantes em computação, envolvendo aspectos relativos ao tempo de execução e ao consumo de memória (referidos abreviadamente como aspectos de tempo e espaço). A análise da eficiência de algoritmos é abordada superficialmente ao longo deste texto, sendo um estudo mais detalhado desse tema deixado para cursos posteriores.
Nesta seção, exploramos um pouco mais sobre recursão e iteração, por meio do exemplo clássico do cálculo do fatorial de um número inteiro não-negativo n, usualmente definido como:
| n! = n × (n−1) × (n−2) × … 3 × 2 × 1 |
Duas formas comuns para implementação dessa função são mostradas a seguir:
|
A função fatr espelha diretamente a seguinte definição
indutiva, que especifica precisamente o significado dos três pontos
(…) na definição de n! dada acima:
|
A versão iterativa, fat, adota a regra de calcular o fatorial
de n usando um contador (i), que varia de 1 a
n, e uma variável (f), que contém o produto 1 ×
2 × … i, obtido multiplicando o valor de i por
f a cada iteração. Mudando o valor do contador e o valor
do produto a cada iteração (para valores de i que variam
de 1 a n), obtemos o resultado desejado na variável f
(ou seja, n!), ao final da repetição. Verifique que, no
caso da execução de uma chamada fat(0), nenhuma
iteração do comando for é executada, e o resultado
retornado pela função é, corretamente, igual a 1 (valor
inicialmente atribuído à variável f).
O exemplo a seguir mostra como pode ser implementada uma versão
recursiva do processo iterativo para cálculo do fatorial. Nesse
caso, o contador de repetições (i) e a variável
(f), que contém o produto 1 × 2 × … i,
são passados como argumentos da função definida
recursivamente, sendo atualizados a cada chamada
recursiva.
|
Outros exemplos de problemas cuja solução requer o uso de recursão ou iteração são abordados a seguir. De modo geral, na solução de tais problemas, o valor calculado em uma iteração ou chamada recursiva de uma função é obtido pela aplicação de funções a valores obtidos na iteração ou chamada recursiva anterior.
O exemplo mais simples é o cálculo do somatório de termos de uma série aritmética. Por exemplo, considere o cálculo do somatório dos termos da série aritmética de passo 1 para um dado n, usualmente denotado por
| i |
implementada a seguir pela
função pa1:
|
Assim como para o cálculo do fatorial, duas versões recursivas,
que usam processos de cálculo diferentes, podem ser
implementadas. Essas definições são mostradas a seguir. A
primeira (pa1r) espelha diretamente a definição indutiva
de
| i |
e a segunda (pa1rIter) espelha o processo iterativo, de maneira
análoga à usada na definição de fatIter.
|
É simples modificar essas definições para o cálculo de somatórios dos termos de séries aritméticas com passo diferente de 1. Essas modificações são deixadas como exercício para o leitor.
Nenhuma dessas implementações constitui a maneira mais eficiente para calcular a soma de termos de uma série aritmética, pois tal valor pode ser calculado diretamente, usando a fórmula:
| i = |
|
O leitor com interesse em matemática pode procurar deduzir essas fórmulas. Conta a história que a fórmula acima foi deduzida e usada por Gauss quando ainda garoto, em uma ocasião em que um professor de matemática pediu-lhe, como punição, que calculasse a soma dos 1000 primeiros números naturais. Deduzindo a fórmula em pouco tempo, Gauss respondeu a questão prontamente. De fato, é possível deduzir a fórmula rapidamente, mesmo sem uso de papel e lápis, depois de perceber que a soma
|
fornece o mesmo resultado que somar n termos iguais a n+1. A dedução da fórmula
| xi = |
|
pode ser feita com artifício semelhante — i.e. multiplicando (x0 + … + xn) por (x − 1).
Essas definições servem, no entanto, para a ilustrar a implementação de somatórios semelhantes, como nos exemplos a seguir.
Considere a implementação de uma função para cálculo de:
| xi |
Também nesse caso, podemos usar um comando de repetição, como
na implementação de pa1, sendo adequado agora usar uma
variável adicional para guardar a parcela obtida em cada
iteração. Essa variável é chamada parc na
implementação apresentada a seguir, que calcula o somatório
das parcelas da série geométrica acima, para um dado x e um
dado n:
|
O uso de parc em pg evita que seja necessário calcular
xi (ou seja, evita que uma operação de
exponenciação tenha que ser efetuada) a cada iteração. Em
vez disso, a parcela da i-ésima iteração (contida em
parc), igual a xi−1, é multiplicada por
x para obtenção da parcela da iteração seguinte.
Para a implementação de um somatório, devemos, portanto,
decidir se cada parcela a ser somada vai ser obtida a partir da
parcela anterior (e nesse caso devemos declarar uma variável, como a
variável parc, usada para armazenar o valor calculado para a
parcela em cada iteração), ou se cada parcela vai ser obtida por
meio do próprio contador de iterações. Como exemplo desse
segundo caso, considere a implementação do seguinte
somatório:
|
|
A seqüência de números 1, 1/2, 1/3, …, 1/n, … é denominada série harmônica.
A parcela a ser somada a cada iteração, 1/i, é obtida nesse caso a partir de i, e não da parcela “anterior”, 1/(i-1):
|
Na maioria das vezes, uma parcela pode ser calculada de maneira mais fácil e eficiente a partir da parcela calculada anteriormente. Em vários casos, esse cálculo não usa a própria parcela anterior, mas valores usados no cálculo dessa parcela. Por exemplo, considere o seguinte somatório, para cálculo aproximado do valor de π:
| π = 4 * (1 − |
| + |
| − |
| + …) |
Nesse caso, devemos “guardar” não o valor mas o sinal da parcela anterior (para invertê-lo) e o denominador usado para cálculo dessa parcela (ao qual devemos somar 2 a cada iteração):
|
Em nosso último exemplo, vamos definir uma função para calcular um valor aproximado para ex, para um dado x, usando a fórmula:
| ex = 1 + (x1 / 1!) + (x2 / 2!) + … |
Para calcular a parcela a ser somada em cada iteração i do
comando de repetição, a implementação usa o denominador
i! e o numerador xi, calculado na parcela
anterior. Optamos pelo uso de um comando while (em vez do
for), para ilustração:
|
A decisão entre usar um comando for ou um comando while
em C é, na maioria das vezes, uma questão de estética ou de
gosto. Existe uma diferença quando um comando continue é
usado internamente a um comando for ou um comando while
(veja Exercício Resolvido 10).
Note que os dois comandos a seguir são equivalentes, se c não
contiver comando de declaração de variável, que é possível somente a
partir da versão C-99 da linguagem, nem um comando
continue (veja Exercício Resolvido 10; no
o comando c2 é executado após o comando continue no
caso do comando for, mas não no caso do while):
Note, contudo, que a versão C-99 permite declarações locais no
comando de inicialização (c1) do comando for, e nesse
caso o escopo da declaração é diferente nos dois casos acima. A
variável introduzida na declaração é visível após c1 no
caso do comando while, até o final do bloco em que o comando
while ocorre, mas no caso do comando for seu escopo é
apenas o comando for, não podendo ser usada em comandos
seguintes ao comando for.
Outro comando de repetição que pode ser usado em programas C é o comando do-while. Esse comando tem a forma:
|
onde $c$ é um comando e $b$ é uma expressão que
denota um valor falso ou verdadeiro. Esse comando é bastante
semelhante ao comando while. No caso do comando do-while,
no entanto, o comando $c$ é executado uma vez, antes do teste
de continuação ($b$). Por exemplo, considere o seguinte
trecho de programa, que imprime os inteiros de 1 a 10, no
dispositivo de saída padrão:
|
Pode ocorrer, em princípio, que a avaliação de certas expressões que contêm símbolos definidos recursivamente, assim como a execução de certos comandos de repetição, não termine. Considere, como um exemplo extremamente simples, a seguinte definição:
|
Essa declaração especifica que a função infinito
retorna um valor do tipo int. Qual seria esse valor? A
avaliação de uma chamada à função infinito nunca
termina, pois envolve, sempre, uma nova chamada a essa função. O
valor representado por uma chamada a essa função não é,
portanto, nenhum valor inteiro. Em computação, qualquer tipo,
predefinido ou declarado em um programa, em geral inclui um valor
especial, que constitui um valor indefinido do tipo em questão e que
representa expressões desse tipo cuja avaliação nunca termina
ou provoca a ocorrência de um erro (como, por exemplo, uma divisão
por zero).
Muitas vezes, um programa não termina devido à aplicação de
argumentos a funções cujo domínio não engloba todos os
valores do tipo da função. Essas funções são comumente
chamadas, em computação, de parciais. Por exemplo, a
definição de fat, dada anteriormente, especifica que essa
função recebe como argumento um número inteiro e retorna
também um número inteiro. Mas note que, para qualquer n < 0,
a avaliação de fat (n) não termina. A definição
de fat poderia, é claro, ser modificada de modo a indicar a
ocorrência de um erro quando o argumento é negativo.
Considere agora a seguinte definição de uma função —
const1 — que retorna sempre 1, para qualquer argumento:
|
A avaliação da expressão:
|
nunca termina, apesar de const1 retornar sempre o mesmo valor
(1), para qualquer argumento (o qual, nesse caso, não é
usado no corpo da função) cuja avaliação termina. Isso ocorre
porque, em C, assim como na grande maioria das linguagens de
programação, a avaliação dos argumentos de uma
função é feita antes do início da execução do corpo
da função.
while.
Solução: Esse comando pode ser definido recursivamente pela seguinte equação:
|
Obs.: A notação = é usada acima para expressar uma equação matemática.
mult2 que use a
mesma técnica empregada na definição de exp2. Ou seja,
use divisão por 2 caso o segundo operando seja par, para obter uma
implementação da operação de multiplicação mais
eficiente do que a apresentada em multr.Exemplos do uso desse algoritmo são encontrados em um dos documentos matemáticos mais antigos que se conhece, escrito por um escrivão egípcio (A’h-mose), por volta de 1700 a.C.
Solução:
|
pgr que espelhe o processo iterativo de pg. Em outras
palavras, defina recursivamente uma função que, dados um
número inteiro x e um número inteiro não-negativo n,
retorne o valor do somatório:
| xi |
Escreva um programa que leia repetidamente pares de valores inteiros
x e n, até que o valor de n seja zero ou negativo, e imprima o
valor do somatório ∑i=0n xi, usando a função pgr.
Solução:
|
exp2, definida na
Figura 4.1, usando um comando de repetição, em vez de
recursão.Solução:
|
A definição recursiva apresentada na Figura 4.1 é
mais simples, pois espelha diretamente a definição indutiva
de exp2, dada anteriormente. A definição acima usa um
esquema não-trivial (não diretamente ligado à definição da
função) para atualização do valor de variáveis no corpo
do comando de repetição.
Solução: O algoritmo de Euclides é um algoritmo clássico e engenhoso para cálculo do máximo divisor comum de dois números inteiros positivos:
| mdc(a,b) = | ⎛ ⎝ | a se b=0, senão mdc(b, a % b) | ⎞ ⎠ |
O operador % é usado acima como em C, ou seja, a%b representa o resto da divisão inteira de a por b (a e b são números inteiros). O algoritmo original de Euclides (escrito no famoso livro Elementos, por volta do ano 3 a.C.) usava mdc(b, a−b) em vez de mdc(b, a % b), na definição acima, mas o uso da divisão torna o algoritmo mais eficiente.
Note que esse algoritmo funciona se a ≥ b ou em caso contrário. Se a < b, a chamada recursiva simplesmente troca a por b (por exemplo, mdc(20,30) é o mesmo que mdc(30,20)).
Em C, podemos escrever então:
|
Podemos também escrever a função mdc usando um comando
de repetição, como a seguir:
|
Defina uma função calc que receba
como argumentos um caractere, que indica uma operação
aritmética (’+’, ’-’, ’*’ e ’/’), e dois
valores de ponto flutuante, e retorne o resultado da aplicação
da operação sobre os dois argumentos. Por exemplo: calc ('+', 1.0, 1.0) deve retornar 2.0 e calc ('*',2.0,3.0) deve retornar 6.0.
Solução: Vamos ilustrar aqui o uso do comando
switch, existente em C, que permite escolher um dentre vários
comandos para ser executado. O comando switch tem a forma:
|
O comando switch pode ser visto como uma seqüência de
comandos de seleção (if), cada um realizando um teste
correspondente a um caso do comando switch.
O significado de um comando switch é o seguinte: a expressão
e é avaliada e é executado o primeiro comando ci, na ordem
c1, …, cn, para o qual o valor fornecido por e é igual ao
valor de ei (caso tal comando exista), sendo também executados
todos os comandos seguintes (ci+1, …, cn), se existirem,
nessa ordem.
A execução de qualquer desses comandos pode ser finalizada, e
geralmente deve ser, por meio de um comando break. No entanto,
na solução desse exercício o uso de um comando break não é
necessário, pois toda alternativa contém um comando return, que
termima a execução da função.
Supõe-se também, na função op definida abaixo, que o caractere
passado como argumento para op é sempre igual a ’+’, ’*’, ’-’ ou ’/’.
|
Se o valor de e não for igual a nenhum dos valores ei, para
i≤ n, um caso default pode ser usado. O caso default
pode ser usado no lugar de case ei, para qualquer ei, para
algum i=1,…,n, mas em geral deve ser usado como último
caso. Se default não for especificado (é comum dizer “se
não existir nenhum caso default”), o comando switch
pode terminar sem que nenhum dos comandos ci, para i=1,…,n,
seja executado (isso ocorre se o resultado da avaliação de e
não for igual ao valor de nenhuma das expressões ei, para
i=1,…,n).
A necessidade do uso de um comando break, sempre que se deseja
que seja executado apenas um dos comandos do comando switch,
correspondente a um determinado caso (expressão), é em geral
reconhecida como um ponto fraco do projeto da linguagem C.
A expressão e, no comando switch, deve ter tipo int,
short, byte ou char, devendo o seu tipo ser
compatível com o tipo das expressões e1, …, en. As
expressões e1, …, en têm que ser valores constantes (e
distintos).
Um comando switch pode ser também precedido de um rótulo — um nome seguido do caractere “:”. Nesse
caso, um comando break pode ser seguido desse nome: isso indica
que, ao ser executado, o comando break causa a terminação
da execução do comando switch precedido pelo rótulo
especificado.
raizq, que
calcula a raiz quadrada de um dado valor x, com erro de
aproximação menor que 0,0001 (0.0001 em
C).A raiz quadrada de x é um número y tal que y2 = x. Para certos números, como, por exemplo, 2, a sua raiz quadrada é um número que teria que ser representado com infinitos algarismos na sua parte decimal, não sendo possível obter essa representação em um tempo finito. Desse modo, o cálculo desses valores é feito a seguir, com um erro de aproximação inferior a um valor preestabelecido — nesse caso, 0,0001. Vamos chamar de e o valor 0,0001. Denotando por | x | o valor absoluto de x, o valor y a ser retornado por raizq(x) deve ser tal que:
| y ≥ 0 e | y2 − x | < e |
Para definir a função raizq, use o método de
aproximações sucessivas de Newton. Para a raiz quadrada, o
método de Newton especifica que, se yi é uma aproximação
para √x, então uma aproximação melhor é dada por:
| yi+1 = (yi + x/yi) / 2 |
Por exemplo, sejam x = 2 e y0 = 2. Então:
|
Repetindo esse processo, podemos obter aproximações para a raiz quadrada com qualquer precisão desejada (sujeitas, é claro, às limitações da representação de números do computador).
Solução: A implementação da função raizq
pode ser feita usando um comando de repetição, como mostrado
abaixo.
|
Um templo, na cidade de Hanói, contém três torres de diamante, em uma das quais Deus colocou, quando criou o mundo, 64 discos de ouro, empilhados uns sobre os outros, de maneira que os discos diminuem de tamanho da base para o topo, como mostrado a seguir. Os monges do templo trabalham sem cessar para transferir, um a um, os 64 discos da torre em que foram inicialmente colocados para uma das duas outras torres, mas de forma que um disco nunca pode ser colocado em cima de outro menor. Quando os monges terminarem de transferir todos os discos para uma outra torre, tudo virará pó, e o mundo acabará.
A questão que se coloca é: supondo que os monges trabalhem tão eficientemente quanto possível, e consigam transferir 1 disco de uma torre para outra em 1 segundo, quanto tempo decorreria (em segundos) desde a criação até o fim do mundo?
Solução: Uma solução recursiva para o problema é baseada na idéia ilustrada abaixo. Nessa solução, supõe-se, como hipótese indutiva, que se sabe como transferir n−1 discos de uma torre para outra (sem colocar um disco em cima de outro menor); o caso base consiste em transferir um disco de uma torre para outra vazia. O número total de movimentações de n discos é definido indutivamente por:
|
| move n−1 discos da torre A para C, usando B |
| move 1 disco de A para B |
| move n−1 discos da torre C para B, usando A |
/home/camarao/ipcc/fig/hanoi-sol.eps
Cada valor da seqüência de valores definida por f(n) representa, de fato, o menor número de movimentações requeridas para mover n discos de uma torre para outra, satisfazendo o requerimento de que um disco nunca pode ser colocado sobre outro de diâmetro menor. Para perceber isso, basta notar que, para mover um único disco d, digamos, da torre A para a torre B, é preciso antes mover todos os discos menores que d para a torre C. Portanto, a resposta à questão proposta anteriormente é dada por f(64). Um resultado aproximado é 1,844674 × 1019 segundos, aproximadamente 584,5 bilhões de anos.
A definição de f estabelece uma relação de recorrência para uma seqüência de valores f(i), para i=1,…, n (uma relação de recorrência para uma seqüência é tal que cada termo é definido, por essa relação, em termos de seus predecessores). A primeira equação na definição de f é chamada condição inicial da relação de recorrência.
Podemos procurar obter uma fórmula que define diretamente, de forma não-recursiva, o valor de f(n), buscando estabelecer um padrão que ocorre no cálculo de f(n), para cada n:
|
Podemos observar que f(n) = 2n − 1, pois:
| 2i = 2n − 1 |
O leitor interessado pode provar (usando indução sobre n) que, para todo n, a definição recursiva de f de fato satisfaz a equação f(n) = 2n − 1.
Supondo que um par de coelhos — um macho e uma fêmea — tenha nascido no início de um determinado ano, que coelhos não se reproduzam no primeiro mês de vida, que depois do primeiro mês um par de coelhos dê origem, a cada mês, a um novo par — macho e fêmea — e que nenhuma morte ocorra durante um ano, quantos coelhos vão existir no final do ano?
Escreva um programa para solucionar esse problema, imprimindo o número de coelhos existentes no final do ano.
Solução: Note que: 1) o número de (pares de) coelhos vivos no final de um mês k é igual ao número de (pares de) coelhos vivos no final do mês k−1 mais o número de (pares de) coelhos que nasceram no mês k; e 2) o número de (pares de) coelhos que nasceram no mês k é igual ao número de (pares de) coelhos vivos no mês k−2 (pois esse é exatamente o número de coelhos que geraram filhotes no mês k).
Portanto, a quantidade de coelhos vivos ao fim de cada mês n é dada pelo número fib(n) da seqüência de números definida a seguir, conhecida como seqüência de Fibonacci:
|
O problema pode então ser resolvido pelo programa a seguir:
|
O número de pares de coelhos no final do décimo segundo mês,
fib(12), é igual a 144 (ou seja, o número de coelhos
é igual a 288).
A função fib definido no programa acima é muito ineficiente,
pois repete muitos cálculos, devido às chamadas recursivas a
fib(n-1) e fib(n-2) (cada chamada de fib(n) envolve
calcular fib(n-1) e fib(n-2), e a chamada a fib(n-2)
envolve chamar fib(n-1) outra vez). A definição a seguir
é muito mais eficiente:
|
As chamadas a fib1 usam r1 e r como acumuladores,
evitando chamadas repetidas desnecessárias. A execução dessa
definição recursiva é equivalente à obtida por meio do comando de
repetição a seguir:
|
break e continue
podem ser usados no corpo de um comando de repetição. A
execução de um comando break causa o término da
repetição e a execução de um comando continue
causa o início imediato de uma próxima iteração. O
comando continue provê uma forma de saltar determinados
casos em um comando de repetição, fazendo com que o controle
passe para a iteração seguinte.O exemplo a seguir imprime a representação unária (usando o
símbolo “|”) de todos os números inteiros de 1
até n que não são múltiplos de um determinado valor
inteiro m>1. O resultado da execução de Exemplo_continue 20 5 é mostrado abaixo.
Os comandos break e continue podem especificar um
rótulo, de mesmo nome do rótulo colocado em um comando de
repetição. No caso de um comando break, o rótulo pode
ser colocado também em um bloco ou em um comando switch (veja
o Exercício Resolvido 6).
Como ilustra esse exemplo, um comando continue sem um rótulo
indica o início da execução da próxima
iteração do comando de repetição mais interno em
relação a esse comando continue. Analogamente, um comando
break sem um rótulo indica o término da execução do
comando de repetição ou comando switch mais interno em
relação a esse comando break.
int main() { int n, m, col = 1, i; printf("Impressao de valores de 1 a n em notacao unaria, sem multiplos de m\n"); printf("Digite n e m: "); scanf("%d%d", &n, &m); for (i=1; i<=n; i++) { printf("\n"); if (i % m == 0) continue; for (col=1; col<=i; col++) printf("|"); } return EXIT_SUCCESS; }
Figura 4.2: Exemplo de uso do comando continue
Impressao de valores de 1 a n em notacao unaria, sem multiplos de m Digite n e m: 20 5 | || ||| |||| |||||| ||||||| |||||||| ||||||||| ||||||||||| |||||||||||| ||||||||||||| |||||||||||||| |||||||||||||||| ||||||||||||||||| |||||||||||||||||| ||||||||||||||||||
Figura 4.3: Resultado do programa de exemplo de uso do comando continue
O comando break provê uma forma de sair de um comando de
repetição, que pode ser, em algumas situações, mais
fácil (ou mais conveniente do que outras alternativas). Em alguns
casos, pode ser mais fácil testar uma condição internamente ao
comando de repetição e usar o comando break, em vez de
incluir essa condição no teste de terminação do comando de
repetição.
O uso do comando break é ilustrado pelo exemplo a
seguir. Considere o problema de ler, repetidamente, um valor inteiro
positivo e imprimir, para cada inteiro lido, seu fatorial. Se for lido
um valor negativo, a execução do programa deve terminar.
|
Uma chamada à função scanf retorna o número de variáveis lidas,
e pode ser usado para detectar fim dos dados de entrada a serem lidos
(isto é, se não existe mais nenhum valor na entrada de dados a ser
lido). O exemplo a seguir lê vários inteiros do dispositivo de entrada
padrão e imprima a soma de todos os inteiros lidos. O programa termina
quando não há mais valores a serem lidos.
|
O programa a seguir funciona de modo semelhante, mas lê vários inteiros positivos do dispositivo de entrada padrão e termina a execução quando quando não há mais valores a serem lidos ou quando um valor negativo ou zero for lido.
|
A entrada termina com indicação de fim dos dados de entrada (em entrada interativa, Control-z seguido de Enter no Windows, ou Control-d no Linux).
Solução: São usadas duas variáveis inteiras max1 e
max2 para armazenar os dois maiores valores lidos, e elas são
atualizadas adequadamente, se necessário, após a leitura de cada
inteiro. O valor inicial atribuído a essas variáveis é o valor
INT_MIN, menor inteiro armazenável em uma variável de tipo
int. Qualquer valor inteiro digitado será maior ou igual a
esse valor e será, caso for maior, atribuído à variável.
INT_MIN é definido em limits.h.
O valor retornado por scanf é usado para verificar fim dos
dados de entrada: scanf retorna -1 como indicação de
fim dos dados de entrada.
O programa é mostrado a seguir.
|
Considere que uma palavra é uma sequência de um ou mais caracteres
que começa com qualquer caractere que não é um delimitador de
palavras. Um delimitador de palavras é um caractere espaço
(branco, i.e. ’ ’), fim-de-linha ('\n''\t'
A entrada termina com indicação de fim dos dados de entrada (em entrada interativa, Control-z seguido de Enter no Windows, ou Control-d no Linux).
Solução: A solução mostrada a seguir usa scanf
com formato %c para ler um caractere, e o valor retornado por
scanf para verificar fim dos dados de entrada (scanf
retorna -1 para indicar fim dos dados).
A função isletter definida retorna verdadeiro (em C,
valor inteiro diferente de zero) se e somente se o caractere passado
como argumento é uma letra. Para isso, é testado se tal caractere
está entre ’a’ e ’z’ ou entre ’A’ e ’Z’.
Para contar palavras, é usado uma variável (fora) que indica
se o caractere corrente, que está sendo lido, está fora ou dentro de
uma palavra. O número de palavras (armazanado na variável
palavras) é incrementado quando se está fora de uma palavra e
um caractere não delimitador de palavras é lido (como especificado
no enunciado, um delimitador de palavras é considerado como sendo um
dos caracteres espaço, fim-de-linha ou tab).
O programa é mostrado a seguir.
|
| http://br.spoj.pl/problems/PAR |
O problema consiste em determinar, para cada jogada de partidas do jogo Par ou Ímpar, o vencedor da jogada.
A entrada representa uma sequência de dados referentes a partidas de Par ou Ímpar. A primeira linha de cada partida contém um inteiro n, que indica o número de jogadas da partida. As n linhas seguintes contêm cada uma dois inteiros a e b que representam o número escolhido por cada jogador (0 ≤ a ≤ 5 e 0 ≤ B ≤ 5). O final da entrada é indicado por n = 0.
A saída deve conter para cada partida, uma linha no formato Partida i, onde i é o número da partida: partidas são numeradas sequencialmente a partir de 1. A saída deve conter também uma linha para cada jogada de cada partida, contendo Par ou Impar conforme o vencedor da partida seja o jogador que escolheu par ou ímpar, respectivamente. Deve ser impressa uma linha em branco entre uma partida e outra.
Por exemplo, para a entrada:
| 3 |
| 2 4 |
| 3 5 |
| 1 0 |
| 2 |
| 1 5 |
| 2 3 |
| 0 |
a saída deve ser:
| Partida 1 |
| Par |
| Par |
| Impar |
| Partida 2 |
| Par |
| Impar |
Solução: O programa abaixo define e usa a função
processaPartida para separar o processamento (cálculo e
impressão) de valores de cada partida, e a função par, que
determina se um dado valor é par ou não. O número de cada partida é
armazenado em uma variável, que tem valor inicial igual a 1 e é
incrementada após o processamento de cada partida.
O programa usa também o recurso de definir a assinatura (ou interface, ou cabeçalho) de cada função definida, para usar (chamar) a função antes de defini-la. Na definição da interface o nome dos parâmetros é opcional, e é omitido no programa abaixo.
|
| http://br.spoj.pl/problems/RUMO9s/ |
int ou long int).
O problema é descrito a seguir.Um número inteiro é múltiplo de nove se e somente se a soma dos seus dígitos é múltiplo de 9. Chama-se grau-9 de um número inteiro n≥ 0 o valor igual a 1 se n=9, 0 se n<9, e 1 mais o grau-9 da soma de seus dígitos, se n>9.
Escreva um programa que, dado uma sequência de inteiros positivos, imprime se cada um deles é múltiplo de nove e, em caso afirmativo, seu grau-9. A entrada, no dispositivo de entrada padrão, contém uma sequência de inteiros positivos, um em cada linha, e termina com o valor 0. Exemplo:
Entrada:
| 999 |
| 27 |
| 9 |
| 998 |
| 0 |
Saída:
| 999 e’ multiplo de 9 e seu grau-9 e’ 3. |
| 27 e’ multiplo de 9 e seu grau-9 e’ 2. |
| 9 e’ multiplo de 9 e seu grau-9 e’ 1. |
| 998 nao e’ multiplo de 9. |
Solução: A solução usa a função isdigit para
testar se um dado caractere é um dígito (i.e. em C, um inteiro sem
sinal, entre ’0’ e ’9’).
A função somaEImprimeCaracs lê e imprime os dígitos contidos
em uma linha da entrada padrão, e retorna o inteiro
correspondente. Para isso, ela subtrai converte cada caractere lido no
inteiro correspondente, subtraindo o caractere ’0’ (uma vez que
os caracteres são ordenados, a partir de ’0’, no código ASCII,
usado em C para representação de caracteres, como valores
inteiros).
|
somaIter, somaRec e soma, tais que, dados dois
números inteiros positivos a e b, retorne o valor
a + b. As duas primeiras definições devem usar apenas as
operações mais simples de incrementar 1 e decrementar 1 (devem
supor que as operações de adicionar e de subtrair mais de uma
unidade não são disponíveis). A primeira definição
deve usar um comando de repetição, e a segunda definição
deve ser recursiva. A terceira definição deve usar o operador + de adição.Inclua essas três definições em um programa de teste, e defina um
programa de teste que leia vários valores a a b do
dispositivo de entrada padrão, e não imprima nada se e somente se,
para cada par de valores a e b lidos, os resultados
retornados pelas execuções das três definições (somaIter,
somaRec e soma) forem iguais. Se existir um par de valores
a e b lido para o qual o resultado retornado pela execução
das três definições não é igual, o programa deve terminar e uma
mensagem deve ser impressa, informando o par de valores a,
b para o qual o resultado da execução foi diferente, assim como
o resultado retornado por cada definição, junto com o nome da função
que retornou cada resultado.
A leitura deve terminar quando não houver mais valores a serem lidos (em entrada interativa, quando o caractere que indica fim dos dados for digitado).
O programa deve definir e usar uma função numdiv que
recebe dois números inteiros positivos e retorna o número de
vezes que uma divisão exata pode ser realizada, neste processo de
substituir o dividendo pelo quociente. O processo de divisões
sucessivas deve terminar quando uma divisão exata não existe.
Exemplos: numdiv(8,2) deve retornar 3 e
numdiv(9,2) deve retornar 0.
|
|
Por exemplo, o número de combinações de 4 objetos, 2 a 2, é igual a 4× 3/2! = 6 (se representamos os objetos por números, as combinações são {1,2}, {1,3}, {1,4}, {2,3}, {2,4} e {3,4}).
Defina uma função que, dados n e p, calcule o número de combinações de n objetos p a p.
Observação: A fórmula acima pode ser escrita também na forma:
|
No entanto, note que uma implementação baseada diretamente nessa última seria menos eficiente do que uma implementação baseada diretamente na primeira, uma vez que o número de operações de multiplicação necessárias para o cálculo seria maior nesse último caso.
Escreva um programa que leia vários pares de números inteiros positivos n, p e imprima, para cada par lido, o número de combinações existentes de n objetos p a p. A leitura deve terminar quando um dos valores lidos for menor ou igual a zero.
Escreva um programa que leia, repetidamente, três valores inteiros positivos c, j, t que representam, respectivamente, o capital inicial, a taxa de juros anual e o número de anos de depósito, e imprima, para cada três valores lidos, o saldo final da conta, calculado usando a função acima. A leitura deve terminar quando um dos três valores lidos for menor ou igual a zero.
O resultado de cada item deve ser obtido usando i) um comando de repetição e ii) uma função recursiva.
Escreva um programa que leia repetidamente pares de valores inteiros x, k e imprima, para cada par lido, o resultado de chamar a k-ésima função acima (k variando de 1 a 5) com o argumento x (que representa o número de termos). A leitura deve terminar quando x≤ 0 ou quando k não for um valor entre 1 e 5.
|
Cada função deve receber o valor de x em radianos e o número de parcelas a serem usadas no somatório.
A definição não deve ser feita calculando o fatorial e a exponencial a cada parcela, mas sim de modo que o valor do numerador e do denominador de cada parcela sejam obtidos a partir dos valores respectivos da parcela anterior.
Escreva um programa que leia, do dispositivo de entrada padrão, um número inteiro positivo n, em seguida vários números de ponto flutuante (um a um), que representam valores de ângulos em graus e, para cada valor, imprima o seno e o cosseno desse valor, usando as funções definidas acima com o número de parcelas igual a n. Note que você deve converter graus em radianos nas chamadas às funções para cálculo do seno e cosseno, e que essas funções devem ter um parâmetro a mais que indica o número de parcelas a ser usado.
A entrada deve terminar quando um valor negativo ou nulo for lido.
Por exemplo, para a entrada:
| 1 72 20 15 24 10 3 0 13 14 |
a saída deve conter (os números pares da entrada antes do primeiro zero, ou seja):
| 72 20 24 10 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |
| … | |||||||||
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
| * |
| *** |
| ***** |
| ******* |
| ********* |
| *********** |
| ************* |
| * |
| *** |
| ***** |
| ******* |
| ********* |
| *********** |
| ************* |
| *********** |
| ********* |
| ******* |
| ***** |
| *** |
| * |
| TC = |
|
Use a função definida acima como parte de um programa que receba como argumentos o valor de uma temperatura inicial, o valor de uma temperatura final e um passo p (valor de incremento), e imprima uma tabela de conversão de graus Fahrenheit em graus centígrados, desde a temperatura inicial até o maior valor que não ultrapasse a temperatura final, de p em p graus Fahrenheit.
| 0 | 1 | ||||||||||||
| 1 | 1 | 1 | |||||||||||
| 2 | 1 | 2 | 1 | ||||||||||
| 3 | 1 | 3 | 3 | 1 | |||||||||
| 4 | 1 | 4 | 6 | 4 | 1 | ||||||||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||||
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||||
| 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | ||||
| 9 | 1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | |||
| 10 | 1 | 10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
As entradas em branco nessa tabela têm, de fato, valor igual a zero, tendo sido deixadas em branco para evidenciar o triângulo formado pelas demais entradas da tabela.
Escreva um programa para imprimir o triângulo de Pascal, usando o fato de que
| = |
|
Observação: A fórmula acima pode ser deduzida facilmente de
| = |
|
'\n''\t'A entrada termina com indicação de fim dos dados de entrada (em entrada interativa, Control-z seguido de Enter no Windows, ou Control-d no Linux).
Dicas: Use scanf com formato %c para ler um caractere, e
use o valor retornado por scanf para verificar fim dos dados
de entrada: scanf retorna -1 para indicar fim dos
dados.
Defina e use função que retorna verdadeiro se e somente se o caractere passado como argumento é uma letra; para defini-la, teste se tal caractere está entre ’a’ e ’z’ ou entre ’A’ e ’Z’.
nA < nB e calcular, nesse caso, se a
menor população vai ou não ultrapassar a maior e, em caso
afirmativo, o número de anos necessário para que isso ocorra (em
caso negativo, o programa deve dar como resultado o valor 0).| http://br.spoj.pl/problems/BIT/ |
O problema consiste em escrever um programa para calcular e imprimir, para cada valor inteiro positivo lido, quantas notas de 50, 10, 5 e 1 reais são necessárias para totalizar esse valor, de modo a minimizar a quantidade de notas.
A entrada é composta de vários conjuntos de teste. Cada conjunto de teste é composto por uma única linha, que contém um número inteiro positivo v, que indica o valor a ser considerado. O final da entrada é indicado por v = 0.
Para cada conjunto de teste da entrada seu programa deve produzir
três linhas na saída. A primeira linha deve conter um identificador
do conjunto de teste, no formato "Teste n"n é o
número do teste; os testes são numerados sequencialmente a partir de
1. Na segunda linha devem aparecer quatro inteiros, que representam
o resultado encontrado pelo seu programa: o primeiro inteiro indica
o número de notas de 50 reais, o segundo o número de notas de 10
reais, o terceiro o número de notas de 5 reais e o quarto o número
de notas de 1 real. A terceira linha deve ser deixada em branco.
Por exemplo, para a entrada:
| 1 |
| 72 |
| 0 |
a saída deve ser:
| Teste 1 |
| 0 0 0 1 |
| Teste 2 |
| 1 2 0 2 |
| http://br.spoj.pl/problems/ALADES/ |
O problema consiste em escrever um programa que, dados valores de hora e minutos corrente e hora e minutos de um alarme, determinar o número de minutos entre os dois valores.
A entrada contém vários casos de teste. Cada caso de teste é descrito em uma linha, contendo quatro números inteiros h1, m1, h2 e m2, sendo que h1:m1 representa hora e minuto atuais, e h2:m2 representa hora e minuto para os quais um alarme foi programado (0≤ h1 < 24, 0≤ m1 < 60, 0≤ h2 < 24, 0 ≤ m2 ≤ 60). O final da entrada é indicado por uma linha que contém apenas quatro zeros, separados por espaços em branco. Os dados devem ser lidos da entrada padrão.
Para cada caso de teste da entrada, deve ser impressa uma linha, no dispositivo de saída padrão, contendo um número inteiro que indica o número de minutos entre os dois horários.
Por exemplo, para a entrada:
| 1 5 3 5 |
| 23 59 0 34 |
| 21 33 21 10 |
| 0 0 0 0 |
a saída deve ser:
| 120 |
| 35 |
| 1417 |
A ocorrência de uma vogal pode ser em letra minúscula ou maiúscula; em ambos os casos o número de ocorrências dessa vogal deve ser incrementado.
A impressão das vogais com maior frequência pode usar a vogal minúscula ou maiúscula (escolhendo é claro um dos casos para todas as vogais com maior frequência).
A leitura deve ser feita caractere a caractere, usando a função
getChar. A leitura deve terminar quando getChar
retornar EOF.
getChar retorna um inteiro: EOF quando não há mais dados
a serem lidos, caso contrário retorna o caractere lido (i.e. a
representação do caractere no código ASCII).
Use 5 variáveis para armazenar a frequência de cada vogal, e uma outra variável para indicar a maior frequência. Imprima as vogais com frequência igual a essa maior frequência.
mmc) entre dois ou mais números é
(como o próprio nome diz) o menor inteiro que é múltiplo de todos
eles. Por exemplo, mmc(4,6) é igual a 12. O máximo
divisor comum (mdc) de dois ou mais números inteiros é (como o
próprio nome diz) o maior divisor de todos eles (i.e. o maior valor
que divide exatamente os números). Por exemplo, mdc(4,6) é
igual a 2.Escreva um programa que leia uma sequência qualquer de números inteiros positivos e imprima o mínimo múltiplo comum entre eles.
O programa deve ler os valores da entrada padrão e imprimir o
resultado na saída padrão. Ele deve funcionar para entradas não
interativas. Ou seja, a entrada pode estar em arquivo, especificado
por redirecionamento da entrada padrão. O programa deve terminar com
o fim dos dados de entrada (i.e. o término da entrada é indicado
pelo valor retornado por scanf).
O seu programa deve ser baseado nos fatos de que:
mmc(a,b) = (a / mdc(a,b)) × bOu seja, use o valor de mdc(a,b) para calcular
mmc(a,b), dividindo a por mdc(a,b) e
multiplicando por b.
mmc de três ou mais números pode ser calculado usando o
fato de que: mmc(a,b,c) = mmc(mmc(a, b), c).Ou seja: para calcular mmc de três ou mais números, obtenha o
mmc do resultado de calcular o mmc dos primeiros com o
último.
mdc de dois números a e b deve
ser feito usando o algoritmo definido no Exercício Resolvido
5.