Поиск циклов функции

haskell
  1. findCycle :: (Eq a) => (a -> a) -> a -> Int
  2. findCycle f x0 = countDistance x0 1
  3.   where
  4.     x1 = getCoincidence (f x0) (f (f x0))
  5.     getCoincidence x0 x1  | x0==x1    = x1
  6.                           | otherwise = getCoincidence (f x0) (f (f x1))
  7.     countDistance x0 n    | x0==x1    = n
  8.                           | otherwise = countDistance (f x0) (n+1)
Поиск циклов в последовательности методом Флойда.

Программа-тест
  1. m :: Int
  2. m = 441
  3.  
  4. gen :: Int -> Int
  5. gen x = x*x `mod` m
  6.  
  7. main :: IO ()
  8. main = putStrLn $ show $ findCycle gen 2
  9.  
  10. findCycle :: (Eq a) => (a -> a) -> a -> Int
  11. findCycle f x0 = countDistance x0 1
  12.   where
  13.     x1 = getCoincidence (f x0) (f (f x0))
  14.     getCoincidence x0 x1  | x0==x1    = x1
  15.                           | otherwise = getCoincidence (f x0) (f (f x1))
  16.     countDistance x0 n    | x0==x1    = n
  17.                           | otherwise = countDistance (f x0) (n+1)
Вывод:
7
Назад

Реклама

Мы в соцсетях

tw tg yt gt