0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
1

Задача:Даны числа N и K, найти разбиение числа N на K слагаемых(без повторений)

26.10.2019, 16:30. Показов 7461. Ответов 13

Помогите решить задачу самыми простыми способами, без сложных операторов и библиотек.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2019, 16:30
Ответы с готовыми решениями:

В файле даны повторяющиеся числа. Вывести на экран числа по возрастанию без повторений
Помогите с ошибкой в проге, выводит числа с повторениями :( #include "pch.h" #include...

Разбиение числа n на k слагаемых
я не могу понять алгоритм разбиение числа n на k слагаемых например, нужно разбить число 17 на 10...

Разбиение положительного числа на 2 слагаемых
Суть проблемы: надо разбить число на два слагаемых. Допустим, 5: 0 5, 1 4, 2 3. застрял на этом ...

Разбиение числа на заданное количество слагаемых
Помогите пожалуйста, есть программа разбиения числа на слагаемые,НО на все возможные, надо сделать...

13
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 842
26.10.2019, 16:45 2
1 + 2 + 3 + ... + K-1 + (N-K*(K-1)/2)
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
26.10.2019, 16:48  [ТС] 3
Не настолько простым способом...
0
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
26.10.2019, 19:49 4
Цитата Сообщение от IlhamN10 Посмотреть сообщение
Не настолько простым способом...
Так вы разъяснили бы, что именно вам надо.

Добавлено через 2 минуты
И без повторений - чего?
N = 2, K =2
Единственное разложение 2 = 1 + 1. Единица повторяется.
А 2 = 2 + 0 можно? или 2 = 3 + (-1)
Уточняйте задачу.
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
27.10.2019, 10:20  [ТС] 5
Нужна программа на c++
0
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
27.10.2019, 10:48 6
Цитата Сообщение от IlhamN10 Посмотреть сообщение
Нужна программа на c++
Вы умеете только задавать вопросы? А отвечать еще не научились? Пока вы не ответите на вопросы поста 4, никакого продуктивного разговора не получится.
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
27.10.2019, 12:46  [ТС] 7
Без повторений имеется в виду : Например разложение числа 7
1 + 1 + 2 + 3 и 1 + 2 + 1 + 3 одно и то же, желательно вывести разложения в порядке возрастания: 1+1+2+3 чтобы не было повторений.
0 использовать нельзя, только натуральные числа.
0
Диссидент
Эксперт C
26970 / 16845 / 3705
Регистрация: 24.12.2010
Сообщений: 37,821
27.10.2019, 17:17 8
IlhamN10, иногда бывает полезно посмотреть на ссылочки внизу страницы
Разбиение числа на заданное количество слагаемых
Разбиение числа n на k слагаемых
Перечислить все разбиения натурального числа на натуральные слагаемые
1
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 842
27.10.2019, 18:20 9
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
#include <iostream>
#include <vector>
 
void print(std::vector<unsigned> &fs) {
  for (auto f : fs) {
    std::cout << f << " ";
  }
  std::cout << "\n";
}
 
void findFactorImpl(unsigned N, unsigned K, std::vector<unsigned> &fs,
                    unsigned f_min) {
  if (K <= 1) {
    fs[0] = N;
    print(fs);
  } else {
    for (unsigned f = f_min; f * K <= N; ++f) {
      fs[K - 1] = f;
      findFactorImpl(N - f, K - 1, fs, f);
    }
  }
}
 
void findFactor(unsigned N, unsigned K) {
  std::vector<unsigned> fs(K);
  findFactorImpl(N, K, fs, 1);
}
 
int main() {
  findFactor(17, 10);
  return 0;
}
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
28.10.2019, 21:08  [ТС] 10
AlexVRud, Не работает

Добавлено через 2 минуты
Байт, я не нашел там кода на c++, только C. И я пока не знаю как перевести с С на С++. Я изучаю С++ только 3 недели...
0
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 842
28.10.2019, 21:18 11
IlhamN10, УМВР, ЧЯДНТ?
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
28.10.2019, 21:45  [ТС] 12
AlexVRud, что?

Добавлено через 24 минуты
Байт, Есть такой код, но он находит ВСЕ разложения, как его переделать что бы он находил только разбиения на К слагаемых?


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
#include <stdlib.h>
#include <iostream>
using namespace std;
#define N 100
int main()
{
    int n, m[N],l, temp;
    int count = 0;
 
    for (int i = 0; i<N; i++) m[i] = 1;
    cin >> n;
 
 
    for (int i = 0; i<n; i++) m[i] = 1;
 
    temp = n - 1;
 
    do
    {
 
        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] != n));
    system("pause");
}
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
28.10.2019, 23:35 13
C++
1
2
3
4
5
6
7
8
9
10
11
int f(int a, int b, int k, std::string s) {
    if (k==0 && a==0) { std::cout << s << "\n"; return 1; }
    if (k<=0 || a<=0) return 0;
    int r = 0; for(int i=b; i<=a; i++) r += f(a-i, i, k-1, s + std::to_string(i) + "\t");
    return r;
}
    
int main() {
    int a, k; std::cin >> a >> k;
    std::cout << "Total " << f(a, 1, k, "") << " ways";
}
Код
1	1	1	12	
1	1	2	11	
1	1	3	10	
1	1	4	9	
1	1	5	8	
1	1	6	7	
1	2	2	10	
1	2	3	9	
1	2	4	8	
1	2	5	7	
1	2	6	6	
1	3	3	8	
1	3	4	7	
1	3	5	6	
1	4	4	6	
1	4	5	5	
2	2	2	9	
2	2	3	8	
2	2	4	7	
2	2	5	6	
2	3	3	7	
2	3	4	6	
2	3	5	5	
2	4	4	5	
3	3	3	6	
3	3	4	5	
3	4	4	4	
Total 27 ways
0
0 / 0 / 0
Регистрация: 19.10.2019
Сообщений: 11
30.10.2019, 15:56  [ТС] 14
Ребят, я уже сам решил. Вот решение:

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
#include <iostream>
#include <iomanip>
 
using namespace std;
int rgen(int *a, int k, int n);
 
int main()
{
    int *a, i,n, k,m;
    cin>>n>>k;
    a = new int [k];
    if(k>n) {cout<<"Error: K > N\n"; return 0;}
    for(i=0; i<k-1; i++) a[i]=1;
    a[k-1]=n - k +1;
    m=0;
      do
    {    cout<<setw(5)<<m<<")  ";
          for(i=0; i<k;i++)
            cout<<a[i]<<" ";
        cout<<endl;
        m++;
    }     while(rgen(a,k,n));
    return 0;
}
 
 
int rgen(int *a, int k, int n)
{
      if(a[k-1]>a[k-2]+1)
      {
          a[k-1]--;
          a[k-2]++;
          return 1;
      }
       int i = k-3;
       int s = a[k-1] +a[k-2];
       while(1)
       { int s1 = (a[i] + 1)*(k-i-1)+1;
           if(s1 <=s){
            a[i]++;
            for(int j=i+1; j<k; j++) a[j]=a[i];
            a[k-1]+=s-s1;
            return 1;
            }
           s+=a[i];
           i--;
           if(i<0) return 0;
           }
       }
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.10.2019, 15:56
Помогаю со студенческими работами здесь

Найти все натуральные числа, не превосходящие числа n, которые можно представить в виде суммы слагаемых
Заданы три натуральных числа a, b, n. Найти все натуральные числа, не превосходящие числа n,...

Даны 3 числа. Для каждого из этих чисел, найти сумму цифр числа и определить у кокого числа сумма больше
Даны 3 числа. Для каждого из этих чисел, найти сумму цифр числа и определить у кокого числа сумма...

Даны три дейтвительных числа a,b и c. Найти минимальное из этих чисел и вычислить сумму первого числа и найденного минимального числа.
Напишите программку (с коментариями если не трудно=) )) Даны три дейтвительных числа a,b и c....

Даны три разных натуральных числа A, B, C. Определить наименьшее число, которое делится без остатка на эти 3 числа
Даны три разных натуральных числа A, B, C. Определить наименьшее число, которое делится без остатка...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru