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 #