Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
1

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

23.07.2013, 14:40. Показов 2465. Ответов 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";
}
Код - решение задачи по ссылке
Программа считывает число, потом записывает числа в массив ,потом сортирует их с помощу QSORT, потом создаю два числа самое маленькое и самое большое с цифр что есть в массиве, потом проверяю их на простоту.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.07.2013, 14:40
Ответы с готовыми решениями:

Ускорение
Здраствуйте, есть код: #include &lt;stdio.h&gt; #define MAX 1000010 long long h; int i, n,...

Разработка и отладка алгоритмов и программ с использованием шаблонов классов и алгоритмов библиотеки STL
1. Создать объект-контейнер и заполнить его данными. 2. Просмотреть контейнер. 3....

Скорость, касательное ускорение, полное ускорение, нормальное ускорение и радиус кривизны траектории
Движение точки задано координатным способом. Найти траекторию и начертить ее. Кроме того определить...

Directx 11: недоступны функции Ускорение DirectDraw, Direct3D, Ускорение текстур AGP
Здравствуйте. Вся проблема как я понял в том, что у меня не правильно работает Directx. Я никак не...

22
Псевдослучайный
1941 / 1141 / 97
Регистрация: 13.09.2011
Сообщений: 3,213
23.07.2013, 16:10 2
Ужс. Давайте вы сначала над стилем поработаете, а уже потом будете чего-то там ускорять?
0
55 / 55 / 6
Регистрация: 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*
1
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:30  [ТС] 4
Цитата Сообщение от NoMasters Посмотреть сообщение
Ужс. Давайте вы сначала над стилем поработаете, а уже потом будете чего-то там ускорять?
Стиль не имеет значения. Главное - скорость!!!!
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 16:31 5
ALEXKIRNAS, ну так сам свой код и читай и ускоряй. Ломать глаза не все горят желанием.
1
10 / 10 / 1
Регистрация: 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, ну так сам свой код и читай и ускоряй. Ломать глаза не все горят желанием.
А я твоему что здесь пирожки печу ?
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 16:37 7
ALEXKIRNAS, здесь ускорять ничего не нужно. В этой задаче надо отсортить 2 массива по 18 цифр и проверить на простому. Как можно написать такой быдлокод по такой задаче? Скорее, ты пирожки печешь, чем решаешь задачу.
0
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:38  [ТС] 8
Цитата Сообщение от Dani Посмотреть сообщение
ALEXKIRNAS, здесь ускорять ничего не нужно. В этой задаче надо отсортить 2 массива по 18 цифр и проверить на простому. Как можно написать такой быдлокод по такой задаче? Скорее, ты пирожки печешь, чем решаешь задачу.
Неужели?!?!?! А ограничение в 1 сек программа не проходит !!!
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 16:40 9
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Неужели?!?!?! А ограничение в 1 сек программа не проходит !!!
Может быть причина в этом...
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
(Помогите тупому!!!!!!!)
Значит, неверная реализация. Такой код никто не разберет.
1
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:44  [ТС] 10
Цитата Сообщение от Dani Посмотреть сообщение
Значит, неверная реализация. Такой код никто не разберет.
Почему? Программа дает верный ответ, но не проходит временное ограничение.
Цитата Сообщение от Dani Посмотреть сообщение
Может быть причина в этом...
Если такой умный, то почему бы тебе не решить задачу.
0
55 / 55 / 6
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 16:44 11
Число называется 2-простым, если являются простыми числа, составленные из цифр этого числа в возрастающем и убывающем порядках.
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
1
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 16:48 12
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Если такой умный, то почему бы тебе не решить задачу.
Я ее уже решал, и уверяю, что все работает. Главное - правильный код.

Добавлено через 2 минуты
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
это частный случай. Лишняя сортировка 18 элементов не даст значительного увеличения времени работы программы, хотя и надо будет проверять на простоту. Да и код будет проще смотреться.
1
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 16:53  [ТС] 13
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
Контр пример 110. По такому алгоритму будет Yes, а нужно No!!!
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 16:55 14
ALEXKIRNAS, 110 - минимальная цифра 0. Она четная, следовательно, число не является 2-простым. Ответ - No.
0
10 / 10 / 1
Регистрация: 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";
}
0
55 / 55 / 6
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 17:01 16
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Дописал программу!!!!
и все равно эта программа ужасная, хоть и работает
2
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 17:04  [ТС] 17
Цитата Сообщение от BigLow Посмотреть сообщение
и все равно эта программа ужасная, хоть и работает
Зато дает 100% правильный ответ. Твоя идея тоже интересная, хотя после раздумий я так и не нашел теста на котром она б споткнулась, но все равно у меня к этой идее есть кроха недоверия.
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 17:25 18
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
ALEXKIRNAS,
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
1
10 / 10 / 1
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 22:22  [ТС] 19
Цитата Сообщение от Dani Посмотреть сообщение
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
Попробуй число 15 по такому методу и ты все поймеш!!
0
1402 / 644 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
23.07.2013, 22:35 20
ALEXKIRNAS, этот алгоритм НЕ дает ответ, что число 15 будет 2-простым. Этот алгоритм позволяет отсеить некоторые числа, которые заведомо не подходят.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.07.2013, 22:35

Найти траекторию движения, скорость, ускорение, нормальное и касательное ускорение точки
Точка движется по плоскости XOY по закону x=x(t), y=y(t)/ В свою очередь плоскость XOY вращается...

Определить траекторию, скорость, полное ускорение, касательное ускорение и радиус кривизны траектории
Движение точки задано уравнением x=x(t) и y=y(t). Определить траекторию, скорость, полное...

Не получается определить ускорение и среднее ускорение тела
Доброго времени суток! Помогите пожалуйста решить задачку: Зависимость пройденного телом пути от...

Найти угловое ускорение и ускорение точки
Ползун А линейки эллипсографа движется с постоянной скоростью V = 2м/с. Определить в момент...

Теория Алгоритмов или Путеводитель по созданию простых и эффективных алгоритмов
Я начинаю изучать язык Си, но в целом представляю, что такое алгоритм; могу написать алгоритм...

Ускорение
Помогите с задачей: На клин, находящийся на горизонтальной поверхности, поместили брусок. Угол...


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

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

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