Re: n 取 n 逆時鐘旋轉排列法

// test002.cpp: 定義主控台應用程式的進入點。
//

#include "stdafx.h"
#include <functional>　 // std::function
#include <memory>　　　 // std::shared_ptr
#include <vector>
#include <iostream>
#include <exception>    // exception
#include <stdexcept>    // exception
#include <new>          // exception
#include <typeinfo>     // exception

using namespace std;

//下面是主要改數字的區域，A就是 Cnr 的n， B就是 Cnr 的r。
//可以透過更改A和B的數字來計算Cnr的結果。
//改成A和B變數可以符合國中數學的二元方程式教學以及帕斯卡三角形教學。

#define A 10
#define B 5

//從1開始遞增
int N = 1;
//新增例外類別
const exception* Logic_Error = new exception("Logic_Error");


// n 取 r 做排列
// 採用逆時旋轉排列法
// 必須 n >= r
class Permutation_nPn
{
// 回報結果
function<void(const shared_ptr<vector<unsigned char> > &, size_t)> m_Report;
// 放置要排列的數字
shared_ptr <vector<unsigned char> > m_Digital_Array;
// 要做排列的數目值
size_t m_r;

void v(size_t n, size_t r)
{
size_t i = n + 1;
while (i--)
{
if (r == 0)
m_Report(m_Digital_Array, m_r);
else
v(n - 1, r - 1);
unsigned char tmp = m_Digital_Array->at(n);
for (size_t j = n; j > 0; --j)
m_Digital_Array->at(j) = m_Digital_Array->at(j - 1);
m_Digital_Array->at(0) = tmp;
}
}

public:
Permutation_nPn() {}

Permutation_nPn(const function<void(const shared_ptr<vector<unsigned char> > &,\
 size_t)> &Receive):m_Report(Receive){}

void nPr(size_t n, size_t r)
{
m_r = r;
m_Digital_Array = shared_ptr<vector<unsigned char> >\
(new vector<unsigned char>(n));
size_t i = n;
while (i--)
{
m_Digital_Array->at(i) = i;
}
v(n - 1, r - 1);
}
};

void startmsg()
{
cout << A << "P" << B << "的排列：" << endl;
}

void Show(const shared_ptr<vector<unsigned char> > &Digital_Array, size_t r)
{
cout << N << ":\t";
for (size_t i = Digital_Array->size() - 1; r > 0; --i, --r)
cout << (int)Digital_Array->at(i) << ' ';
cout << endl;
++N;
}

int cnt(int tmp001)
{
int i;
int num001 = 1;
for (i = 0; i < tmp001; i++)
num001 = num001 * (i + 1);
return num001;
}

int cntN(int tmpA, int tmpB)
{
int tmp002;
if (tmpA < tmpB)throw Logic_Error;
try {
int tmpC = cnt(tmpA);
int tmpD = cnt(tmpB);
int tmpE = cnt(tmpA - tmpB);
tmp002 = tmpC / (tmpD*tmpE);

//tmp002 = cnt(tmpA) / cnt(tmpB)*cnt(tmpA - tmpB);//error
}
catch (const exception& e) {
cout << e.what() << endl;
system("PAUSE");
exit(-1);
}
if (tmp002 > 0) {
return tmp002;
}
else { throw Logic_Error; }
}


int main()
{

Permutation_nPn P(Show);

startmsg();
N = 1;


int N2 = cntN(A, B);
int N3 = cnt(B)*N2;

cout << "A=" << A << endl;
cout << "B=" << B << endl;
cout << "N2=" << N2 << endl;
cout << "N3=" << N3 << endl;

if (N3 > 40000) {
cout << "N3組合數字過大，取消顯示，程式結束。" << endl;
//為了方便展示所以取消顯示所有解
system("PAUSE");
exit(-1);
}
cout << "將開始計算，請準備。" << endl;

system("PAUSE");
//主程式
P.nPr(A, B);
//驗算

cout << "A=" << A << endl;
cout << "B=" << B << endl;
cout << "N=" << N << " ( = N3 + 1)" << endl;  // N = N3+1 ，否則就是算錯了
cout << "N2=" << N2 << endl;
cout << "N3=" << N3 << endl;

cout << "計算完成。" << endl;


system("PAUSE");

return 0;
}