VPF::[С++] Количество разбиений числа

Krom0707

Дата 10.1.2008, 16:00 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 10.1.2008

Репутация: нет
Всего: нет

Требуется создать программу на С++: подсчет количества разбиений числа на сумму слагаемых.
Программа должна считать количество разбиений числа 100 меньше 5 секунд, не могу преодолеть этот барьер. Вот две программы, помогите кто чем может!

Код


#include <iostream.h> 

int a[1000]; 
void add( int n, int max, int k) 
{ 
if ( n < max ) max = n; 
for ( int i = max; i>0; i-- ){ 
a[k] = i; 
if ( i==n ) 
{ 
for( int i=0; i<k; i++ ) 
cout << a << "+"; 
cout << a[k] << endl; 
} 
else 
add( n-i,i ,k+1 ); 
} 
} 

int main() 
{ 
int n=6; 
add(n,n,0); 
return 0; 
} 




//---------------------------------------------------------------------------

#pragma hdrstop

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
        int n, k, m, s, i;
        int j=1;
        int *x;
clrscr();
printf("input n: ");
scanf("%d", &n);
x=new int[n+1];
for(i=1;i<n+1;i++)
    {
    x[i]=1;
    }
k=n;
while(k>1)
{
i=k-1;
while(i!=1 && x[i-1]<=x[i])
    {
    i=i-1;
    }
x[i]=x[i]+1;
s=0;
for(m=i+1;m<k+1;m++)
    {
    s=s+x[m];
    }
for(m=1;m<s;m++)
    {
    x[i+m]=1;
    }
k=i+s-1;
j++;
}
printf("\noutput %d",j);
getch();
        return 0;
}
//---------------------------------------------------------------------------

Это сообщение отредактировал(а) Kuvaldis - 10.1.2008, 19:19

Kuvaldis

Дата 10.1.2008, 19:20 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61

M
Kuvaldis

Пользуемся тегами подсветки кода;)

--------------------

Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей

PPS05

Дата 10.1.2008, 20:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 262
Регистрация: 6.11.2005
Где: Беларусь, Минск

Репутация: 1
Всего: 7

Вот, писал когда-то. Входное число в decomp.in. Предполагается, что перестановка слагаемых не дает нового способа (впрочем, нетрудно подправить, наверное...)

Код


#include <stdio.h>

int N;

FILE * out;

void input()
{
    FILE * in = fopen("decomp.in", "rt");
    fscanf(in, "%d", &N);
    fclose(in);
}

int ans[200];
int ai;

void ok()
{
    for (int i=0; i<ai-1; i++)
        fprintf(out, "%d+", ans[i]);
    fprintf(out, "%d\n", ans[ai-1]);
}

int min(int a, int b)
{
    return a<b?a:b;
}

void backtrack(int s)
{
    N -= s;
    ans[ai++] = s;
    if (N == 0)
        ok();
    else
    {
        for (int p=min(N, s); p>0; p--)
            backtrack(p);
    }
    N += s;
    ai--;
}

void solve()
{
    ai = 0;
    out = fopen("decomp.out", "wt");
    for (int s=N-1; s>0; s--)
        backtrack(s);
    fclose(out);
}

int main(void)
{
    input();
    solve();
    return 0;
}

--------------------

Ушел с форума и не вернулся.

Krom0707

Дата 11.1.2008, 09:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 10.1.2008

Репутация: нет
Всего: нет

Спасибо, только и твой алгоритм выполняется больше 5 секунд, а мне нужно быстрее!

crazy_hand

Дата 11.1.2008, 15:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 12.12.2007
Где: Санкт-Петербург

Репутация: нет
Всего: нет

Krom0707,
PPS05, попробуй в этот алгоритме число константой задавать - ведь оно заранее известно, а считывание из файла - очень долгая операция.

Krom0707

Дата 11.1.2008, 15:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 10.1.2008

Репутация: нет
Всего: нет

Я так и сделал, для 99 алгоритм считает 16 секунд! Надо 5!

xvr

Дата 11.1.2008, 15:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: нет
Всего: 223

Цитата(Krom0707 @ 10.1.2008, 16:00)

Код


#include <iostream.h> 

int a[1000]; 
void add( int n, int max, int k) 
{ 
if ( n < max ) max = n; 
for ( int i = max; i>0; i-- ){ 
a[k] = i; 
if ( i==n ) 
{ 
for( int i=0; i<k; i++ ) 
cout << a << "+"; 
cout << a[k] << endl; 
} 
else 
add( n-i,i ,k+1 ); 
} 
} 

int main() 
{ 
int n=6; 
add(n,n,0); 
return 0; 
} 




//---------------------------------------------------------------------------

#pragma hdrstop

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

//---------------------------------------------------------------------------

#pragma argsused
int main(int argc, char* argv[])
{
        int n, k, m, s, i;
        int j=1;
        int *x;
clrscr();
printf("input n: ");
scanf("%d", &n);
x=new int[n+1];
for(i=1;i<n+1;i++)
    {
    x[i]=1;
    }
k=n;
while(k>1)
{
i=k-1;
while(i!=1 && x[i-1]<=x[i])
    {
    i=i-1;
    }
x[i]=x[i]+1;
s=0;
for(m=i+1;m<k+1;m++)
    {
    s=s+x[m];
    }
for(m=1;m<s;m++)
    {
    x[i+m]=1;
    }
k=i+s-1;
j++;
}
printf("\noutput %d",j);
getch();
        return 0;
}
//---------------------------------------------------------------------------

Тебе нужно подсчитать количество разбиений или найти все разбиения?
Если первое, то не нужно печатать собственно разбиения, достаточно посчитать их количество. Если второе - то сам по себе простой вывод через cout всех их займет более 5 сек.
Если же нужно именно второе, то попробуй вывод в файл (можно даже перенаправить с коммандной строки) и выводить через fprintf - он быстрей.

Сама по себе твой алгоритм и так достаточно оптимален, ускорить будет сложно.

PPS05

Дата 11.1.2008, 15:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 262
Регистрация: 6.11.2005
Где: Беларусь, Минск

Репутация: 1
Всего: 7

Цитата(crazy_hand @ 11.1.2008, 14:06

)

попробуй в этот алгоритме число константой задавать - ведь оно заранее известно, а считывание из файла - очень долгая операция.

Пренебрежительно мало. smile

--------------------

Ушел с форума и не вернулся.

PPS05

Дата 11.1.2008, 15:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 262
Регистрация: 6.11.2005
Где: Беларусь, Минск

Репутация: 1
Всего: 7

Проверьте, пожалуйста, для 100 ответ 190569292 ?
Если да, то вот код (работает доли секунды, не комментирую, ибо не уверен в правильности):

Код


#include <stdio.h>

int M[110][110];

int foo(int i, int j)
{
    if (M[i][j] != 0)
        return M[i][j];
    if (i == j)
        return 1;
    if (j > i)
        return 0;
    int permuts = 0;
    for (int k = 1; (k <= (i-j)) && (k <= j); k++ )
        permuts += foo(i-j, k);
    M[i][j] = permuts;
    return permuts;
}

int main(void)
{
    int answer = 0;
    const int N = 100;
    for (int i = 1; i <= N; i++ )
        answer += foo(N, i);
    printf("%d\n", answer);
    return 0;
}

Это сообщение отредактировал(а) PPS05 - 11.1.2008, 15:36

--------------------

Ушел с форума и не вернулся.

xvr

Дата 11.1.2008, 15:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: нет
Всего: 223

Цитата(Krom0707 @ 11.1.2008, 15:12)

Я так и сделал, для 99 алгоритм считает 16 секунд! Надо 5!

Посмотрел твою вторую программу - ничего не понял smile

Для подсчета количества разбиений (если считать все разбиения, включая перестановки слогаемых) можно применить метод динамического програмирования:

Ищутся разбиения для всех чисел не больших, чем заданное (и сохраняются в массиве)

Поиск количества разбиений для числа N происходит так:
1) Одно разбиение - само число целиком
2) Разбиваем число на 2 половины (N-1 способами: A и B=N-A), прибавляем произведения количества возможных разбиений для A и B

Код


#include <stdio.h>
#include <stdlib.h>

int all_divs[1000];

int main(int argc, char** argv)
{
  int N=atoi(argv[1]);
  all_divs[0]=all_divs[1]=1;
  for(int num=1;num<=N;++num)
   {
     int acc=1;
     for(int a=1;a<num;++a)
      acc+=all_divs[a]*all_divs[num-a];
     all_divs[num]=acc;
   }
 printf("Total: %d\n",all_divs[N]);
 return 0;
}

Время исполнения для 100 - 5 ms
(для 999 - 50 ms)

Результат для 100 - 2029745963 (хм, кто больше smile

)

Это сообщение отредактировал(а) xvr - 11.1.2008, 15:54

PPS05

Дата 11.1.2008, 16:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 262
Регистрация: 6.11.2005
Где: Беларусь, Минск

Репутация: 1
Всего: 7

Я больше поверю, что ответ 2029745963... smile

Я тоже делал динимическим, только лень было с порядком вычисления возиться. Функция foo(i, j) возвращает количество разбиений для числа i, если первое слагаемое j. M - для запоминания ранее высчитанных ("рекурсия с меморизацией").

--------------------

Ушел с форума и не вернулся.

Krom0707

Дата 11.1.2008, 16:29 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 10.1.2008

Репутация: нет
Всего: нет

Спасибо ,PPS05, ваша программа работает идеально!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »