| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2037 人关注过本帖
标题:[原创]NKOJ数分解递归实现
只看楼主 加入收藏
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
结帖率:33.33%
收藏
 问题点数:0 回复次数:14 
[原创]NKOJ数分解递归实现
题目描述:
把一个给定的整数分解成若干个素数的和。
Input
一个数。(32位无符号整型数范围内。)

Output
一些素数。

Sample Input
9Sample Output
3 3 3
实现:
#include<stdio.h>
#include<math.h>
int prime(unsigned int n)  //素数判断
{
   unsigned int i;
   int flag=0;  //标志位设为0

   for(i=2;i<=sqrt(double(n))+1;i++)
   {
       if(n==2) { flag=1; break; }
       if(n%i!=0) flag=1;
       else { flag=0; break; }
   }
    if(flag==1) return 1;
    if(flag==0) return 0;
}
void serparte(unsigned int n,int k,int i)  //分解数
{
    if(n%i==0||prime(n))
    {
        k=n-i;
        printf("%d ",i);
        if(prime(k)) printf("%d ",k);
        else
             serparte(k,k,i);
    }
    else
    {
        ++i;
        serparte(n,k,i);
    }
}
int main()
{
    int n,k=0;
    while(scanf("%d",&n)!=EOF)
        serparte(n,k,2);
    return 0;
}
搜索更多相关主题的帖子: NKOJ 递归 分解 
2008-01-07 20:05
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
在来个非递归的:
#include<stdio.h>
#include<math.h>
int prime(unsigned int n)  //素数判断
{
   unsigned int i;
   int flag=0;  //标志位设为0

   for(i=2;i<=sqrt(double(n))+1;i++)
   {
       if(n==2) { flag=1; break; }
       if(n%i!=0) flag=1;
       else { flag=0; break; }
   }
    if(flag==1) return 1;
    if(flag==0) return 0;
}
void serparte(unsigned int n)  //分解数
{
    int i;
    for(i=2;;)
    {
        if(n%i==0||prime(n))
        {
            n=n-i;
            printf("%d ",i);
            if(prime(n))
            {
                printf("%d ",n);
                break;
            }
            else continue;
        }
        else
        {    ++i;  }
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
        serparte(n);
    return 0;
}
时间还是慢~

樱花大战,  有爱.
2008-01-07 20:21
zbqf109
Rank: 1
等 级:新手上路
帖 子:289
专家分:0
注 册:2006-12-31
收藏
得分:0 
没有考虑 9 = 7 + 2 或者 5 + 2 + 2 等情况?

坚决不跟用TC的人打交道!
2008-01-07 21:26
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
把一个给定的整数分解成若干个素数的和。

如果可以我直接给分成若干个2和1/0个3.

倚天照海花无数,流水高山心自知。
2008-01-07 21:34
zbqf109
Rank: 1
等 级:新手上路
帖 子:289
专家分:0
注 册:2006-12-31
收藏
得分:0 
回复 4# 的帖子
其实应该说若干个 2 和 0/1 个 3/5/7/11/…

坚决不跟用TC的人打交道!
2008-01-07 21:39
forever74
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:CC
等 级:版主
威 望:58
帖 子:1688
专家分:4262
注 册:2007-12-27
收藏
得分:0 
是啊,题目有点松了,要说分解成最少个素数还凑合。
2008-01-07 21:39
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
原帖由 [bold][underline]zbqf109[/underline][/bold] 于 2008-1-7 21:39 发表 [url=http://bbs.][/url]
其实应该说若干个 2 和 0/1 个 3/5/7/11/…


完全不需要3后面的数.

倚天照海花无数,流水高山心自知。
2008-01-07 22:04
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
呵呵,对了,,,谢谢nuciewth的提醒......从5开始都可以被2,3分解了/////

樱花大战,  有爱.
2008-01-07 22:15
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
回复 8# 的帖子
是从2开始
2008-01-07 23:36
中学者
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:20
帖 子:3554
专家分:80
注 册:2007-9-14
收藏
得分:0 
1是不是素数好像又争议~

樱花大战,  有爱.
2008-01-07 23:39
快速回复:[原创]NKOJ数分解递归实现
数据加载中...
 
   



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

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