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

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

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

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

04.10.2009, 10:16. Просмотров 3846. Ответов 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
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 08:13 #16
мой вариант, критикуйте (в функцию вывод не объединял - ибо лень)
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
 
#define sizeVec(c) int((c).size())
#define all(c) (c).begin(),(c).end()
#define REST(a)  ((a).first)        // остаток
#define ARR(a)  ((a).second)        // массив найденных слагаемых
#define LOST(a) (*(ARR(*a).end()-1)) // последний элемент списка слагаемых
 
using namespace std;
 
typedef vector <pair<int, vector<int> > > Analysis;
 
 
void main()
{
    int n,countDecom=1, count=1;
    vector<int> buf;
    Analysis allBuf, tempBuf;
    Analysis::iterator begun;
    cout<<"input number:"<<endl;
    cin>>n; 
    cout<<"variants decomposition:"<<endl;
    cout<<countDecom<<": "<<n<<endl;
    // запись основных родоначальных пар
    while((n/2+n%2)>count)
    {
        buf.clear();
        buf.push_back(count);
        tempBuf.push_back(make_pair(n-count,buf)); 
        count++; 
    }
 
    // вывод результата
    for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
    { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
    }
 
    while(!(tempBuf.empty()))
    {
        // размножение вариантов с уменьшением остатка
        allBuf.clear();
        for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
        { count=1;
        //  cout<<LOST(it)<<"<"<<REST(*it)-count<<endl;
            while(LOST(it)<REST(*it)-count)
            {
                //cout<<count<<endl;
                buf.clear();
                for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
                    buf.push_back(*itt);
                buf.push_back(LOST(it)+count);
                allBuf.push_back(make_pair(REST(*it)-count-LOST(it),buf));
                count++;
            }
        } // end for
        
        tempBuf.clear();
        // если варианты размножились
        if(!(allBuf.empty()))
        { // проверяем остатки и думаем что делать
            for (Analysis::iterator it=allBuf.begin(); it!=allBuf.end(); it++)
            {
        if (LOST(it)<REST(*it))
         tempBuf.push_back(*it);
 
                if (REST(*it)==0)
                {
                    cout<<++countDecom<<":"; 
                    for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
                        cout<<" "<<*itt;
                    cout<<endl;
                }                   
            }
        } // end if
 
        // вывод результата
        for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
        { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
        }
 
 
    } // end while(!(tempBuf.empty()))
 
    // вывод результата
    for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
    { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
    }
 
 /*
               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;
                 
        }*/
        cout<<endl; system("pause");
 
}
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 08:14 #17
мой вариант, критикуйте (в функцию вывод не объединял - ибо лень)
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
 
#define sizeVec(c) int((c).size())
#define all(c) (c).begin(),(c).end()
#define REST(a)  ((a).first)        // остаток
#define ARR(a)  ((a).second)        // массив найденных слагаемых
#define LOST(a) (*(ARR(*a).end()-1)) // последний элемент списка слагаемых
 
using namespace std;
 
typedef vector <pair<int, vector<int> > > Analysis;
 
 
void main()
{
    int n,countDecom=1, count=1;
    vector<int> buf;
    Analysis allBuf, tempBuf;
    Analysis::iterator begun;
    cout<<"input number:"<<endl;
    cin>>n; 
    cout<<"variants decomposition:"<<endl;
    cout<<countDecom<<": "<<n<<endl;
    // запись основных родоначальных пар
    while((n/2+n%2)>count)
    {
        buf.clear();
        buf.push_back(count);
        tempBuf.push_back(make_pair(n-count,buf)); 
        count++; 
    }
 
    // вывод результата
    for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
    { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
    }
 
    while(!(tempBuf.empty()))
    {
        // размножение вариантов с уменьшением остатка
        allBuf.clear();
        for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
        { count=1;
        //  cout<<LOST(it)<<"<"<<REST(*it)-count<<endl;
            while(LOST(it)<REST(*it)-count)
            {
                //cout<<count<<endl;
                buf.clear();
                for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
                    buf.push_back(*itt);
                buf.push_back(LOST(it)+count);
                allBuf.push_back(make_pair(REST(*it)-count-LOST(it),buf));
                count++;
            }
        } // end for
        
        tempBuf.clear();
        // если варианты размножились
        if(!(allBuf.empty()))
        { // проверяем остатки и думаем что делать
            for (Analysis::iterator it=allBuf.begin(); it!=allBuf.end(); it++)
            {
        if (LOST(it)<REST(*it))
         tempBuf.push_back(*it);
 
                if (REST(*it)==0)
                {
                    cout<<++countDecom<<":"; 
                    for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
                        cout<<" "<<*itt;
                    cout<<endl;
                }                   
            }
        } // end if
 
        // вывод результата
        for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
        { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
        }
 
 
    } // end while(!(tempBuf.empty()))
 
    // вывод результата
    for (Analysis::iterator it=tempBuf.begin(); it!=tempBuf.end(); it++)
    { cout<<++countDecom<<": "<<REST(*it); 
        for (vector<int>::iterator itt=ARR(*it).begin(); itt!=ARR(*it).end(); itt++)
            cout<<" "<<*itt;
        cout<<endl;
    }
 
 /*
               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;
                 
        }*/
        cout<<endl; system("pause");
 
}
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 10:42 #18
модераторы удалите второй пост, чего-то у меня сегодня не лады с сайтом, полчаса зайти не мог и сообщение отправить
0
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
06.10.2009, 12:10 #19
До 26 включительно результаты одинаковы, что у меня, что у TanT ,
Дальше не проверял.
У меня медленнее, правда, работает, но это оговорено.
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 12:54 #20
Цитата Сообщение от kravam Посмотреть сообщение
До 26 включительно результаты одинаковы, что у меня, что у TanT ,
Дальше не проверял.
У меня медленнее, правда, работает, но это оговорено.
для 80 потестируй, если не сложно. мне количество разложений интересно.
Somebody, у тя скока для 80?
У меня 77312 вариантов, ну и времени заняло минут 10. точно не засекал
0
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
06.10.2009, 14:19 #21
Добавлено через 42 минуты
Не, мне бесполезно тестировать. Она уже минут 40 стоит на таких значениях.
15 14 13 12 10 9 4 3

Добавлено через 1 минуту
0
easybudda
Модератор
Эксперт CЭксперт С++
9698 / 5648 / 964
Регистрация: 25.07.2009
Сообщений: 10,863
06.10.2009, 16:29 #22
Цитата Сообщение от alibaba314 Посмотреть сообщение
а, если 6=3+2+1 ????

это правильно, но по моему не достаточно!
Задание уточните!
Сколько "правильных" вариантов в этом примере?
a) 6 = 6 + 0
b) 6 = 5 + 1
c) 6 = 4 + 2
d) 6 = 3 + 2 + 1
Единица встречается в b и d, а двойка в c и d. Или важно только, чтобы внутри одного варианта числа не повторялись?
например
e) 6 = 4 + 1 + 1 //не правильно
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 16:49 #23
easybudda, для 6ти 4 варианта, у тебя a,b,c,d
требуется чтобы в одном разложении небыло повторяющихся цифр
0
easybudda
Модератор
Эксперт CЭксперт С++
9698 / 5648 / 964
Регистрация: 25.07.2009
Сообщений: 10,863
07.10.2009, 01:26 #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
#include <stdio.h>
#include <stdlib.h>
 
int main(){
    int n; /* собственно число */
    int a, b, c, d; /* вспомогательные переменные */
    int count; /* счётчик */
    
    printf("enter some number more then null: ");
    if ( !scanf("%d", &n) )
        exit(1);
    if ( n < 1 ){
        printf("Wrong number\n");
        exit(1);
    }
    printf("Composed numbers of %d:\n", n);
    count = 1; /* как минимум, само себе число всегда равно */
    printf("%d = %d\n", n, n);
    if ( n == 1 ){
        printf("Total %d calculation\n", count);
        exit(0);
    }
    
    /* дальше собственно программа */
    for ( a = 1; a < ((n / 2) + (n % 2)); a++ ){
        b = n - a;
        count++;
        printf("%d = %d + %d\n", n, a, b);
        c = a + 1;
        while ( (b - c) > c ) {
            printf("%d = %d", n, a);
            for ( d = a + 1; d < c; d++ )
                printf(" + %d", d);
            printf(" + %d + %d\n", c, b - c + d - a - 1);
            c++;
            b -= c;
            count++;
        } 
    }
    printf("Total %d calculations\n", count);
        
    exit(0);
}
Добавлено через 7 минут
не-а, всё равно не всё печатает. завтра додумаю...
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,200
Завершенные тесты: 1
07.10.2009, 13:12 #25
Цитата Сообщение от TanT Посмотреть сообщение
для 80 потестируй, если не сложно. мне количество разложений интересно.
Somebody, у тя скока для 80?
У меня 77312 вариантов, ну и времени заняло минут 10. точно не засекал
На 80 тоже 77312. Твоя прога выполнялась 71 секунду (сделай строку-буфер и один вывод в конце, из-за постоянного вывода может тормозить), моя 20 секунд (6 секунд расчёт, 14 - вывод результата).
Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
0
TanT
эволюционирую потихоньку
466 / 464 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
07.10.2009, 13:17 #26
Цитата Сообщение от Somebody Посмотреть сообщение
Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
запустить и уйти пить чай
вывод тормозит, это точно. но на временные характеристики ограничений не было. оптимизировать много ещё чего конечно можно. главное что количество комбинаций совпало.
0
kravam
быдлокодер
1703 / 890 / 45
Регистрация: 04.06.2008
Сообщений: 5,489
07.10.2009, 14:31 #27
Цитата Сообщение от Somebody Посмотреть сообщение
На 80 тоже 77312. Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
У меня круче всех- всех дольше.
Но это потому, в частности, что, например, возьмём число 20 и варианты для трёшек.
Вот она перебирает ВСЕ варианты
20 19 18_________ 20 19 17___________ 20 19 16 и так далее
Ковыряться не стал, надо же ТС что-то делать!
0
iluha82
1 / 1 / 0
Регистрация: 07.10.2009
Сообщений: 9
08.10.2009, 11:11 #28
Задачка - СУПЕР! Мне очень понравилась пол часа репу чесал
Зацените мой код:
Решение при условии что слагаемые не должны повторяться... т.е. не может быть 10=5+5...

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
#include <iostream>
#include <string>
#include <stdlib.h>
#include <sstream> 
 
using namespace std;
void sumrecurs(int max, int min, string endline);
 
int main(int argc, _TCHAR* argv[])
{
    int N;
    cout<<"insert number:"<<endl;
    cin>>N;
    sumrecurs(N,0,"");
    system("pause");
    return 0;
}
 
void sumrecurs(int max, int min, string endline)
{
    static int x=-1;
    x++;
    if (max-(min+1)<=(min+1)) return;
    for (int i=min+1,j=max-i;j>i;i++,j--)
    {
        std::ostringstream stringout; 
        stringout << "+"<<i<<endline; 
        std::string msg= stringout.str(); 
        sumrecurs(j,i,msg);
        cout <<j<<msg<<endl;
    }
    if (endline=="") cout <<"Total: "<<x<<endl;
}
Добавлено через 51 минуту
Вывод конечно тормозит... а вот если без него, то работает буквально милисекунды

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
#include "stdafx.h"
#include <iostream>
#include <string>
#include <stdlib.h>
#include <sstream> 
 
using namespace std;
void sumrecurs(int max, int min);
 
int main(int argc, _TCHAR* argv[])
{
    int N;
    cout<<"insert number:"<<endl;
    cin>>N;
    sumrecurs(N,0);
    system("pause");
    return 0;
}
 
void sumrecurs(int max, int min)
{
    static int x=-1;
    x++;
    for (int i=min+1,j=max-i;j>i;i++,j--)
    {
        sumrecurs(j,i);
    }
    if (min==0) cout <<"Total: "<<x<<endl;
    return;
}
0
PABBIH
55 / 0 / 0
Регистрация: 17.02.2017
Сообщений: 1
17.02.2017, 18:16 #29
OMG, сколько же тут говнокода в этой ветке!
Я даже специально зарегистрировался, не могу это стерпеть, жуть какая.
Эта задача - один из классических примеров динамического программирования.

Решение за O(n^2):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int dp[1001][1001];
int uniquePartitions(int number, int minAllowedToAdd) {
    if (number == 0 || minAllowedToAdd == number)
        return 1;
 
    if (number < 0 || minAllowedToAdd > number)
        return 0;
 
    int &result = dp[number][minAllowedToAdd];
    if (result)
        return result;
 
    return result = uniquePartitions(number, minAllowedToAdd + 1) + 
                             uniquePartitions(number - minAllowedToAdd, minAllowedToAdd + 1);
}
Запускать так:

C++
1
cout << uniquePartitions(80, 1) << "\n";
0
17.02.2017, 18:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2017, 18:16
Привет! Вот еще темы с ответами:

Перестановки без повторений - 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...


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

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

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