Algoritmos e Estruturas de Dados
(1º Ano, 1º Semestre)Licenciatura em
Engª. de Produção
Programas - exemplo
em torno dos seguintes tópicos:
- Algoritmia
- Programação imperativa (Linguagem BASIC)
- Introdução à Programação Estruturada
Pedro Pimenta
Dezembro de 1996, Novembro 1997
Depto. de Informática da Universidade do Minho
Campus de Azurém
Índice
Viva a UMinho 3
Variáveis e Operadores 3
Variáveis e Operadores - I 3
Variáveis e Operadores - II 4
Funções 5
Classificação de triângulos 6
Classificação de triângulos (alternativa...) 7
Fibonacci 9
Fibonacci (refinamentos...) 9
Determinação de divisores de um número 10
Determinação de divisores de um número (refinamentos...) 11
Números primos 12
Números primos (refinamentos ...) 12
Determinação do Factorial de um número 13
Determinação do Factorial de um número (alternativa) 14
Hi-Lo 14
Soma dos algarismos de um número 16
Números amigos 17
Soma dos divisores de um número 17
então... 17
Totobola 18
Totobola (c/ randomize... ) 18
Vectores 19
Vectores - I 19
Crivo de Eratóstenes) 19
Funções 20
Totoloto 20
Totoloto - I 20
Totoloto - II 21
Totoloto - III 22
Arrumador 23
Combinações de n p a p 25
Combinações de n p a p 25
Combinações de n p a p 26
Combinações de n p a p 26
Combinações de n p a p 27
Ficheiros 27
Viva a UMinho
Este primeiro programa deseja chamar a atenção para o aspecto típico de um programa em BASIC:
REM
REM Programa exemplo
REM PP, 96.09
PRINT "Viva a UMinho!"
END
Variáveis e Operadores
As variáveis e os operadores são os elementos-base com que os programadores implementam os algoritmos, escrevendo programas. O seu conhecimento e compreensão são fundamentais para o raciocínio que está na base da construção de um algoritmo.
Variáveis e Operadores - I
Neste exemplo são utilizados alguns dos tipos de variáveis base, assim como os operadores mais simples. Este programa já contém mais instruções que o anterior (). Modifique ou acrescente linhas, e verifique se o programa funciona como está à espera
REM Variáveis e Operadores-I
REM
CLS
' Volume de uma esfera, conhecido o seu raio:
PRINT "Volume de uma esfera:"
raio = 3.4
volume = (3 / 4) * (3.141592) * raio ^ 3
PRINT "Raio, Volume="; raio; volume
' Fórmula resolvente de uma equação de 2º grau
PRINT "Fórmula resolvente:"
a = 3
b = -3
c = .34
PRINT "a x^2 + b x + c = 0"
PRINT a, b, c
REM Implemente as etapas de verificação aos valores de a, b e c
bd = b * b - 4 * a * c
PRINT "raízes:"
x1 = (-b + SQR(bd)) / (2 * a)
x2 = (-b - SQR(bd)) / 2 / a
PRINT "x1="; x1
PRINT "x2="; x2
REM Resto da divisão inteira mod(a,b)
PRINT "Resto da divisão inteira"
a = 23
b = 4
PRINT "Resto da divisão de "; a; "por"; b; ":"; a MOD b
END
Variáveis e Operadores - II
Com este programa prosseguimos a exploração de diferentes tipos de variáveis.
REM Variáveis e Operadores-II
CLS
' Concatenação de "strings" - variáveis alfanuméricas:
PRINT "Concatenação de strings:"
Nome$ = "Vasco"
Apelido$ = "da Gama"
REM Corrija o programa para que apareça no ecrâ "Vasco da Gama"
PRINT Nome$ + Apelido$
REM Variável tipo inteiro (simples - 2 bytes):
a% = 32765
PRINT a%
REM PRINT a% + 10
REM Variável tipo inteiro longo (4 bytes):
b& = 2147483640
PRINT b&
REM PRINT b& + 23
REM Variável tipo real (simples -4 bytes)
c! = 3.4E+38
PRINT c!
REM PRINT c! + 1E+37
REM PRINT c! * 1.1
REM Variável tipo real (dupla - 8 bytes)
d# = 1.7D+308
PRINT d#
REM PRINT d# * 1.1
REM Como exercício, programe a ocorrência de erros de "underflow"
REM Bom trabalho !
END
Funções
Neste programa exemplifica-se a utilização de diversas funções (matemáticas e sobre strings).
Nota: Algumas instruções do programa serão impressas em mais de uma linha... Descubra quais são e não as escreva assim no seu editor de texto ()!
' Exemplos de algumas funções em QBASIC
' PP, 96.11
'
CLS
'Funções matemáticas
a = 4.5 * 7.6
b = INT(a)
PRINT a, b
'Atenção aos argumentos das funções trigonométricas !
pi = 3.1415926#
alfa = 90 * (pi / 180)
PRINT "Alfa:"; alfa
PRINT "cos("; alfa; ")="; COS(alfa), "sin("; alfa; ")="; SIN(alfa)
PRINT "Tg("; alfa; ")="; TAN(alfa)
beta = 60 * (pi / 180)
PRINT "Beta:"; beta
PRINT "COS("; beta; ")="; COS(beta), "SIN("; beta; ")="; SIN(beta)
tangente = 1
gama = ATN(1)
PRINT "O arco cuja tangente é :"; tangente; " é "; gama
PRINT "(ou "; gama * 180 / pi; " graus)"
' Entrada de variáveis
INPUT "Introduza uma variável positiva..."; x
PRINT "A raiz quadrada de"; x; "é "; SQR(x)
PRINT "O quadrado de"; x; "é "; x * x
PRINT x; "elevado a 2.3 é"; x ^ 2.3
PRINT "A raiz cúbica de"; x; "é "; x ^ (1 / 3)
'John Neper - Matemático escocês, 1550-1617.
e = EXP(1)
PRINT "Número de Neper:"; e
s = e ^ 3.45
PRINT "e^"; 3.45; "="; s; "."
a$ = "palavra"
tamanho = LEN(a$)
PRINT "A palavra-"; a$; "-tem "; tamanho; "letras."
esq$ = LEFT$(a$, 3)
dir$ = RIGHT$(a$, 3)
meio$ = MID$(a$, 4, 1)
PRINT esq$, meio$, dir$
PRINT esq$; meio$; dir$
esq$ = UCASE$(esq$)
PRINT esq$; meio$; dir$
esq$ = LCASE$(esq$)
PRINT esq$; meio$; dir$
END
Classificação de triângulos
Este programa implementa um algoritmo para a classificação de triângulos em equilátero, isósceles ou escaleno de acordo com os comprimentos de cada um dos lados.
Nota: Algumas instruções do programa serão impressas em mais de uma linha... Descubra quais são e não as escreva assim no seu editor de texto ()!
REM Classificação de um triângulo
l1 = 4
l2 = 5
l3 = 3
' Etapas de verificação
IF l1 > 0 AND l2 > 0 AND l3 > 0 THEN ' Lados positivos
IF l1 < l2 + l3 AND l2 < l1 + l3 AND l3 < l1 + l2 THEN
IF l1 = l2 AND l2 = l3 THEN
PRINT "TRIÂNGULO RECTÂNGULO"
ELSEIF l1 <> l2 AND l2 <> l3 AND l1 <> l3 THEN
PRINT "TRIÂNGULO ISÓSCELES"
ELSE
PRINT "TRIÂNGULO ESCALENO"
END IF
IF l1 * l1 = l2 * l2 + l3 * l3 OR l2 * l2 = l1 * l1 + l3 * l3 OR l3 * l3 = l1 * l1 + l2 * l2 THEN
PRINT "Triângulo rectângulo !"
END IF
ELSE
PRINT "Erro - Os lados dados não podem constituir um triângulo"
END IF
ELSE
PRINT "Erro - Lado inválido."
END IF
END
Classificação de triângulos (alternativa...)
Um outro algoritmo conduz a um fluxograma e a um programa com um aspecto bastante diferente...
fluxograma
- Não constituindo uma tarefa elementar, o bloco de "verificações" é representado por um rectângulo desenhado a traço interrompido.
- Note a inicialização da variável Li (Lados iguais)
- Em vez de uma sequência de comparações elementares, esta comparação múltipla permite uma representação simbólica mais simples do algoritmo.
Nota: Porque falta o caso Li = 2 ? O que acontece neste caso ?
programa
Nota: Algumas instruções do programa serão impressas em mais de uma linha... Descubra quais são e não as escreva assim no seu editor de texto ()!
Outra Nota: Além da classificação, o programa seguinte também verifica se o triângulo é rectângulo...
'Classificação de um triângulo
l1 = 4
l2 = 4
l3 = 4
CLS
PRINT "Lados :"; l1; l2; l3
LadosIguais = 0
' Etapas de verificação
IF l1 > 0 AND l2 > 0 AND l3 > 0 THEN ' Lados positivos
IF l1 < l2 + l3 AND l2 < l1 + l3 AND l3 < l1 + l2 THEN
IF (l1 = l2) THEN LadosIguais = LadosIguais + 1
IF (l2 = l3) THEN LadosIguais = LadosIguais + 1
IF (l3 = l1) THEN LadosIguais = LadosIguais + 1
SELECT CASE LadosIguais
CASE 0
PRINT "Triângulo escaleno."
CASE 1
PRINT "Triângulo isósceles."
CASE 2
PRINT "???"
CASE 3
PRINT "Triângulo equilátero."
END SELECT
IF l1 * l1 = l2 * l2 + l3 * l3 OR l2 * l2 = l1 * l1 + l3 * l3 OR l3 * l3 = l1 * l1 + l2 * l2 THEN
PRINT "Triângulo rectângulo !"
END IF
ELSE
PRINT "Erro - Os lados dados não podem constituir um triângulo"
END IF
ELSE
PRINT "Erro - Lado inválido."
END IF
END
Fibonacci +)
A sucessão de Fibonacci pode ser definida do seguinte modo:
n1 = 1; n2 = 1; ni = ni-1 + ni-2
conduzindo aos seguintes termos iniciais: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
O programa seguinte ilustra como obter os termos menores que 10000:
'Série de Fibonacci
REM ..... declaração de variáveis ....
a = 1
b = 1
c = a + b
DO
PRINT c
a = b
b = c
c = a + b
LOOP WHILE c < 10000
Fibonacci (refinamentos...)
No exemplo seguinte, o programa permite conhecer os 20 primeiros termos da sucessão de Fibonacci, sendo indicado no output do programa o número de ordem e o valor de cada um dos termos da sucessão:
'Série de Fibonacci
contador = 1
a = 1
PRINT contador, a
contador = contador + 1
b = 1
PRINT contador, b
DO
c = a + b
contador = contador + 1
PRINT contador, c
a = b
b = c
LOOP WHILE contador < 20
O exemplo seguinte ilustra a utilização da estrutura de controlo for ... next, em substituição da estrutura do ... loop while (), para a execução de um número pré-determinado de passos.
'Série de Fibonacci
CLS
contador = 1
soma = 0
a = 1
PRINT contador, a
contador = contador + 1
b = 1
PRINT contador, b
FOR contador = 3 TO 20
c = a + b
PRINT contador, c
a = b
b = c
NEXT contador
Determinação de divisores de um número
A determinação dos divisores de um número (posteriormente utilizada para a determinação de números primos, números amigos, etc) baseia-se na função x módulo y, representada, em BASIC, por x mod y. No exemplo seguinte, são indicados, para cada n, todos os divisores (incluindo o 1 e o próprio n):
' Determinação dos divisores de um número
' PP, 96.11
CLS
FOR n = 2 TO 200
PRINT "Divisores de "; n; ":";
FOR d = 1 TO n
IF n MOD d = 0 THEN PRINT d;
NEXT d
NEXT n
END
Determinação de divisores de um número (refinamentos...)
Neste refinamento, utilizam-se exclusivamente variáveis inteiras, procurando tornar o programa mais rápido (e excluindo os números 1 e n);
' Determinação dos divisores de um número
' PP, 96.11
CLS
FOR n# = 2 TO 200
PRINT "Divisores de "; n#; ":";
FOR d# = 2 TO n# - 1#
IF n# MOD d# = 0 THEN PRINT d#;
NEXT d#
NEXT n#
END
No próximo refinamento, é reduzido (ainda mais...) o espaço de procura:
' Determinação dos divisores de um número
' PP, 96.11
DEFLNG A-B
CLS
FOR A = 2 TO 200
PRINT "Divisores de "; A; ":";
FOR B = 2 TO SQR(A)
IF A MOD B = 0 THEN PRINT B;
NEXT B
NEXT A
END
Números primos
De acordo com a definição de número primo, o programa anterior foi modificado de forma a que, no caso da busca de divisores conduzir a um número de divisores (divisores) nulo, o programa imprima a informação de que o número em questão é primo:
Nota: utilizando a função TIMER ou TIME$, podemos medir com precisão o tempo de execução dos nossos programas...
' Determinação de números primos
' PP, 96.11
CLS
inicio$ = TIME$
inicio = TIMER
FOR n = 2 TO 200
divisores = 0
FOR d = 2 TO n - 1
IF n MOD d = 0 THEN
divisores = divisores + 1
END IF
NEXT d
IF divisores = 0 THEN
PRINT n; "é um número primo"
END IF
NEXT n
PRINT inicio$, TIME$
PRINT TIMER - inicio; "segundos..."
END
Números primos (refinamentos ...)
São bastantes os refinamentos que o programa original permite (Porquê ?) ...
Os mais evidentes consistem em procurar divisores até n/2, e terminar a procura dos divisores de n assim que se encontre um deles... O programa seguinte implementa estas melhorias:
' Determinação de números primos
' PP, 96.11
CLS
FOR n = 2 TO 200
divisores = 0
d = 2
DO
IF (n MOD d = 0) THEN divisores = divisores + 1
d = d + 1
LOOP WHILE ((divisores = 0) AND (d <= n / 2))
IF divisores = 0 THEN
PRINT n; "é um número primo"
END IF
NEXT n
END
Outros refinamentos consistem em procurar números primos apenas entre os números ímpares, assim como procurar divisores apenas até :
' Determinação de números primos
' PP, 96.11
CLS
inicio$ = TIME$
inicio = TIMER
FOR n = 3 TO 200 STEP 2
divisores = 0
d = 2
DO
IF (n MOD d = 0) THEN divisores = 1
d = d + 1
LOOP WHILE ((divisores = 0) AND (d <= SQR(n)))
IF (divisores = 0) THEN
PRINT n; "é um número primo"
END IF
NEXT n
PRINT inicio$, TIME$
PRINT TIMER - inicio; "segundos..."
END
Determinação do Factorial de um número
O programa seguinte calcula o factorial de um número dado, n, multiplicando n por n-1, n-2, ...2.
O facto de operar com inteiros (ainda que long) limita claramente a sua operacionalidade.
' Cálculo do factorial de um número
' PP, 96.11
DEFLNG A-Z
' Qual o factorial de 13 ?
CLS
INPUT "Número "; n
factorial = n
FOR i = n - 1 TO 2 STEP -1
factorial = factorial * i
NEXT i
PRINT "Factorial="; factorial
END
Determinação do Factorial de um número (alternativa)
Com a utilização de variáveis double, podemos calcular factoriais de ordens de grandeza muito superiores !
' Cálculo do factorial de um número
' PP, 96.11
DEFDBL A-Z
CLS
INPUT "Número "; n
factorial = n
FOR i = n - 1 TO 2 STEP -1
factorial = factorial * i
NEXT i
PRINT "Factorial="; factorial
END
Hi-Lo
Este programa pretende dar ao computador um algoritmo que o permita adivinhar o número (entre 1 e 100) em que uma pessoa esteja a pensar: o computador sugere um palpite, e a pessoa deverá dizer se esse palpite é igual, menor ou maior que o número em que está a pensar...
fluxograma
Neste fluxograma, os blocos de comparação estão indicados em losangos indicados a traço interrompido, já que não são tarefas elementares.
programa
' Hi-Lo
' PP, 96.10
CLS
min = 1
max = 100
FimDoCiclo = 0
DO
palpite = INT(.5 * (min + max))
PRINT palpite;
INPUT resposta$
SELECT CASE resposta$
CASE "="
PRINT "Acertei !"
FimDoCiclo = 1
CASE "+"
PRINT "Numero secreto maior que "; palpite
min = palpite
CASE "-"
PRINT "Numero secreto menor que "; palpite
max = palpite
END SELECT
LOOP WHILE FimDoCiclo = 0
' Como poderemos determinar o número de tentativas
' necessárias para chegar ao valor certo ?
END
Soma dos algarismos de um número
Problema-tipo das disciplinas de introdução à programação, o algoritmo seguinte aproveita as propriedades da divisão de inteiros e da função x módulo y:
fluxograma
- Seja x um inteiro;
- Podemos calcular a soma dos algarismos de qualquer inteiro, ou deve x verificar algumas condições particulares ?
- Inicialização da variável soma
- Determinação do algarismo das unidades...
- Obtenção de um novo x por exclusão do algarismo das unidades...
programa
' Soma dos algarismos de um número
' PP, 96.11
CLS
INPUT "Valor "; x#
soma = 0
WHILE x# > 0
soma = soma + x# MOD 10
x# = x# / 10
WEND
PRINT "Soma dos algarismos = "; soma
END
Números amigos
O exemplo seguinte baseia-se na definição: "Dois números, n1 e n2, dizem-se amigos se a soma dos divisores de n1 for igual a n2 e a soma dos divisores de n2 for igual a n1"
Soma dos divisores de um número
Comecemos por ver como poderemos calcular a soma dos divisores de um número...
' Soma dos divisores de um número
' PP, 96.11
DEFLNG A-B
CLS
FOR N = 2 TO 50
SDD = 0
PRINT "Divisores de "; N; ":";
FOR B = 2 TO N / 2
IF N MOD B = 0 THEN
PRINT B;
SDD = SDD + B
END IF
NEXT B
SELECT CASE SDD
CASE 0:
PRINT " Número primo"
CASE ELSE
PRINT " SDD:"; SDD
END SELECT
NEXT N
END
então...
poderemos utilizar as ideias do programa anterior para resolver o problema original...
' Soma dos divisores de um número - Números amigos.
' PP, 96.11
DEFLNG A-B
CLS
FOR n1 = 2 TO 500
sdn1 = 0
FOR b = 2 TO n1 / 2
IF n1 MOD b = 0 THEN sdn1 = sdn1 + b
NEXT b
sdn2 = 0
FOR b = 2 TO sdn1 / 2
IF sdn1 MOD b = 0 THEN sdn2 = sdn2 + b
NEXT b
IF (n1 = sdn2) THEN PRINT n1; " e "; sdn1; "são números amigos"
NEXT n1
END
Totobola
A utilização de números aleatórios permite um grande número de exemplos... A geração de matrizes de totobola é seguramente uma das mais citadas... Como alterar este programa de forma a gerar uma chave nova cada vez que é executado ?
' Chave de totobola
' PP, 96.11
CLS
RANDOMIZE TIMER
FOR i = 1 TO 13
PRINT USING "Jogo ## "; i;
resultado = RND
IF resultado < .33333 THEN
PRINT "1"
ELSEIF (resultado < .6666666) THEN
PRINT " X"
ELSE PRINT " 2"
END IF
NEXT i
END
Totobola (c/ randomize... )
De forma a obter uma chave diferente cada vez que se executa o programa, poderemos utilizar a função randomize baseada no TIMER:
' Chave de totobola
' PP, 96.11
CLS
RANDOMIZE TIMER
FOR i = 1 TO 13
PRINT USING "Jogo ## "; i;
SELECT CASE INT(3 * RND)
CASE 0
PRINT "1"
CASE 1
PRINT " X"
CASE 2
PRINT " 2"
CASE ELSE
PRINT "Algo correu mal ..."
END SELECT
NEXT i
END
Vectores
Como declarar vectores? Como inicializar vectores? Quais as principais tarefas a desempenhar sobre vectores?
Vectores - I
Declaração e inicialização de um vector de 15 elementos.
' Utilização de DIM()
' PP, 96.11
CLS
DIM x(100)
RANDOMIZE TIMER
FOR i = 1 TO 100
x(i) = INT(20 * RND)
' x(i) = 5+int(15*rnd)
' x(i) = (50 + INT(150 * RND)) / 10
PRINT x(i)
NEXT i
' Implementação de funções estatísticas....
' Qual o valor mínimo ?
' Qual o valor máximo ?
' Quantas vezes aparece cada valor ?
' Qual a média global ?
' ...
END
Crivo de Eratóstenes)
O crivo de Eratóstenes pode ser implementado utilizando um vector como indicador da existência de divisores de um dado número, de forma a determinar números primos...
' Crivo de Eratóstenes
' PP, 96.11
DEFLNG A-B
DIM numero(100)
CLS
FOR n = 2 TO 100
multiplo = 2 * n
WHILE (multiplo <= 100)
numero(multiplo) = 1
multiplo = multiplo + n
WEND
NEXT n
FOR i = 1 TO 100
IF (numero(i) = 0) THEN PRINT i; "é primo."
NEXT i
END
Funções
Os exemplos Totoloto e Combinações de n p a p pretendem familiarizar o estudante com o conceito de função, assim como com algumas ideias alternativas para a sua implementação.
Totoloto
Este conjunto de programas pretende mostrar as etapas de criação de um programa capaz de gerar um chave para o totoloto.
Totoloto - I
Este primeiro programa utiliza a capacidade de gerar números aleatórios para obter 6 números, não-repetidos, na gama adequada ({1,2,..., 49}) ... mas não estarão ordenados em ordem crescente...
' Chave de totoloto
' PP, 96.11
DIM n(10)
CLS
RANDOMIZE TIMER
n(1) = 1 + INT(49 * RND)
i = 2
DO
n(i) = 1 + INT(49 * RND)
repetido = 0
FOR j = 1 TO i - 1
IF n(j) = n(i) THEN repetido = 1
NEXT j
IF (repetido = 0) THEN
' PRINT n(i)
i = i + 1
ELSE
PRINT "Repetido !"
END IF
LOOP WHILE (i < 7)
PRINT "Chave do totoloto"
FOR i = 1 TO 6
PRINT n(i)
NEXT i
' O que fazer para escrever a chave ordenada ?
'
END
Totoloto - II
Esta versão inlui uma função que ordena por ordem crescente os números obtidos:
' Ordenação de um vector de números
' Chave de totoloto ordenada
' PP, 96.12
DECLARE FUNCTION ordena! (v!())
DIM n(10)
CLS
RANDOMIZE TIMER
n(1) = 1 + INT(49 * RND)
i = 2
DO
n(i) = 1 + INT(49 * RND)
repetido = 0
FOR j = 1 TO i - 1
IF n(j) = n(i) THEN repetido = 1
NEXT j
IF (repetido = 0) THEN
' PRINT n(i)
i = i + 1
ELSE
PRINT "Repetido !"
END IF
LOOP WHILE (i < 7)
PRINT "Chave do totoloto"
FOR i = 1 TO 6
PRINT n(i)
NEXT i
' O que fazer para escrever a chave ordenada ?
r = ordena(n())
PRINT "Chave do totoloto ordenada"
FOR i = 1 TO 6: PRINT n(i): NEXT
END
FUNCTION ordena (v())
' Bubble-sort
' troca - variável que indica a ocorrência de uma troca
DO
troca = 0
FOR i = 1 TO 5
IF v(i) > v(i + 1) THEN
SWAP v(i), v(i + 1)
troca = 1
END IF
NEXT i
LOOP WHILE (troca = 1)
END FUNCTION
Totoloto - III
Nesta última versão, a função de ordenação foi modificada, de modo a permitir comparar o vector original e o vector ordenado:
' Ordenação de um vector de números
' Chave de totoloto ordenada
' PP, 96.12
DECLARE FUNCTION ordena! (v!(), n, o())
DIM n(10), o(10)
CLS
RANDOMIZE TIMER
n(1) = 1 + INT(49 * RND)
i = 2
DO
n(i) = 1 + INT(49 * RND)
repetido = 0
FOR j = 1 TO i - 1
IF n(j) = n(i) THEN repetido = 1
NEXT j
IF (repetido = 0) THEN
' PRINT n(i)
i = i + 1
ELSE
PRINT "Repetido !"
END IF
LOOP WHILE (i < 7)
PRINT "Chave do totoloto"
FOR i = 1 TO 6
PRINT n(i)
NEXT i
' O que fazer para escrever a chave ordenada ?
r = ordena(n(), 6, o())
PRINT "Chave(s) do totoloto:"
PRINT "Original", "Ordenada "
FOR i = 1 TO 6: PRINT n(i), o(i): NEXT
END
FUNCTION ordena (v(), n, o())
' Bubble-sort
' troca - variável que indica a ocorrência de uma troca
' Inicialização
FOR i = 1 TO n
o(i) = v(i)
NEXT i
DO
troca = 0
FOR i = 1 TO 5
IF o(i) > o(i + 1) THEN
SWAP o(i), o(i + 1)
troca = 1
END IF
NEXT i
LOOP WHILE (troca = 1)
END FUNCTION
Arrumador
A grande vantagem da utilização de funções é a possibilidade de voltar a utilizá-las mais tarde - neste exemplo, o objectivo é o de dividir os elementos de um conjunto original em subconjuntos cuja soma dos elementos não ultrapassem um dado valor-limite. A etapa de ordenação é efectuada por uma função ligeiramentemais completa que a anterior (indicada na página seguinte):
' Arrumador
' PP, 96.12
DECLARE FUNCTION ordena! (ordem, n!, v!(), o!())
CLS
RESTORE vector
READ dv
DIM n(dv), arrumado(dv), sc(dv), no(dv)
PRINT "Vector original:"
FOR i = 1 TO dv
READ n(i)
soma = soma + n(i)
PRINT n(i);
NEXT i
PRINT "Soma:"; soma
r = ordena(-1, dv, n(), no())
IF (r <> 1) THEN
PRINT "Erro na ordenação."
END
END IF
PRINT "Vector ordenado:"
FOR i = 1 TO dv: PRINT n(i); : NEXT: PRINT
a = TIMER
PRINT "SUB-CONJUNTOS:"
subconjunto = 0
arrumados = 0
DO
subconjunto = subconjunto + 1
PRINT "SUBCONJUNTO "; subconjunto; ":";
DO
maisalgum = 0
FOR i = 1 TO dv
IF arrumado(i) = 0 AND sc(subconjunto) + n(i) <= 100 THEN
PRINT n(i);
arrumado(i) = 1
arrumados = arrumados + 1
sc(subconjunto) = sc(subconjunto) + n(i)
maisalgum = 1
END IF
NEXT i
LOOP WHILE (maisalgum)
PRINT "S:"; sc(subconjunto)
LOOP WHILE (arrumados < dv)
b = TIMER
PRINT "Arrumação conseguida em"; b - a; "segundos."
END
vector:
DATA 18
DATA 50, 30, 51, 52, 29, 30, 52, 32, 29, 25, 28,25,28,26,24,25,27,27
FUNCTION ordena (ordem, n, v(), o())
ordena = 1
DO
troca = 0
FOR i = 1 TO n - 1
SELECT CASE ordem
CASE 1:
IF v(i) < v(i + 1) THEN
SWAP v(i), v(i + 1)
troca = 1
END IF
CASE -1:
IF v(i) > v(i + 1) THEN
SWAP v(i), v(i + 1)
troca = 1
END IF
CASE ELSE
ordena = -1
END SELECT
NEXT i
LOOP WHILE (troca = 1)
END FUNCTION
Combinações de n p a p
Os exemplos que se seguem procuram indicar as etapas de desenvolvimento de um programa destinado ao cálculo de combinações de n elementos p a p, partindo da equação:
Combinações de n p a p
Na primeira versão, o cálculo do factorial de cada termo é efectuado com recurso a um ciclo for ... next independente:
' Cálculo Combinatório
' PP, 96.12
CLS
PRINT "Cálculo de combinações de n p a p"
INPUT "Valor de n"; n
INPUT "Valor de p"; p
factn = n
FOR i = n - 1 TO 2 STEP -1
factn = factn * i
NEXT i
factp = p
FOR i = p - 1 TO 2 STEP -1
factp = factp * i
NEXT i
factnmp = (n - p)
FOR i = n - p - 1 TO 2 STEP -1
factnmp = factnmp * i
NEXT i
cnpp = factn / (factp * factnmp)
PRINT "Combinações de"; n; p; "a"; p; "="; cnpp
END
Combinações de n p a p
Esta segunda versão utiliza uma função para o cálculo do factorial dos termos intervenientes (n, p e n-p):
DECLARE FUNCTION fact! (n!)
' Cálculo Combinatório
' PP, 96.12
CLS
PRINT "Cálculo de combinações de n p a p"
INPUT "Valor de n"; n
INPUT "Valor de p"; p
cnpp = fact(n) / (fact(p) * fact(n - p))
PRINT "Combinações de"; n; p; "a"; p; "="; cnpp
END
FUNCTION fact (n)
f = n
FOR i = n - 1 TO 2 STEP -1
f = f * i
NEXT i
fact = f
END FUNCTION
Combinações de n p a p
Na terceira versão, a utilização de variáveis static permite acompanhar a execução do programa:
DECLARE FUNCTION fact! (n!)
' Cálculo Combinatório
' PP, 96.12
CLS
PRINT "Cálculo de combinações de n p a p"
INPUT "Valor de n"; n
INPUT "Valor de p"; p
cnpp = fact(n) / (fact(p) * fact(n - p))
PRINT "Combinações de"; n; p; "a"; p; "="; cnpp
END
FUNCTION fact (n)
STATIC v
v = v + 1
PRINT "Chamada"; v; "n="; n
f = n
FOR i = n - 1 TO 2 STEP -1
f = f * i
NEXT i
fact = f
END FUNCTION
Combinações de n p a p
Na quarta versão, a função é implementada de forma recursiva - o recurso a uma variável static e alguns print's na função tem como objectivo fazer compreender melhor como funciona uma função recursiva:
DECLARE FUNCTION fact! (n!)
' Cálculo Combinatório
' PP, 96.12
CLS
PRINT "Cálculo de combinações de n p a p"
INPUT "Valor de n"; n
INPUT "Valor de p"; p
cnpp = fact(n) / (fact(p) * fact(n - p))
PRINT "Combinações de"; n; p; "a"; p; "="; cnpp
END
FUNCTION fact (n)
STATIC v
v = v + 1
PRINT "Chamada"; v; "n="; n
IF (n = 1) THEN
fact = 1
PRINT "---------------------"
ELSE
fact = n * (fact(n - 1))
END IF
END FUNCTION
Ficheiros
Neste exemplo são indicadas as formas mais frequentes de operar com ficheiros.
' Utilização de ficheiros...
' PP, 97.01
CLS
a = 34: b$ = "--------"
OPEN "teste1" FOR OUTPUT AS #1
PRINT #1, a; b$
PRINT #1, a, b$
CLOSE #1
PRINT "O conteúdo do ficheiro é:"
SHELL ("type teste1")
OPEN "teste1" FOR APPEND AS #4
PRINT #4, "Valor de a:"; a
PRINT #4, "Valor de b$:"; b$
CLOSE #4
PRINT "... e foi actualizado para :"
SHELL ("type teste1")
PRINT "Outro exemplo:"
a = 111: b = 222
OPEN "teste2" FOR OUTPUT AS #1
WRITE #1, a, b
PRINT #1, a, b
CLOSE #1
SHELL ("type teste2")
PRINT "Valores lidos do ficheiro:"
OPEN "teste2" FOR INPUT AS #1
INPUT #1, c, d
PRINT "c,d:"; c, d
INPUT #1, e, f
PRINT "e,f:"; e, f:
CLOSE #1
Nenhum comentário:
Postar um comentário