Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Оптимизация кода
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Mokujin Mokujin вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.01.2014
По умолчанию Оптимизация кода - 08.01.2014, 01:04

Здравствуйте!
Написал программу, которая находит n элемент последовательности, которая задается рекуррентной формулой: f(0) = 0, f(1) = 0
f(n) = f(n-1) + q(n), где q(n) это наименьший простой делитель числа n.
Преподаватель требует оптимизировать код так, чтобы программа работала достаточно быстро с n<=10^8
haskell Код:
import Control.Monad (replicateM)
import System.Exit

-- Функция для нахождения минимального простого числа,
-- на которое нацело делится переданный параметр
fun :: Int -> Int
fun n = fun' $ 2:[3, 5 .. floor $ sqrt $ fromIntegral n]
    where fun' []     = n
          fun' (x:xs) | n `mod` x == 0 = x
                      | otherwise      = fun' xs

-- Функция для построения n-ого номера указанной
-- в задании последовательности
seq' :: Int -> Int
seq' 0 = 0
seq' 1 = 0
seq' n = seq' (n - 1) + fun n

main        :: IO ()
main        = do str <- getLine --кол-во тестов
                 run $  read  str


run 0      =  return ()
run tc     = do str <- getLine
                print.seq' $ read str
                run (tc - 1)



Также имеется другое решение
haskell Код:
import Control.Monad (forM_, when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Data.List (sort)
powmod :: Integer -> Integer -> Integer -> Integer
powmod b e m =
    let times p q = (p*q) `mod` m
        pow b e x
            | e == 0 = x
            | even e = pow (times b b)
            (e `div` 2) x
            | otherwise = pow (times b b)
            (e `div` 2) (times b x)
    in pow b e 1

isSpsp :: Integer -> Integer -> Bool
isSpsp n a =
    let getDandS d s =
           if even d then getDandS (d `div` 2) (s+1)
                     else (d, s)
        spsp (d, s) =
            let t = powmod a d n
            in if t == 1 then True else doSpsp t s
        doSpsp t s
            | s == 0 = False
            | t == (n-1) = True
            | otherwise = doSpsp ((t*t) `mod` n) (s-1)
    in spsp $ getDandS (n-1) 0


isPrime :: Integer -> Bool
isPrime n =
    let ps = [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]
    in n `elem` ps || all (isSpsp n) ps

rhoFactor :: Integer -> Integer -> Integer
rhoFactor n c =
               let f x = (x*x+c) `mod` n
                   fact t h
                      | d == 1 = fact t' h'
                      | d == n = rhoFactor n (c+1)
                      | isPrime d = d
                      | otherwise = rhoFactor d (c+1)
                      where
                          t' = f t
                          h' = f (f h)
                          d = gcd (t' - h') n
               in fact 2 2

rhoFactors :: Integer -> Integer --функция считает наименьший простой делитель
rhoFactors n =
    let facts n
            | n == 2 = 2
            | even n = 2
            | isPrime n = n
            | otherwise = let f = rhoFactor n 1
                          in f
    in facts n


main        :: IO ()
main        = do str <- getLine
                 run $  read  str


run 0      =  return ()
run tc     = do str <- getLine
                print.func $ read str
                run (tc - 1)
func:: Integer->Integer
func 0 = 0
func 1 = 0
func n = (rhoFactors n) + func(n-1)

Надеюсь на вашу помощь.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация SSD Egorro Накопители 0 30.04.2012 13:07
Оптимизация DocRain Любые вопросы от новичков 6 31.03.2012 00:05
Оптимизация Jean-Esther Haskell 2 02.03.2012 00:16
Оптимизация по скорости Кошмар Python 21 29.01.2008 20:19
Оптимизация программы EiZeRR С/С++ 3 20.11.2006 19:44
Оптимизация на Builder 6 Романнист C++ Builder 1 18.03.2006 11:05
Оптимизация кода выделение символов atomsk С/С++ 6 11.06.2005 13:22
Где взять VW 5 NC оптимизация 7.2 gerasim_sergey Smalltalk 8 01.06.2004 17:55
Оптимизация для Java eloiman Java 0 25.02.2004 14:27
Оптимизация кода BCB LaMiK C++ Builder 6 18.02.2004 18:26
Оптимизация Anonymous PHP 1 29.01.2004 14:37
Анализ кода, семантика, генерация, оптимизация Anonymous Алгоритмы 4 18.02.2003 00:42



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов