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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 148, средняя оценка - 4.86
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
#1

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

17.08.2011, 12:48. Просмотров 21000. Ответов 52
Метки нет (Все метки)

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

Разложение натурального числа на слагаемые - C++
Я не силен в математике, но математику надоело вести математические методы и он начал давать задачки по созданию программ, все бы ничего,...

Разложение натурального положительного числа на слагаемые? - C++
Помогите... Нужно разложить число на слагаемые... Причем, условия такие: слагаемые должны быть в диапазоне от 1 до 10 (соответственно...

Разложение на слагаемые - C++
Подскажите идею для написания программы, желательно с рекурсией: Дано натуральное число n. Небходимо вывести все возможные варианты...

Разложение на слагаемые - C++
На входе у нас число (нат, пол) которое нужно разложить и ожидаймое количество слагаймых алгоритм решения таков..выделяем место для...

разложение на все возможные слагаемые - C++
требуется разложить число, вводимое с клавиатуры и не большее 45, на слагаемые от 1 до 9 Добавлено через 6 минут (разными вариантами...

Найти все слагаемые заданного числа - C++
Задача: Дано число n, отобразить его всевозможные k слагаемые. Может у кого есть готовая задача или кто может помочь? Заранее спасибо.

Подсчитать количество различных разбиений числа N на натуральные слагаемые - C++
Условие: требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два разложения считаются различными, если...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:15     Разложение числа на слагаемые #31
Цитата Сообщение от diagon Посмотреть сообщение
У меня по-другому получается =)
Но это все-таки погрешность, ибо разницы в коде практически нету.


Diagon, я не хвалю свой алгоритм, просто хочу понять почему так...
Почему ваш у вас быстрее, а мой - у меня, чудо какое-то...
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:22     Разложение числа на слагаемые #32
Цитата Сообщение от Olga_ Посмотреть сообщение
Но почему, у меня нет отсечений лишних и у меня в 2 раза быстрее работает. Пусть решают независисые эксперты
Так если бы эксперты =)
Результат будет зависеть от компилятора(gcc оба кода отлично соптимизировал, а какой-нибудь VC вообще повиснет при компиляции), загруженности системы, расположения звезд на небе...
По поводу отсечения - алгоритмы одинаковые, разная реализация. У вас она более оптимальная, а у меня более понятная и больше простора оптимизирующему компилятору =)
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:26     Разложение числа на слагаемые #33
Цитата Сообщение от diagon Посмотреть сообщение
Результат будет зависеть от компилятора
Да, вы правы, от всего зависит. А еще от системы зависит - запись/чтения в файл.
talis
791 / 543 / 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_
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
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 11:39     Разложение числа на слагаемые #36
Время выполнения в миллисекундах по показателю clock(), avg - среднее значение
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:42     Разложение числа на слагаемые #37
Цитата Сообщение от talis Посмотреть сообщение
-=ЮрА=- - 0, 16, 0, 16, 16, 0, avg = 8
xDDDDD
Это как вообще?
А разница банально в оптимизации..
Только результат действительно нереалистичный какой-то, даже если компилировать с ключами на максимальную оптимизацию.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:44     Разложение числа на слагаемые #38
Цитата Сообщение от talis Посмотреть сообщение
Время выполнения в миллисекундах по показателю clock(), avg - среднее значение
Странно, очень странно Но спасибо за тест

Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
xDDDDD
Это как вообще?
Присоединяюсь
talis
791 / 543 / 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");
}
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 11:57     Разложение числа на слагаемые #40
Цитата Сообщение от talis Посмотреть сообщение
Просто вам с Ольгой нужно просчитать 6 метров вывода, а ему - 50 килобайт
Тогда этот вариант сразу отпадает, нужны все разбиения числа на слагаемые.

Придется признать, что у diagon оптимальнее вариант
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 11:59     Разложение числа на слагаемые #41
Бывают более оптимальные.
http://********/index.asp?main=bstatus&id_t=365
Я на 3м месте там. На первом в три раза быстрее.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:02     Разложение числа на слагаемые #42
Цитата Сообщение от diagon Посмотреть сообщение
Бывают более оптимальные.
Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
18.08.2011, 12:07     Разложение числа на слагаемые #43
diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.

Olga_, ну у вас не самое худшее . Моя первая мысль вообще была создать кэш сумм всех цифр от 2 до n - 1, а затем его обходить и, при необходимости, этим же кэшем пользуясь, выводить слагаемые слагаемого. Но потом, правда, сообразил, что обход его будет дольше, чем простое вычитание, так что пришёл к чему-то вроде варианта diagon.

Цитата Сообщение от Olga_ Посмотреть сообщение
Бывают-не бывают, по сравнению с моим вроде оптимальнее, хотя на моем компьютере наоборот, странно
А что у вас за компилятор, процессор и ОС?

Добавлено через 2 минуты
diagon, и, если бы у них была не винда, может по памяти вы бы и вперёд вырвались - кто знает?

Добавлено через 1 минуту
Да и компилятор у них мелкосовтовский
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
18.08.2011, 12:08     Разложение числа на слагаемые #44
Цитата Сообщение от talis Посмотреть сообщение
А что у вас за компилятор, процессор и ОС?
Да все простое: компиляторы Builder C++ и Visual Studio, процессор Celeron 2800, ОС - Win XP
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.08.2011, 12:10     Разложение числа на слагаемые
Еще ссылки по теме:

Разложение числа - C++
Число можно разложить по 5 и по 3, то есть если это допустим 8 то выйдет 5 и 3, причем не должно быть остатка, допустим 22 можно разложить...

разложение числа - C++
Как ,допустим, разложить число 1924 на 1 9 2 4. Даже идей нет

Разложение числа - C++
Всем привет! Есть некое число N и массив arr (k - размер массива). Нужно написать программу, которая выведет на экран все возможные...

Разложение числа - C++
вот написал прогу которая которая должна разложить число N на множители по массиву M и К где М {1,5,10,50,100} а К мы должны сами найти....

Разложение Натурального числа - C++
Привет.Помогите пожалуйста решить задачу. Разложить натуральное число на простые множители (вывести, например, 36=1*2*2*3*3 или 7 = 1*7)....


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.08.2011, 12:10     Разложение числа на слагаемые #45
Цитата Сообщение от talis Посмотреть сообщение
diagon, я бы не ориентировался на эту таблицу. Там основным критерием является количество символов кода, что не есть хорошо.
Однако это единственно возможный критерий. По другим критериями Java, Basic, c++ отлетают сразу, остаются чистый си и паскаль. А так как время/память вычисляются неточно, то можно пересдать задачу, и она может отработать оптимальнее. Тогда чтобы оказаться в топе, нужно писать прекалк и по сотне раз отправлять одну и ту же задачу...
А пытаясь сжать свой код я многому научился... =)
Yandex
Объявления
18.08.2011, 12:10     Разложение числа на слагаемые
Ответ Создать тему
Опции темы

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