Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 22.09.2011
Сообщений: 30
1

Генератор разбиений числа

26.10.2011, 01:14. Показов 3443. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
У нас есть шаблон структуры всех разбиений числа:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//-- Gen.h 
#pragma  once 
namespace combi      
{
struct  partition  // генератор разбиений целого числа   
  {
short n,    // исходное число
sn,     // количество элементов в текущем разбиении
        q;        // индекс текущего элемента для разбиения
    int  *sset;     // указатель на массив текущего разбиения
    partition (short n); // конструктор
    bool getfirst ();      // получить начальное разбиение
    bool getnext();    // получить разбиение
  };
};
Реализация методов структуры partition:
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
//-- Gen.cpp 
#include "stdafx.h"
#include <iostream>
#include "Gen.h" 
namespace combi
{
 partition::partition(short n) 
{
    this->n = n; this->sn = 0; this->q = 0;
    this->sset= new int [n];
    }
 bool partition::getfirst() 
 {
    bool rc = true;
    this->sset[0] = this->n; this->sn = 1;
if (rc  =  (this->n >= 0))  this->q = (this->n <= 1)?-1:0;
    return rc;
 }
bool partition::getnext()
{
 bool rc = true;
  if (rc = (this->q >= 0))
    if (this->sset[q] == 2)
     { this->sset[this->q--] = 1; this->sset[(++this->sn)-1] = 1;} 
    else 
     {
        --this->sset[q];
        int  nx  =  this->sn - this->q; 
        this->sn =  (this->q + 1)+1;     
         while (nx > this->sset[q]) 
             {
              this->sset[this->sn-1] = this->sset[q];  
              this->sn++; nx -= this->sset[q];
             };
         this->sset[sn-1] = nx; 
         this->q = (this->sn-1) -((nx == 1)?1:0);
     }; 
  return rc;
};
}
Пример применения генератора для построения всех разбиений числа 7:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//Main  
//
#include "stdafx.h"
#include "Gen.h"
#include <iostream>
 
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(LC_ALL, "rus");
combi::partition p(7);
bool iscontinue  = p.getfirst();
std::cout<<"Разбиение числа 7";
while(iscontinue)
{
 std::cout<<std::endl; 
 for (int i = 0; i < p.sn; i++)std::cout<<p.sset[i]<<", " ; 
 iscontinue = p.getnext();
};
std::cout<<std::endl; 
system("pause");
return 0;
}
Подскажите, пожалуйста, куда надо вписывать эти коды, чтобы программа заработала?
Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.10.2011, 01:14
Ответы с готовыми решениями:

Нахождение разбиений числа
Все привет, ребят помогите. Суть задания: разбиений числа, есть число, нужно его разбить. Например,...

Подсчитать количество различных разбиений числа N на натуральные слагаемые
Условие: требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два...

[Оптимизация] Количество разбиений числа
Задача: необходимо найти количество всех разбиений числа. Функция работает, но нужно быстрее. Что...

Количество разбиений числа на нечетные слагаемые
Нужно найти число способов ризбивки числа в виде суммы положительных целых нечетных чисел. ва...

0
26.10.2011, 01:14
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.10.2011, 01:14
Помогаю со студенческими работами здесь

Найдите число неупорядоченных разбиений числа 7 на 2,3,4
Здравия! Препод дал нам по 5 вопросов для подготовки к зачету. 4 я сделал, одну решить не могу,...

Сгенерировать и определить количество разбиений целого числа
Сгенерировать и определить количество Q(N,M) разбиений целого числа N со слагаемыми, не...

Рекурсивный подсчёт количества разбиений натурального числа
Составить рекурсивную программу-функцию подсчета количества x(m) разбиений натурального числа m, то...

Подсчитайте количество различных разбиений числа n на суммы натуральных слагаемых
Помогите пожалуйста решить задачку

Для числа от 2 до 20 распечатайте количество его различных разбиений на сумму натуральных слагаемых
Для данного натурального числа от 2 до 20 распечатайте количество его раз-личных разбиений на сумму...

Распечатать количество различных разбиений числа на сумму натуральных слагаемых, используя рекурсию
Для данного натурального числа от 2 до 20 распечатайте количество его различных разбиений на сумму...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru