Форум программистов, компьютерный форум CyberForum.ru

ускорение времени выполнения программы - C++

Восстановить пароль Регистрация
 
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 20:10     ускорение времени выполнения программы #1
здравствуйте. решал олимпиадную задачу:

...Он берет произвольное положительное число А и выписывает на доске арифметическую прогрессию с первым членом равным А и разницей, равной также А, то есть имеем последовательность А, А + А, А + 2А, а + 3А, .... Степана интересует первое число данной последовательности, которое является полным кубом некоторого натурального числа. Степан доказал, что для любого натурального числа А в описанной выше арифметической прогрессии существует полный куб некоторого натурального числа.
Например, первый член арифметической прогрессии 2, тогда должны выписать на доске последовательность 2, 4, 6, 8, ... Четвертый член этой арифметической прогрессии является полным кубом числа 2 (8 = 23).
Напишите программу, которая для заданного числа А, определяет минимальное количество членов арифметической прогрессии, которые нужно выписать на доске, чтобы среди них был полный куб некоторого натурального числа.
Входные данные:

Единственная строка входного файла содержит одно целое число А (1 ≤ А ≤ 109).
Выходные данные:

Выходной файл должен содержать одно целое число - минимальное количество членов арифметической прогрессии, которые нужно выписать на доске, чтобы среди них был полный куб.

Пояснение:
Первый пример: четвертый член этой арифметической прогрессии (2, 4, 6, 8, ...) является полным кубом числа 2 (8 = 2^3).
Другой пример: второй член этой арифметической прогрессии (4, 8, ...) является полным кубом числа 2 (8 = 2^3).
Третий пример: первый член этой арифметической прогрессии (125, ...) является полным кубом числа 5 (125 = 5^3).


я написал такой код:
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
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> ar(10000);
int a=0;
int prog(int a){
    int b =a;
    int c=1;
    while(true){
        c++;
        a+=b;
        if(find(ar.begin(), ar.end(), a) != ar.end()){
            return c;
            break;
        }
    }
}
ofstream fout("interesting.out");
int main(){
    ifstream fin("interesting.in");
    fin>>a;
    for(int i =1; i<=ar.size(); i++){
        ar[i]=pow(i,3);
    }
    if(find(ar.begin(), ar.end(), a) != ar.end())
    {
      fout << 1;
    }
    else{
         fout << prog(a);
    }
    return 0;
}
она рабочий , но время выполнения превышает лимит, указанный в правилах...
какие есть способы ускорить?
надеюсь получить помощь с вашей стороны))
спасибо за внимание.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2016, 20:10     ускорение времени выполнения программы
Посмотрите здесь:

Ошибка времени выполнения C++
C++ Подсчет времени выполнения сортировки
C++ Уменьшение времени выполнения цикла
C++ Ошибка времени выполнения.
Оптимизация времени выполнения C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
_Valera_
 Аватар для _Valera_
486 / 368 / 94
Регистрация: 27.01.2015
Сообщений: 1,588
28.01.2016, 20:35     ускорение времени выполнения программы #2
Цитата Сообщение от Prolamer Посмотреть сообщение
C++
1
2
int a=0;
int prog(int a){
нужно больше конфликтов имен...

Цитата Сообщение от Prolamer Посмотреть сообщение
C++
1
vector<int> ar(10000);
это бред искать все числа и их кубы на отрезке, мне кажется что быстрей будет просто брать корень в самой функции.

Если уже для такого способа, то юзай дерево, что ли

Добавлено через 2 минуты
Цитата Сообщение от Prolamer Посмотреть сообщение
она рабочий
точно?
Цитата Сообщение от Prolamer Посмотреть сообщение
C++
1
2
3
4
5
6
7
if(find(ar.begin(), ar.end(), a) != ar.end())
* * {
* * * fout << 1;
* * }
* * else{
* * * * *fout << prog(a);
* * }
что-то я не вижу еще одного цикла для проверки всех чисел из файла.
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 21:08  [ТС]     ускорение времени выполнения программы #3
рабочий точно
извините, я не совсем понял зачем ещё один цикл? в файле ведь одно число
_Valera_
 Аватар для _Valera_
486 / 368 / 94
Регистрация: 27.01.2015
Сообщений: 1,588
28.01.2016, 21:10     ускорение времени выполнения программы #4
Цитата Сообщение от Prolamer Посмотреть сообщение
в файле ведь одно число
ну я весь вопрос не читал, и предположил что там набор из нескольких тестов.

но если там всего один тест, то зачем делать минимум 10000 операций, еще до начала поиска?
Цитата Сообщение от Prolamer Посмотреть сообщение
for(int i =1; i<=ar.size(); i++){
* * * * ar[i]=pow(i,3);
* * }
просто ищи корень.
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 21:48  [ТС]     ускорение времени выполнения программы #5
Цитата Сообщение от Dimension Посмотреть сообщение
del it
спасибо Вам большое
очень помогли

Добавлено через 37 минут
Цитата Сообщение от _Valera_ Посмотреть сообщение
но если там всего один тест, то зачем делать минимум 10000 операций, еще до начала поиска?
Цитата Сообщение от Prolamer Посмотреть сообщение
for(int i =1; i<=ar.size(); i++){
* * * * ar[i]=pow(i,3);
* * }
просто ищи корень.
если вас правильно понял, то
C++
1
2
3
4
5
6
7
if(isdigit(cbrt(aa))){
 
            cout << 1;
        }
        else{
           cout << prog(aa);
        }
вот так вот попробовал, но не получилось...
вы уж извините, совсем новичок
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
28.01.2016, 22:08     ускорение времени выполнения программы #6
Цитата Сообщение от Prolamer Посмотреть сообщение
спасибо Вам большое
очень помогли
не было время дописать ,киньте ссылку на задачу
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 22:14  [ТС]     ускорение времени выполнения программы #7
Цитата Сообщение от Dimension Посмотреть сообщение
не было время дописать ,киньте ссылку на задачу
1. она на украинском, и я перевёл всё, кроме первых двух предложений, которые никак не влияют на решение задачи.
2. не могу кинуть ссылку по причине того, что я решаю эту задачу в закрытом тренировочном туре, логин и пароль для доступа даются классным руководителем...
если, конечно , важно, то могу заскринить
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
28.01.2016, 22:24     ускорение времени выполнения программы #8
Prolamer, думаю ваш скрин не сможет код проверить ,хотя бы ограничение по времени напишите
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 22:30  [ТС]     ускорение времени выполнения программы #9
Цитата Сообщение от Dimension Посмотреть сообщение
Prolamer, думаю ваш скрин не сможет код проверить ,хотя бы ограничение по времени напишите
как-то так...
Миниатюры
ускорение времени выполнения программы  
_Valera_
 Аватар для _Valera_
486 / 368 / 94
Регистрация: 27.01.2015
Сообщений: 1,588
28.01.2016, 22:58     ускорение времени выполнения программы #10
Цитата Сообщение от Prolamer Посмотреть сообщение
вот так вот попробовал, но не получилось...
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 <math.h>
 
int main()
{
    for (int i = 1;i <= 109;++i)
    {
        int x = i;//то что ты считаешь из файла. 
        int step = x;
        while (true)
        {
 
            float y = pow(x, 1.0 / 3);
 
            if (!((int)y - y))
            {
                std::cout <<"test "<<i <<"  "<< x <<" "<<y<< std::endl;
                break;
            }
 
            x += step;
        }
    }
    system("PAUSE");
    return 0;
}
возможно так, у меня все тесты меньше чем за секунду прошел. Ну если я правильно понял условие.
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
29.01.2016, 01:28     ускорение времени выполнения программы #11
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от _Valera_ Посмотреть сообщение
Ну если я правильно понял условие.
не 109 а 109

проверьте
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
39
40
41
42
43
44
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;
vector<pair<int, int> >a;
const int N = 10005;
int lp[N + 1];
int main() {
    ios_base::sync_with_stdio(false);
    int b, c = 0;
    cin>>b;
    vector<int> pr;
    for (int i = 2; i <= N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j<(int)pr.size() && pr[j] <= lp[i] && i*pr[j] <= N; ++j)
            lp[i * pr[j]] = pr[j];
    }
    for (int i = 0;pr[i]*pr[i]*pr[i] <= b;i++) {
        if (b%pr[i] == 0) {
            while (b%pr[i] == 0) {
                c++;
                b /= pr[i];
            }
            a.push_back(make_pair(pr[i], c));
            c = 0;
        }
    }
    if (b > 1)
        a.push_back(make_pair(b, 1));
    ll ans = 1;
    for (int i = 0;i < a.size();i++) 
        if (a[i].second % 3) {
            int t = 3 - (a[i].second % 3);
            a[i].second += t;
            ans *= pow(a[i].first,t);
        }
    cout << ans<<endl;
    
    cin.get(), cin.get();
    return 0;
}
zer0mail
2180 / 1863 / 187
Регистрация: 03.07.2012
Сообщений: 6,627
Записей в блоге: 1
29.01.2016, 01:34     ускорение времени выполнения программы #12
Думаю, для начала надо разложить А на простые множители.
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 09:39  [ТС]     ускорение времени выполнения программы #13
Dimension,
спасибо Вам большое))
вот результат, программа работает достаточно быстро, а с остальным попытаюсь разобраться сам
к сожалению, я не полностью понимаю ваш код, но, думаю, это из-за моей неопытности
Миниатюры
ускорение времени выполнения программы  
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 09:43  [ТС]     ускорение времени выполнения программы #14
спасибо всем большое!
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
29.01.2016, 10:47     ускорение времени выполнения программы #15
Prolamer, там ошибки есть в коде ,и последние тесты из-за переполнения не проходят
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ll long long
using namespace std;
vector<pair<int, int> >a;
const int N = 70000;
const int base = 1000000000;
int lp[N + 1];
inline void mul(vector<ll> &a,ll b) {
    int carry = 0;
    for (size_t i = 0; i<a.size() || carry; ++i) {
        if (i == a.size())
            a.push_back(0);
        long long cur = carry + a[i] * 1ll * b;
        a[i] = int(cur % base);
        carry = int(cur / base);
    }
    while (a.size() > 1 && a.back() == 0)
        a.pop_back();
}
int main() {
    ios_base::sync_with_stdio(false);
    int in, c = 0;
    cin>>in;
    vector<int> pr;
    for (int i = 2; i <= N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j<(int)pr.size() && pr[j] <= lp[i] && i*pr[j] <= N; ++j)
            lp[i * pr[j]] = pr[j];
    }
    for (int i = 0;pr[i]*pr[i] <= in;i++) {
        if (in%pr[i] == 0) {
            while (in%pr[i] == 0) {
                c++;
                in /= pr[i];
            }
            a.push_back(make_pair(pr[i], c));
            c = 0;
        }
    }
    if (in > 1)
        a.push_back(make_pair(in, 1));
    vector<ll> ans;
    ans.push_back(1);
    for (int i = 0;i < a.size();i++) 
        if (a[i].second % 3) {
            int t = 3 - (a[i].second % 3);
            a[i].second += t;
            ll p = pow(a[i].first, t);
            mul(ans, p);
        }
    for (auto i : ans)
        cout << i;
    //cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    cin.get(), cin.get();
    return 0;
}
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 13:50  [ТС]     ускорение времени выполнения программы #16
Цитата Сообщение от Dimension Посмотреть сообщение
Prolamer, там ошибки есть в коде ,и последние тесты из-за переполнения не проходят
такие вот ошибки в новом коде:
main.cpp:55: ошибка: 'i' does not name a type
for (auto i : ans)
^



main.cpp:59: ошибка: expected ';' before 'return'
return 0;
^



main.cpp:59: ошибка: expected ')' before 'return'


main.cpp:59: ошибка: expected primary-expression before 'return'
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2016, 14:00     ускорение времени выполнения программы
Еще ссылки по теме:

C++ Контроль времени выполнения программы
Подсчёт времени выполнения программы C++
C++ Ошибка времени выполнения (terminate)

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

Или воспользуйтесь поиском по форуму:
Dimension
Dimension
547 / 428 / 132
Регистрация: 08.04.2014
Сообщений: 1,693
Завершенные тесты: 1
29.01.2016, 14:00     ускорение времени выполнения программы #17
вместо 55 строки
C++
1
2
for(int i=0;i<ans.size();i++)
  cout<<ans[i];
Yandex
Объявления
29.01.2016, 14:00     ускорение времени выполнения программы
Ответ Создать тему
Опции темы

Текущее время: 14:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru