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

Разложение числа на слагаемые - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 148, средняя оценка - 4.86
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 12:48     Разложение числа на слагаемые #1
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой самый быстрый алгоритм разложения числа на слагаемые вы предложите? Думаю, максимальный тест n<=50.
З.Ы. Проверю на время сам. И разложения должны быть без повторений (перестановка слагаемых не дает новых разложений) и чтоб строка слагаемых выводилась в файл "in.txt".
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.08.2011, 12:48     Разложение числа на слагаемые
Посмотрите здесь:

C++ Разложение числа
C++ Разложение на слагаемые
Разложение числа C++
Разложение натурального положительного числа на слагаемые? C++
C++ Разложение числа на цифры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 12:54     Разложение числа на слагаемые #2
Мое решение этой задачи
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
int n, sum[40];
void print_terms(int left, int min = 0, int i = 0){
    if (left < 0 || min == n)
        return;
    sum[i] = min;
    if (min != 0)
    {
        print_terms(left - min, min, i + 1);
    }
    print_terms(left - 1, min + 1, i);
    if (left == 0)
    {
        for (int j = 0; j <= i; ++j)
            std::cout << sum[j] << (j != i ? '+' : '\n');
    }
        
}
int main(){
    std::cin >> n; 
    print_terms(n);
}
Непонятно только это
Цитата Сообщение от Dani Посмотреть сообщение
числа должны идти в порядке возрастания
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 13:00  [ТС]     Разложение числа на слагаемые #3
Цитата Сообщение от diagon Посмотреть сообщение
Непонятно только это
Сообщение от Dani
числа должны идти в порядке возрастания
Забудь)))

Добавлено через 5 минут
Цитата Сообщение от diagon Посмотреть сообщение
Мое решение этой задачи
Можешь с файлами? (чтоб все было по честному - время разложения)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 13:04     Разложение числа на слагаемые #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Ну у меня явно не самое быстрое решение, т.к. по два рекурсивных вызова на каждой цифре идет. Если верить acmp, то при n ~ 40 работает ~0.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
#include <iostream>
int n, sum[40];
void print_terms(int left, int min = 0, int i = 0){
    if (left < 0 || min == n)
        return;
    sum[i] = min;
    if (min != 0)
    {
        print_terms(left - min, min, i + 1);
    }
    print_terms(left - 1, min + 1, i);
    if (left == 0)
    {
        for (int j = 0; j <= i; ++j)
            std::cout << sum[j] << (j != i ? '+' : '\n');
    }
        
}
int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::cin >> n; 
    print_terms(n);
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 13:09  [ТС]     Разложение числа на слагаемые #5
diagon, тестировал три раза. При n=50 программа работает минимум за 953 миллисекунды. Кто предложит лучшее решение???
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 13:38     Разложение числа на слагаемые #6
Dani, а слагаемых должно быть больше 2-х? Например, 6 = 1 + 2 + 3 - такое нужно? Или хватит 1 + 5, 2 + 4, 3 + 3?
-=ЮрА=-
Заблокирован
Автор FAQ
17.08.2011, 13:38     Разложение числа на слагаемые #7
Как вариант, но с индикацией работает медленно
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
 
void split_int(int num);
int main()
{
    int N;
    time_t bgn,end;
    do
    {
        time(&bgn);
        printf("Enter int number: ");
        scanf("%d",&N);
        split_int(N);
        time(&end);
        printf("split time %.3f sec",difftime(end,bgn));
        printf("[Y/N] Y - Enter new number\r\n");
    }
    while(toupper(getch()) == 'Y');
    //split_int
}
 
void split_int(int num)
{
    int i1,i2,i3,i4,i5,i6,i7,i8,i9,MAX = 10;
    for(i1 = 1; i1 < MAX; i1++)
    {
        if(i1 == num)
                printf("%d = %d\r\n",i1,num);
        for(i2 = 1; i2 < MAX; i2++)
        {
            if(i1 + i2 == num)
                printf
                (
                    "%d + %d = %d\r\n",
                    i1,i2,num
                );
            for(i3 = 1; i3 < MAX; i3++)
            {
                if(i1 + i2 + i3 == num)
                    printf
                    (
                        "%d + %d + %d = %d\r\n",
                        i1,i2,i3,num
                    );
                for(i4 = 1; i4 < MAX; i4++)
                {
                    if(i1 + i2 + i3 + i4 == num)
                        printf
                        (
                            "%d + %d + %d + %d = %d\r\n",
                            i1,i2,i3,i4,num
                        );
                    for(i5 = 1; i5 < MAX; i5++)
                    {
                        if(i1 + i2 + i3 + i4 + i5 == num)
                            printf
                            (
                                "%d + %d + %d + %d + %d= %d\r\n",
                                i1,i2,i3,i4,i5,num
                            );
                        for(i6 = 1; i6 < MAX; i6++)
                        {
                            if(i1 + i2 + i3 + i4 + i5 + i6 == num)
                                printf
                                (
                                    "%d + %d + %d + %d + %d + %d = %d\r\n",
                                    i1,i2,i3,i4,i5,i6,num
                                );
                            for(i7 = 1; i7 < MAX; i7++)
                            {
                                if(i1 + i2 + i3 + i4 + i5 + i6 + i7 == num)
                                    printf
                                    (
                                        "%d + %d + %d +%d + %d + %d + %d = %d\r\n",
                                        i1,i2,i3,i4,i5,i6,i7,num
                                    );
                                for(i8 = 1; i8 < MAX; i8++)
                                {
                                    if(i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 == num)
                                        printf
                                        (
                                            "%d + %d + %d + %d + %d + %d + %d + %d = %d\r\n",
                                            i1,i2,i3,i4,i5,i6,i7,i8,num
                                        );
                                    for(i9 = 1; i9 < MAX; i9++)
                                        if(i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 == num)
                                            printf
                                            (
                                                "%d + %d + %d + %d + %d + %d + %d + %d + %d = %d\r\n",
                                                i1,i2,i3,i4,i5,i6,i7,i8,i9,num
                                            );
                                }
 
                            }
                        }
                    }
                }
            }
        }
    }
    printf("\r\n");
}
Миниатюры
Разложение числа на слагаемые  
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
17.08.2011, 13:40     Разложение числа на слагаемые #8
Цитата Сообщение от Dani Посмотреть сообщение
При n=50 программа работает минимум за 953 миллисекунды.
мой терминал показывает 12 секунд

Цитата Сообщение от Dani Посмотреть сообщение
естировал три раза.
чем тестировал?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 13:40  [ТС]     Разложение числа на слагаемые #9
Цитата Сообщение от talis Посмотреть сообщение
Или хватит 1 + 5, 2 + 4, 3 + 3?
Хватит

Добавлено через 27 секунд
Цитата Сообщение от Maxwe11 Посмотреть сообщение
у меня работало 12 секунд
Это же решение Diagon?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.08.2011, 13:43     Разложение числа на слагаемые #10
Цитата Сообщение от Maxwe11 Посмотреть сообщение
мой терминал показывает 12 секунд
Гы.
Код
diagon@shadeware:~$ cat input.txt && time ./a.out
50

real	0m0.607s
user	0m0.568s
sys	0m0.016s
diagon@shadeware:~$
У меня там вообще все разложения числа на слагаемые выводятся... Например, для 3 - 1 + 1 + 1, 1 + 2
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.08.2011, 13:44     Разложение числа на слагаемые #11
Цитата Сообщение от Dani Посмотреть сообщение
Цитата Сообщение от talis
Или хватит 1 + 5, 2 + 4, 3 + 3?
Хватит
Раз хватит, то так:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
 
int main( int argc, char ** argv )
{
    /* допишите здесь freopen - не хочу файлы создавать :-) */
 
    int num, i;
 
    scanf( "%i", &num );
 
    for( i = 1; i <= num / 2; i++ )
       printf( "%i + %i\n", i, num - i );
 
    return 0;
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 13:58  [ТС]     Разложение числа на слагаемые #12
Цитата Сообщение от Maxwe11 Посмотреть сообщение
чем тестировал?
C++
1
clock();
Добавлено через 1 минуту
Цитата Сообщение от talis Посмотреть сообщение
Раз хватит, то так:
Не туда почитал, не больше двух а больше или равно 2.

Добавлено через 1 минуту
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
Как вариант, но с индикацией работает медленно
хм.. у вас почти все выражения одной длины: не нашел 25+25 = 50

Добавлено через 4 минуты
Цитата Сообщение от Dani Посмотреть сообщение
Сообщение от -=ЮрА=-
Как вариант, но с индикацией работает медленно
У Вас работает за 7734 ms

Добавлено через 6 минут
output Diagon: 5.76 мегабайт, а -=Юра=- - 98,5 мегабайт. У кого-то что-то не так.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
17.08.2011, 14:47     Разложение числа на слагаемые #13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
работает медленно
Может сто'ит time(&bgn); собственно перед функцией поставить, а не перед запросом и чтением значения из потока?
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.08.2011, 14:59     Разложение числа на слагаемые #14
Лучше рекурсивного перебора с отсечениями не видел (это как у diagon).
-=ЮрА=-
Заблокирован
Автор FAQ
17.08.2011, 16:01     Разложение числа на слагаемые #15
Цитата Сообщение от easybudda Посмотреть сообщение
Может сто'ит time(&bgn); собственно перед функцией поставить, а не перед запросом и чтением значения из потока?
- логично, я согласен

Попытался исключить вывод одинаковых значений, вот к чему пришёл
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
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
 
void split_int(int num);
 
int main()
{
    int N;
    time_t bgn,end;
    do
    {
        printf("Enter int number: ");
        scanf("%d",&N);
        time(&bgn);
        split_int(N);
        time(&end);
        printf("split time %lf sec",difftime(end,bgn));
        printf("[Y/N] Y - Enter new number\r\n");
    }
    while(toupper(getch()) == 'Y');
    //split_int
}
 
void split_int(int num)
{
    int i1,i2,i3,i4,i5,i6,i7,i8,i9,MAX = 10;
    for(i1 = 0; i1 < MAX; i1++)
    for(i2 = i1; i2 < MAX; i2++)
    for(i3 = i2; i3 < MAX; i3++)
    for(i4 = i3; i4 < MAX; i4++)
    for(i5 = i4; i5 < MAX; i5++)
    for(i6 = i5; i6 < MAX; i6++)
    for(i7 = i6; i7 < MAX; i7++)
    for(i8 = i7; i8 < MAX; i8++)
    for(i9 = i8; i9 < MAX; i9++)
    {
        if(i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 == num)
        {
            if(i1 != 0)
                printf("%d + ",i1);
            if(i2 != 0)
                printf("%d + ",i2);
            if(i3 != 0)
                printf("%d + ",i3);
            if(i4 != 0)
                printf("%d + ",i4);
            if(i5 != 0)
                printf("%d + ",i5);
            if(i6 != 0)
                printf("%d + ",i6);
            if(i7 != 0)
                printf("%d + ",i7);
            if(i8 != 0)
                printf("%d + ",i8);
            if(i9 != 0)
                printf("%d",i9);
            printf(" == %d\r\n",num);
        }
 
    }           
    printf("\r\n");
}
Миниатюры
Разложение числа на слагаемые  
-=ЮрА=-
Заблокирован
Автор FAQ
17.08.2011, 16:34     Разложение числа на слагаемые #16
Маленькая модернизация (чтобы избежать вот такого вывода __+ 6 + 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void split_int(int num)
{
    char stub[] = " + ";
    int i1,i2,i3,i4,i5,i6,i7,i8,i9,MAX = 10;
    for(i1 = 0; i1 < MAX; i1++)
    for(i2 = i1; i2 < MAX; i2++)
    for(i3 = i2; i3 < MAX; i3++)
    for(i4 = i3; i4 < MAX; i4++)
    for(i5 = i4; i5 < MAX; i5++)
    for(i6 = i5; i6 < MAX; i6++)
    for(i7 = i6; i7 < MAX; i7++)
    for(i8 = i7; i8 < MAX; i8++)
    for(i9 = i8; i9 < MAX; i9++)
    {
        if(i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 == num)
        {
            if(i1 != 0)
                printf("%d",i1);
            if(i2 != 0)
            {
                if(i1 != 0)
                    printf("%s",stub);
                printf("%d",i2);
            }
            if(i3 != 0)
            {
                if(i2 != 0)
                    printf("%s",stub);
                printf("%d",i3);
            }
            if(i4 != 0)
            {
                if(i3 != 0)
                    printf("%s",stub);
                printf("%d",i4);
            }
            if(i5 != 0)
            {
                if(i4 != 0)
                    printf("%s",stub);
                printf("%d",i5);
            }
            if(i6 != 0)
            {
                if(i5 != 0)
                    printf("%s",stub);
                printf("%d",i6);
            }
            if(i7 != 0)
            {
                if(i6 != 0)
                    printf("%s",stub);
                printf("%d",i7);
            }
            if(i8 != 0)
            {
                if(i7 != 0)
                    printf("%s",stub);
                printf("%d",i8);
            }
            if(i9 != 0)
            {
                if(i8 != 0)
                    printf("%s",stub);
                printf("%d",i9);
            }
            printf(" == %d\r\n",num);
        }
 
    }           
    printf("\r\n");
}
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
17.08.2011, 21:35     Разложение числа на слагаемые #17
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include<stdio.h>
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
long a[100];
FILE *g;
 
void Partition(long n, long high, long pos)
{
   long i;
   if (n > 0)
   {
       for (i = 1; i <= high; i++)
       {
          a[pos] = i;
          Partition(n - i, MIN(i, n - i), pos + 1);
       }
   }
   else
   {
       for (i = 0; i < pos; i++)
          fprintf(g, "%ld ", a[i]);
       fprintf(g, "\n");
   }
}
 
int main()
{
   long n;
   if ((g = fopen("OUTPUT.TXT","wt")) == NULL)
      return 1;
   printf("n = ");
   scanf("%ld", &n);
   Partition(n, n - 1, 0);
   return 0;
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
17.08.2011, 22:20  [ТС]     Разложение числа на слагаемые #18
Цитата Сообщение от Olga_ Посмотреть сообщение
Код C1
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 #include<stdio.h>
#define MIN(x, y) ((x) < (y) ? (x) : (y))
long a[100];
FILE *g;
void Partition(long n, long high, long pos)
{
long i;
if (n > 0)
{
for (i = 1; i <= high; i++)
{
a[pos] = i;
Partition(n - i, MIN(i, n - i), pos + 1);
}
}
else
{
for (i = 0; i < pos; i++)
fprintf(g, "%ld ", a[i]);
fprintf(g, "\n");
}
}
int main()
{
long n;
if ((g = fopen("OUTPUT.TXT","wt")) == NULL)
return 1;
printf("n = ");
scanf("%ld", &n);
Partition(n, n - 1, 0);
Ровно 1 секунда!
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 08:43     Разложение числа на слагаемые #19
Dani, это хорошо или плохо по сравнению с другими вариантами (так как вы тестируете на время)?
И заметьте, используется всего одно условие, никаких лишних отсечений, пробегаем только необходимые слагаемые.

Добавлено через 21 минуту
А если просто требуется подсчитать количество, то код совсем компактным стает:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
 
void Partition(int n, int high, int *count)
{
   if (n)
      for (int i = 1; i <= high; i++)
          Partition(n - i, MIN(i, n - i), count);
   else
      (*count)++;
}
 
int main()
{
   int n, count = 0;
   std::cin >> n;
   Partition(n, n - 1, &count);
   std::cout << count;
   return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.08.2011, 10:40     Разложение числа на слагаемые
Еще ссылки по теме:

C++ разложение на все возможные слагаемые
C++ разложение числа
C++ Подсчитать количество различных разбиений числа N на натуральные слагаемые

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.08.2011, 10:40  [ТС]     Разложение числа на слагаемые #20
Цитата Сообщение от Olga_ Посмотреть сообщение
Dani, это хорошо или плохо по сравнению с другими вариантами (так как вы тестируете на время)?
У Diagon 953 ms.
Yandex
Объявления
18.08.2011, 10:40     Разложение числа на слагаемые
Ответ Создать тему
Опции темы

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