정수 분할[가능한 모든 분할을 일괄 인쇄]
4
4=1+1+1+1
4=1+1+2
4=1+3
4=2+2
4=4
5n=4를 입력하면 두 번째 줄부터 여섯 번째 줄까지 다섯 가지 구분이 있습니다. 분할은 위와 같습니다.
코드는 다음과 같습니다.
#include
#include
#include
using namespace std;
int n,total=0;
int a[100] = {1};
void print(int t) //
{
total ++ ; //
printf("%d=",n);
for(int i=1;i<=t;i++)
{
if(i==t)
printf("%d
",a[i]);
else
printf("%d+",a[i]);
}
}
void solve(int s,int t)
{
for(int i=a[t-1];i<=s;i++)
{
if(i<=n) // i 1 ， n
{
a[t] = i; // i
s -= i; //s i,s
if(s==0) // ，
print(t);
else
solve(s,t+1); //
s += i; // ， ，
}
}
}
int main()
{
scanf("%d",&n);
solve(n,1);
printf("%d
",total);
return 0;
}
그러나 귀속은 매우 시간을 소모한다. 특히 n이 비교적 클 때 그 문제는 hduoj1028http://acm.hdu.edu.cn/showproblem.php?pid=1028그래서 우리는 새로운 방법을 다시 찾아야 한다. 책에서 모함수가 있는 방법을 언급한 적이 있다. 아래에 코드를 제시하면 코드가 정말 공교롭다. 어쩔 수 없이 알고리즘은 정말 재미있다.
#include
#include
using namespace std;
int c1[125];
int c2[125];
int main()
{
int n,i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<=n;i++)
{
c1[i]=1;
c2[i]=0;
}
for(i=2;i<=n;i++)
{
for(j=0;j<=n;j++)
{
for(k=0;j+k<=n;k+=i)
c2[j+k]+=c1[j];
}
for(j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 백엔드에서 데이터를 트리로 변환하고 맵은 json 트리를 생성하여 백엔드로 되돌려줍니다. (백엔드 변환)java 백엔드, 데이터를 트리로 변환하고,map는 json 트리를 생성하여 전방으로 되돌려줍니다(백엔드 변환) 1. 왜 이런 블로그를 쓰나요? 2.java 백엔드 코드 3. 전환된 데이터는 다음과 유사한 형식으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
