C程序?qū)崿F(xiàn)整數(shù)的素數(shù)和分解問題

更新時間：2014年09月17日 11:05:39 投稿：shichen2014

這篇文章主要介紹了C程序?qū)崿F(xiàn)整數(shù)的素數(shù)和分解問題,對于算法的學(xué)習(xí)有不錯的借鑒價值,需要的朋友可以參考下

本文以實(shí)例形式講述了C程序?qū)崿F(xiàn)整數(shù)的素數(shù)和分解問題，分享給大家供大家參考之用。具體方法如下：

要求：對于一個給定的整數(shù)，輸出所有這種素數(shù)的和分解式，對于同構(gòu)的分解只輸出一次(比如5只有一個分解2+3，而3+2是2+3的同構(gòu)分解式)。

例如：

對于整數(shù)8，可以作為如下三種分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

看到此題時，我的頭一反應(yīng)是求解背包問題

思路如下：

f(N, array) = f(N - array[i], array), 保存結(jié)果，array是保存里面元素值，即所有素數(shù)，參考前面一題，如果素數(shù)只能唯一使用一次，那么就建立對應(yīng)的一個bool數(shù)組即可，每使用一次就標(biāo)記為true，然后遞歸函數(shù)之后需要重新置為false，對于本題不需要如此，但是需要將保存結(jié)果的數(shù)組除去當(dāng)前嘗試的素數(shù)。

代碼如下：

/*  
* 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 << "除去同構(gòu)" << endl;
 outputResult2(number, prvec, result, 0);
}

運(yùn)行結(jié)果如下圖所示：

注意：對于同構(gòu)問題，我是看輸出結(jié)果之后想到的，outputResult函數(shù)中，結(jié)果332，這樣不對的結(jié)果，一個明顯的特征是出現(xiàn)3后，其后面的數(shù)不能再小于3，那么只需要對保存3當(dāng)前的position即可，然后在當(dāng)前position循環(huán)，就可以消除同構(gòu)問題。

相信本文所述對大家C程序算法設(shè)計的學(xué)習(xí)有一定的借鑒價值。

您可能感興趣的文章: