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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.96
alibaba314
18 / 18 / 1
Регистрация: 22.03.2009
Сообщений: 58
04.10.2009, 10:16     Число разложений без повторений ! #1
напишите програму , которая считает количество разложений Q(N) данного натурального числа N на неупорядоченные слагаемые без повторений. например, для N=5 есть 3 различных разложений 5=5=4+1=3+2. разложения считаются различными если множества слагаемых различаются.

интересная задача!!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,302
06.10.2009, 14:19     Число разложений без повторений ! #21
Добавлено через 42 минуты
Не, мне бесполезно тестировать. Она уже минут 40 стоит на таких значениях.
15 14 13 12 10 9 4 3

Добавлено через 1 минуту
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
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 //не правильно
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
06.10.2009, 16:49     Число разложений без повторений ! #23
easybudda, для 6ти 4 варианта, у тебя a,b,c,d
требуется чтобы в одном разложении небыло повторяющихся цифр
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
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 минут
не-а, всё равно не всё печатает. завтра додумаю...
Somebody
2775 / 1588 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
07.10.2009, 13:12     Число разложений без повторений ! #25
Цитата Сообщение от TanT Посмотреть сообщение
для 80 потестируй, если не сложно. мне количество разложений интересно.
Somebody, у тя скока для 80?
У меня 77312 вариантов, ну и времени заняло минут 10. точно не засекал
На 80 тоже 77312. Твоя прога выполнялась 71 секунду (сделай строку-буфер и один вывод в конце, из-за постоянного вывода может тормозить), моя 20 секунд (6 секунд расчёт, 14 - вывод результата).
Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
TanT
эволюционирую потихоньку
 Аватар для TanT
464 / 462 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
07.10.2009, 13:17     Число разложений без повторений ! #26
Цитата Сообщение от Somebody Посмотреть сообщение
Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
запустить и уйти пить чай
вывод тормозит, это точно. но на временные характеристики ограничений не было. оптимизировать много ещё чего конечно можно. главное что количество комбинаций совпало.
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,302
07.10.2009, 14:31     Число разложений без повторений ! #27
Цитата Сообщение от Somebody Посмотреть сообщение
На 80 тоже 77312. Что надо сделать, чтобы выполнялось 10 минут, даже предположить не могу.
У меня круче всех- всех дольше.
Но это потому, в частности, что, например, возьмём число 20 и варианты для трёшек.
Вот она перебирает ВСЕ варианты
20 19 18_________ 20 19 17___________ 20 19 16 и так далее
Ковыряться не стал, надо же ТС что-то делать!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2009, 11:11     Число разложений без повторений !
Еще ссылки по теме:

Последовательность чисел без повторений C++
C++ Найти число разложений числа на 2 множителя
C++ Перестановка без повторений
C++ Перестановки без повторений
Перестановка без повторений C++

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

Или воспользуйтесь поиском по форуму:
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;
}
Yandex
Объявления
08.10.2009, 11:11     Число разложений без повторений !
Ответ Создать тему
Опции темы

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