VPF::[Алгоритм] Количество разбиений числа

Krom0707

Дата 10.1.2008, 12:46 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 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;
}
//---------------------------------------------------------------------------

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

maxim1000

Дата 10.1.2008, 17:25 (ссылка)

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

Загрузка ...

Эксперт

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

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

только не надо тему создавать, я эту переношу...

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

qqq

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