Разделение целого числа + Количество разделов

Question

Разделение целого числа + Количество разделов

Разделение целого числа n — это способ записи n в виде суммы натуральных чисел. За

Например, для n = 7 разбиение равно 1 + 1 + 5. Мне нужна программа, которая находит все

разбиения целого числа ‘n’ с использованием целых чисел ‘r’. Например, все разделы n=7

с помощью r=3 целые числа 1+1+5, 1+2+4, 1+3+3, 2+2+3,

Это то, что я до сих пор:

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
for(int i=0;i<=level;i++)
cout << v[i] << " ";
cout << endl;
}

void part(int n, vector<int>& v, int level){
int first; /* first is before last */

if(n<1) return ;
v[level]=n;
print(v, level);

first=(level==0) ? 1 : v[level-1];

for(int i=first;i<=n/2;i++){
v[level]=i; /* replace last */
part(n-i, v, level+1);
}
}

int main(){
int num;
cout << "Enter a number:";
cin >> num;

vector<int> v(num);

part(num, v, 0);
}

Выход этой программы:

Enter a number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3

Process returned 0 (0x0)   execution time : 1.837 s
Press any key to continue.

Как я могу изменить свой код, чтобы иметь эту переменную ‘r’?

РЕДАКТИРОВАТЬ:

В случае, если неясно, значение ‘r’ представляет количество целых чисел на раздел. Таким образом, в случае выше, если r = 2, то в разделах может быть только два целых числа. Перегородки будут 4 + 1 и 3 + 2. Значение ‘r’ должно быть введено пользователем.

3

c++integer-partition

Решение

Другие решения

Своего рода «взломать» было бы сделать r аргумент part, передать его рекурсивно, просто распечатать вывод, если level равняется r,

0

Как насчет этого? Передали ли дополнительный аргумент в качестве ссылки для r и увеличивали r каждый раз в пределах блока рекурсии?

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
for(int i=0;i<=level;i++)
cout << v[i] << " ";
cout << endl;
}

void part(int n, vector<int>& v, int level, int &r){
int first; /* first is before last */

if(n<1) return ;
v[level]=n;
print(v, level);

first=(level==0) ? 1 : v[level-1];

for(int i=first;i<=n/2;i++){
v[level]=i; /* replace last */
r++;
part(n-i, v, level+1, r);
}
}

int main(){
int num;
cout << "Enter a number:";
cin >> num;

int r = 0;
vector<int> v(num);

part(num, v, 0, r);
cout << "r = " << r << endl;
}

Выход приходит как:

Enter a number:5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3
r = 6

Это то, что вы ищите?

0

Источник

Accepted Answer

По сути, то, что сказал Кодор, плюс вам не нужно возвращаться в part() как только вы нашли раздел целевой длины, так как они будут длиннее:

#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
for(int i=0;i<=level;i++)
cout << v[i] << " ";
cout << endl;
}

void part(int n, vector<int>& v, int level, int r){
int first; /* first is before last */

if(n<1) return ;
v[level]=n;
if( level+1 == r ) {
print(v, level);
return;
}

first=(level==0) ? 1 : v[level-1];

for(int i=first;i<=n/2;i++){
v[level]=i; /* replace last */
part(n-i, v, level+1, r);
}
}

int main(){
int num,r;
cout << "Enter a number:";
cin >> num;
cout << "Enter size (r):";
cin >> r;

vector<int> v(num);

part(num, v, 0, r);
}

Выход:

Enter a number:5
Enter size (r):2
1 4
2 3

1