Novo exercício de Matemática resolvido e postado aqui, gente! Resolvi o Imberbe Matemático de algumas formas diferentes e aqui trago essas soluções para vocês. Esse problema vale 5 pontos no Beecrowd, então bora ver como eu pontuei?
Plataforma: URI (BEECROWD)
Problema: 3312
Linguagens: C, C++ e Haskell
Enunciado:
Guilherme tem dez anos e é um pequeno entusiasta da matemática, e descobriu recentemente a existência dos famosos números primos. Com seu grande interesse pela disciplina, sua professora Marlene já lhe adiantou alguns conteúdos e um deles é o fatorial. Guilherme adora fazer exercícios e deseja treinar mais para preparar‐se para a Olimpíada de Matemática. Marlene passou uma lista de números para Guilherme resolver em casa, na qual todos os números primos encontrados deverão ser encontrados também seu respectivo fatorial. Ajude Guilherme a conferir seus exercícios e estudar para a Olimpíada.
Solução:
Há algumas soluções possíveis. Uma delas é usando o Crivo de Eratóstenes.
Código em C:
#include <stdio.h> #define LIMITE 101 #define TOTAL_PRIMOS 25 #define MAX_VALORES 100000 int main() { int n; int i; int j; int k; int valores[MAX_VALORES]; int primos[LIMITE]; int osPrimos[TOTAL_PRIMOS] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; char *fats[LIMITE]; char *fatoriais[TOTAL_PRIMOS] = {"2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"}; for (i = 0; i < LIMITE; i++) primos[i] = 0; for (i = 0; i < TOTAL_PRIMOS; i++) { j = osPrimos[i]; primos[j] = 1; fats[j] = fatoriais[i]; } scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d ", &valores[i]); for (i = 0; i < n; i++) { k = valores[i]; if (primos[k]) printf("%d! = %s\n", k, fats[k]); } return 0; }
Código em C++:
#include <iostream> #include <string> const int LIMITE = 101; const int TOTAL_PRIMOS = 25; const int MAX_VALORES = 100000; int main() { int n; int i; int j; int k; int valores[MAX_VALORES]; int primos[LIMITE]; int osPrimos[TOTAL_PRIMOS] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; std::string fats[LIMITE]; std::string fatoriais[TOTAL_PRIMOS] = {"2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"}; for (i = 0; i < LIMITE; i++) primos[i] = 0; for (i = 0; i < TOTAL_PRIMOS; i++) { j = osPrimos[i]; primos[j] = 1; fats[j] = fatoriais[i]; } std::cin >> n; for (i = 0; i < n; i++) std::cin >> valores[i]; for (i = 0; i < n; i++) { k = valores[i]; if (primos[k]) std::cout << k << "! = " << fats[k] << std::endl; } return 0; }
Código em Haskell:
Solução 1:
import Control.Monad (mapM_) pertence :: Eq a => a -> [a] -> Bool pertence a [] = False pertence a (x:xs) = a == x || pertence a xs filtro :: (Int -> Bool) -> [Int] -> [Int] filtro p xs = [x | x <- xs, p x] nDivisivel :: Int -> Bool nDivisivel n = mod n (n+1) /= 0 divisor :: Int -> Int -> Int -> Bool divisor 2 _ _ = False divisor _ _ 1 = True divisor _ _ 0 = False divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) crivo :: [Int] -> [Int] crivo [] = [] crivo (x:xs) | divisor 1 x (x-1) = x : crivo xs | otherwise = crivo xs primosAte100 :: [Int] primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] fatoriaisAte100 :: [String] fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"] pares :: [(Int, String)] pares = zip primosAte100 fatoriaisAte100 getResposta [] _ = [] getResposta (x:xs) (y:ys) | x == fst y = (show x ++ "! = " ++ snd y) : getResposta xs pares | otherwise = getResposta (x:xs) ys main :: IO () main = do n <- readLn :: IO Int linha <- getLine let valores = map read (words linha) :: [Int] let primosEncontrados = crivo valores let respostaFinal = getResposta primosEncontrados pares mapM_ putStrLn respostaFinal
Solução 2: parecida, mas com alguns detalhes diferentes.
pertence :: Eq a => a -> [a] -> Bool pertence a [] = False pertence a (x:xs) = a == x || pertence a xs filtro :: (Int -> Bool) -> [Int] -> [Int] filtro p xs = [x | x <- xs, p x] nDivisivel :: Int -> Bool nDivisivel n = mod n (n+1) /= 0 divisor :: Int -> Int -> Int -> Bool divisor 2 _ _ = False divisor _ _ 1 = True divisor _ _ 0 = False divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) crivo :: [Int] -> [Int] crivo [] = [] crivo (x:xs) | divisor 1 x (x-1) = x : crivo xs | otherwise = crivo xs primosAte100 :: [Int] primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] fatoriaisAte100 :: [String] fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"] pares :: [(Int, String)] pares = zip primosAte100 fatoriaisAte100 getAns :: [Int] -> [(Int, String)] -> IO () getAns [] _ = return () getAns (x:xs) (y:ys) | x == fst y = do putStrLn (show x ++ "! = " ++ snd y) getAns xs pares | otherwise = getAns (x:xs) ys main :: IO () main = do n <- readLn :: IO Int linha <- getLine let valores = map read (words linha) :: [Int] let ans = crivo valores getAns ans pares
Solução 3: mais uns detalhes diferentes.
pertence :: Eq a => a -> [a] -> Bool pertence a [] = False pertence a (x:xs) = if a == x then True else pertence a xs filtro :: (Int -> Bool) -> [Int] -> [Int] filtro p [] = [] filtro p (x:xs) = if p x == True then (x: filtro p xs) else (filtro p xs) nDivisivel :: Int -> Bool nDivisivel n = mod n (n+1) /= 0 divisor :: Int -> Int -> Int -> Bool divisor 2 _ _ = False divisor _ _ 1 = True divisor _ _ 0 = False divisor x a b = if mod a b == 0 then divisor (x+1) a (b-1) else divisor x a (b-1) crivo :: [Int] -> [Int] crivo [] = [] crivo (x:xs) = if divisor 1 x (x-1) == True then x:crivo (ys) else crivo (xs) where (y:ys)= filtro nDivisivel (x:xs) primosAte100 :: [Int] primosAte100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] fatoriaisAte100 :: [String] fatoriaisAte100 = ["2", "6", "120", "5040", "39916800", "6227020800", "355687428096000", "121645100408832000", "25852016738884976640000", "8841761993739701954543616000000", "8222838654177922817725562880000000", "13763753091226345046315979581580902400000000", "33452526613163807108170062053440751665152000000000", "60415263063373835637355132068513997507264512000000000", "258623241511168180642964355153611979969197632389120000000000", "4274883284060025564298013753389399649690343788366813724672000000000000", "138683118545689835737939019720389406345902876772687432540821294940160000000000000", "507580213877224798800856812176625227226004528988036003099405939480985600000000000000", "36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000", "850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000", "4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000", "894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000", "39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000", "16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000", "96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000"] pares :: [(Int, String)] pares = zip primosAte100 fatoriaisAte100 getAns :: [Int] -> [(Int, String)] -> IO () getAns [] _ = return () getAns (x:xs) (y:ys) = do if x == fst y then do putStrLn (show x ++ "! = " ++ snd y) getAns xs pares else getAns (x:xs) ys main :: IO () main = do n <- readLn :: IO Int linha <- getLine let valores = map read (words linha) :: [Int] let ans = crivo valores getAns ans pares
Essa é a chave aleatória do blog para doações: 6d8bc7a8-5d74-493a-ab7a-3515baf35956.
Agradeço aos que puderem ajudar!
Valeu e até a próxima!
Nenhum comentário:
Postar um comentário