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

Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.60
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
26.07.2012, 15:07     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #1
Помогите ускорить алгоритм. Надо определить все числа с не повторяющимися цифрами от 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;
            }
        }
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.07.2012, 15:07     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами
Посмотрите здесь:

Нахождение и запись в массив простых чисел с повторяющимися цифрами C++
C++ Алгебра: Есть массив чисел и число f, надо определить, можно ли получить f, складывая любое количество чисел из массива
C++ Построить последовательность из 20 чисел, образованную цифрами пятеричного представления последовательности натуральных чисел
Найти количество четырехзначных чисел с тремя одинаковыми цифрами C++
Как ускорить данный алгоритм нахождения минимума на отрезке? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 15:55     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #2
А что тебе мешает взять цикл для 1 to 10 (кол-во цифр), каждый новую итерацию заполнять числом 1234...9 (допустим) и потом уже перестановками получать числа?
Т.е, для 3 у тебя будет первоначальное число 123, а затем уже перестановками 3! = 6 чисел. Правда для 9 цифр получится 9! перестановок, но быстрее и не выйдет, как мне кажется

Или я неправильно понял тебя?
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
26.07.2012, 16:33  [ТС]     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #3
Цитата Сообщение от nexen Посмотреть сообщение
каждый новую итерацию заполнять числом 1234...9 (допустим) и потом уже перестановками получать числа?
Что-то я не понял этой идеи, можно небольшой набросок.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 16:52     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #4
C++
1
2
3
4
5
6
7
8
9
for (int n=1; n<=MAX_DIG; ++n)
{
for (int i=1; i<=n; ++i)
number[i-1] = i; // число вида 123 для 3 цифр, 123456789 для 9
...
// алгоритм следующей лексикографической перестановки, где используем push_back(number), \
а number в свою очередь может быть, допустим, типа string
...
}
Вот только я не учел цифру 0, с ней немного подумать надо будет, на что времени у меня нет

Допустим, вот алгоритм перестановок (первый, который нашел) http://algolist.manual.ru/maths/comb...rmutations.php
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.07.2012, 16:57     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #5
yuron_477, смотри в сторону размещений, например к-тво 3-х значных чисел с уникальными цифрами можно посчитать так:
1-ю цифру можно выбрать размещением из 9 по 1
2-ю цифру так же из 9 по 1
3-ю цифру из 8 по 1
посчитаеное перемножаем и получаем к-тво 3-х значных чисел с уникальными цифрами
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.07.2012, 17:01     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #6
Jupiter, он же писал "определить все числа", да и в коде есть push_back и нет явного cout << numbers.size(); // имею ввиду, ему нужно не кол-во получить, а сами числа
golatin
259 / 216 / 38
Регистрация: 12.10.2011
Сообщений: 311
Завершенные тесты: 1
26.07.2012, 17:06     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #7
См. "Количество размещений из n по k":
Общий ответ
http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{n}A\begin{matrix}<br />
i\\ n<br /> <br />
\end{matrix}=\sum_{i=1}^{n}\frac{n!}{(n-i)!}
С учетом того, что с 0 числа не могут начинаться, делите полученный результат на 10, ну и добавьте 1, т.к. 0 входит в диапазон.

Не по теме:

(1+9+9*8+9*8*7+...+9*8*7*6*5*4*3*2)+1

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.07.2012, 17:51     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами
Еще ссылки по теме:

Вычисление суммы чисел, образованных цифрами в строке C++
C++ Cоставить алгоритм и программу для вычисления суммы чисел
Ввести n положительных целых чисел. Найти количество чисел, записанных только четными цифрами C++

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

Или воспользуйтесь поиском по форуму:
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
28.07.2012, 17:51  [ТС]     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами #8
Возвращаясь к старому. Оказывается для моей задачи существует гениальный алгоритм под названием next_permutation. Случайно наткнулся на него. Вот, на его основе переделал я свой код - результатом доволен, добился того чего хотел. Вот новый код, может кому надо будет:
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
//Программа для генерации всех чисел от 0 до 9876543210 с не повторяющимися цифрами
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <vector>
#include <time.h>
#include <Windows.h>
using namespace std;
 
long long numberFromArray(int* ar, const int);  //ф-ция для получения целого числа из цифр массива
 
int main()
{
    SetConsoleCP (1251); SetConsoleOutputCP (1251);
 
    fstream file;  
    file.open("0...9876543210.txt", ios_base::out, ios::trunc);  //тут будет хранится наш набор чисел
    if (!file.is_open())
    {
        cerr<<"Не удалось создать файл!"<<endl;
        system("pause");
        return -1;
    }
 
    const int size = 10;
    int myints[size] = {0,1,2,3,4,5,6,7,8,9};
    vector<long long> vec_temp;
    vector<long long> result;
    long long temp = 0;
 
    clock_t time;
    time = clock();  //время начала работы
 
    do 
    { 
        temp = numberFromArray(myints, size);  //на каждой итерации цикла получаем число из массива
        for (int i = 1000000000; i>=1;)    //тут из 10-значного числа получаем 9-ти, 8-ми, 7-ми, и т.д. значные числа
        {
            vec_temp.push_back(temp%i);  //закидываем их в тот же самые вектор
            i/=10;
        }   
        vec_temp.push_back(temp);  //тут закидываем в вектор 10-ти значные числа
    } while (next_permutation (myints,myints+size));  //комбинует все варианты перестановок массива
 
    cout<<"Начало сортировки_"<<endl;
    sort(vec_temp.begin(), vec_temp.end());  //сортируем вектор для последующего копирования только уникальных чисел в результирующий вектор
 
    cout<<"Отбрасывания повторяющихся элементов_"<<endl;
    for (int i = 0; i<vec_temp.size()-1; i++)
    {
        if (vec_temp[i] != vec_temp[i+1])
            result.push_back(vec_temp[i]);  //тут получаем наши уникальные числа
    }
    result.push_back(vec_temp.back());  //нужно для последнего числа
 
    time = clock() - time;  //время конца работы
    //выводим время работы
    cout<<"= Процесс занял "<<static_cast<double>(time)/CLOCKS_PER_SEC<<" секунд =\n";
    
    cout<<"Начало записи файла_"<<endl;  //файл получается размером 96 МБ
    for (int i = 0; i<result.size(); i++)
    {
        if (i%15 == 0)
            file<<endl;
        file<<setw(11)<<right<<result[i];
    }
        
    cout<<"Готово."<<endl<<endl;
    system("pause");
    return 0;
}
 
long long numberFromArray(int* ar, const int n)
{
    long long temp = 0;
    long long k = 1;
    for (int i = 0; i<n-1; i++)
        k*=10;
    for (int i = 0; i<n; i++, k/=10)
        temp += ar[i]*k;
    return temp;
}
Данные записываются в текстовый файл размером около 96 МБ.
Yandex
Объявления
28.07.2012, 17:51     Надо ускорить алгоритм вычисления чисел с не повторяющимися цифрами
Ответ Создать тему
Опции темы

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