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

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

Войти
Регистрация
Восстановить пароль
 
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
#1

Оптимизация вычислений - C++

12.03.2012, 18:05. Просмотров 771. Ответов 9
Метки нет (Все метки)

Есть код:

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
fstream file("out13.txt", ios::out);
    
    int index[16], summ;
    
    for(index[0] = 0; index[0]<=9; ++index[0])
    {
        cout << "index[0] = " << index[0] << '\n';
        for(index[1] = 0; index[1]<=9; ++index[1])
        {
            cout << "index[1] = " << index[1] << '\n';
            for(index[2] = 0; index[2]<=9; ++index[2])
            {
                for(index[3] = 0; index[3]<=9; ++index[3])
                {
                    for(index[4] = 0; index[4]<=9; ++index[4])
                    {
                        for(index[5] = 0; index[5]<=9; ++index[5])
                        {
                            for(index[6] = 0; index[6]<=9; ++index[6])
                            {
                                for(index[7] = 0; index[7]<=9; ++index[7])
                                {
                                    for(index[8] = 0; index[8]<=9; ++index[8])
                                    {
                                        for(index[9] = 0; index[9]<=9; ++index[9])
                                        {
                                            for(index[10] = 0; index[10]<=9; ++index[10])
                                            {
                                                for(index[11] = 0; index[11]<=9; ++index[11])
                                                {
                                                    for(index[12] = 0; index[12]<=9; ++index[12])
                                                    {
                                                        summ = 0;
                                                  for(int i=0; i<13; ++i) summ += index[i];
                                                if(summ == 13)
                                                {
                                                  for(int i=0; i<13; ++i) if(index[i] != 0) file << index[i];
                                                file << '\n';
                                              }
                                                        
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    file.close();

Но он будет выполняться слишком долго. Какие есть идеи оптимизации?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2012, 18:05     Оптимизация вычислений
Посмотрите здесь:

Порядок вычислений C++ - C++
Каков порядок вычисления для этого предложения,какие предположения можно сделать о типе операндов?Имеет ли место неоднозначность...

Погрешность вычислений - C++
определить погрешность вычислений на ЭВМ выражения а*(1/a), задавая тип данных для переменной a - float, double, long double. Для этого...

Точность вычислений - C++
Для проверки точности вычислений существуют формулы и калькулятор на 200000 знаков до и после запятой. Проверяются любые вычисленные...

Погрешность вычислений - C++
Читаю книгу Дейтелов &quot;Как программировать на С++&quot;, попалась следующая задача, где нужно вводить кол-во бензина, пройденный путь, исходя из...

Результат вычислений функции - C++
Результат вычислений функции называют её?

Шаблон параллельных вычислений - C++
Имеется задача, состоящая из подзадач разной сложности. Хочется решать эти подзадачи параллельно. Пусть имеется итератор подзадач....

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 18:58     Оптимизация вычислений #2
А задачу можно узнать?
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 19:01  [ТС]     Оптимизация вычислений #3
Мне нужно перебрать все числа от 999...999 до 0. Где количество 9 равно N. В файл записываются только варианты, гда сумма цифр числа = N. я перебрал уже 1..10, нужно до 16 включительно.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 19:19     Оптимизация вычислений #4
Я как-то писал подобную задачу для чисел от 10^9 до 10^10, но максимум, чего я достиг - 2 минуты. До 10^16 вообще сложно перебирать, даже если цикл будет пустым, то работать будет очень долго.
P.S. ваш вариант можно оптимизировать, если вычислять сумму получившего числа за O(1), и автоматически отсекать лишние циклы, когда эта сумма становится больше требуемой.

Добавлено через 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
#include <stdio.h>
 
#define FOR(x, l, code)                                 \
    for ( a##x = l; a##x <= 9 && sum <= 10 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;
    
    FOR(1, 1,
    FOR(2, 0,
    FOR(3, 0,
    FOR(4, 0,
    FOR(5, 0,
    FOR(6, 0,
    FOR(7, 0,
    FOR(8, 0,
    FOR(9, 0,
    FOR(10, 0,
        
        if ( sum == 10 )
        {
            long long number = a1 * 1e9 + a2 * 1e8 + a3 * 1e7 + a4 * 1e6
                             + a5 * 1e5 + a6 * 1e4 + a7 * 1e3 + a8 * 1e2
                             + a9 * 10 + a10;           
            
            printf("%lld ", number);            
        }
        
    ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
В принципе можно и для 10^16 посчитать таким способом, т.к. на самом деле перебирается небольшое количество чисел, все лишнее отсекается.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.03.2012, 19:51     Оптимизация вычислений #5
Цитата Сообщение от diagon Посмотреть сообщение
Только вместо массива я макрос использовал, за секунду отрабатывает, причем почти все время на вывод уходит.
А Вы попробуйте сразу в файл выводить.

diagon, есть более быстрый способ: методом перебора или рекурсией перебираем все варианты когда последующая цифра равна или больше предыдущей (можно отсекать лишние циклы, варианты). Натыкаемся на вариант когда сумма цифр числа = N. Делаем перестановку этого набора и идем дальше.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 20:02     Оптимизация вычислений #6
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А Вы попробуйте сразу в файл выводить.
Так за 0.015 отрабатывает =)
Правда я вывод более оптимальный сделал:
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
#include <stdio.h>
 
#define FOR(x, l, code)                                 \
    for ( a##x = l; a##x <= 9 && sum <= 10 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    freopen("output.txt", "w", stdout);
    
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10;
    
    FOR(1, 1,
    FOR(2, 0,
    FOR(3, 0,
    FOR(4, 0,
    FOR(5, 0,
    FOR(6, 0,
    FOR(7, 0,
    FOR(8, 0,
    FOR(9, 0,
    FOR(10, 0,
        
        if ( sum == 10 )
        {
            putchar(a1 + '0');
            putchar(a2 + '0');
            putchar(a3 + '0');
            putchar(a4 + '0');
            putchar(a5 + '0');
            putchar(a6 + '0');
            putchar(a7 + '0');
            putchar(a8 + '0');
            putchar(a9 + '0');
            putchar(a10 +'0');
            putchar(' ');
        }
        
    ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Делаем перестановку этого набора и идем дальше.
В смысле? Если просто выводить все перестановки этого числа, то в дальнейшем, когда попадется перестановка этого числа, как узнать, что оно уже было?
Ну, например, для трехзначного:
102
можно вывести перестановки
102, 120, 210, 201, но когда попадется число 120, то как узнать, что оно уже выводилось?
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
12.03.2012, 20:06     Оптимизация вычислений #7
Цитата Сообщение от diagon Посмотреть сообщение
Ну, например, для трехзначного:
102
можно вывести перестановки
102, 120, 210, 201, но когда попадется число 102, то как узнать, что оно уже выводилось?
я же писал:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
все варианты когда последующая цифра равна или больше предыдущей
то есть нам попадется вариант 012, по этому варианту мы делаем перестановки 021, 102, 120, 210, 201.
Варианты 021, 102, 120, 210, 201 нам уже не попадутся.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 20:08     Оптимизация вычислений #8
Цитата Сообщение от valeriikozlov Посмотреть сообщение
то есть нам попадется вариант 012, по этому варианту мы делаем перестановки 021, 102, 120, 210, 201.
Варианты 021, 102, 120, 210, 201 нам уже не попадутся.
Ну да, тогда вариант оптимальнее сложно придумать.
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 20:43  [ТС]     Оптимизация вычислений #9
Прокомментируйте пожалуйста код, не совсем понимаю что к чему
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 11:32     Оптимизация вычислений
Еще ссылки по теме:

Точность вычислений у double - C++
Дана задача: &quot;Определить, на сколько нулей заканчивается факториал числа n&quot;. Пример: вводим &quot;25&quot;, на выходе должны получить &quot;6&quot; (25! =...

Перенос вычислений в подпрограмму - C++
Здравствуйте, есть лаба в которой нужно найти след трёх прямоугольных матриц и вывести на экран наибольший их них. Вычисления нужно...

Точности вычислений double - C++
Вот у меня возникла проблема при подсчете ряда тейлора в заданном интервале. Проблема заключается в том, что когда я ввижу интервал и...

Сравнение скорости вычислений с# и С++ - C++
Сделал тестовые расчеты для сравнения скорости расчетов с# и С++ на примере умножения квадратных матриц. Сравнил расчеты без ускорения...


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.03.2012, 11:32     Оптимизация вычислений #10
Цитата Сообщение от Ksan Посмотреть сообщение
Прокомментируйте пожалуйста код, не совсем понимаю что к чему
Почитайте где-нибудь про макросы
первый FOR(1, 1, ...) раскрывается как
C
1
2
3
4
5
6
for (a1 = 1; a1 <= 9 && sum <= 10; ++a1)
{
    sum += a1;
    ...
    sum -= a1;
}
Ну и этот код перебирает все десятизначные числа.

Вот код, который перебирает числа от 0 до 10^16.
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
#include <stdio.h>
 
#define FOR(x, code)                                    \
    for ( a##x = 0; a##x <= 9 && sum <= 16 ; ++a##x )   \
    {                                                   \
        sum += a##x;                                    \
        code                                            \
        sum -= a##x;                                    \
    }           
    
 
 
int main()
{   
    freopen("output.txt", "w", stdout);
    
    int sum = 0;
    int a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16;
    
    FOR(1, 
    FOR(2, 
    FOR(3, 
    FOR(4, 
    FOR(5, 
    FOR(6, 
    FOR(7, 
    FOR(8, 
    FOR(9, 
    FOR(10, 
    FOR(11,
    FOR(12,
    FOR(13,
    FOR(14,
    FOR(15,
    FOR(16,
        
        if ( sum == 16 )
        {
            char str[17];
            
            str[0] = a1 + '0';
            str[1] = a2 + '0';
            str[2] = a3 + '0';
            str[3] = a4 + '0';
            str[4] = a5 + '0';
            str[5] = a6 + '0';
            str[6] = a7 + '0';
            str[7] = a8 + '0';
            str[8] = a9 + '0';
            
            str[9 ] = a10 + '0';
            str[10] = a11 + '0';
            str[11] = a12 + '0';
            str[12] = a13 + '0';
            str[13] = a14 + '0';
            str[14] = a15 + '0';
            str[15] = a16 + '0';
            
            str[16] = '\0';
            
            char * p = str;
            while (*p == '0')
                ++p;
                
            printf("%s ", p);
        }
        
    ) ) ) ) ) ) ) ) ) ) ) ) ) ) ) )
    
    return 0;                                   
}
Работает у меня ровно 100 секунд, но проверить правильность я не могу, т.к. размер файла доползает до 2.1 гб, а больше у меня, видимо, создать нельзя, поэтому еще половина чисел попросту недописывается =\
А вообще это быдлокод, конечно, лучше использовать вариант, который предложил valeriikozlov.
Yandex
Объявления
13.03.2012, 11:32     Оптимизация вычислений
Ответ Создать тему
Опции темы

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