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

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

Войти
Регистрация
Восстановить пароль
 
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
#1

Ускорение алгоритмов - C++

23.07.2013, 14:40. Просмотров 1085. Ответов 22
Метки нет (Все метки)

Имеется код, нужно его ускорить. (Помогите тупому!!!!!!!)
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
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
 
int c (const void* a, const void*b)
{
    return *(int *)a- *(int *)b;
}
 
int main ()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    std::string n;
    std::getline(std::cin, n);
    int m=n.size(), *a=new int [m]; unsigned __int64 i=0, z;
    for( ; m-i; i++) *(a+i)=n[i]-48;
    qsort(a,m,sizeof(int),c);
    if(!*a) goto A;
    __int64 b=1, ch=0, ch1=0;
    for(i=0; m-i; i++, b*=10) ch+=b* *(a+i);
    for(i=m-1, b=1; i+1; i--, b*=10) ch1+=b* *(a+i);
    for(i=2; i*i<=ch || i*i<=ch1; i++) for(z=i*i; z<=ch || z<=ch1; z+=i) if(z==ch || z==ch1) goto A;
    std::cout << "Yes";
    return 0;
A:
    std::cout << "No";
}
Код - решение задачи по ссылке http://********/index.asp?main=task&id_task=516
Программа считывает число, потом записывает числа в массив ,потом сортирует их с помощу QSORT, потом создаю два числа самое маленькое и самое большое с цифр что есть в массиве, потом проверяю их на простоту.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2013, 14:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ускорение алгоритмов (C++):

Ускорение алгоритма - C++
Я хочу реализовать свой метод компрессии данных (не спрашивайте зачем, оч. надо). Он заключается в следующем (смотрим картинку). Я...

Ускорение ввода - C++
#include &lt;bits/stdc++.h&gt; #define ll long long using namespace std; bool ar; int main() { int n,cnt=0; scanf(&quot;%d&quot;,...

Ускорение програмки - C++
#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;stdlib.h&gt; struct Tree { char s; struct Tree *d; ...

Ускорение програмы на с++ - C++
Здраствуйте!Нужно ускорить программу по возможности. #include &lt;iostream&gt; #include &lt;vector&gt; #include...

Ускорение проги потоками - C++
Здорова господа! Только что у меня прога глючила и вылетала я от не заметил она именно в дебаг режиме вылетала и медленно работала, а...

Ускорение алгоритма перебора - C++
Здравствуйте! В общем есть такая задачка: Имеются N(1 ≤ N ≤ 18) камней с массами W1, W2 , … WN. И, короче, нужно разложить камни на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
NoMasters
Псевдослучайный
1753 / 1096 / 72
Регистрация: 13.09.2011
Сообщений: 3,132
23.07.2013, 16:10 #2
Ужс. Давайте вы сначала над стилем поработаете, а уже потом будете чего-то там ускорять?
BigLow
55 / 55 / 2
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 16:13 #3
я бы функцию int c (const void* a, const void*b) заменил бы этой:

C++
1
2
3
4
int c(const int *a, const int *b)
{
    return *a- *b;
}
не будет лишних преобразований из void* в int*
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:30  [ТС] #4
Цитата Сообщение от NoMasters Посмотреть сообщение
Ужс. Давайте вы сначала над стилем поработаете, а уже потом будете чего-то там ускорять?
Стиль не имеет значения. Главное - скорость!!!!
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 16:31 #5
ALEXKIRNAS, ну так сам свой код и читай и ускоряй. Ломать глаза не все горят желанием.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:34  [ТС] #6
Цитата Сообщение от BigLow Посмотреть сообщение
я бы функцию int c (const void* a, const void*b) заменил бы этой
Компилятор (MS VS 2010) не дает использовать функцию с qsort();

Добавлено через 1 минуту
Цитата Сообщение от Dani Посмотреть сообщение
ALEXKIRNAS, ну так сам свой код и читай и ускоряй. Ломать глаза не все горят желанием.
А я твоему что здесь пирожки печу ?
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 16:37 #7
ALEXKIRNAS, здесь ускорять ничего не нужно. В этой задаче надо отсортить 2 массива по 18 цифр и проверить на простому. Как можно написать такой быдлокод по такой задаче? Скорее, ты пирожки печешь, чем решаешь задачу.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:38  [ТС] #8
Цитата Сообщение от Dani Посмотреть сообщение
ALEXKIRNAS, здесь ускорять ничего не нужно. В этой задаче надо отсортить 2 массива по 18 цифр и проверить на простому. Как можно написать такой быдлокод по такой задаче? Скорее, ты пирожки печешь, чем решаешь задачу.
Неужели?!?!?! А ограничение в 1 сек программа не проходит !!!
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 16:40 #9
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Неужели?!?!?! А ограничение в 1 сек программа не проходит !!!
Может быть причина в этом...
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
(Помогите тупому!!!!!!!)
Значит, неверная реализация. Такой код никто не разберет.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:44  [ТС] #10
Цитата Сообщение от Dani Посмотреть сообщение
Значит, неверная реализация. Такой код никто не разберет.
Почему? Программа дает верный ответ, но не проходит временное ограничение.
Цитата Сообщение от Dani Посмотреть сообщение
Может быть причина в этом...
Если такой умный, то почему бы тебе не решить задачу.
BigLow
55 / 55 / 2
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 16:44 #11
Число называется 2-простым, если являются простыми числа, составленные из цифр этого числа в возрастающем и убывающем порядках.
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 16:48 #12
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Если такой умный, то почему бы тебе не решить задачу.
Я ее уже решал, и уверяю, что все работает. Главное - правильный код.

Добавлено через 2 минуты
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
это частный случай. Лишняя сортировка 18 элементов не даст значительного увеличения времени работы программы, хотя и надо будет проверять на простоту. Да и код будет проще смотреться.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:53  [ТС] #13
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
Контр пример 110. По такому алгоритму будет Yes, а нужно No!!!
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 16:55 #14
ALEXKIRNAS, 110 - минимальная цифра 0. Она четная, следовательно, число не является 2-простым. Ответ - No.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:58  [ТС] #15
Спасибо всем кто гадил и/или давал совет в теме!!!!
Дописал программу!!!!
Время выполнения - 0.012 сек. Память - 60 кб.
Код:
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
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
 
int c (const void* a, const void*b)
{
    return *(int *)a- *(int *)b;
}
 
int main ()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    std::string n;
    std::getline(std::cin, n);
    int m=n.size(), *a=new int [m], i=0;
    for( ; m-i; i++) *(a+i)=n[i]-48;
    qsort(a,m,sizeof(int),c);
    if(!*a) goto A;
    int b=1, ch=0, ch1=0;
    for(i=0; m-i; i++, b*=10) ch+=b* *(a+i);
    for(i=m-1, b=1; i+1; i--, b*=10) ch1+=b* *(a+i);
    for(i=2; i*i<ch1; i++) if(!(ch1%i) || !(ch%i)) goto A;
    std::cout << "Yes";
    return 0;
A:
    std::cout << "No";
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2013, 16:58
Привет! Вот еще темы с ответами:

Сумма простых чисел ускорение - C++
Надо находить сумму всех простых чисел. Ограничения: на числе прибл. 1000000000 надо вписаться в минуту #include &lt;iostream&gt; #include...

ускорение времени выполнения программы - C++
здравствуйте. решал олимпиадную задачу: ...Он берет произвольное положительное число А и выписывает на доске арифметическую прогрессию...

Многократное ускорение кода[литература] - C++
Здравствуйте, я дилетант в ЯП C++ перешёл на него после достаточно долгого изучения C# с целью выигрыша в производительности, поэтому я...

Ускорение программы: сравнивание 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ция...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.07.2013, 16:58
Ответ Создать тему
Опции темы

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