首页 > 其他 > 详细

数的拆分x有一布判重特别重要!

时间:2017-03-24 19:57:00      阅读:286      评论:0      收藏:0      [点我收藏+]
qwqx
突然想起要打上题目
任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。
n=714种拆分方法:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
 

//AC自动机x
#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<math.h>
using namespace std;
int n,h;
int a[100]= {1}; //开始必须为1;
int search(int,int);
int print(int);
int main() {
cin>>n;
search(n,1);
cout<<"total="<<h<<endl;
return 0;
}
int search(int s,int t) {
for(int i=a[t-1]; i<=s; i++) //此步为判重x 比前一个数大,比总数小,避免重复。
{
if(i<n) //防止7=7的现象产生!!这点非常重要
{
a[t]=i;
s-=i;
if(s==0) print(t);//当需要拆分的数是0的时候结束
else search(s,t+1);//继续搜索下一个
s+=i;//回溯
}
}
}
int print(int t) {
cout<<n<<"=";
for(int i=1; i<=t-1; i++)
cout<<a[i]<<"+";
cout<<a[t]<<endl;
h++;
}

数的拆分x有一布判重特别重要!

原文:http://www.cnblogs.com/zxqxwnngztxx/p/6613107.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!