Departamento de Ciência da
Computação - IME - USP
O método das congruências lineares pode ser usado para gerar uma sequência X1,X2,. . ., Xi, Xi+1,. . . de números a partir de um inteiro positivo X0, conhecido como semente. O número Xi+1 da sequência é obtido a partir do número Xi pela fórmula Xi+1 = (aXi + b) mod m
Uma maneira de obter números aleatórios no intervalo [0,1], utilizando o método das congruências lineares, é a divisão dos números da sequência por m.
Para saber se um gerador de números aleatórios é razoavelmente bom, pode-se verificar as frequências dos números gerados.
Escreva um programa em Python que lê os números inteiros a, b, m, X0 e n, gera n números aleatórios no intervalo [0,1] usando o método das congruências lineares, e imprime as frequências de ocorrências dos números nos intervalos [0; 0.2, [0.2; 0.4[, [0.4; 0.6[, [0.6; 0.8[, [0.8; 1.0]. A frequência em um intervalo é a quantidade de vezes que números ocorreram no intervalo, dividido por n.
#--------------------------------------------------------------------
# DEBUG é uma variável usada durante a fase de teste
# NÃO FAZ PARTE DA SOLUÇÃO DA QUESTÃO
#
# DEBUG = True para programa imprimir valores calculados
# DEBUG = False para programa ser executado "silenciosamente"
#
# Sugerimos que você faça algo semelhante durante o desenvolvimento
# dos seus programas
#--------------------------------------------------------------------
DEBUG = True # não faz parte da solução
# valores usados pelo gerador de números aleatórios
a = int(input("Digite o valor de a: "))
b = int(input("Digite o valor de b: "))
m = int(input("Digite o valor de m: "))
# semente do gerador de números aleatórios
X = int(input("Digite o valor e X0: "))
# quantidada de números aleatórios a serem gerados
n = int(input("Digite o valor de n: "))
# contadores de quantidade de número em cada intervalo
# para serem usados nos cálculos das frequências
quant_0_2 = 0
quant_0_4 = 0
quant_0_6 = 0
quant_0_8 = 0
quant_1_0 = 0
i = 0
while i < n:
X = (a*X + b)%m
r = X/m
if DEBUG: # não faz parte da solução
print("DEBUG: X =", X)
print("DEBUG: r =", r)
if r < 0.2:
quant_0_2 = quant_0_2 + 1
elif r < 0.4:
quant_0_4 = quant_0_4 + 1
elif r < 0.6:
quant_0_6 = quant_0_6 + 1
elif r < 0.8:
quant_0_8 = quant_0_8 + 1
else: # neste ponto vale que: 0.8 <= r and r <= 1
quant_1_0 = quant_1_0 + 1
if DEBUG: # não faz parte da solução
print("DEBUG: quant 0 <= r and r < 0.2 =", quant_0_2)
print("DEBUG: quant 0.2 <= r and r < 0.4 =", quant_0_4)
print("DEBUG: quant 0.4 <= r and r < 0.6 =", quant_0_6)
print("DEBUG: quant 0.6 <= r and r < 0.8 =", quant_0_8)
print("DEBUG: quant 0.8 <= r and r <= 1.0 =", quant_1_0)
input("Digite ENTER para continuar.\n")
i = i + 1
print("Frequência no intervalo [0 ;0.2[ =", quant_0_2/n)
print("Frequência no intervalo [0.2;0.4[ =", quant_0_4/n)
print("Frequência no intervalo [0.4;0.6[ =", quant_0_6/n)
print("Frequência no intervalo [0.6;0.8[ =", quant_0_8/n)
print("Frequência no intervalo [0.8;1.0] =", quant_1_0/n)
# SUGESTÃO:
#
# teste o programa acima com os valores do EP2
#
# a = 22695477
# b = 1
# m = 4294967296 (== 2**32)
# X = 10
# n = ?
#
# e observe os valores gerados
Dada uma sequência de números inteiros, o valor absoluto (módulo) da diferença entre dois números consecutivos da sequência corresponde à altura do ``degrau'' entre eles. Por exemplo, na seguinte sequência com 7 números
4 0 -1 2 2 3 8
Escreva um programa em Python que lê um inteiro n$(n ≥ 2) e uma sequência com n números inteiros, e imprime a maior altura de um degrau que ocorre na sequência. Por exemplo, na sequência acima, a maior altura de um degrau na sequência é 5.
#--------------------------------------------------------------------
# DEBUG é uma variável usada durante a fase de teste
# NÃO FAZ PARTE DA SOLUÇÃO DA QUESTÃO
#
# DEBUG = True para programa imprimir valores calculados
# DEBUG = False para programa ser executado "silenciosamente"
#
# Sugerimos que você faça algo semelhante durante o desenvolvimento
# dos seus programas
#--------------------------------------------------------------------
DEBUG = True
# leia o tamanho da sequência
n = int(input("Digite o tamanho da sequência: "))
# leia o primeiro número da sequência
anterior = int(input("Digite um número: "))
# inicialize maior_altura
maior_altura = 0 # as alturas são >= 0
i = 1 # quantidade de números lidos
while i < n:
# neste ponto do programa vale que: a variável maior_altura
# se refere à maior altura de um degrau encontrado na parte da
# sequência que foi lida até aqui.
# leia o próximo número da sequência e incremente o contador de
# números lidos
atual = int(input("Digite um número: "))
i = i + 1
# calcule a altura do degrau entre anterior e atual
altura_degrau = atual - anterior
if altura_degrau < 0:
altura_degrau = -altura_degrau
# verifique se a altura do degrau corrente é maior
# que a maior altura de um degrau até o início da iteração
if altura_degrau > maior_altura:
maior_altura = altura_degrau
# trecho a seguir não faz parte da solução
/*if DEBUG:
print("DEBUG: foram lidos =", i, "números")
print("DEBUG: número anterior =", anterior)
print("DEBUG: número atual =", atual)
print("DEBUG: altura do degrau =", altura_degrau)
print("DEBUG: maior altura =", maior_altura)
input("Digite ENTER para continuar.\n")
# atualize anterior para próxima iteração
anterior = atual
print("A maior altura de um degrau na sequência é: ", maior_altura)
Três números inteiros positivos a, b e c, a &tt; b < c, formam um trio Pitagoreano se a2+ b2 = c2. Por exemplo, os números 3, 4, e 5 formam um trio Pitagoreano pois 32 + 42 = 52.
Alguns números inteiros positivos podem ser escritos como a soma de um trio Pitagoreano. Por exemplo, 12 é um desses números pois 3 + 4 + 5 = 12.
Escreva um programa em Python que lê um número inteiro n (n < 0) e verifica se ele corresponde à soma de um trio Pitagoreano. Em caso afirmativo, o seu programa deve imprimir os valores do trio e, em caso contrário, deve imprimir que o número não é soma de trio Pitagoreano.
Exemplos de entrada e saída:
| Entrada (valor de n) | saída |
| 10 | 10 não é soma de trio Pitagoreano |
| 12 | 12 é soma do trio Pitagoreano (3, 4, 5) |
| 24 | 24 é soma do trio Pitagoreano (6, 8, 10) |
#--------------------------------------------------------------------
# SOLUÇÃO 1: Solucao arroz-com-feijao.
# Usa uma variável booleana (flag) como um inteiro
#
#--------------------------------------------------------------------
# linha a seguir não faz parte da solução
trios_gerados = 0 # contador de trios gerados
# leia o valor de n
n = int(input("Digite um número: "))
# n não é soma de um trio pitagoreano até que se
# prove o contrário
é_soma = 0
a = 1
while a < n and é_soma == 0:
# os candidatos a b são a+1, a+2, ...
b = a + 1
while b < n and é_soma == 0:
# os candidatos a c são b+1, b+2
c = b + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
while c < n and é_soma == 0:
if a*a + b*b == c*c and a + b + c == n:
é_soma = 1
c = c + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
b = b + 1
a = a + 1
print("\nForam gerados", trios_gerados, "trios\n") # não faz parte da solução
if é_soma == 1:
a = a - 1
b = b - 1
c = c - 1
print(n, "é soma do trio Pitagoreano (", a, ",", b, ",", c, ")")
print(a, "*", a, "+", b, "*", b, "=", c, "*", c, "=", c*c) # não faz parte da solução
print(a, "+", b, "+", c, "=", a+b+c) # não faz parte da solução
else:
print(n, "não é soma de trio Pitagoreano")
#--------------------------------------------------------------------
# SOLUÇÃO 2: Idêntica à solução anterior. Usa uma "legitima" variável
# booleana do Python (variável que assume valores True e False)
#
#--------------------------------------------------------------------
# linha a seguir não faz parte da solução
trios_gerados = 0 # contador de trios gerados
# leia o valor de n
n = int(input("Digite um número: "))
# n não é soma de um trio pitagoreano até que se
# prove o contrário
é_soma = False
a = 1
while a < n and not é_soma:
# os candidatos a b são a+1, a+2, ...
b = a + 1
while b < n and not é_soma:
# os candidatos a c são b+1, b+2, ...
c = b + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
while c < n and not é_soma:
if a*a + b*b == c*c and a + b + c == n:
é_soma = True
c = c + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
b = b + 1
a = a + 1
print("\nForam gerados", trios_gerados, "trios\n") # não faz parte da solução
if é_soma:
a = a - 1
b = b - 1
c = c - 1
print(n, "é soma do trio Pitagoreano (", a, ",", b, ",", c, ")")
print(a, "*", a, "+", b, "*", b, "=", c, "*", c, "=", c*c) # não faz parte da solução
print(a, "+", b, "+", c, "=", a+b+c) # não faz parte da solução
else:
print(n, "não é soma de trio Pitagoreano")
#--------------------------------------------------------------------
# SOLUÇÃO 3: Idêntica à solução anterior.
# Apenas procura testar um pouco menos de candidatos a c
# "... c*c <= a*a + b*b ..."
#
# Esta solução é na verdade um passo intermediário entre
# a solução arroz-com-feijão e a solução 4 que tem
# um while a menos.
#--------------------------------------------------------------------
# linha a seguir não faz parte da solução
trios_gerados = 0 # contador de trios gerados
# leia o valor de n
n = int(input("Digite um número: "))
# n não é soma de um trio pitagoreano até que se
# prove o contrário
é_soma = False
a = 1
while a < n and not é_soma:
# os candidatos a b são a+1, a+2, ...
b = a + 1
while b < n and not é_soma:
# os candidatos a c são b+1, b+2, ...
c = b + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
while c*c < a*a + b*b:
c = c + 1
trios_gerados = trios_gerados + 1 # não faz parte da solução
if a*a + b*b == c*c and a + b + c == n:
é_soma = True
b = b + 1
a = a + 1
print("\nForam gerados", trios_gerados, "trios\n") # não faz parte da solução
if é_soma:
a = a - 1
b = b - 1
print(n, "é soma do trio Pitagoreano (", a, ",", b, ",", c, ")")
print(a, "*", a, "+", b, "*", b, "=", c, "*", c, "=", c*c) # não faz parte da solução
print(a, "+", b, "+", c, "=", a+b+c) # não faz parte da solução
else:
print(n, "não é soma de trio Pitagoreano")
#--------------------------------------------------------------------
# SOLUÇÃO 4: Em relação à solução anterior:
#
# * procura gerar menos valores de b: "... b < n - a ..."
# * dados a e b produz apenas um candidato a c "... c = n - a - b ..."
#
#--------------------------------------------------------------------
# linha a seguir não faz parte da solução
trios_gerados = 0 # contador de trios gerados
# leia o valor de n
n = int(input("Digite um número: "))
# n não é soma de um trio pitagoreano até que se
# prove o contrário
é_soma = False
a = 1
while a < n and not é_soma:
# os candidatos a b são a+1, a+2, ..., n-a-1
b = a + 1
while b < n-a and not é_soma:
# dados a e b só existe um candidato a c
c = n - a - b
trios_gerados = trios_gerados + 1 # não faz parte da solução
if a*a + b*b == c*c:
é_soma = True
b = b + 1
a = a + 1
print("\nForam gerados", trios_gerados, "trios\n") # não faz parte da solução
if é_soma:
a = a - 1
b = b - 1
print(n, "é soma do trio Pitagoreano (", a, ",", b, ",", c, ")")
print(a, "*", a, "+", b, "*", b, "=", c, "*", c, "=", c*c) # não faz parte da solução
print(a, "+", b, "+", c, "=", a+b+c) # não faz parte da solução
else:
print(n, "não é soma de trio Pitagoreano")
#--------------------------------------------------------------------
# SOLUÇÃO 5: Em relação à solução anterior apenas:
#
# * testar menos valores de a: "... a < n//3 ..."
# * testar menos valores de b: "... b <= (n-a)//2 ..."
#
# Assim teremos que os trios gerados satisfazem
# a < b < c
#--------------------------------------------------------------------
# linha a seguir não faz parte da solução
trios_gerados = 0 # contador de trios gerados
# leia o valor de n que verificaremos se a soma
# de um trio pitagoreano
n = int(input("Digite um número: "))
# testa para os candidatos a a, b e c se
# n = a*a + b*b + c*c
# n não é soma de um trio pitagoreano até que se
# prove o contrário
é_soma = False
# os candidatos a a são 1, 2, 3, ..., n//3
# aqui estamos usando o fato de a < b < c
a = 1
while a < n//3 and not é_soma:
# os candidatos a b são a+1, a+2, ..., (n-a)//2
b = a + 1
while b <= (n-a)//2 and not é_soma:
# dados a e b só existe um candidato a c
c = n - a - b
trios_gerados = trios_gerados + 1 # não faz parte da solução
if a*a + b*b == c*c:
é_soma = True
b = b + 1
a = a + 1
print("\nForam gerados", trios_gerados, "trios\n") # não faz parte da solução
if é_soma:
a = a - 1
b = b - 1
print(n, "é soma do trio Pitagoreano (", a, ",", b, ",", c, ")")
print(a, "*", a, "+", b, "*", b, "=", c, "*", c, "=", c*c) # não faz parte da solução
print(a, "+", b, "+", c, "=", a+b+c) # não faz parte da solução
else:
print(n, "não é soma de trio Pitagoreano")
/*
# SOLUÇÃO 6: colocaremos aqui qualquer solução que virmos e que
# seja essencialmente diferente das anteriores.
#
# SUGESTÃO:
#
# Teste os programas acima com n = 1000
#