Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.76/21: Рейтинг темы: голосов - 21, средняя оценка - 4.76
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918

Сложение дробей с округлением

14.11.2021, 02:24. Показов 4854. Ответов 21
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте. Решал задачу со следующим условием:
Дано целое число n.
Найдите значение суммы (РИС. 1)
Здесь ⌊x⌋ — это округление x вниз: наибольшее целое число, не превосходящее x. Формат входных данных
В первой строке записано целое число n (2 <= n <= 10^18). Формат выходных данных
В первой строке выведите одно целое число — значение суммы.
Примеры

ввод 3
вывод 2


ввод 10
вывод 11

решил сделать список числителей, знаменателей и потом все это дело поделить. Закономерно ошибка - тайм лимит. Подскажите, пожалкйста, как оптимизировать решение. Код:

Python
1
2
3
4
n = int(input())
chisl = [i for i in range(n - 1, 0, -1)]
znam = [i ** 2 for i in range(1, n)]
print(sum([int(i / j) for i, j in zip(chisl, znam)]))
рисунок:
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
14.11.2021, 02:24
Ответы с готовыми решениями:

Сложение дробей в цикла
Я вот пытался решить задачу, но что то не то total=0.0 for numerator in range(1,30,1): for denominator in range(30,1,-1): ...

Сложение дробей
Всем доброго времени суток. Получил задание по программированию, но не пойму как решить. Подскажите алгоритм пожалуйста, а если есть...

Сложение дробей
Условие только такое S=1+2/3+3/4+4/5+...9/10 2/3-это дроби две третих например помогите:cry:

21
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
14.11.2021, 02:25  [ТС]
Ограничение по времени:2 секунды
Ограничение по памяти: 512 мебибайт
0
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
14.11.2021, 14:12
Удалено.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 14:29
alilxxey,
Python
1
2
n = int(input())
print(sum(int((n - i) / (i * i)) for i in range(1, n)))
Добавлено через 9 минут
alilxxey, Думаю можно даже так.
Python
1
print(sum(int((n - i) / (i * i)) for i in range(1, int(n ** 0.5))))
0
2431 / 1474 / 633
Регистрация: 01.11.2021
Сообщений: 2,269
14.11.2021, 14:34
Опыта для этого не много, просто было интересно.

Видимо задание для оптимизации вычисления степеней, наверно. Например, если округление в меньшую сторону, то если добавить условие, что числитель меньше знаменателя, то вычислять смысла нет, т.к. все время будет 0, а на это уходит большая часть времени.

В 2сек уложиться невероятно, интересно посмотреть, если кто-то справится для 10** 18.

Просто сумму посчитать можно и так, но мне кажется не в этом суть задания.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
summa = 0
for i in range(n - 1, 1, -1):
 
    ch = i
    zn = (n - i) ** 2
 
    result = ch // zn
 
    if ch < zn:
        break
 
    summa += result
 
print(summa)
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 14:38
Alexarh, мой код выходит за 2 сек, при n = 10^14
1
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
14.11.2021, 14:42  [ТС]
anton78spb, да, я уже написал похожий код:
Python
1
2
3
for i in range(1, n):
        answ += int((n - i) / (i * i))
    return answ
, но и он недостаточно эффективен по времени, думаю, тут надо решать с помощью мат. индукции и просто считать с помощью питона готовую формулу
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 15:07
alilxxey, Там правда у меня ошибочка небольшая. Стандартная, в конце диапазона единичку забыл. Там надо в к корню из n еще +1 добавить.
Python
1
print(sum(int((n - i) / (i * i)) for i in range(1, int(n ** 0.5) + 1)))
0
enx
 Аватар для enx
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
14.11.2021, 15:12
alilxxey, попробуй еще из math извлечение корня и возведение импортнуть, глянь какой будет прирост.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 15:16
alilxxey, Вот так еще на 10% быстрее. Но не в разы.
Python
1
print(sum(int((n - i) / (i * i)) for i in range(2, int(n ** 0.5) + 1)) + n - 1)
Добавлено через 1 минуту
enx, У меня в коде корень берется только один раз, а в квадрат я возвожу простым умножением.
0
enx
 Аватар для enx
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
14.11.2021, 15:24
anton78spb, конечно, я про другой вариант выше говорил.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 16:15
Че-то никак не пойму как это можно ускорить. Количество элементов необходимых для расчета суммы выбрано правильно, он равно корню из n. Т.е. лишних вычислений, с заведомо нулевым результатом не производится. Соответственно при максимальном n = 10^18, у нас получится ряд из 10^9, значений.
Первый элемент суммы всегда равен n - 1.

Добавлено через 19 минут
И еще вопрос. Почему вариант использующий исключительно целочисленное деление.
Python
1
sum((n - i) // (i * i) for i in range(1, int(n ** 0.5) + 1))
Работает дольше, чем вариант с отсеканием дробной части от результата полученного при помощи "обычного" деления.
Python
1
sum(int((n - i) / (i * i)) for i in range(1, int(n ** 0.5) + 1))
0
enx
 Аватар для enx
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
14.11.2021, 16:20
anton78spb, флоты медленные очень, в Питоне так вообще кошмар.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 16:29
Вот такой вариант работает примерно на 25% быстрее предыдущих.
Python
1
sum((n - i) / i // i for i in range(1, int(n ** 0.5) + 1))
Единственное не понятно, почему сумма получается вещественным числом. Т.е. она как-бы "целая", но заканчивается почему-то на ".0" (тока с нулем). Т.е. все слагаемые внутри такие же, с ".0" на конце.
От куда берется этот десятичный разделитель? Мы же сначала делим "обычным" способом, а после делим "нацело", и соответственно результатом деления нацело должно получиться целое число.

Добавлено через 55 секунд
enx, Так прикол-то в том, что в данном примере они работают быстрее чем целочисленные вычисления.
0
enx
 Аватар для enx
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
14.11.2021, 16:35
anton78spb, да все просто на самом деле:

Python
1
print(6.0 // 2)
Bash
1
3.0
Добавлено через 24 секунды
Флоты они такие, всегда найдут способ пробраться )))
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 16:54
Цитата Сообщение от enx Посмотреть сообщение
Флоты они такие, всегда найдут способ пробраться
Спс. Даже представить себе не мог что будет такой результат.

Короче, друзья. Все вышенаписанные варианты, это тупиковая ветвь. Т.к. при n = 10^15, даже сумма "простого ряда" от 1 до корня из n уже считается больше двух секунд. И это без каких-либо вычислений элементов этого ряда.

Python
1
sum(i for i in range(1, int(n ** 0.5) + 1))
Надо искать какое-то математическое решение.

Добавлено через 4 минуты
Также проверил, что sum работает быстрее чем суммировать "ручками" в цикле. И замена sum на fsum из модуля math практически не помогает.
0
enx
 Аватар для enx
1190 / 766 / 277
Регистрация: 05.09.2021
Сообщений: 1,772
14.11.2021, 16:56
anton78spb, глянь как будет на np.sum, он быстрее раз в 10 на таком массиве. Но суть верная, тут нужна формула, я ее не знаю к сожалению тоже. Может кто заглянет, подскажет.
0
1956 / 874 / 352
Регистрация: 05.09.2021
Сообщений: 1,387
14.11.2021, 17:13
Цитата Сообщение от enx Посмотреть сообщение
Но суть верная, тут нужна формула, я ее не знаю к сожалению тоже.
Если взять отношение суммы этого ряда от n к самому n, то у него есть предел, оно стремится к 1.64493....

Добавлено через 5 минут
Цитата Сообщение от enx Посмотреть сообщение
глянь как будет на np.sum
Не помогло, даже медленнее.
0
1 / 1 / 0
Регистрация: 06.08.2021
Сообщений: 2
19.11.2021, 20:14
у меня вот этот код на 70 баллов зашел, тут надо математически решать, вряд ли с помощью индукции

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
from math import floor
 
a = int(input())
summa = 0
if a == 2:
    print(1)
elif a == 3:
    print(2)
else:
    for i in range(1 , floor(a**0.5)):
        h = floor((a - i) / (i ** 2))
        summa += h
    print(summa)
1
712 / 351 / 120
Регистрация: 09.12.2020
Сообщений: 918
20.11.2021, 21:26  [ТС]
RedHathacker, Да, у меня такой же почти код на 68 баллов зашел.
Цитата Сообщение от RedHathacker Посмотреть сообщение
тут надо математически решать, вряд ли с помощью индукции
Ну как раз с помощью математической индукции такие задачи и решаются, просто надо много думать..

Добавлено через 1 минуту
RedHathacker, напиши пожалуйста мне в лс
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
20.11.2021, 21:26
Помогаю со студенческими работами здесь

Сложение дробей
Даны две дроби А/В и С/Д (А, В, С, D — натуральные числа). Составить программу для сложения этих дробей. Результат должен быть...

сложение дробей
Даны две дроби A/B и C/D (А, В, С, D — натуральные числа). Составить функцию сложения этих дробей. Ответ должен быть несократимой дробью.

Сложение дробей
Даны две рациональные дроби: a/b и c/d. Сложите их и результат представьте в виде несократимой дроби m/n

Сложение дробей
Как сложить две дроби? #include&lt;iostream&gt; using namespace std; class Drob { private: float chislet, znamenat;

Сложение дробей.
Я хочу сложить массив дробей. Числитель у меня один массив а знаменательль другой массив. Если бы у меня небыло дробей можно было бы...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита, которое может. . .
Команды "Заполнить" и "Очистить" на форме документа
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа разработанного в конфигурации КА2. В качестве источника данных указан регистр накопления, в который записываются данные о. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru