Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 23.03.2018
Сообщений: 10

Погрешность при вычислении процента в цикле

25.03.2018, 01:00. Показов 1074. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте, есть любители олимпиадных задач? Условие на картинке или по ссылке: https://www.e-olymp.com/ru/problems/21

Алгоритм решения довольно прост сортировать массив элементов и брать первые два элемента в массиве, вычислить процент от суммы этих чисел, с последующим возвращением нового числа с вычтенным процентом в массив чтобы массив оставался отсортированным, время на составление алгоритма не забрало много времени и реализация тоже... на языке Python. Однако из-за большого количества времени которое тратится на предварительную сортировку и последующие операции Python справился лишь с 60% тестов, на остальных был перебор по времени и я решил воспользоваться скоростью С++. Кстати, заметил, что на сайте по статиске данной задачи нет ни одного решения на C#, Python, Ruby, Haskell, PHP, как мне кажется по причине скорости.

Не в силах самостоятельно справится с этой задачей на С++, не знаю тонкостей при вычислении процента и корректировке погрешности сведением её до минимума в С++ без использования библиотек; данный код справляется лишь с 85% тестов, ошибки на двух последних и 9. Скорее всего связаны с погрешность при вычислении процента на больших числах, что можно использовать чтобы как можно точнее вычислять значения без потери доли или может быть я что-то упустил при вычислениях?

Буду благодарен любой помощи и наводящим советам.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <vector>
 
using namespace std;
 
int main(void) {
    int account;
    int amount;
    long double p;
    vector<long double> v;
    multiset<long double> ms;
 
    cin >> amount >> p;
 
    while (cin >> account)
        v.push_back(account);
 
    stable_sort(v.begin(), v.end());
 
    ms.insert(v.begin(), v.end());
 
    while (ms.size() != 1) {
        long double a = *(ms.begin());
        ms.erase(ms.begin());
        long double b = *(ms.begin());
        ms.erase(ms.begin());
 
        long double x = a + b;
 
        long double vat = x * (p / 100);
 
        ms.insert(x - int(vat * 100 + 0.5) / 100.0);
    }
    cout << setprecision(20) << *(ms.begin()) << endl;
}
Миниатюры
Погрешность при вычислении процента в цикле  
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.03.2018, 01:00
Ответы с готовыми решениями:

Погрешность при вычислении синуса
вот исходный код программы(вычисляет синус через многочлен Тейлора): #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define PI...

Погрешность при вычислении интеграла
Не подскажете, почему при вычислении определённого интеграла методом Симпсона на шаге m+1 погрешность равна h^3?

Погрешность при вычислении и округлении
Здравствуйте! Мне надо было написать простенькую функцию, которая переводит дробную часть числа из десятичной в q-ую систему счисления....

10
5 / 5 / 6
Регистрация: 23.03.2018
Сообщений: 98
25.03.2018, 01:48
StolenCookie,
Цитата Сообщение от StolenCookie Посмотреть сообщение
ms.insert(x - int(vat * 100 + 0.5) / 100.0);
а что, если в этой строке не int(vat * 100 + 0.5) написать, а использовать функцию round() или ceil() (#include <cmath>)?

и можно писать так cout.precision(20); .
1
0 / 0 / 0
Регистрация: 23.03.2018
Сообщений: 10
26.03.2018, 23:31  [ТС]
Цитата Сообщение от perevertysh Посмотреть сообщение
а что, если в этой строке не int(vat * 100 + 0.5) написать, а использовать функцию round() или ceil() (#include <cmath>)?
Благодарю за совет! К сожаленю не особо влияет на результат
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
26.03.2018, 23:59
StolenCookie, результат может исказиться и при делении на 100. Округляйте также после деления.

Добавлено через 8 минут
C++
1
2
cout << setprecision(2);
ms.insert(x - vat * 100) / 100.0 + 0.00001);
И я бы вообще при денежных расчетах не советовал использовать числа с плавающей точкой. Лучше тот же int. Просто хранить вместе с копейками значение.
1
0 / 0 / 0
Регистрация: 23.03.2018
Сообщений: 10
27.03.2018, 00:05  [ТС]
Цитата Сообщение от QuakerRUS Посмотреть сообщение
Лучше тот же int.
Благодарю, учту. Но как же тогда вычислять процент с типом long long, там уж без деления и умножения на сто раза 2-3 не обойтись чтобы преобразовать всё в копейки, я пробовал примерно то же самое но по результатам доходил максимум до 75%, где-то стабильно закрадывается ошибка в виде тысячных а потом сотых и десятых что скорее всего приводит к искажению
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
27.03.2018, 03:57
StolenCookie, да, про процент ничего в условии не сказано, какой он должен иметь тип.

Добавлено через 3 часа 0 минут
Поковырялся с этой задачей и сделал следующие выводы.

1. В условии задачи не описаны типы переменных, точность входных данных а так же погрешность выходного ответа.
2. В зависимости от расположения бубна при реализации какого то именно четко кем то где то описанного жадного алгоритма с точностью не ниже long double зависит правильность ответов (не дай бог округлится на 0.000000000001 лишний раз).
3. Для финансовой задачи высчитывать остаток на счете числами с плавающей точкой - шизофрения.

Итог: автору задачи двойка, и что б ему икалось от всех, кто его вспоминал, пытаясь подобрать ответы.
1
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
27.03.2018, 15:05
Проблема не в точности. Проблема в том, что задача идиотская.
На типы и прочее пока что все равно
Если писать на даблах - 45%
Если добавлять round при вычислении нового значения - уже 75
Почему? Зачем? Откуда? Где это было сказано?
Да даже если на обычных дробях написать - все равно будет проблемка. Потому что условие идиотское.
Задача на структуры данных - нельзя сюда пихать такой маразм.
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
27.03.2018, 15:11
Ромаха, при long double уже 85% проходит.
0
0 / 0 / 0
Регистрация: 23.03.2018
Сообщений: 10
27.03.2018, 15:14  [ТС]
С float 40%, с double 60% и с long double 85%, я вначале писал на double, думал хватит и потом очень удивился когда при использовании long double вышло 85%, выше уже ничего нет. Это пока максимальный результат которого я добился, и еще если добавить в конце 0.05 засчитываются остыльные два непрошедших теста и один всё равно остаётся с ошибкой.
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
27.03.2018, 16:30
Для максимальной точности надо использовать целые числа. Вот только почему-то у меня выходит бред, ответ на 1 тест не совпадает. Либо я туплю либо
Цитата Сообщение от Ромаха Посмотреть сообщение
Проблема в том, что задача идиотская.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cstdint>
#include <queue>
#include <functional>
 
using LL = std::int64_t;
 
int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    int n, p; 
    std::cin >> n >> p;
    int x;
    LL sum = 0;
    LL psum = 0;
    for (int i = 0; i < n; i++)
        std::cin >> x, q.push(x), sum += x;
    sum *= 100;
    while (q.size() > 1) {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        q.push(a + b);
        psum += 1LL * (a + b) * p;
    }
    LL res = sum - psum;
    std::cout << res / 100 << '.' << res % 100 << '\n';
}
0
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
27.03.2018, 16:31
Новичок, в том то и прикол, что с int64_t у меня вроде только 40% результат получается. Или меньше, не помню уже.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
27.03.2018, 16:31
Помогаю со студенческими работами здесь

Оценить погрешность при вычислении функции
Оценить погрешность при вычислении функции: u=\frac{{x}^{2}{y}^{3}}{{z}^{4}}, если относительные погрешности \delta x=0.04, \delta...

Большая погрешность в вычислении длины кривой
Есть задание: вычислить длину контура эллипса. Входные данные - коэффициенты a и b из канонического уравнения и n - количество точек для...

В цикле do while реализовать подсчёт сложного процента с ежемесячной капитализацией по банковскому вкладу
Два друга решили копить деньги. Первоначальный вклад обоих составил 100$ . Кузьма решил каждый месяц пополнять вклад на 10% от...

Нужно посчитать погрешность измерений (по примеру). Мне не ясно из примера как нашли погрешность
Нужно посчитать погрешность измерений.(по примеру) Мне не ясно из примера как нашли погрешность, понятно,что искали дифференциал, но почему...

При склеивании строк в цикле, уже на пятом цикле возникает переполнение памяти
При склеивании строк в цикле, уже на пятом цикле возникает переполнение памяти. Что не так и как правильно сделать? Не пинайте нуба! ...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru