C法式完成整數的素數和分化成績

C法式完成整數的素數和分化成績。本站提示廣大學習愛好者：（C法式完成整數的素數和分化成績）文章只能為提供參考，不一定能成為您想要的結果。以下是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 <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法式算法設計的進修有必定的自創價值。