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

Элементы Комбинаторики - C++

Восстановить пароль Регистрация
 
Dantes48
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 16
05.07.2013, 20:02     Элементы Комбинаторики #1
Даны натуральные числа a1,...a10. Предположим что имеется 10 монет достоинством a1,...,a10. Обозначим через bk число способов, которыми можно выплатить сумму k, т.е. bk - число решений уравнения a1x1+a2x2+...+a10x10=k, где xi может принимать целые неотрицательные значения. получить b0,...,b20.

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
#include "stdio.h"
#include <locale.h>
#include <math.h>
 
int main()
{
    setlocale(LC_ALL,"Russian_Russia.1251"); // Русский язык
    printf("Beginning\n");
    int a[10], b[21] = {0}, x[21];
    int i;  
    for (i=0; i<10; i++)
    {
        a[i] = i+1;
    }
    for (i=0; i<10; i++)
    {
        printf("a[%i] = %i\n", i, a[i]);
    }
    for (i=0; i<21; i++)
    {
        x[i] = i;
    }
    printf("\n");
    for (i=0; i<21; i++)
    {
        printf("b[%i]   = %i\n", i, b[i]);      
    }
    printf("\n");
    for (i=0; i<21; i++)
    {
        printf("x[%i]   = %i\n", i, x[i]);      
    }
    printf("\n");
    int k, sum; 
    int d1, f2, g3, h4, j5, l6, z7, x8, c9, v10;
    for (k=0; k<21; k++)    // 1
    {
        for (d1=0; d1<=k; d1++) // 2
        {
            for (f2=0; f2<=k; f2++) // 3
            {
                for (g3=0; g3<=k; g3++) // 4
                {
                    for (h4=0; h4<=k; h4++) // 5
                    {
                        for (j5=0; j5<=k; j5++) // 6
                        {
                            for (l6=0; l6<=k; l6++) // 7
                            {
                                for (z7=0; z7<=k; z7++) // 8
                                {                                                                           
                                    for (x8=0; x8<=k; x8++) // 9
                                    {                                                                           
                                        for (c9=0; c9<=k; c9++) // 10
                                        {                                                                           
                                            for (v10=0; v10<=k; v10++)  // 11
                                                {                                                                                                               
                                                sum=a[1]*x[d1]+a[2]*x[f2]+a[3]*x[g3]+a[4]*x[h4]+a[5]*x[j5]+a[6]*x[l6]+a[7]*x[z7]+a[8]*x[x8]+a[9]*x[c9]+a[10]*x[v10]; 
                                                if (sum == k )
                                                {
                                                    b[k]++;
                                                    printf("b[%i]   = %i\n", k, b[k]);
                                                    printf("||Сумма %i ||| a[1]*%i | a[2]*%i | a[3]*%i | a[4]*%i | a[5]*%i | a[6]*%i | a[7]*%i | a[8]*%i | a[9]*%i | a[10]*%i |\n", k, d1, f2, g3, h4, j5, l6, z7, x8, c9, v10);
                                                }                                               
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    printf("\n");
    for (i=0; i<21; i++)
    {
        printf("b[%i]   = %i\n", i, b[i]);      
    }   
    printf("The End\n");
    // необходимы для отладки
    getchar();
    getchar();  
    return 0;   
}
Прошу помочь с улучшением данной программы, т.к. при решении методом перебора программа выполняется достаточно долгое время..
Миниатюры
Элементы Комбинаторики  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.07.2013, 21:04     Элементы Комбинаторики #2
посмотрите похожую задачу, принцип тот же
составить алгоритм подсчета количества способов, которыми можно разменять рубль медными монетами(достоинством в1,2,3,5 копеек)
Dantes48
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 16
09.07.2013, 15:18  [ТС]     Элементы Комбинаторики #3
Вот что получилось в результате)
Спасибо, все работает)

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
#include "stdio.h"
#include <locale.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
 
int F(int *a, int i, int n);
    
int main()
{
    setlocale(LC_ALL,"Russian_Russia.1251"); // Русский язык
    srand(time(0)); // для настоящих рандомных результатов
    printf("Beginning\n");
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int i;
    printf("Достоинства монет:\n");
    
    for (i=0; i<10; i++)
    {
        //a[i]=rand()%19+1;
        printf("%i\t", a[i]);
    }   
    for (i=0; i<=20; i++)
    {
        printf("\nСумма %i \t- Способов получения %i", i, F(a, 9, i));
    }
    printf("\nThe End\n");
    // необходимы для отладки
    getchar();
    getchar();  
    return 0;   
}
 
int F(int *a, int i, int n)
{
    if (n < 0)
    {
        return 0;
    }
    else 
    {
        if (n == 0)
        {
            return 1;
        }
    }
    if (i < 0)
    {
        return 0;
    }
    else
    {
        return  F(a, i - 1, n) + F(a, i, n - a[i]);
    }   
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.07.2013, 15:20     Элементы Комбинаторики #4
Цитата Сообщение от Dantes48 Посмотреть сообщение
Спасибо, все работает

Не по теме:

на здоровье, обращайтесь

Yandex
Объявления
09.07.2013, 15:20     Элементы Комбинаторики
Ответ Создать тему
Опции темы

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