Форум программистов, компьютерный форум 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++ Разложение числа на цифры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 10:44     Разложение числа на слагаемые #21
Цитата Сообщение от Dani Посмотреть сообщение
У Diagon 953 ms.
Странно, а у меня его программа 2500 миллисекунд работает, а моя 1200 А вы так тестируете?

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
#include<stdio.h>
#include<time.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, t;
   if ((g = fopen("OUTPUT.TXT","wt")) == NULL)
      return 1;
   printf("n = ");
   scanf("%ld", &n);
   t = clock();
   Partition(n, n - 1, 0);
   printf("%ld\n", clock() - t);
   return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 10:47     Разложение числа на слагаемые #22
Olga_, Dani, на время тестирования отключайтесь от инета и отключайте антивирус. У меня с ним время выполнения прыгает на 1000мс в каждую сторону, без него - разброс порядка 300мс.

Добавлено через 44 секунды
Да, и на винде консоль тормознутая, не выводите на неё.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 10:49     Разложение числа на слагаемые #23
Цитата Сообщение от talis Посмотреть сообщение
Olga_, Dani, на время тестирования отключайтесь от инета и отключайте антивирус. У меня с ним время выполнения прыгает на 1000мс в каждую сторону, без него - разброс порядка 300мс.

Добавлено через 44 секунды
Да, и на винде консоль тормознутая, не выводите на неё.
А ваши тесты всех вариантов что показывают?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
18.08.2011, 10:50  [ТС]     Разложение числа на слагаемые #24
Цитата Сообщение от talis Посмотреть сообщение
Olga_, Dani, на время тестирования отключайтесь от инета и отключайте антивирус. У меня с ним время выполнения прыгает на 1000мс в каждую сторону, без него - разброс порядка 300мс.
На олимпиадах это вряд ли будут делать)

Добавлено через 49 секунд
Цитата Сообщение от Olga_ Посмотреть сообщение
Странно, а у меня его программа 2500 миллисекунд работает, а моя 1200 А вы так тестируете?
Также
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 10:52     Разложение числа на слагаемые #25
Цитата Сообщение от Dani Посмотреть сообщение
Также
Так вы же написали, что у diagona быстрее? Хотя, по коду и времени, нет
Я просто хочу привлечь ваше внимание к тому, что алгоритм получился очень экономичным и быстрым
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 10:56     Разложение числа на слагаемые #26
Вот доказательство тормознутости вывода

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
#include <stdio.h>
#include <time.h>
 
int main()
{
    unsigned short i = 0, a;
 
    clock_t time1 = clock();
 
    for( ; i < 0xffff; i++ )
    {
        a = i << 1; /* чтобы компилятор не отбросил второй цикл */
        printf( "%i\n", i );
    }
 
    clock_t time2 = clock();
 
    printf( "Time: %i; a = %i\nPress any key to test without output", time2 - time1, a );
 
    getch();
 
    a = 0;
    printf( "\na = %i\n", a );
 
    time1 = clock();
 
    for( i = 0; i < 0xffff; i++ )
       a = i << 1; /* чтобы компилятор не отбросил цикл */
 
    time2 = clock();
 
    printf( "Time: %i; a = %i\nPress any key to quit", time2 - time1, a );
 
    getch();
 
    return 0;
}

А варианты сейчас прогоню у себя и отпишусь
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:03     Разложение числа на слагаемые #27
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Тот же самый алгоритм на С++:

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
#include <iostream>
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
long a[100];
 
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 - 1;  i++)
          std::cout << a[i] << "+";
       std::cout << a[i] << "\n";
   }
}
 
int main(){
    long n;
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::cin >> n;
    Partition(n, n - 1, 0);
    return 0;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:05     Разложение числа на слагаемые #28
Цитата Сообщение от Olga_ Посмотреть сообщение
Так вы же написали, что у diagona быстрее? Хотя, по коду и времени, нет
А в чем разница-то? =)
Сменить язык, немного изменить условия - получится то же самое. Даже аргументы функций практически совпадают. P.S. clock'ом неточно измерять, погрешность у него высокая. Попробую у себя более точно time'ом замерить.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:07     Разложение числа на слагаемые #29
Цитата Сообщение от diagon Посмотреть сообщение
А в чем разница-то? =)
Меньше условий После смены языка - пост 27. И все же алгоритмы немного разные и написаны независимо
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:11     Разложение числа на слагаемые #30
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
diagon@shadeware:~$ cat first.cpp && g++ first.cpp -std=c++0x && time ./a.out
#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);
}
 
real    0m0.671s
user    0m0.636s
sys 0m0.020s
diagon@shadeware:~$ cat second.cpp && g++ second.cpp -std=c++0x && time ./a.out
#include <iostream>
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
long a[100];
 
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 - 1;  i++)
          std::cout << a[i] << "+";
       std::cout << a[i] << "\n";
   }
}
 
int main(){
    long n;
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    std::cin >> n;
    Partition(n, n - 1, 0);
    return 0;
}
 
real    0m0.786s
user    0m0.768s
sys 0m0.012s
diagon@shadeware:~$
У меня по-другому получается =)
Но это все-таки погрешность, ибо разницы в коде практически нету.
Причем с ключем -O3, что странно, обе программы медленнее работают..
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:15     Разложение числа на слагаемые #31
Цитата Сообщение от diagon Посмотреть сообщение
У меня по-другому получается =)
Но это все-таки погрешность, ибо разницы в коде практически нету.


Diagon, я не хвалю свой алгоритм, просто хочу понять почему так...
Почему ваш у вас быстрее, а мой - у меня, чудо какое-то...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:22     Разложение числа на слагаемые #32
Цитата Сообщение от Olga_ Посмотреть сообщение
Но почему, у меня нет отсечений лишних и у меня в 2 раза быстрее работает. Пусть решают независисые эксперты
Так если бы эксперты =)
Результат будет зависеть от компилятора(gcc оба кода отлично соптимизировал, а какой-нибудь VC вообще повиснет при компиляции), загруженности системы, расположения звезд на небе...
По поводу отсечения - алгоритмы одинаковые, разная реализация. У вас она более оптимальная, а у меня более понятная и больше простора оптимизирующему компилятору =)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:26     Разложение числа на слагаемые #33
Цитата Сообщение от diagon Посмотреть сообщение
Результат будет зависеть от компилятора
Да, вы правы, от всего зависит. А еще от системы зависит - запись/чтения в файл.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 11:35     Разложение числа на слагаемые #34
Я не эксперт, но вот, прогнал Сишный вариант Ольги, первый вариант diagon (извините, не знаю как склоняется ваш ник ) и последний вариант -=ЮрЫ=-, все при n = 50. Единственное - ко всем прикрутил метод замера через разницу показаний clock() до и после просчёта, и весь вывод, кроме результатов замера, отправил в файл. К моему великому удивлению:

Olga_ - 1109, 1109, 1125, 1110, 1141, 1142, avg = 1122,6666
diagon - 226, 265, 250, 250, 255, 250, avg = 249,3333
-=ЮрА=- - 0, 16, 0, 16, 16, 0, avg = 8

Теперь о выводе:

У diagon и Ольги вывод выглядит равноценным и занимает под 6 метров. У -=ЮрЫ=- он занимает 47,7 килобайт, но и выдаёт не все варианты разложения слагаемых. Файловый вывод в варианте diagon был через std::ofstream (c++ так c++), а в Ольгином и -=ЮриноМ=- через fprintf.

При глупой и наивной попытке скопировать вывод Ольги в сообщение firefox сильно задумался, по-этому пришлось снять задачу... Выкладываю файлами.

test_c_2.7z

Система:

Windows XP SP2 (увы, какая была загружена, такая и была загружена)
AMD Turion X-2 DualCore Mobile RM-74 2.2 GHz (к чёрту DualCore, всё равно в одном потоке выполняется)
3 Gb RAM
gcc 4.4.1 TDM-2 mingw
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:38     Разложение числа на слагаемые #35
Цитата Сообщение от talis Посмотреть сообщение
К моему великому удивлению:

Olga_ - 1109, 1109, 1125, 1110, 1141, 1142, avg = 1122,6666
diagon - 226, 265, 250, 250, 255, 250, avg = 249,3333
-=ЮрА=- - 0, 16, 0, 16, 16, 0, avg = 8
А что это за цифры? Неужели миллисекунды
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 11:39     Разложение числа на слагаемые #36
Время выполнения в миллисекундах по показателю clock(), avg - среднее значение
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:42     Разложение числа на слагаемые #37
Цитата Сообщение от talis Посмотреть сообщение
-=ЮрА=- - 0, 16, 0, 16, 16, 0, avg = 8
xDDDDD
Это как вообще?
А разница банально в оптимизации..
Только результат действительно нереалистичный какой-то, даже если компилировать с ключами на максимальную оптимизацию.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:44     Разложение числа на слагаемые #38
Цитата Сообщение от talis Посмотреть сообщение
Время выполнения в миллисекундах по показателю clock(), avg - среднее значение
Странно, очень странно Но спасибо за тест

Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
xDDDDD
Это как вообще?
Присоединяюсь
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 11:53     Разложение числа на слагаемые #39
Цитата Сообщение от diagon Посмотреть сообщение
Это как вообще?
А разница банально в оптимизации..
Только результат действительно нереалистичный какой-то, даже если компилировать с ключами на максимальную оптимизацию.
Цитата Сообщение от Olga_ Посмотреть сообщение
Присоединяюсь
Да никаких ключей не было, даже на целевой процессор. Просто вам с Ольгой нужно просчитать 6 метров вывода, а ему - 50 килобайт

Добавлено через 8 минут

Не по теме:

У всех было 502 bad gateway..?



Вот код Юры, который я компилировал. Сами смотрите:

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
106
107
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
 
void split_int(int num);
 
FILE * fd;
 
int main()
{
    fd = fopen( "Yura.txt", "w" );
 
        int N;
 
        do
        {
                printf("Enter int number: ");
                scanf("%d",&N);
 
                clock_t time = clock();
 
                split_int(N);
 
                printf( "split time %ld msec", clock() - time );
                printf("[Y/N] Y - Enter new number\r\n");
 
                fseek( stdout, 0, SEEK_END );
        }
        while(toupper(getch()) == 'Y');
        //split_int
 
    fclose( fd );
}
 
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)
                                fprintf( fd, "%d",i1);
                        if(i2 != 0)
                        {
                                if(i1 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i2);
                        }
                        if(i3 != 0)
                        {
                                if(i2 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i3);
                        }
                        if(i4 != 0)
                        {
                                if(i3 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i4);
                        }
                        if(i5 != 0)
                        {
                                if(i4 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i5);
                        }
                        if(i6 != 0)
                        {
                                if(i5 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i6);
                        }
                        if(i7 != 0)
                        {
                                if(i6 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i7);
                        }
                        if(i8 != 0)
                        {
                                if(i7 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i8);
                        }
                        if(i9 != 0)
                        {
                                if(i8 != 0)
                                        fprintf( fd, "%s",stub);
                                fprintf( fd, "%d",i9);
                        }
                        fprintf( fd, " == %d\r\n",num);
                }
 
        }
        fprintf( fd, "\r\n");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.08.2011, 11:57     Разложение числа на слагаемые
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:57     Разложение числа на слагаемые #40
Цитата Сообщение от talis Посмотреть сообщение
Просто вам с Ольгой нужно просчитать 6 метров вывода, а ему - 50 килобайт
Тогда этот вариант сразу отпадает, нужны все разбиения числа на слагаемые.

Придется признать, что у diagon оптимальнее вариант
Yandex
Объявления
18.08.2011, 11:57     Разложение числа на слагаемые
Ответ Создать тему
Опции темы

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