Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
#1

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

28.01.2016, 20:10. Просмотров 424. Ответов 16
Метки нет (Все метки)

здравствуйте. решал олимпиадную задачу:

...Он берет произвольное положительное число А и выписывает на доске арифметическую прогрессию с первым членом равным А и разницей, равной также А, то есть имеем последовательность А, А + А, А + 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;
}
она рабочий , но время выполнения превышает лимит, указанный в правилах...
какие есть способы ускорить?
надеюсь получить помощь с вашей стороны))
спасибо за внимание.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.01.2016, 20:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос ускорение времени выполнения программы (C++):

Подсчёт времени выполнения программы - C++
Здравствуйте, помогите разобраться, не получается подсчитать время выполнения программы. Вот код: #include &lt;time.h&gt; #include...

Контроль времени выполнения программы - C++
Добрый день. У меня маленькая проблемка. Есть задача. Задача А - Гистограмма Ограничение времени: 1 с Ограничение памяти: 1024 M ...

Оптимизация времени выполнения - C++
Доброго времени суток. Есть следующая задача. Задача олимпиадная, потому учитывается время выполнения, нужно вложится в 1секунду. Мой код...

Ошибка времени выполнения. - C++
Вот код: void Add_Kod ( _kod*&amp; KodBuf, int a, char* buf, char* buf2) { if(a==1) { KodBuf = new _kod; KodBuf.ch = *(buf);...

Измерение времени выполнения - C++
Подскажите пожалуйста как измерить время выполнения чего-то с наносекундной точностью. std::chrono::high_resolution_clock::time_point...

Ошибка времени выполнения - C++
Я пишу проэкт в Visual Studia 2008 на C++. У меня есть несколько проблем. Во-первых, когда я собираю финальную версию (release) и...

16
_Valera_
488 / 370 / 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);
* * }
что-то я не вижу еще одного цикла для проверки всех чисел из файла.
1
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 21:08  [ТС] #3
рабочий точно
извините, я не совсем понял зачем ещё один цикл? в файле ведь одно число
0
_Valera_
488 / 370 / 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);
* * }
просто ищи корень.
1
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);
        }
вот так вот попробовал, но не получилось...
вы уж извините, совсем новичок
0
Dimension
Dimension
569 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
28.01.2016, 22:08 #6
Цитата Сообщение от Prolamer Посмотреть сообщение
спасибо Вам большое
очень помогли
не было время дописать ,киньте ссылку на задачу
0
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 22:14  [ТС] #7
Цитата Сообщение от Dimension Посмотреть сообщение
не было время дописать ,киньте ссылку на задачу
1. она на украинском, и я перевёл всё, кроме первых двух предложений, которые никак не влияют на решение задачи.
2. не могу кинуть ссылку по причине того, что я решаю эту задачу в закрытом тренировочном туре, логин и пароль для доступа даются классным руководителем...
если, конечно , важно, то могу заскринить
0
Dimension
Dimension
569 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
28.01.2016, 22:24 #8
Prolamer, думаю ваш скрин не сможет код проверить ,хотя бы ограничение по времени напишите
0
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
28.01.2016, 22:30  [ТС] #9
Цитата Сообщение от Dimension Посмотреть сообщение
Prolamer, думаю ваш скрин не сможет код проверить ,хотя бы ограничение по времени напишите
как-то так...
0
Миниатюры
ускорение времени выполнения программы  
_Valera_
488 / 370 / 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;
}
возможно так, у меня все тесты меньше чем за секунду прошел. Ну если я правильно понял условие.
1
Dimension
Dimension
569 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 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;
}
1
zer0mail
2373 / 2003 / 199
Регистрация: 03.07.2012
Сообщений: 7,192
Записей в блоге: 1
29.01.2016, 01:34 #12
Думаю, для начала надо разложить А на простые множители.
1
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 09:39  [ТС] #13
Dimension,
спасибо Вам большое))
вот результат, программа работает достаточно быстро, а с остальным попытаюсь разобраться сам
к сожалению, я не полностью понимаю ваш код, но, думаю, это из-за моей неопытности
0
Миниатюры
ускорение времени выполнения программы  
Prolamer
0 / 0 / 0
Регистрация: 24.01.2016
Сообщений: 16
29.01.2016, 09:43  [ТС] #14
спасибо всем большое!
0
Dimension
Dimension
569 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 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;
}
1
29.01.2016, 10:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.01.2016, 10:47
Привет! Вот еще темы с ответами:

Ускорение программы: сравнивание 4-х столов с пятым - C++
У меня естъ прoгрaмa кoтoрaя связaнa с SQL .Oнa делaет селект из 4 стoлoв и срaвнивaет с 5 стoлoм. Если в 5 стoле естъ тaкaя-же инфoрмaция...

Подсчет времени выполнения функции - C++
Делаю 2 вида сортировки, не знаю как подсчитать их время. #include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;conio.h&gt; using namespace...

Оптимизация [сокращение времени выполнения] - C++
Здравствуйте, стояла такая задача: Была сделана следующая программа: #include &lt;iostream&gt; using namespace std; int lucky(int...

Подсчет времени выполнения процедуры - C++
Такой вопрос- необходимо получить время выполнения процедуры сортировки массива. Для этого я использовал следующее выражение void...


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

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

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