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

Разбиение на слагаемые - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.97
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
17.11.2010, 18:25     Разбиение на слагаемые #1
Задание:нужно вывести на экран в лексикографическом порядке все разбиения на слагаемые числа n от 1 до 20.
пример:
n=5
5=1+1+1+1+1
5=1+1+1+2
5=1+1+3
5=1+2+2
5=1+4
5=2+3
5=5
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
archinko
13 / 13 / 2
Регистрация: 02.03.2010
Сообщений: 29
17.11.2010, 21:56     Разбиение на слагаемые #2
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
#include <stdlib.h>
#include <iostream>
using namespace std;
#define N 20
int main()
{
    int n,m[N],temp;
    for(int i=0;i<N;i++) m[i]=1;
 
    while(n<1 || n>N){
    cout<< "Введите значение для n от 1 до "<<N<<endl;
    cin>>n;
    if(n<1 || n>N) cout<< "Не допустимое число"<<endl;
    }
 
    temp=n-1;
 
    do 
    {
        cout<<n<<"=";
        for(int i=0;i<n;i++) 
        {
            if(i==n-1 || m[i+1]==0) {
                cout<<m[i]<<endl;
                break;}
            else cout<<m[i]<<"+";
        }
        if(m[temp]-1>=m[temp-1]+1 && temp>=1) m[temp]--,m[temp-1]++;
        else{
        m[temp-1]+=m[temp];
        m[temp--]=0;
        }
    }while(m[0]!=0);
                
}
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
17.11.2010, 23:39  [ТС]     Разбиение на слагаемые #3
Спасибо конечно но нельзя ли не на с++ а на с,и если не затруднит можете добавить, пожалуйста, комментарии.Заранее благодарю
archinko
13 / 13 / 2
Регистрация: 02.03.2010
Сообщений: 29
18.11.2010, 01:30     Разбиение на слагаемые #4
Ну как то так. Отличаеться от первой только тем, что cin и cout заменил на printf и scanf. Уф как-то много я текста в коментах накатал О_о
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
#include <stdlib.h>
#include <stdio.h>
#define N 20
int main()
{
        int n,m[N],temp;
    //Запрос у пользователя значения n, если введеное значение не попадает в указанный диапозон (1=<n=<N) то спрашиваем заново
        while(n<1 || n>N){
        printf("Введите значение для n от 1 до %d\n",N); 
        scanf("%d",&n);
        if(n<1 || n>N) printf("Не допустимое число\n");
        }
    
    for(int i=0;i<n;i++) m[i]=1; //Инициализируем массив m[] единицами( В самом начале любое число можно представить сумой единиц. Например 5=1+1+1+1+1 или 3=1+1+1, по этому единицами)
 
        temp=n-1; //эту переменную будем использовать, что бы двигаться по масиву m[]
    //далее основной цыкл while, выполняеться до тех пор пока m[0]!=0
        do 
        {
                printf("%d=",n);
                for(int i=0;i<n;i++) 
                {
                        if(i==n-1 || m[i+1]==0) {   //Если это уже последний элемент массива m[] или следующий элемент в масиве m[] равен 0, делаем конец строки, 1 уровнение напечатано ну и break для выхода из текущего for
                                printf("%d\n",m[i]);
                                break;}
                        else printf("%d+",m[i]); //если же это еще не последний элемент масива то просто печатаем еще одно слагаемое 
                }
//Здесь немного сложный для понимания момент. С помощью temp мы фиксируем длину нашего масива. Постепенно массив будет уменшаться и temp соответсвенно. 
                if(m[temp]-1>=m[temp-1]+1 && temp>=1) m[temp]--,m[temp-1]++; /* Если m[текущая]-1 больше или равна m[следующая]+1, то тогда увеличуем m[следующая] на 1 ,а m[текущая] соответсвенно уменшаем на 1. Таким образом сума слагаемых не изменится. Вот пример такой ситуации: 5=1+1+3. В данный момент масив m выглядит так: 
m[0]=1 
m[1]=1
m[2]=3
Проверяем m[текущею] (а это m[2]) c m[следующей] (ну а это m[1]), и "если m[текущая]-1 больше или равна m[следующая]+1" то тогда m[2]-- а m[1]++. Вот какой у нас получится теперь масив :
m[0]=1 
m[1]=2
m[2]=2
А вот какое уровнение получится 5=1+2+2
*/
                else{ /* Ну а если "m[текущая]-1 НЕ больше или равна m[следующая]+1" то тагда сумируем два последних элемента массива, и записуем его в следующую ячейку масива. Последний элемент обнуляем и temp уменшаем на единицу (m[temp--]=0). Вот пример такой ситуации: 5=1+2+2. В данный момент масив m выглядит так: 
m[0]=1 
m[1]=2
m[2]=2
Как видим m[2]-1<m[1]+1. Значит программа выполнит следующие:
m[1]=m[1]+m[2];
m[2]=0;
Ну и уменшим temp на единицу (temp--)
Вот какое уровнение теперь у нас получится 5=1+4
*/
                m[temp-1]+=m[temp];
                m[temp--]=0; //Когда temp станет равным 0, здесь мы обнулим m[0]. А значит выйдем таки из цыкла while по условию (m[0]!=0)
                }
        }while(m[0]!=0);
                                
}
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
18.11.2010, 20:21  [ТС]     Разбиение на слагаемые #5
Спасибо !Но были маленькие ошибки) сначала бесконечно выводилось 5=0и 5=5 если вводил пять ))убрал break; переписал как while(m[0]!=n); и добавил условие чтобы если не чего нет то не писало 0 вот че получилось))
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
#include <stdlib.h>
#include <stdio.h>
#define N 20
int main()
{
        int n,m[N],temp;
        
        while(n<1 || n>N){
        printf("Vvedite ot n 1 do %d\n",N);
        scanf("%d",&n);
        if(n<1 || n>N) printf("Ne to 4uc/lo\n");
        }
 
        for(int i=0;i<n;i++) m[i]=1; 
 
        temp=n-1; 
        do
        {
                printf("%d=",n);
                for(int i=0;i<n;i++)
                {
                       if(m[i]!=0)
                           if(i==n-1 || m[i+1]==0) {
                                printf("%d\n",m[i]);
                                }
                        else printf("%d+",m[i]);
                }
 
                if(m[temp]-1>=m[temp-1]+1 && temp>=1) m[temp]--,m[temp-1]++;
                else{ 
                m[temp-1]+=m[temp];
                m[temp--]=0;
                }
        }while(m[0]!=n);
 
}
Добавлено через 20 минут
ой тоесть не while(m[0]!=n); а while(m[n]!=0); вот))
archinko
13 / 13 / 2
Регистрация: 02.03.2010
Сообщений: 29
18.11.2010, 20:22     Разбиение на слагаемые #6
Если сделать while(m[0]!=n), то последнее уровнение не появиться( когда n=n). Но это ,конечно, не критично .

Ыыы, а у меня если сделать while(m[n]!=0) бесконечно печатаеться 5=5=5=5=...
ЗЫ: компилирую gcc (-std=c99), с g++ такой же результат.
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
18.11.2010, 20:35  [ТС]     Разбиение на слагаемые #7
Слушай не мог ты проверить мой код но уже другой программы и подсказать коечто?

Задание:Требуется написать программу которая по заданным числам х и y найдет все пары чисел а и b такие что сумма чисел равна х, а произведение у либо наоборот,сумма чисел равна у, а произведение х!
Мой код:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(int argc, char** argv) {
    int x,y,a=0,b=0,i,j;
    scanf("%i%i",&x,&y);
    
   printf("ec/lu cymma %i, a proisvedenie %i to\n",x,y);
    for (j=0;j<=y;j++)
    {for (i=0;i<=(x);i++){
        a=i+j;
        b=i*j;
    if ((a==x)&&(b==y))
    printf("a=%i     b=%i\n",i,j);}}
    printf("ec/lu cymma %i, a proisvedenie %i to\n",y,x);
   for (j=0;j<=y;j++)
   {for (i=0;i<=x;i++){
        a=i+j;
        b=i*j;
    if ((a==y)&&(b==x))
    printf("a=%i     b=%i\n",i,j);}
   }
 
 
    return 0;
}
также есть вопрос как можно сделать так чтобы х и у были и отрицательные? нужно в диапазоне (-10^9;10^9)

Добавлено через 1 минуту
В NetBeans 6.9.1 все кул))

Добавлено через 4 минуты
попробовал в Borland тоже бесконечно пишет блин!ахаха
значит netbeans подлая штука)))ахах и while(m[o]!=n) это правильно)сори)
archinko
13 / 13 / 2
Регистрация: 02.03.2010
Сообщений: 29
18.11.2010, 22:08     Разбиение на слагаемые #8
Код вроде правильный. Для отрицательных чисел вводим две переменные - znakx и znaky, которые будут определять знак х и знак у. Ну а в цыкле переменные i и j будем гнать не просто от 0 до х (от 0 до у соответственно), а от -х до х( -у до у соответственно). Ну а переменные znakx и znaky помогут понять в какую сторону гнать эти переменные, от плюса к минусу или от минуса к плюсу.

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
#include <stdio.h>
 
int main(int argc, char** argv) {
    int x,y,a=0,b=0,znakx=1,znaky=1,i,j;
    scanf("%i%i",&x,&y);
    if(x<0) znakx=-1;
    if(y<0) znaky=-1;
 
   printf("ec/lu cymma %i, a proisvedenie %i to\n",x,y);
    for (j=-y;j!=y+znaky;j+=znaky)
    {for (i=-x;i!=x+znakx;i+=znakx){
        a=i+j;
        b=i*j;
    if ((a==x)&&(b==y))
    printf("a=%i     b=%i\n",i,j);}}
    printf("ec/lu cymma %i, a proisvedenie %i to\n",y,x);
   for (j=-y;j!=y+znaky;j+=znaky)
   {for (i=-x;i!=x+znakx;i+=znakx){
        a=i+j;
        b=i*j;
    if ((a==y)&&(b==x))
    printf("a=%i     b=%i\n",i,j);}
   }
 
 
    return 0;
}
Добавлено через 54 минуты
Лучше конечно такую задачу делать не брутфорсом )) . Тут нужно всего лишь решить две простенких систем уровнений :
1) a+b=x
a*b=y
2) a+b=y
a*b=x
х и у нам даны. Таким образом можно найти даже не целые a и b.
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
18.11.2010, 23:11  [ТС]     Разбиение на слагаемые #9
Спасибо))
да знаю что легче системой но на моем уровне знаний мне проще брутфорсить))ахах
слушай не мог бы ты мне простым языком объяснить while? Чего то все как то заумно пишут про него, что нечего не понятно))))
archinko
13 / 13 / 2
Регистрация: 02.03.2010
Сообщений: 29
18.11.2010, 23:51     Разбиение на слагаемые #10
Попытаюсь) Ну для начала надо знать, что while бывает с предУсловием и с постУсловием. Цикл while выполняется до тех пор пока условие истинное (Истина на языке С/C++ это все что не ноль). То есть пока не ноль, цикл выполняеться.

Теперь немного о предусловии и постусловии.

Вот так выглядит while с предусловием:

while (условие)
{
код
}
В while с предусловием проверка условия идет в начале, а это значит, что если условие ложное (то есть 0) то цикл не выполниться ни разу.

Вот так выглядит while с постусловием:

do
{
код
}
while (условие); // обрати внимание, нужно обязательно поставить ";" после условия.
В while с постусловием проверка условия идет в конце, а это значит, что цикл в любом случае выполниться хотя бы один раз, даже если условие == ложь.

Вот пару примеров :
C++
1
2
3
4
5
6
7
int i=0;
 
while(i<2)
{
    printf("%i",i);
    i++;
} // Этот цикл выполниться два раза : 0 менше 2, 1 менше 2, но 2 уже не менше, по этому только два раза.
Точно такой же цикл но с постусловием :

C++
1
2
3
4
5
6
7
8
9
int i=0;
 
do
{
    printf("%i",i);
    i++;
}while(i<2); //Все выполниться точно так же как и в коде выше, а именно так : 1 раз код выполниться не 
//зависимо от того ложь или истина в условии, 2 раз будет выполняться, потому что 1 менше 2, ну а третий 
//раз не будет выполняться, потому что 2 не менше 2.
Вот еще пример что бы понять разницу между предусловием и постусловием :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int i=0;
 
while(i!=0) // "i не равно ноль" - не правда, i равно ноль, значит значение ложь и цикл не выполниться ни разу. 
//Кстати, как я писал выше, в языке СИ истина все что не ноль, а ноль соответсвенно ложь. Это значит, что 
//вместо while(i!=0) можно написать while(i). i=0, то есть ложь.
{
    printf("%i",i);
}
 
int i=0;
 
do
{
    printf("%i",i);
    
}while(i); // Этот цикл выполниться один раз, так как while с постусловием выполняеться в любом случае хотя бы один раз. Ну а так как i=0, цикл завершиться.
А так выглядит вечный цыкл :

C++
1
2
3
4
while(666)// вечная истина
{
    printf("Печаль(");
}
Ches.spb
 Аватар для Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
08.12.2010, 23:04  [ТС]     Разбиение на слагаемые #11
Спасибо теперь разобрался))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2010, 00:43     Разбиение на слагаемые
Еще ссылки по теме:

C++ Суммировать слагаемые при фиксированном параметре x
C++ QR -разбиение
C++ Подсчитать количество различных разбиений числа N на натуральные слагаемые

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
10.12.2010, 00:43     Разбиение на слагаемые #12
Цитата Сообщение от archinko Посмотреть сообщение
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
#include <stdlib.h>
#include <iostream>
using namespace std;
#define N 20
int main()
{
    int n,m[N],temp;
    for(int i=0;i<N;i++) m[i]=1;
 
    while(n<1 || n>N){
    cout<< "Введите значение для n от 1 до "<<N<<endl;
    cin>>n;
    if(n<1 || n>N) cout<< "Не допустимое число"<<endl;
    }
 
    temp=n-1;
 
    do 
    {
        cout<<n<<"=";
        for(int i=0;i<n;i++) 
        {
            if(i==n-1 || m[i+1]==0) {
                cout<<m[i]<<endl;
                break;}
            else cout<<m[i]<<"+";
        }
        if(m[temp]-1>=m[temp-1]+1 && temp>=1) m[temp]--,m[temp-1]++;
        else{
        m[temp-1]+=m[temp];
        m[temp--]=0;
        }
    }while(m[0]!=0);
                
}
Программа работает неверно, так как, например, для 10 выдает 26 вариантов:

Введите значение для n от 1 до 20
10
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
10=1+1+1+1+1+1+1+1+1+1
10=1+1+1+1+1+1+1+1+2
10=1+1+1+1+1+1+1+3
10=1+1+1+1+1+1+2+2
10=1+1+1+1+1+1+4
10=1+1+1+1+1+2+3
10=1+1+1+1+1+5
10=1+1+1+1+2+4
10=1+1+1+1+3+3
10=1+1+1+1+6
10=1+1+1+2+5
10=1+1+1+3+4
10=1+1+1+7
10=1+1+2+6
10=1+1+3+5
10=1+1+4+4
10=1+1+8
10=1+2+7
10=1+3+6
10=1+4+5
10=1+9
10=2+8
10=3+7
10=4+6
10=5+5
10=10
Для продолжения нажмите любую клавишу . . .

А надо 42 варианта:

n = 10
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
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2
10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 3
10 = 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2
10 = 1 + 1 + 1 + 1 + 1 + 1 + 4
10 = 1 + 1 + 1 + 1 + 1 + 2 + 3
10 = 1 + 1 + 1 + 1 + 1 + 5
10 = 1 + 1 + 1 + 1 + 2 + 2 + 2
10 = 1 + 1 + 1 + 1 + 2 + 4
10 = 1 + 1 + 1 + 1 + 3 + 3
10 = 1 + 1 + 1 + 1 + 6
10 = 1 + 1 + 1 + 2 + 2 + 3
10 = 1 + 1 + 1 + 2 + 5
10 = 1 + 1 + 1 + 3 + 4
10 = 1 + 1 + 1 + 7
10 = 1 + 1 + 2 + 2 + 2 + 2
10 = 1 + 1 + 2 + 2 + 4
10 = 1 + 1 + 2 + 3 + 3
10 = 1 + 1 + 2 + 6
10 = 1 + 1 + 3 + 5
10 = 1 + 1 + 4 + 4
10 = 1 + 1 + 8
10 = 1 + 2 + 2 + 2 + 3
10 = 1 + 2 + 2 + 5
10 = 1 + 2 + 3 + 4
10 = 1 + 2 + 7
10 = 1 + 3 + 3 + 3
10 = 1 + 3 + 6
10 = 1 + 4 + 5
10 = 1 + 9
10 = 2 + 2 + 2 + 2 + 2
10 = 2 + 2 + 2 + 4
10 = 2 + 2 + 3 + 3
10 = 2 + 2 + 6
10 = 2 + 3 + 5
10 = 2 + 4 + 4
10 = 2 + 8
10 = 3 + 3 + 4
10 = 3 + 7
10 = 4 + 6
10 = 5 + 5
10 = 10
Для продолжения нажмите любую клавишу . . .

Вот так правильно:
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
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>  T_summands;
//////////////////////////////////////////////////////////////////////////////////////
void  print_summands
    (
        int                n_start,
        const T_summands&  summands
    )
{
    std::cout << n_start
              << " = ";
    for(T_summands::const_iterator  summands_it = summands.begin();
        summands_it != summands.end(); ++summands_it)
    {
        std::cout << *summands_it
                  << (summands_it != summands.end() - 1 ? " + " : "\n");
    }    
}
//////////////////////////////////////////////////////////////////////////////////////
void  summands_partition
    (
        int                n_start,
        int                n_cur, 
        const T_summands&  summands
    )
{
    if(!n_cur)
    {
        print_summands(n_start, summands);
    }    
    
    for(int cur_slag = summands.empty() ? 1 : summands.back(); 
        n_cur - cur_slag >= 0; ++cur_slag)    
    {
        T_summands  summands_new(summands);
        summands_new.push_back(cur_slag);
        summands_partition(n_start, n_cur - cur_slag, summands_new);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::cout << "n = ";
    int  n = 0;
    std::cin >> n;
    T_summands  summands;    
    summands_partition(n, n, summands); 
}
Yandex
Объявления
10.12.2010, 00:43     Разбиение на слагаемые
Ответ Создать тему
Опции темы

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