• 欢迎访问搞代码网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站!
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏搞代码吧

C程序实现整数的素数和分解问题

c语言 搞代码 4年前 (2022-01-06) 32次浏览 已收录 0个评论

这篇文章主要介绍了C程序实现整数的素数和分解问题,对于算法的学习有不错的借鉴价值,需要的朋友可以参考下

本文以实例形式讲述了C程序实现整数的素数和分解问题,分享给大家供大家参考之用。具体方法如下:

要求:对于一个给定的整数,输出所有这种素数的和分解式,对于同构的分解只输出一次(比如5只有一个分解2+3,而3+2是2+3的同构分解式)。

例如:

对于整数8,可以作为如下三种分解:
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5
 
看到此题时,我的头一反应是求解背包问题

思路如下:

f(N, array) = f(N – array[i], array), 保存结果,array是保存里面元素值,即所有素数,参考前面一题,如果素数只能唯一使用一次,那么就建立对应的一个bool数组即可,每使用一次就标记为true,然后递归函数之后需要重新置为false,对于本题不需要如此,但是需要将保存结果的数组除去当前尝试的素数。

代码如下:

 /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include #include #include #include using namespace std; vector res

来源gaodai^.ma#com搞#代!码网

ult; vector prvec; void outputResult(int N, vector &prime, vector &result) { if(N <0) return; if(N == 0) { copy(result.begin(), result.end(), ostream_iterator(cout, " ")); cout << endl; return; } for(int i = 0; i <prime.size(); i++) { //为提高效率,可以在此做个判定条件,尽快返回 if(N - prime[i] <0) break; result.push_back(prime[i]); outputResult(N - prime[i], prime, result); result.pop_back(); } } void outputResult2(int N, vector &prime, vector &result, int position) { if(N <0) return; if(N == 0) { copy(result.begin(), result.end(), ostream_iterator(cout, " ")); cout << endl; return; } for(int i = position; i <prime.size(); i++) { //为提高效率,可以在此做个判定条件,尽快返回 if(N - prime[i] <0) break; result.push_back(prime[i]); outputResult2(N - prime[i], prime, result, i); result.pop_back(); } } bool isPrime(int number) { if(number <= 1) return false; if(number == 2) return true; for(int i = 2; i <number; i++) { if(number % i == 0) return false; } return true; } void generatePrime(int number, vector &result) { for(int i = 2; i <number - 1; i++) { if(isprime(i)) result.push_back(i); } void main() int number=8; generateprime(number, prvec); outputresult(number, prvec, result); cout << "除去同构" endl; outputresult2(number, result, 0);

运行结果如下图所示:

注意:对于同构问题,我是看输出结果之后想到的,outputResult函数中,结果332,这样不对的结果,一个明显的特征是出现3后,其后面的数不能再小于3,那么只需要对保存3当前的position即可,然后在当前position循环,就可以消除同构问题。

相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。

以上就是C程序实现整数的素数和分解问题的详细内容,更多请关注gaodaima搞代码网其它相关文章!


搞代码网(gaodaima.com)提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected],我们会在看到邮件的第一时间内为您处理,或直接联系QQ:872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:C程序实现整数的素数和分解问题

喜欢 (0)
[搞代码]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址