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

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

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

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

23.07.2013, 14:40. Просмотров 1088. Ответов 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, потом создаю два числа самое маленькое и самое большое с цифр что есть в массиве, потом проверяю их на простоту.
0
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. И, короче, нужно разложить камни на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BigLow
55 / 55 / 2
Регистрация: 07.07.2013
Сообщений: 345
23.07.2013, 17:01 #16
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Дописал программу!!!!
и все равно эта программа ужасная, хоть и работает
2
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 17:04  [ТС] #17
Цитата Сообщение от BigLow Посмотреть сообщение
и все равно эта программа ужасная, хоть и работает
Зато дает 100% правильный ответ. Твоя идея тоже интересная, хотя после раздумий я так и не нашел теста на котром она б споткнулась, но все равно у меня к этой идее есть кроха недоверия.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 17:25 #18
Цитата Сообщение от BigLow Посмотреть сообщение
необязательно сортировать. если минимальная или максимальная цифра в числе четная, то оно не является 2-простым
ALEXKIRNAS,
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
1
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 22:22  [ТС] #19
Цитата Сообщение от Dani Посмотреть сообщение
После того как отсортируем цифры в убывающем порядке - в конце будет стоять минимальная цифра, а после того как отсортируем в возрастающем порядке - в конце будет стоять максимальная цифра. Четное число - то, что делится на 2. На 2 делятся те числа, что оканчиваются на 0,2,4,6,8. Следовательно, то число где максимальная или минимальная цифра - четная, будет четным, т.к. будет оканчиваться на четную цифру (при возрастающей и/или убывающей сортировке). Как известно, четное простое число только 2, следовательно, данное число не будет являться простым.
Попробуй число 15 по такому методу и ты все поймеш!!
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:35 #20
ALEXKIRNAS, этот алгоритм НЕ дает ответ, что число 15 будет 2-простым. Этот алгоритм позволяет отсеить некоторые числа, которые заведомо не подходят.
1
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 22:37  [ТС] #21
Цитата Сообщение от Dani Посмотреть сообщение
ALEXKIRNAS, этот алгоритм дает ответ, что число 15 будет 2-простым. Этот алгоритм позволяет отсеить некоторые числа, которые заведомо не подходят.
Как же?!?!?!?! Число 15 же не простое (15 - минимальное число составленное из чисел 1 и 5), а за задачей 2-простим называется число у которого минимальное и максимальное значения составленое из его чисел простые.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.07.2013, 22:39 #22
ALEXKIRNAS, я исправил опечатку, алгоритм лишь отсеивает некоторые числа для ускорения (это предложил BigLow). Я же придерживаюсь того, что код не надо этим усложнять.
1
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
23.07.2013, 22:48  [ТС] #23
Цитата Сообщение от Dani Посмотреть сообщение
Я же придерживаюсь того, что код не надо этим усложнять.
Согласен!!!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.07.2013, 22:48
Привет! Вот еще темы с ответами:

Сумма простых чисел ускорение - 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, 22:48
Ответ Создать тему
Опции темы

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