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

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

Восстановить пароль Регистрация
 
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 14:40     Ускорение алгоритмов #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
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, потом создаю два числа самое маленькое и самое большое с цифр что есть в массиве, потом проверяю их на простоту.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,094
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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 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";
}
BigLow
55 / 55 / 2
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 17:01     Ускорение алгоритмов #16
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Дописал программу!!!!
и все равно эта программа ужасная, хоть и работает
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 17:04  [ТС]     Ускорение алгоритмов #17
Цитата Сообщение от BigLow Посмотреть сообщение
и все равно эта программа ужасная, хоть и работает
Зато дает 100% правильный ответ. Твоя идея тоже интересная, хотя после раздумий я так и не нашел теста на котром она б споткнулась, но все равно у меня к этой идее есть кроха недоверия.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 17:25     Ускорение алгоритмов #18
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
ALEXKIRNAS,
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 22:22  [ТС]     Ускорение алгоритмов #19
Цитата Сообщение от Dani Посмотреть сообщение
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
Попробуй число 15 по такому методу и ты все поймеш!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2013, 22:35     Ускорение алгоритмов
Еще ссылки по теме:

Ускорение програмки C++
C++ Ускорение проги потоками
Перевести с Delphi на C++. Ускорение умножения двоичных чисел с анализом двух разрядов C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:35     Ускорение алгоритмов #20
ALEXKIRNAS, этот алгоритм НЕ дает ответ, что число 15 будет 2-простым. Этот алгоритм позволяет отсеить некоторые числа, которые заведомо не подходят.
Yandex
Объявления
23.07.2013, 22:35     Ускорение алгоритмов
Ответ Создать тему
Опции темы

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