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

Нахождение разбиений числа - C++

Восстановить пароль Регистрация
 
olezhkapisatel
0 / 0 / 0
Регистрация: 19.07.2016
Сообщений: 32
30.07.2016, 02:48     Нахождение разбиений числа #1
Все привет, ребят помогите. Суть задания: разбиений числа, есть число, нужно его разбить. Например, {3,1,1} или {3,2} — разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует p(5) = 7 разбиений числа 5: {1,1,1,1,1}, {2,1,1,1}, {2,2,1}, {3,1,1}, {3,2}, {4,1}, {5}. Ну вы поняли, и мне надо сделать диапазон, типо что бы пользователь задавал на какие числа он хочет разбить заданное число, к примеру 5 разбить только на 1 и на 2, выходит: {1,1,1,1,1}, {2,1,1,1}, {2,2,1}. Вот как то так, есть 2 кода, как я их не изменял как не пытался, не выходит
1 код
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
#include <iostream>
int n, sum[10];
using namespace std;
void pokemoni(int left, int min = 0, int i = 0)
{
    if (left < 0 || min == n)
        return;
    sum[i] = min;
    if (min != 0)
    {
        pokemoni(left - min, min, i + 1);
    }
    pokemoni(left - 1, min + 1, i);
    if (left == 0)
    {
        for (int j = 0; j <= i; ++j)
            cout << sum[j] << (j != i ? '+' : '\n');
    }
 
}
void main()
{
    setlocale(LC_ALL, "Russian");
    cout << "Введите целое число: ";
    cin >> n;
    pokemoni(n);
    system("pause");
}
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
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");
}
Заранее спасибо!
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2016, 02:48     Нахождение разбиений числа
Посмотрите здесь:

C++ Нахождение числа ближнего к X
Нахождение наименьшего числа (С++) C++
Нахождение целого числа C++
Нахождение минимального числа C++
нахождение делителей числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DemolitionMan
 Аватар для DemolitionMan
22 / 54 / 18
Регистрация: 06.04.2016
Сообщений: 325
30.07.2016, 03:46     Нахождение разбиений числа #2
Я не понял, числа от 1 до 10 или любое число?
MansMI
Нарушитель
1047 / 844 / 205
Регистрация: 08.01.2012
Сообщений: 3,032
30.07.2016, 04:35     Нахождение разбиений числа #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
void sum(vector<int> v,int pv,string str,int sm,int n)
{
    if(str=="") str="{";
    else str+=",";
    for(size_t i=pv; i<v.size(); i++)
    {
        int s=sm+v[i];
        if(s>n) return;
        char sv[10];
        itoa(v[i],sv,10);
        if(s==n) cout<<str+sv<<"}\n";
        else sum(v,i,str+sv,s,n);
    }
}
void main(int argc,char* argv[])
{
    setlocale(LC_ALL,"Rus");
    cout<<"Число: ";
    int n,ns;
    cin>>n;
    cout<<"Количество видов слогаемых: ";
    cin>>ns;
    vector<int> v(ns);
    for(int i=0; i<ns; i++)
    {
        cout<<i+1<<"-е: ";
        cin>>v[i];
    }
    for(int i=ns-1; i; i--)
    for(int j=0; j<i; j++)
        if(v[j]>v[i]) swap(v[i],v[j]);
    //for(int i=0; i<ns; i++) cout<<v[i]<<" \n";
    sum(v,0,"",0,n);
    system("pause");
}
olezhkapisatel
0 / 0 / 0
Регистрация: 19.07.2016
Сообщений: 32
30.07.2016, 05:34  [ТС]     Нахождение разбиений числа #4
MansMI, воу воу, ничего себе подгон, я ожидал максимум подсказку, большое спс парень
DemolitionMan
 Аватар для DemolitionMan
22 / 54 / 18
Регистрация: 06.04.2016
Сообщений: 325
30.07.2016, 05:34     Нахождение разбиений числа #5
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
//---------------------------------------------------------------------------
#include <vcl.h>
#include <iostream>
#include <conio.h>
#pragma hdrstop
//---------------------------------------------------------------------------
#pragma argsused
using namespace std;
int main(int argc, char* argv[])
{
int z, m, Digits, Half, L, Left,//-SamoLevoeChislo
Right, Pair;
 
cout << "Vvedite chislo.\n";
cin >> z;
 
int *r = new int[z];  //z-razmer
 
cout << "\nSozdali massiv.\n";
for(m=0;m<z;m++)
{
    r[m] = 0;
    cout << r[m];
    if(m != (z-1)) cout << " ";
}
cout << "\n";
 
//ГђГ*çáèâГ*ГҐГ¬ îò Г¬Г*ëåГ*üêîãî êîëè÷åñòâГ* ýëåìåГ*òîâ ГЄ áîëüøîìó
for(L = 0; L < (z-1); L++)
{
for(m=0;m<z;m++) r[m] = 0;  //ГЋГ·ГЁГ±ГІГЄГ*
for(m=0;m<L;m++) r[m] = 1;  //Г‡Г*ïîëГ*ГїГҐГ¬ åäèГ*ГЁГ¶Г*ìè ëåâóþ Г·Г*Г±ГІГј
Pair = z-L;
 
Half = (z-L)/2;//äëÿ 7 - 3
for(Left = 1; Left <= Half; Left++)
    {
    Right = Pair-Left;
    r[L] = Left;
    r[L+1] = Right;
    //ГЏГҐГ·Г*ГІГј
    for(m=0;m<=L+1;m++)
        {
        cout << r[m];
        if(m != (L+1)) cout << " ";
        }
    cout << "\n";
    }
}
getch();
return 0;
}
//---------------------------------------------------------------------------
Я осилил!!! А-ха-ха!!! Я лучший!!!
olezhkapisatel
0 / 0 / 0
Регистрация: 19.07.2016
Сообщений: 32
30.07.2016, 05:36  [ТС]     Нахождение разбиений числа #6
Ребят кто будет юзать(может у кого похожее задание) там кароч функцию itoa(v[i],sv,10); в 10 строке над заменить на _itoa_s(v[i], sv, 10); а то визуалка 15 прикопалась
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2016, 07:17     Нахождение разбиений числа
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2804 / 1580 / 247
Регистрация: 03.05.2010
Сообщений: 3,678
30.07.2016, 07:17     Нахождение разбиений числа #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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int           >   T_partition;
typedef std::vector     < T_partition   >   T_partitions;
///////////////////////////////////////////////////////////////////////////////
void    add_partitions
    (
        int                 num,
        int                 min,
        int                 max,
        T_partitions    &   partitions,
        T_partition         prefix  =   {}
    )
{
    if( !num )
    {
        partitions.emplace_back( prefix );
        return;
    }
 
    for (
            int
            i   =   std::max( 1,    min );
            i   <=  std::min( max,  num );
            ++i
         )
    {
        auto    prefix_cur          ( prefix );
        prefix_cur.emplace_back     (i);
 
        add_partitions
            (
                num - i,
                i,
                max,
                partitions,
                prefix_cur
            );
    }//for
}
///////////////////////////////////////////////////////////////////////////////
void    print_partitions( T_partitions  const   &   partitions )
{
    for( auto   const   &   partition   :   partitions )
    {
        std::copy
            (
                partition.begin             (),
                partition.end               (),
                std::ostream_iterator<int>  ( std::cout,    " " )
            );
        std::cout   <<  std::endl;
    }//for
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::cout   <<  "num\t= ";
    int     num{};
    std::cin    >>  num;
 
    std::cout   <<  "min\t= ";
    int     min{};
    std::cin    >>  min;
 
    std::cout   <<  "max\t= ";
    int     max{};
    std::cin    >>  max;
 
    T_partitions    partitions;
 
    add_partitions
        (
            num,
            min,
            max,
            partitions
        );
 
    if  (
            partitions.empty()
        )
    {
        std::cout   <<  "no solutions"
                    <<  std::endl;
    }
    else
    {
        print_partitions( partitions );
    }
}
Yandex
Объявления
30.07.2016, 07:17     Нахождение разбиений числа
Ответ Создать тему
Опции темы

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