Форум программистов, компьютерный форум, киберфорум
Наши страницы
Haskell
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
MaBa2014
0 / 0 / 0
Регистрация: 25.02.2018
Сообщений: 5
1

Найти первые 10 цифр для суммы чисел до 1 триллиона, кратных 3, 5, 7, 11 или 13

14.02.2019, 20:15. Просмотров 1270. Ответов 7

Вычислите сумму всех чисел, меньших 1000000000000 (одного триллиона не включительно) кратных 3, 5, 7, 11 или 13. Выведите первые 10 цифр решения.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.02.2019, 20:15
Ответы с готовыми решениями:

Суммировать N 50-значных чисел и вывести на экран первые 10 цифр суммы
День добрый. Нужно найти первые 10 цифр суммы нескольких 50-значных чисел. На первой строке...

Найти первые n чисел, содержащих цифру 7, кратных числу 9 и находящихся в интервале
надо написать на с++ в visual studio. Найти первые n чисел, содержащих цифру 7, кратных числу 9 и...

Найти произведение суммы кратных 3 чисел
Двумерные массивы: Найти произведение суммы кратных 3 чисел в 4-ом столбце на количество нечетных...

Найти первые 120 натуральных чисел, сумма цифр которых равна 10
Люди помогите пожалуйста! Для зачета не хватает одной проги на Си. Не могу понять как ее...

Найти квадрат суммы целых положительных чисел, кратных 5 и меньших числа z
Найти квадрат суммы целых положительных чисел, кратных 5 и меньших числа z ..... (z любое число)....

7
Curry
2991 / 2072 / 257
Регистрация: 01.06.2013
Сообщений: 4,526
Записей в блоге: 9
15.02.2019, 01:05 2
Подозреваю что тут нужно складывать и вычитать суммы арифметических прогрессий.
1
Catstail
Модератор
24831 / 12626 / 2305
Регистрация: 12.02.2012
Сообщений: 20,552
15.02.2019, 09:05 3
Нда... Грубой силой тяжеловато получится...

Добавлено через 21 минуту
Haskell
1
2
3
4
5
6
7
8
9
10
11
sumK :: Integer -> Integer -> Integer
sumK n k =  ((k+m)*p) `div` 2
            where p = (n-1) `div` k
                  m = k*p
 
task :: String
task = take 10 $ show $ (sumK n 3) + (sumK n 5) + (sumK n 7) + (sumK n 11) + (sumK n 13)
       where n=1000000000000
 
Main> task
"4220113220"
0
Black Fregat
3047 / 1655 / 469
Регистрация: 31.05.2009
Сообщений: 5,845
15.02.2019, 10:55 4
Catstail, не всё так просто.. 1001 этот код посчитает целых 3 раза, а по условию надо только 1
Так что минус 10 сумм для попарных произведений, плюс 10 сумм для произведений по 3, минус 5 сумм для произведений по 4 плюс (sumK n 35035)
2
15.02.2019, 10:55
Curry
2991 / 2072 / 257
Регистрация: 01.06.2013
Сообщений: 4,526
Записей в блоге: 9
15.02.2019, 11:04 5
Catstail, в эту сумму некоторые числа попадают не по одному разу. К примеру, 15 есть в прогрессии по 3 и по 5. Т.е. ещё нужно вычитать сумму прогрессии по 15. Но если повычитать все суммы прогрессий комбинаций чисел 3,5,7,11,13, то окажется что мы, вычитали некоторые числа несколько раз, т.к. прогрессии с шагом 3*5 и 7*11 тоже имеют общие элементы, и тогда ещё нужно прибавить сумму прогрессии с шагом 3*5*7*11, и .т.д.
Что бы не записывать сложение и вычитание таких прогрессий вручную нужно соорудить такую рекурсию которая будет генерировать шаги прогрессий для сложения (первый раз [3,5,7,11,13]), на второй итерации шаги прогрессии взаимно комбинируются с перемножением шагов и исключением дублей. Их суммы вычисляются и вычитаются из итога (т.е. знак инвертируется на каждом шаге). и т.д. пока на последнем шаге не получатся после комбинаций все прогрессии одинаковые
- 3*5*7*11*13, что после удаления дублей даст одну прогрессию. Это признак последнего шага.
Вот. Попытался изложить мысль. А сделать готовое у меня, увы, времени нет.
0
loothood
89 / 71 / 11
Регистрация: 07.06.2015
Сообщений: 121
Записей в блоге: 12
15.02.2019, 11:31 6
а с чего вы взяли что нельзя учитывать числа кратные одновременно 3 и 5 например? Я из условия этого не вижу
1
Catstail
Модератор
24831 / 12626 / 2305
Регистрация: 12.02.2012
Сообщений: 20,552
15.02.2019, 12:06 7
Black Fregat, Curry, - да, ошибочка...
0
Curry
2991 / 2072 / 257
Регистрация: 01.06.2013
Сообщений: 4,526
Записей в блоге: 9
17.02.2019, 00:18 8
Лучший ответ Сообщение было отмечено MaBa2014 как решение

Решение

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import Data.List
 
main :: IO ()
main = do
    let maxNum = 1000000000000 :: Integer 
        divisors = [3,5,7,11,13]
        sumK k =  ((k+m)*p) `div` 2 -- (с) Catstail
            where p = (maxNum-1) `div` k
                  m = k*p
        go r d sgn = let z = nub [insert x y| x <- divisors, y <- d, x `notElem` y]
                         r' = r + sgn * sum (map (sumK . product) z)      
                     in case z of
                         [_] -> r'
                         _ -> go r' z $ sgn*(-1)
    putStrLn $ take 10 $ show $ go 0 [[]] 1
--  print $ go 0 [[]] 1 -- for bruteforce compare
-- Brute force
-- print $ sum [i| i <- [1 .. (maxNum-1)], any ((==0).(i `mod`)) divisors]
Алгоритм сравнивал с bruteforce вариантом для maxNum = 20000. Результат совпадает.

Добавлено через 14 минут
или так
Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import Data.List
 
main :: IO ()
main = do
    let maxNum = 1000000000000 :: Integer 
        divisors = [3,5,7,11,13]
        sumK k =  ((k+m)*p) `div` 2 -- (с) Catstail 
            where p = (maxNum-1) `div` k
                  m = k*p
        go r d sgn = let z = nub [x*y| x <- divisors, y <- d, (y `mod` x) /= 0]
                         r' = r + sgn * sum (map sumK z)      
                   in case z of
                     [_] -> r'
                     _ -> go r' z $ sgn*(-1)
    putStrLn $ take 10 $ show $ go 0 [1] 1
3
17.02.2019, 00:18
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2019, 00:18

Найти квадрат суммы целых положительных чисел, кратных 5 и меньших числа z
Найти квадрат суммы целых положительных чисел, кратных 5 и меньших числа z ..... (z любое число)....

Составить программу для вычисления суммы чисел из диапазона от а до b, кратных 7
Добрый день) Помогите, пожалуйста, решить задачу: Составить программу для вычисления суммы чисел...

Среди всех чисел из интервала от А до Б, которые кратны 3, найти количество таких, у которых квадрат суммы цифр равен произведению его цифр.
Среди всех чисел из интервала от А до Б, которые кратны 3, найти количество таких, у которых...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.