| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2172 人关注过本帖
标题:将任意正数N分解成多个互不相同的正整数的和,并打印所有可能的组合方式。例 ...
只看楼主 加入收藏
hwshtongxin
Rank: 1
等 级:新手上路
帖 子:35
专家分:4
注 册:2009-1-6
结帖率:66.67%
收藏
 问题点数:0 回复次数:5 
将任意正数N分解成多个互不相同的正整数的和,并打印所有可能的组合方式。例如N=6,组合方式有1+5,2+4,1+2+3
首先能不能把这里面的实现算法解释下。还有可通过什么数据结构来实现题目要求。
搜索更多相关主题的帖子: 分解 正数 整数 打印 
2009-10-25 21:45
xiaohui240
Rank: 1
来 自:武汉
等 级:新手上路
威 望:1
帖 子:9
专家分:8
注 册:2009-9-24
收藏
得分:0 
采用递归的方法。
2009-10-26 17:22
hwshtongxin
Rank: 1
等 级:新手上路
帖 子:35
专家分:4
注 册:2009-1-6
收藏
得分:0 
回复 2楼 xiaohui240
怎么个递归的方法?能否再详细点。。
能否写个伪代码出来。。
学习下。。这个 题已经困扰着我好久了。
2009-10-26 23:36
farss
Rank: 1
等 级:新手上路
帖 子:7
专家分:2
注 册:2008-6-9
收藏
得分:0 
最简单的办法:

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


int main()
{
    int i,j,n;
    printf("请输入n:");
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
    for(j=n-i;j>=i;j--)
      {
                      printf("%d+%d=%d\n",i,j,n);
                      break;
                      }
        printf("\n");
                    }
   
   
    system("pause");
    return 0;
        
}


[ 本帖最后由 farss 于 2009-10-27 10:26 编辑 ]
2009-10-27 10:07
hwshtongxin
Rank: 1
等 级:新手上路
帖 子:35
专家分:4
注 册:2009-1-6
收藏
得分:0 
回复 4楼 farss
好像你这里只考虑了一部分。。。
两个和等于n的情况,在情况: n=6; n=1+2+3时,好像 还需要再考虑。。。。。。。
大家一起想想,,是否有更完善的方法。。。。。。。。。

2009-10-27 11:32
hwshtongxin
Rank: 1
等 级:新手上路
帖 子:35
专家分:4
注 册:2009-1-6
收藏
得分:0 
/////////在网上找了个程序,运行了下,还可以,但具体的实现过程还没看懂,大家一起看看。。
#include<iostream>
using namespace std;
////////////////////
static int n;
int *a;
static long total=0;
void output(int s)
{
    int i=1;
    cout<<"n: "<<n<<endl;
    cout<<"a["<<i<<"]: "<< a[i] <<'\t';
    //////////////
    for(i=2; i<=s; i++)
        cout<<"a["<<i<<"]: "<<a[i]<<'\t';
    cout<<endl;
}
/////////////////
int filter(int s)
{
    int i,j;
    if( s==1 )
        return -1;
    for( i=s; i>0; i-- )
        for( j=1; j<i;j++ )
            if( a[i]==a[j] )
                return -1;
        return 0;
}
////////////////////////////////////
void dfs( int d, int low, int rest )
{
   int i;
   if(rest ==0)
   {
       if(filter(d-1)==0)
       {
           total++;
           output(d-1);
       }
   }
   if( low > rest )
   {
       return;
   }
   ///////////////////////
   for( i=low; i<=rest; i++ )
   {
   a[d]=i;
   //cout<<"i: "<<i<<endl;
   dfs(d+1,i, rest-i);
   //cout<<"ii: "<<i<<endl;
   }
}
///////////////////////////////////////
///////////////////////////////////////
int main()
{
  int num;
  cout<<"input the num: ";
  cin>>num;
  /////
  n=num;
  a=new int [n+1];
  //
  dfs(1,1,n);
  cout<<"total: "<<total<<endl;
  cout<<endl;
  delete []a;
  return 0;
}
2009-10-27 13:15
快速回复:将任意正数N分解成多个互不相同的正整数的和,并打印所有可能的组合方 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035739 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved