本文以实例形式讲述了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，对于本题不需要如此，但是需要将保存结果的数组除去当前尝试的素数。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
/* * Copyright (c) 2011 alexingcool. All Rights Reserved. */#include <iostream>#include <iterator>#include <algorithm>#include <vector>using namespace std;vector<int> result;vector<int> prvec;void outputResult(int N, vector<int> &prime, vector<int> &result){ if(N < 0) return; if(N == 0) { copy(result.begin(), result.end(), ostream_iterator<int>(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<int> &prime, vector<int> &result, int position){ if(N < 0) return; if(N == 0) { copy(result.begin(), result.end(), ostream_iterator<int>(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<int> &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, prvec, result, 0);} |
运行结果如下图所示：
注意：对于同构问题，我是看输出结果之后想到的，outputResult函数中，结果332，这样不对的结果，一个明显的特征是出现3后，其后面的数不能再小于3，那么只需要对保存3当前的position即可，然后在当前position循环，就可以消除同构问题。
相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。
