26.07.2012, 15:07. Просмотров 1326. Ответов 7
Помогите ускорить алгоритм. Надо определить все числа с не повторяющимися цифрами от 0 до 9876543210. У меня время просчета занимает очень длительное время уже на 8-значном числе. Что-то не могу догнать как сделать быстрее. Вот код:
| 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <iostream>
#include <vector>
#include <time.h>
#include <Windows.h>
using namespace std;
const int size = 1000000; //нужно ускорить алгоритм до разумного время просчета максимального числа 9876543210
bool isunique(int); //проверяет число на повторяющиеся цифры
void bubbleSort(int* arr, int size); //Сортировка пузырьком(обменом)
int main()
{
SetConsoleCP (1251); SetConsoleOutputCP (1251);
clock_t time;
time = clock(); //время начала отсчета
vector<int> uniqueNumbers;
for (int i = 0; i<size; i++)
{
if (isunique(i)) //если число без повторяющихся цифр
uniqueNumbers.push_back(i); //закинуть его в вектор
}
time = clock() - time; //время конца отсчета
for (int i = uniqueNumbers.size()-100; i<uniqueNumbers.size(); i++) //выводим 100 последних елемента для проверки правильности работы
cout<<uniqueNumbers[i]<<" ";
cout<<endl<<endl<<"================================================================================\n";
//выводим время работы
double timeOfWork = static_cast<double>(time)/CLOCKS_PER_SEC;
if (timeOfWork<60)
cout<<"Вычисления длились "<<timeOfWork<<" секунд\n";
else if (timeOfWork<3600)
cout<<"Вычисления длились "<<timeOfWork/60<<" минут, "<<static_cast<int>(timeOfWork)%60<<"секунд\n";
else
cout<<"Очень долго"<<endl;
system("pause");
return 0;
}
bool isunique(int n)
{
if (n>9876543210)
return false;
int count = 1; //количество цифр в числе n
double temp = n;
while ((temp/=10) > 1)
count++;
int* digits = new int[count];
int j = 1;
temp = count;
while (--temp)
j*=10; // делитель для получения остатка от деления
for (int i = 0; i<count; i++) // закидываем цифры в массив по порядку
{
digits[i] = n/j; // поделить на делитель и получить цифру
n-=(j*digits[i]); // отнять первую цифру от числа спереди
j/=10; //уменшить делитель на 10
}
// сортировка массива:
bubbleSort(digits, count);
for (int i = 0; i<count-1; i++)
{
if (digits[i]==digits[i+1])
{
delete [] digits;
return false;
}
}
delete [] digits;
return true;
}
void bubbleSort(int* arr, int size)
{
int tmp;
for(int i = 0; i < size - 1; ++i) // i - номер прохода
{
for(int j = 0; j < size - 1; ++j) // внутренний цикл прохода
{
if (arr[j + 1] < arr[j])
{
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
} |
|
