Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 38, средняя оценка - 4.97
Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
#1

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

17.11.2010, 18:25. Просмотров 6740. Ответов 12
Метки нет (Все метки)

Задание:нужно вывести на экран в лексикографическом порядке все разбиения на слагаемые числа 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2010, 18:25
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Разбиение на слагаемые (C++):

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

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

различные слагаемые - C++
По данному числу 1≤n≤10^9 найдите максимальное число k, для которого n можно представить как сумму k различных натуральных слагаемых....

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

Число разбиений на слагаемые C++ - C++
Подскажите, есть такая задача. По данному целому числу 1≤n≤1000 найдите число способов представить n в виде суммы положительных целых...

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

12
archinko
14 / 14 / 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);
                
}
1
Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
17.11.2010, 23:39  [ТС] #3
Спасибо конечно но нельзя ли не на с++ а на с,и если не затруднит можете добавить, пожалуйста, комментарии.Заранее благодарю
0
archinko
14 / 14 / 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);
                                
}
1
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); вот))
0
archinko
14 / 14 / 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++ такой же результат.
0
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) это правильно)сори)
0
archinko
14 / 14 / 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.
1
Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
18.11.2010, 23:11  [ТС] #9
Спасибо))
да знаю что легче системой но на моем уровне знаний мне проще брутфорсить))ахах
слушай не мог бы ты мне простым языком объяснить while? Чего то все как то заумно пишут про него, что нечего не понятно))))
0
archinko
14 / 14 / 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("Печаль(");
}
0
Ches.spb
1 / 1 / 0
Регистрация: 12.11.2010
Сообщений: 51
08.12.2010, 23:04  [ТС] #11
Спасибо теперь разобрался))
0
Mr.X
Эксперт С++
3060 / 1705 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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); 
}
1
KiraBush
0 / 0 / 0
Регистрация: 16.04.2017
Сообщений: 13
10.05.2018, 19:42 #13
archinko, а как сделать так, чтобы количество слагаемых можно было ввести с клавиатуры?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.05.2018, 19:42
Привет! Вот еще темы с ответами:

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

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

Суммировать слагаемые при фиксированном параметре x - C++
Пожалуйста помогите!!!!!!!!!!!!!!!!!! Я здесь пытался что-то сделать но увы((((( черновая работа, если нечего неправильно сделайте...

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


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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