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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.96
alibaba314
19 / 19 / 1
Регистрация: 22.03.2009
Сообщений: 58
#1

Число разложений без повторений ! - C++

04.10.2009, 10:16. Просмотров 3776. Ответов 28
Метки нет (Все метки)

напишите програму , которая считает количество разложений Q(N) данного натурального числа N на неупорядоченные слагаемые без повторений. например, для N=5 есть 3 различных разложений 5=5=4+1=3+2. разложения считаются различными если множества слагаемых различаются.

интересная задача!!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2009, 10:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Число разложений без повторений ! (C++):

Найти число разложений числа на 2 множителя - C++
Допустим вводят произвольное число с клавиатуры и надо вывести сколькими способами можно в разложении это число упаковать в двумерный...

Перестановки без повторений - C++
Требуется дописать исключение повторений в коде,спасибо. #include <iostream> using namespace std; const int N =11; int n,a,p; ...

Перебор без повторений - C++
текст задачи во вложении мой код: #include <iostream> using namespace std; int f(int v) { if (v == 0) return 1; ...

Рандом без повторений - C++
Здравствуйте! Искал по форуме, но так и не нашел подходящее решение такой задачи: пользователь вводит К ПРИМЕРУ число 7. я беру от него...

Перестановка без повторений - C++
Сгенерировать перестановку N чисел без повторений. Требуется использовать циклы. Функции пока не прошли.

Перестановка без повторений - C++
Всем привет! У меня возникла небольшая проблема при написании программы, буду благодарна за любую помощь. Задание гласит следующее:...

28
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
04.10.2009, 10:33 #2
спасибо, написал, задачa и вправду интересная!!!
0
alibaba314
19 / 19 / 1
Регистрация: 22.03.2009
Сообщений: 58
04.10.2009, 11:32  [ТС] #3
можно объяснить алгоритм задачи ??
0
easybudda
Модератор
Эксперт CЭксперт С++
9681 / 5631 / 954
Регистрация: 25.07.2009
Сообщений: 10,808
04.10.2009, 14:28 #4
alibaba314, Слово "неупорядоченные" смущает... А так вот:
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
#include <stdio.h>
#include <locale.h>
 
/*
    напишите програму , которая считает количество разложений Q(N) 
    данного натурального числа N на неупорядоченные слагаемые без повторений. 
    например, для N=5 есть 3 различных разложений 5=5=4+1=3+2. 
    разложения считаются различными если множества слагаемых различаются.
*/
 
int main(){
    int n, head, tail, count;
    
    setlocale(LC_ALL, "Russian");
    
    while ( 1 ){
        printf("\nВведите целое число большее нуля, или 0 для выхода: ");
        scanf("%d", &n);
        if ( !n )
            break;
        for ( head = n, tail = 0, count = 0; head >= tail; count++, head--, tail++ )
            printf("%d = %d + %d\n", n, head, tail);
        printf("%d способов разложить число %d на слагаемые\n", count, n);
    }
    
    return 0;
}
1
easybudda
Модератор
Эксперт CЭксперт С++
9681 / 5631 / 954
Регистрация: 25.07.2009
Сообщений: 10,808
04.10.2009, 14:35 #5
Число разложений без повторений !
0
alibaba314
19 / 19 / 1
Регистрация: 22.03.2009
Сообщений: 58
04.10.2009, 16:21  [ТС] #6
а, если 6=3+2+1 ????

это правильно, но по моему не достаточно!
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
04.10.2009, 23:14 #7
Тут всё неправильно.
Код easybudda, выдаёт выражения только из двух слагаемых, а их может быть сколь хочешь (поскольку в условии не оговорено обратное.)

Тут решать и решать.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.10.2009, 06:22 #8
Написал на скорую руку код, протестировать до конца нет времени, но вроде работает.
Если будут какие-либо замечания по коду, смогу ответить только во вторник вечером.
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
#include < iostream.h >
#include "windows.h"
int N, a, i, i1, j, N1, temp1, temp2, *mas;
int main()
{
     SetConsoleCP(1251);
     SetConsoleOutputCP(1251);
     cout<<"Ââåäèòå ÷èñëî"<<endl;
     cin>>N;
     a=0;
     N1=N;
     while(N1>=0)
     {
         a++;
         N1-=a;
     }
     mas=new int[a-1];
     for(i=0; i<a-1; i++)
         mas[i]=i+1;
     if(N1!=0)
       mas[a-2]=mas[a-3]+a+1+N1;
     a--;
     for(i=0; i<a; i++)
         cout<<mas[i]<<" ";
     cout<<endl;
     while(a>1)
     {
     for(j=a-2; j>-1; j--)
     {
         temp1=mas[j];
         temp2=mas[a-1];
         while(mas[j]+1<mas[a-1]-1)
         {
             mas[j]++;
             mas[a-1]--;
             N1=0;
             for(i=0; i<a-1; i++)
                 for(i1=i+1; i1<a; i1++)
                     if(mas[i]==mas[i1])
                        N1=1;
             if(N1==0)
             {
             for(i=0; i<a; i++)
                 cout<<mas[i]<<" ";
             cout<<endl;
             }
         }
         mas[j]=temp1;
         mas[a-1]=temp2;
 
         
     }
     mas[a-2]+=mas[a-1];
     a--;
     }
   return 0;
}
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
05.10.2009, 09:21 #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
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;
 
void main()
{ 
    int n, temp, tempPrev, countDecom=1, count=1, countArr=1, nMinusTemp;
    vector<int> buf;
 
    cout<<"input number:"<<endl;
    cin>>n; 
    cout<<"variants decomposition:"<<endl;
    cout<<countDecom<<":"<<n<<endl;
 
    while((n/2+n%2)>count)
    {
        countDecom++;
        temp=count;
        nMinusTemp=n-count;
 
        if((temp+1)<nMinusTemp)  // если цикл пойдёт
        {   
            while((++temp)<nMinusTemp)
            { buf.push_back(temp); /*cout<<" "<<temp;*/  nMinusTemp-=temp;}
            if( (!buf.empty()) && (temp==nMinusTemp) )
            {
                cout<<countDecom<<":"<<count;
                for (vector<int>::iterator it=buf.begin(); it!=buf.end(); it++)
                    cout<<" "<<*it; 
                cout<<" "<<temp<<endl;  
            }
            buf.clear();
        }
            cout<<countDecom<<":"<<count<<" "<<n-count<<endl;
        count++;  
    }
    cout<<endl; system("pause");
}
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.10.2009, 20:45 #10
TanT,
Не все варианты выдает (проверял на числе 14).
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
05.10.2009, 20:52 #11
Нахрапом не решить, сразу говорю.
0
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
05.10.2009, 21:10 #12
Цитата Сообщение от kravam Посмотреть сообщение
Нахрапом не решить, сразу говорю.
не такие крепости брали однако, хочется что-то простое придумать. должен быть вариант.
а свой косяк понял
пойду посплю и стопудово чего-нить придумается
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
05.10.2009, 23:15 #13
Вот вам базовый код
Суть: вводится число, допустим 10. Создаётся такой массив чисел
10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Потом берутся все сочетания однушек (10, но не 9, это я предусмотрел)
Потом берутся все сочетания двушек из 10 (по-научному число сочетаний из n по m, как-то так), суммируются и проверяются на равенство 10.
То есть 10+ 9, 10+ 8, 10+ 7, 10+ 6... 9+ 8, 9+ 7 и так далее
Если находится такие числа- они заносятся в массив array. И этот массив выводится

Потом проверяются тройки, четвёрки, и так далее. Всё это делается в цикле, в основной функции
А поиск элементов в массиве и суммирование осуществляется в функции func_recurs.

При вводе числа 24 работа завершается ошибкой. То есть выведется простыня значений (верных, невповторяющихся, а потом прерывание)

В общем, можно код по многим направлениям усовершенстовать
1) Определиться с размером массива array (я наугад поделил число на 2 и всё)
2) Сделать так, чтобы при поиске двушек число 10 не было задействовано, ибо "10+ любое число" больше 10. А при поиске трёшек (третья итерация) чтобы не были задействовано соответсвенно, число 9 (может и 8, но это надо будет обосновывать)
3) Если вводишь число то же самое 25, допустим, а количество слагаемых задаёшь не в цикле, ну то есть просто вызываешь эту функцию один раз, допустим, так:
(То есть осуществляется поиск всех семёрок)

C++
1
func_recurs (0, 0, 7,25,7, massiv_chisel, array);
То работа проги заканчивается корректно. Да что там говорить, ребята, она корректо сработала так:
C++
1
func_recurs (0, 0, 6,100,6, massiv_chisel, array);
Неплохо, да? Умел бы прицеплять текстовые файлы прицепил бы, показал
Но не в цикле, а при отдельном вызове!
Вывод: cам по себе вызов функции жрёт немного памяти. А просто потому всё заканчивается ошибкой, что память остаётся занятой ПРЕДЫДУЩИМИ вызовами функций, которые уже даром не нужны. Вывели на экран значение- и всё.
Вот как-то научиться эту память освобождать.
Вот вам поле деятельности.
А я за сим удаляюсь.
Всегда ваш.
Кварам.


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
#include <iostream>
#include <stdio.h>
using namespace std;
 
//Вот это самое число
int osn_summa;
 
void func_recurs (int nomer_funktsii, int nomer_elementa, int kolichestvo_drugih_chisel, int kolichestvo_chisel, 
                  int kol_ostavshihsa_chisel,  int* stroka, int* array) {
 
static int summa= 0;
 
 
 for (int i= nomer_elementa; i< kolichestvo_chisel- kol_ostavshihsa_chisel+ 1; i++) {
 
  if (nomer_funktsii<kolichestvo_drugih_chisel- 1) {
   array [nomer_funktsii]= stroka [i];
   summa= summa+ stroka [i];
   
    func_recurs (nomer_funktsii+ 1, i+ 1,kolichestvo_drugih_chisel,kolichestvo_chisel, kol_ostavshihsa_chisel- 1, stroka, array);
 
   summa= summa- stroka [i];
  }
 
  else {
   summa= summa+ stroka [i];
   array [nomer_funktsii]= stroka [i];
   if (summa== osn_summa) {
    for (int j= 0; j< kolichestvo_drugih_chisel; j++) {
     printf ("%d   ", array [j] );
    }
    printf ("\n");
   }
   summa= summa- stroka [i];
   break;
  }
 }
}
 
 
 
int main () {
 
 
 
 
 cout<<"Вводите число"<<endl;
 cin>> osn_summa;
 
 //Сделаеv массивчик и заполним его
 int* massiv_chisel= new int [osn_summa];
 
 //Заполнение
 for (int i= 0; i< osn_summa; i++) {
  massiv_chisel [i]= osn_summa- i; 
 }
 
 //В этот массив будут заноситься числа-значения
 int array [osn_summa/2];
 
 //Вызов функции в цикле. Сперва с одним значением, потом со вторым и так далее
 for (int i= 1; i< osn_summa; i++) {
  func_recurs (0, 0, i,osn_summa, i, massiv_chisel, array);
 }
 
 //Закомментируйте предыдущий цикл, расскоментируйте этот вызов
 //Скомпилируйте, запустите и наслаждайтесь
 //func_recurs (0, 0, 6,100, 6, massiv_chisel, array);
 
 suda: system ("PAUSE");
 delete [] massiv_chisel;
 
 return 0;
}
Добавлено через 30 минут
Чтобы уж не быть голословным, вызывайте функции так прогу с такими параметрами
C++
1
2
3
4
5
6
7
  func_recurs (0, 0, 1, 100, 1, massiv_chisel, array);
  func_recurs (0, 0, 2, 100, 2, massiv_chisel, array);
  func_recurs (0, 0, 3, 100, 3, massiv_chisel, array);
  func_recurs (0, 0, 4, 100, 4, massiv_chisel, array);
  func_recurs (0, 0, 5, 100, 5, massiv_chisel, array);
  func_recurs (0, 0, 6, 100, 6, massiv_chisel, array);
  func_recurs (0, 0, 7, 100, 7, massiv_chisel, array);
И ждите. У меня всё нормально прошло, правда, машина долго работала но это из-за того, что вхолостую перебирает заведомо ненужные значения, я писал вначале.
А вот с восьмёркой запускать не советую.
Я окончания работы не дождался.
И ЕСЛИ ТАК БУДЕТЕ ЗАПУСКАТЬ ВВООДИТЕ ЧИСЛО 100. Или вообще закомментируйте ввод.
...А в цикле не хочет работать почему-то...
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,197
Завершенные тесты: 1
06.10.2009, 00:37 #14
Напоминает http://www.cyberforum.ru/showthread.php?t=47694, только там надо было найти количество таких разложений.
Мой вариант без оптимизаций по времени, до 80 работает (вроде бы) более-менее быстро.
vector<string> Decompose(int n, int m) - разложения для числа n с числами не больше m.
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
#include <iostream>
#include <vector>
#include <string>
#include <limits>
 
using namespace std;
 
string IntToStr(int n)
{
    string s;
    s.reserve(3);
    char c[2] = {0, 0};
    do
    {
        c[0] = n % 10 + '0';
        s = string(c) + s;
        n /= 10;
    } while (n != 0);
    return s;
}
 
vector<string> Decompose(int n, int m)
{
    vector<string> result;
    if (m > n) m = n;
    if (n == 0)
    {
        result.push_back("");
        return result;
    }
    if (m == 0)
        return result;
    for (int cn = m; cn > 0; cn--)
    {
        string head = IntToStr(cn) + ' ';
        vector<string> tails = Decompose(n - cn, cn - 1);
        for (size_t i = 0; i < tails.size(); i++)
            result.push_back(head + tails[i]);
    }
    return result;
}
 
int main()
{
    int n;
    cin >> n;
    vector<string> result = Decompose(n, n);
    cout << endl;
    for (size_t i = 0; i < result.size(); i++)
        cout << result[i] << endl;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.peek();
    return 0;
}
0
kravam
быдлокодер
1697 / 884 / 45
Регистрация: 04.06.2008
Сообщений: 5,482
06.10.2009, 06:26 #15
Не работает чё-то.
В main куда m писать?
Но всё равно не работает Decompose(5, 4)

Чёрный экран только

Добавлено через 26 минут
Пацаны, я дико извиняюсь. Заккоментируйте строчку 36 break;

Добавлено через 1 час 58 минут
Короче, разобрался я, в чём дело, почему в цикле не работает.
Дело в том, что я для вспомогательного массива тупо выделил размер так: поделил основоной размер на 2.

Но в функции это не учёл! И если размер вспомогательного массива, допустим, 10, то функция заполняет и 11, и 12 и 13 и так далее адреса! А по этим адресам запросто находится счётчик цикла... Всё, кранты циклу. По крайней мере, у меня так было.
Исправьте там строку
int array [osn_summa/2]; на int array [osn_summa];
0
06.10.2009, 06:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2009, 06:26
Привет! Вот еще темы с ответами:

Перестановки без повторений - C++
Как из этого кода сделать конфетку — чтобы не выводились повторения? #include &lt;iostream&gt; using namespace std; string s; ...

Random, значения без повторений - C++
Нашел здесь на форуме код для рандома без повторений: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;locale&gt; #include...

Последовательность чисел без повторений - C++
Здравствуйте. Мне нужно сформировать последовательности,состоящие из нулей и единиц.Последовательности не должны повторяться. Подскажите...

Выписать все перестановки без повторений - C++
Тему копирую из раздела C#, из-за того что на си народу больше. Есть строка 0,1,2,3,4 и к примеру таблица int m = 5; int...


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

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

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