вторник, 13 сентября 2011 г.

Решение задачи о подсчете количества подчисел числа, на которые оно делится без остатка

Снова на Хабре проскочила статья-конкурс, посвященная Дню Программиста, который отмечается сегодня (кстати, с праздником всех причастных к сему событию :) В статье приводится самая простая задача, собственное решение которой на Хаскеле я и хочу привести ниже.
Итак, условие задачи:
==
Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка. Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4. Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.
==

Мое решение, не претендующее на какую-либо оптимальность:

===
addLst l 0 = gen l [[]] 0
addLst l _ = []

gen [] acc _ = acc
gen (h:t) acc lvl = 
     gen t (reverse (h : head acc) : acc) 1 ++ addLst t lvl

calc _ [] = 0
calc i x  
    | n == 0 = 0
    | i `mod` n == 0 = 1
    | otherwise = 0
    where
       n = read x :: Int  

cnt num = sum $ map (calc num) (tail $ gen (show num) [[]] 0)

main = do 
    print $ cnt 1938
    print $ cnt 1919
    print $ cnt 101
===

Функции addLst и gen предназначены для генерации всех подчисел строчного представления числа n. Функция calc возвращает число 0 или 1 в зависимости от того, делится ли наше заданное на входе число на соответствующее подчисло или нет. Ну и функция cnt, по сути, собирает всё вместе.

Для используемых в функции main чисел 1938, 1919 и 101 программа, соответственно, выдает результаты: 4, 4 и 3.

Комментариев нет:

Отправить комментарий