首页 > 代码库 > NOJ--1046--dfs
NOJ--1046--dfs
刚刚A了那题之后 想到以前自己的OJ那边有个整数划分...
同时 tz 那边也有个很相似的 我是做了TZ的再做了自己OJ的 一起 放上链接
touch me
touch me 其实 我们解决的问题 应该主要是 字典序的输出和不能重复的输出
就是说 1+1+2出现了 那么1+2+1就不应该出现 -- 这是不能重复输出的一个例子
1+3 应该出现在 2+ 2 的前面----这是字典序输出
我的解决方法就是 将 n 从 1开始遍历到n 其实这样已经解决了 字典序输出的问题 因为是从小到大的
至于 重复输出 我们只要记录下 我们开始遍历的这个n的值 然后以它递归的时候 就不要从1开始 而是从它自身开始 不要从它自身后面一位开始 因为它自身是可以无限累加的 比如5是可以由 5个1 构成的
至此 我们已经解决了 上面提到的2个问题 ------------ 我把2份代码 都贴下面
发现 博客园的代码折叠功能真的很好~.....
1 #include <iostream> 2 using namespace std; 3 4 int n; 5 int arr[60]; 6 7 void dfs( int sum , int pos ,int cnt ) 8 { 9 if( sum>n )10 return;11 else if( sum==n )12 {13 printf( "%d",arr[0] );14 for( int i = 1 ; i<cnt ; i++ )15 {16 printf( " %d",arr[i] );17 }18 printf( "\n" );19 }20 else21 {22 for( int i = pos ; i<=n ; i++ )23 {24 arr[cnt] = i;25 dfs( sum+i , i , cnt+1 );26 }27 }28 }29 30 int main()31 {32 while( ~scanf("%d",&n) )33 {34 dfs(0,1,0); 35 }36 }
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 int n; 6 int arr[200]; 7 8 void dfs( int sum , int pos , int cnt ) 9 {10 if( sum>n )11 return;12 else if( sum==n )13 {14 printf( "%d=%d",n,arr[0] );15 for( int i = 1 ; i<cnt ; i++ )16 {17 printf( "+%d",arr[i] );18 }19 printf( "\n" );20 }21 else22 {23 for( int i = pos ; i<n ; i++ )24 {25 arr[cnt] = i;26 dfs( sum+i , i , cnt+1 );27 }28 }29 }30 31 int main()32 {33 while( ~scanf("%d",&n) )34 {35 dfs(0,1,0); 36 }37 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。