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

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

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

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

12.03.2012, 18:05. Просмотров 870. Ответов 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();

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

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

Распараллеливание вычислений - C++
Вычисляю произведение матриц несколькими потоками (количество задаётся пользователем). Потоки &quot;засыпают&quot; на 1 мс. При вычислении...

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

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

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

Распараллеливание вычислений - C++
Здравствуйте. Может кто сможет подсказать как мне решить следующую задачу: необходимо распараллелить следующий последовательный код:...

9
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.03.2012, 18:58 #2
А задачу можно узнать?
0
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 19:01  [ТС] #3
Мне нужно перебрать все числа от 999...999 до 0. Где количество 9 равно N. В файл записываются только варианты, гда сумма цифр числа = N. я перебрал уже 1..10, нужно до 16 включительно.
0
diagon
Higher
1936 / 1202 / 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 посчитать таким способом, т.к. на самом деле перебирается небольшое количество чисел, все лишнее отсекается.
0
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
12.03.2012, 19:51 #5
Цитата Сообщение от diagon Посмотреть сообщение
Только вместо массива я макрос использовал, за секунду отрабатывает, причем почти все время на вывод уходит.
А Вы попробуйте сразу в файл выводить.

diagon, есть более быстрый способ: методом перебора или рекурсией перебираем все варианты когда последующая цифра равна или больше предыдущей (можно отсекать лишние циклы, варианты). Натыкаемся на вариант когда сумма цифр числа = N. Делаем перестановку этого набора и идем дальше.
1
diagon
Higher
1936 / 1202 / 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, то как узнать, что оно уже выводилось?
0
valeriikozlov
Эксперт С++
4682 / 2508 / 322
Регистрация: 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 нам уже не попадутся.
1
diagon
Higher
1936 / 1202 / 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 нам уже не попадутся.
Ну да, тогда вариант оптимальнее сложно придумать.
0
Ksan
27 / 27 / 0
Регистрация: 02.11.2010
Сообщений: 370
12.03.2012, 20:43  [ТС] #9
Прокомментируйте пожалуйста код, не совсем понимаю что к чему
0
diagon
Higher
1936 / 1202 / 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.
0
13.03.2012, 11:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 11:32
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

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