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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
MOLK
0 / 0 / 0
Регистрация: 22.09.2011
Сообщений: 30
#1

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

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

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

Нахождение разбиений числа - C++
Все привет, ребят помогите. Суть задания: разбиений числа, есть число, нужно его разбить. Например, {3,1,1} или {3,2} — разбиения числа 5,...

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

Генератор числа от -1 до 1 - C++
Хай! Пытаюсь написать генератор для рандомной выдачи числа от -1 до 1. Что делаю не так скажите? srand(time(0)); tmpValue...

Очередь целых чисел, генератор случайного числа, и задача - C++
Помогите, пожалуйста, с задачей! Для тех, кто в этом хорошо разбирается, я уверен, что эта задача не заберет много времени, плюс жизнь мою...

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

Вывести одно целое число– количество возможных разбиений войска на отряды - C++
Согласно многовековой традиции, сэр Петрейн каждую субботу ходит охотиться на дракона. Однако, за один вечер до выхода в очередной поход,...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.10.2011, 01:14
Привет! Вот еще темы с ответами:

Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми - C++
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми. ...

Генератор на С++ - C++
Всем привет, вот нашел классную прогу, она делает все то что мне нужно за 2мя исключениями 1) Он производит генерацию с 1-го символа,...

Генератор приглашений - C++
Подскажите, пожалуйста, как реализовать на C++ генератор приглашений по следующим требованиям: Имеется список имен (файл1) и шаблон...

Генератор объектов - C++
Я пишу консольную игру, и планирую сделать её с пароякой режимов. Например: 1) Режим прохождения - игрок по очереди сражается с каждым...


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

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

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