討論區快速選單
知識庫快速選單
沒有人比Cloudera更了解大數據 政府補助!學嵌入式+物聯網
[ 回上頁 ] [ 討論區發言規則 ]
(教學)Visual C++ 2005程式設計:如何應用Auto Number Generator現
更改我的閱讀文章字型大小
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2014/12/9 上午 06:06:56
auto Number Generator Electronic List應用方式說明
Joey Chan製作
版本:Visual C++ 2005以上都可以使用

自動號碼產生器是一項超越時代的程式,
這裡A4element已經完全電腦化,
不需要用紙,不需要人力,也不需要印表機。
想想看可以在工業界節省多少費用。
為了要應用這一個好用的程式碼,
筆者特別開發了幾個範例程式,
比如說這兩天比較多人討論的捷運站問題,
可以利用這個產生器做初步的路線計算跟評估,
非常方便。
歡迎各種公司行號利用本程式所提到的程式技術,
應用開發更高層次工業化的程式,
拼經濟救台灣。

程式碼的網址:
http://joeymovieyoutube.blogspot.tw/2014/12/visual-c-2005auto-number-generator.html


使用方式:
1.
使用Visual C++ 2005建立一個WIN32主控台應用程式,
命名為"ANG_Example01",
這時候編譯器會自動生成空白檔案"ANG_Example01.cpp"和正常的"stdafx.h",
並且新增一個空白標頭檔,名為
"arrays.h"
然後把下面相同名稱的"ANG_Example01.cpp"和"arrays.h"的檔案內容,
拷貝貼上到相同名稱的空白檔案裡面。

並且要整理程式碼換行的部份,
讓不該換行的程式碼不要換行,
就可以讓程式碼正確執行了。

2.新增程式碼部份
#define DELAYTIME 1500
這裡定義了每次顯示捷運站數字的間隔時間,
預設值1500是1.5秒的間隔。
如果調大這個數字就可以讓畫面更換的比較慢一點。

3.預設參數可以計算1到10的捷運路線數量,
最大值雖然可以調整到10,但是數字會跳的非常慢,
可能要好幾個星期才會顯示完。
使用路線數字10的時候第10號捷運路線會以0號路線顯示。
如果要增加到10以上的數字就要加大switch case敘述,
工作量其實是非常龐大的,
提供給各位做為參考。
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2014/12/23 下午 01:05:04
如何應用auto Number Generator現有的程式碼
2014/12/23
新版程式碼已經公布,

使用方式:
使用Visual C++ 2005建立一個WIN32主控台應用程式,
命名為"ANG_Example03",
這時候編譯器會自動生成空白檔案"ANG_Example03.cpp"和正常的"stdafx.h",
並且新增一個空白標頭檔,名為
"arrays.h"
然後把下面相同名稱的"ANG_Example03.cpp"和"arrays.h"的檔案內容,
拷貝貼上到相同名稱的空白檔案裡面。

並且要整理程式碼換行的部份,
讓不該換行的程式碼不要換行,
就可以讓程式碼正確執行了。

程式碼網址:
http://joeymovieyoutube.blogspot.tw/2014/12/visual-c-2005-auto-number-generator_21.html
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2014/12/23 下午 02:18:53
我提供一下資料來源:
這個程式實作的遞迴部份程式碼,
可以參考 金禾資訊 吳燦銘先生 資料結構使用C++ 4-2-4 八皇后問題
arrays.h則是來自 charles river media書店,
Allen Sherrod先生的
Data Structure and Algorithms for Game Developers.
這些都是已公開的教學用程式碼,
實作程式碼只要把MyErrorHandler的#pragma關掉的敘述寫到程式裡面,
就可以正確的在電腦執行。
利用現有的教科書open source程式碼,
就可以完成auto Number Generator的實作了。

資料來源:
金禾資訊 吳燦銘先生 資料結構使用C++ , ISBN 9789861492575
Allen Sherrod先生 Data Structure and Algorithms for Game Developers ISBN-10 1584504951
僅此致謝,
希望工業化以後,
2014版可以推出更進步的VC++教科書。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/10 下午 04:41:11
你這叫排列組合產生器比較適當吧,有沒有辦法把功能抽離出來做成 class,和範例混在一起看起來有點頭痛
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/10 下午 10:06:16
首先要說的是,
這個程式沒有辦法寫得更簡單了,
因為Visual C++ 2005的C++/CLI新規格,
使得程式碼最少要寫這麼多才能通過編譯。
歡迎大家提出更多版本讓它變簡單一點。

這個程式確實可以應用到排列組合上面,
但是最棒的是ANG_prototype.cpp編譯成程式執行檔以後,
用最大值計算十階乘的排列組合估計要十八天以上才能計算完成,
如果用系統管理員執行程式,
就可以生成排列組合數字的檔案:
autoNumberGeneratorElectronicList.txt
是一個文字檔,可以直接讀取,
直接讀取這個文字檔可以利用到更多的用途上面。
就不用每次電腦開機都要算十八天。
所以它也算是一個規模很大的計算程式。
在一般的PC電腦,讀取這個文字檔案會LAG,
這是因為現在的PC電腦沒有達到工業電腦的晶片等級,
所以速度很慢。

我曾經嘗試過把這個程式改寫成為class不過並沒有寫成,
由於遞迴呼叫必須要傳遞參數,
所以不能設定成私有的class,
而必須用公開的函數進行運算。
如果要編寫class就必須重新寫一個程式,
利用fopen來依序讀取
生成好的autoNumberGeneratorElectronicList.txt,
這樣就可以完成程式的封裝,
不必每次開機都要算十八天以上要很久。

ANG_Example03.cpp範例程式碼在這個網址,
http://joeymovieyoutube.blogspot.tw/2014/12/visual-c-2005-auto-number-

generator_21.html

另外,
稍早的ANG_Prototype.cpp目前則是在這個網址,

http://joeymovieyoutube.blogspot.tw/2014_11_01_archive.html

只要分別拷貝貼上arrays.h ,ANG_Prototype.cpp,和基本的stdafx.h
再把程式碼換行的部分整理一下,
讓不該換行的程式碼不要換行,
就可以正確的執行了,
版本是Visual C++ 2005以上都可以使用。

順便廣告一下ACE Online影片的連結現在的網址:
http://joeymovieyoutube.blogspot.tw/2013/01/ace-online.html

最後,如果有高手能把這個程式寫成class也歡迎貼到板上來分享,
謝謝。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/11 下午 10:39:03
這個 class 應可達到你的須求,你試試看

#include <iostream>
#include <iomanip>
#include <list>
#include <vector>

using namespace std;

/*
 不重覆選取排列
*/
template <typename T>
class Permutation
{
 int m_Quantity; // 要排列的數量
 list<const T*> m_Samples; // 要排列的樣本
 vector<const T*> m_Package; // 作為輸出的容器

 template <typename Fn>
 void Pick(int Level,Fn &Export)
 {
  if(Level == 0)
   Export((const vector<const T*> &)m_Package);

  int n = m_Samples.size();
  while(n)
  {
   m_Package.push_back(m_Samples.front());
   m_Samples.pop_front();
   Pick(Level-1,Export);
   m_Samples.push_back(m_Package.back());
   m_Package.pop_back();
   --n;
  }
 }

public:
 // Constructor
 // n = 要排列的數量
 Permutation(int n)
 {
  m_Quantity = n;
 }

 // Destructor
 ~Permutation()
 {
 }

 // 放入要排序的樣本,數量須大於或等於建構時所定義
 void Add(const T *Obj)
 {
  m_Samples.push_back(Obj);
 }

 // Export 為回叫函數 或 函數物件
 // 函數格式為 Export(const vector<const int*> &Package)
 // 樣本不足夠排列回覆 false,且不會由回叫函數匯出任何資料
 template <typename Fn>
 bool Start(Fn &Export)
 {
  if(m_Samples.size() < m_Quantity)
   return false;

  Pick(m_Quantity,Export);
  return true;
 }
};

// 作為 Permutation 匯出用的回叫函數
void Show(const vector<const int*> &Package)
{
 const int tmp = *Package.operator [](0);

 cout << *Package[0] << ' '
    << *Package[1] << ' '
    << *Package[2] << ' '
    << *Package[3] << ' '
    << *Package[4] << endl;
}

int main(int argc, char* argv[])
{
 int Num[] = {0,11,22,33,44,55,66,77,88,99};

 Permutation<int> P(5); // 取 5 個數字排列
 P.Add(&Num[0]);
 P.Add(&Num[1]);
 P.Add(&Num[2]);
 P.Add(&Num[3]);
 P.Add(&Num[4]);
 P.Add(&Num[5]);
 P.Add(&Num[6]);
 P.Add(&Num[7]);
 P.Add(&Num[8]);
 P.Add(&Num[9]);

 P.Start(Show);

 return 0;
}

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 上午 01:44:21


>
> // Export 為回叫函數 或 函數物件
> // 函數格式為 Export(const vector<const int*> &Package)


這一段改一下

函數格式為 Export(const vector<const T*> &Package)
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 上午 11:41:48
>const int tmp = *Package.operator [](0);

用意是?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 下午 02:23:02

>>const int tmp = *Package.operator [](0);
>
>用意是?

抱歉,忘了刪,本來函數是宣告成 void Show(const vector<const int&> &Package),
但卻無法這樣 Package[0] 取出物件(用 vs2008 編譯),我在那抓 bug
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 下午 02:30:42
改了一些地方,速度也變快了,我重貼一次

#include <iostream>
#include <list>
#include <vector>

using namespace std;

/*
 不重覆選取排列
*/
template <typename T>
class Permutation
{
 int m_Quantity; // 要排列的數量
 list<const T*> m_Samples; // 要排列的樣本
 vector<const T*> m_Package; // 作為輸出的容器

 template <typename Fn>
 void Pick(int Level,Fn &Export)
 {
  if(Level == 0)
  {
   Export((const vector<const T*> &)m_Package);
   return;
  }

  int n = m_Samples.size();
  while(n)
  {
   m_Package.push_back(m_Samples.front());
   m_Samples.pop_front();
   Pick(Level-1,Export);
   m_Samples.push_back(m_Package.back());
   m_Package.pop_back();
   --n;
  }
 }

public:
 // Constructor
 // n = 要排列的數量
 Permutation(int n)
 {
  m_Quantity = n;
 }

 // Destructor
 ~Permutation()
 {
 }

 // 放入要排序的樣本,數量須大於或等於建構時所定義
 void Add(const T *Obj)
 {
  m_Samples.push_back(Obj);
 }

 // Export 為回叫函數 或 函數物件
 // 函數格式為 void(const vector<const T*> &)
 // 其中 T 為樣本形別
 // 樣本不足夠排列回覆 false,且不會由回叫函數匯出任何資料
 template <typename Fn>
 bool Start(Fn &Export)
 {
  if(m_Samples.size() < m_Quantity)
   return false;

  Pick(m_Quantity,Export);
  return true;
 }
};

// 作為 Permutation 匯出用的回叫函數
void Show(const vector<const int*> &Package)
{
 cout << *Package[0] << ' '
    << *Package[1] << ' '
    << *Package[2] << ' '
    << *Package[3] << ' '
    << *Package[4] << endl;
}

int main(int argc, char* argv[])
{
 int Num[] = {0,11,22,33,44,55,66,77,88,99};

 Permutation<int> P(5); // 取 5 個數字排列
 P.Add(&Num[0]);
 P.Add(&Num[1]);
 P.Add(&Num[2]);
 P.Add(&Num[3]);
 P.Add(&Num[4]);
 P.Add(&Num[5]);
 P.Add(&Num[6]);
 P.Add(&Num[7]);
 P.Add(&Num[8]);
 P.Add(&Num[9]);

 P.Start(Show);

 return 0;
}



作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 下午 05:37:02
修完整一點,範例多了物件樣本和函數物件示範

#include <iostream>
#include <list>
#include <vector>

using namespace std;

/*
 不重覆選取樣本的排列演算法
 T 可以是一般形別或物件類別
*/
template <typename T>
class Permutation
{
 unsigned int m_Quantity; // 要排列的數量
 list<const T*> m_Samples; // 要排列的樣本
 vector<const T*> m_Package; // 作為輸出的容器

 template <typename Fn>
 void Pick(unsigned int Level,Fn &Export)
 {
  if(Level == 0)
  {
   Export((const vector<const T*> &)m_Package);
   return;
  }

  unsigned int n = m_Samples.size();
  while(n)
  {
   m_Package.push_back(m_Samples.front());
   m_Samples.pop_front();
   Pick(Level-1,Export);
   m_Samples.push_back(m_Package.back());
   m_Package.pop_back();
   --n;
  }
 }

public:
 // Constructor
 // n = 要排列的數量
 Permutation(unsigned int n)
 {
  m_Quantity = n;
 }

 // Destructor
 ~Permutation()
 {
 }

 // 放入要排列的樣本,數量須大於或等於建構時所定義
 void Add(const T *Obj)
 {
  m_Samples.push_back(Obj);
 }

 // Export 為回叫函數 或 函數物件
 // 函數格式為 void(const vector<const T*> &)
 // 其中 T 為樣本形別
 // 樣本不足夠排列回覆 false,且不會由回叫函數匯出任何資料
 template <typename Fn>
 bool Start(Fn &Export)
 {
  if(m_Samples.size() < m_Quantity)
   return false;

  Pick(m_Quantity,Export);
  return true;
 }
};

// 作為 Permutation 匯出用的回叫函數
void Show(const vector<const int*> &Package)
{
 cout << *Package[0] << ' '
    << *Package[1] << ' '
    << *Package[2] << ' '
    << *Package[3] << ' '
    << *Package[4] << endl;
}

// 要作為排列的物件樣本
class A
{
 string m_Str;
public:
 A(const string &Str)
 {
  m_Str = Str;
 }
 ~A()
 {
 }
 void ShowStr() const
 {
  cout << m_Str.c_str();
 }
};

// 作為 Permutation 匯出用的回叫函數物件
class Show2
{
public:
 // Constructor
 Show2(){}
 // Destructor
 ~Show2(){}

 // 作為 Permutation 匯出用的回叫函數
 void operator()(const vector<const A*> &Package)
 {
  for(int n = 0; n < 5; ++n)
   Package[n]->ShowStr();

  cout << endl;
 }
};

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 下午 05:37:29
int main(int argc, char* argv[])
{
 int Num[] = {0,11,22,33,44,55,66,77,88,99};

 Permutation<int> P(5); // 取 5 個數字排列
 P.Add(&Num[0]);
 P.Add(&Num[1]);
 P.Add(&Num[2]);
 P.Add(&Num[3]);
 P.Add(&Num[4]);
 P.Add(&Num[5]);
 P.Add(&Num[6]);
 P.Add(&Num[7]);
 P.Add(&Num[8]);
 P.Add(&Num[9]);

 P.Start(Show);


 A *pAarray[10]; // 存放物件樣本

 Permutation<A> P2(5); // 取 5 個物件排列
 pAarray[0] = new A("零"); P2.Add(pAarray[0]);
 pAarray[1] = new A("壹"); P2.Add(pAarray[1]);
 pAarray[2] = new A("貳"); P2.Add(pAarray[2]);
 pAarray[3] = new A("參"); P2.Add(pAarray[3]);
 pAarray[4] = new A("肆"); P2.Add(pAarray[4]);
 pAarray[5] = new A("伍"); P2.Add(pAarray[5]);
 pAarray[6] = new A("陸"); P2.Add(pAarray[6]);
 pAarray[7] = new A("柒"); P2.Add(pAarray[7]);
 pAarray[8] = new A("捌"); P2.Add(pAarray[8]);
 pAarray[9] = new A("玖"); P2.Add(pAarray[9]);

 P2.Start(Show2());

 for(int n = 0; n < 10; ++n)
  delete pAarray[n];

 return 0;
}
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/12 下午 10:16:56
Permutation::Pick 用 recursion 的邏輯. 一般來說, 相較於 loop, recursion 會比較慢, 會使用更多的系統資源;

最重要的是: 因為你無法知道並控制 recursion 能夠進入的深度, 所以同樣的 recursion 程式碼, 在不同編譯器, 不同平台會有不同的表現: 在某些編譯器/平台能夠執行到底, 但在另一個編譯器/平台上也許會執行錯誤 (stack overflow); 而且這個錯誤是無法預測, 無法抓捕, 也無法恢復.

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 上午 01:48:48
loop 版做好了,但也只是用一個容器來代替 stack 保存變數值,雖然遞迴還要保存其他東西 stack 會用掉更多。但就邏輯設計而言也只是換湯不換藥,而且還要摸擬遞迴控制,寫得辛苦看得痛苦


/*
 不重覆選取樣本的排列演算法
 T 可以是一般形別或物件類別
*/
template <typename T>
class Permutation
{
 unsigned int m_Quantity; // 要排列的數量
 list<const T*> m_Samples; // 要排列的樣本
 vector<const T*> m_Package; // 作為輸出的容器

 // 代替遞迴的 loop 版,其實也只能摸擬遞迴,因為
 vector<const int> n_stack; // 須保存遞迴版中那個 n
 template <typename Fn>
 void Pick(unsigned int Level,Fn &Export)
 {
  unsigned int L = 1;
  bool up = true;
  while(true)
  {
   if(L == Level)
   {
    for(unsigned int n = m_Samples.size(); n > 0; --n)
    {
     m_Package.push_back(m_Samples.front());
     m_Samples.pop_front();
     Export((const vector<const T*> &)m_Package);
     m_Samples.push_back(m_Package.back());
     m_Package.pop_back();
    }
    --L;
    up = false;
   }
   else if(L == 0)
   {
    return;
   }
   else
   {
    if(up)
    {
     n_stack.push_back(m_Samples.size());
     m_Package.push_back(m_Samples.front());
     m_Samples.pop_front();
     ++L;
    }
    else
    {
     unsigned int n = n_stack.back() - 1;
     n_stack.pop_back();
     m_Samples.push_back(m_Package.back());
     m_Package.pop_back();
     if(n > 0)
     {
      n_stack.push_back(n);
      m_Package.push_back(m_Samples.front());
      m_Samples.pop_front();
      ++L;
      up = true;
     }
     else
     {
      --L;
     }
    }
   }
  }
 }

public:
 // Constructor
 // n = 要排列的數量
 Permutation(unsigned int n)
 {
  m_Quantity = n;
 }

 // Destructor
 ~Permutation()
 {
 }

 // 放入要排列的樣本,數量須大於或等於建構時所定義
 void Add(const T *Obj)
 {
  m_Samples.push_back(Obj);
 }

 // Export 為回叫函數 或 函數物件
 // 函數格式為 void(const vector<const T*> &)
 // 其中 T 為樣本形別
 // 樣本不足夠排列回覆 false,且不會由回叫函數匯出任何資料
 template <typename Fn>
 bool Start(Fn &Export)
 {
  if(m_Quantity == 0 || m_Samples.size() < m_Quantity)
   return false;

  Pick(m_Quantity,Export);
  return true;
 }
};
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 上午 02:33:50
我有個問題,排列比較好寫,組合要怎麼寫?
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 上午 10:17:23
組合一般來說會比排列的數量要少,
初步的計畫是在遞迴算出結果以後,
利用幾個迴圈核對重複的部分,
把出現兩次以上的重覆結果部分pop掉就可以了。
同時計算刪掉的個數。
我當時的程式碼有用到UnorderedArray這個教科書的類別,
所以可以使用pop功能。
你可以參考使用,
或是改用VC++2014 2015新的程式碼都可以。

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 上午 11:40:07

>組合一般來說會比排列的數量要少,
>初步的計畫是在遞迴算出結果以後,
>利用幾個迴圈核對重複的部分,
>把出現兩次以上的重覆結果部分pop掉就可以了。

我初步的想法是保持取樣的順序,不要發生左邊右邊反轉的情況,應可避掉重覆的結果,不碓定這樣做是否完美
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 下午 01:44:50
以五個號碼做個例子說明:

比方說迴圈現在跑到要計算
13524 35241 52413 24135 41352 這五個排列,
只能算是"13524"的同一個組合。
所以要先有一個迴圈計算出13524這五個排列,
接下來做一個迴圈
搜尋找出13524 35241 52413 24135 41352這五個排列在全部答案的哪幾個位置,
最後pop掉重複的35241 52413 24135 41352這四個資料,就完成了一次計算。
接著,次數i++,再進行下一個不同排列的pop運算。
所以如果要算組合的話,
陣列最好要有pop的功能會比較好用。
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 下午 01:59:37
難怪每次開機都要算十八天以上.......
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 下午 02:06:30
>13524 35241 52413 24135 41352
>只能算是"13524"的同一個組合。
按照高中教材,或許應該說是"13524"的同一個環狀排列。
對了,組合跟環狀排列的解法是不同的,
這部分可以去請教建中的同學會比較清楚,
這部分是高中數學的教材。
我剛剛說明的應該是環狀排列的算法,
不是組合的算法。
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/13 下午 02:52:55
再舉個例子:
1,2,3,4,5一共有五個球,其中選出n個球,n<5,
這時候就叫做5中取n的組合。
例如5個球中間選出2個球,n=2,
就有下列解法:
(12)(23)(34)(45)(15)(13)(14)(24)(25)(35)共十組。
這時候並不會用到1,2,3,4,5的所有排列解法。
預計要用的是迴圈跟汽泡排序法。

真正會用到1,2,3,4,5排列解法的是像之前說的環狀排列,
13524 35241 52431 24135 41352這樣五個環狀排列才算是同一組。
這時候才要預計寫幾個迴圈來pop掉重複的資料。

所以這兩種情況的處理方式是不同的,
依照我國的教科書要把它當成不同的題目來處理才對。


作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 上午 04:26:21
12345 不重複選取 3 個做組合,有 10 種組合方法,保持順序選取就可做到,我有空再寫看看,還是有人要出來寫
123
124
125
134
135
145
234
235
245
345
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 上午 09:01:22
[參考資料: https://msdn.microsoft.com/en-us/library/aa289166.aspx]
組合程式. 程式用了一些 C++11 的語法如 auto, 編譯器如不支援自己轉成 std::vector<T>::const_iterator.
因為用的是內建類型, 計算會有上限, unsigned long long 應該可以到 64C32, 再大就 overflow 了.

[code: C++11]
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

template <typename T> std::ostream& operator <<(std::ostream& os, const std::vector<T>& vt)
{
    os << "{ ";
    for (auto cit = vt.cbegin(); cit != vt.cend(); ++cit)
    {
     os << *cit << ' ';
    }
    os << "}";
    return os;
}

namespace combination
{
    unsigned long long choose(const size_t n, const size_t r)
    {
     if (n < r)
     return 0;
     else if (n == r)
     return 1;

     // choose(100, 97) ==> choose(100, 3)
     size_t k2 = (r < n - r) ? r : n - r;

     // n * (n-1) * (n-2) ... (n-k2+1)
     // -------------------------------
     // 1 * 2 * ... k2
     unsigned long long ans = n;
     for (size_t i = 2; i <= k2; ++i)
     {
     ans = (ans * (n - i + 1))/i;
     }
     return ans;
    }

    size_t LargestV(size_t a, size_t b, unsigned long long x)
    {
     long v = a - 1;
     while (choose(v, b) > x)
     --v;
     return v;
    }

    void GetMthElement(const size_t n, const size_t r, unsigned long long m, std::vector<size_t>& result)
    {
     result.resize(r);
     size_t a = n;
     size_t b = r;
     unsigned long long x = (choose(n, r) - 1) - m;
     for (size_t i = 0; i < r; ++i)
     {
     result[i] = LargestV(a, b, x);
     x = x - choose(result[i], b);
     a = result[i];
     b = b - 1;
     }
     for (size_t i = 0; i < r; ++i)
     {
     result[i] = n - result[i];
     }
    }

    void C(const size_t n, const size_t r)
    {
     std::vector<size_t> result(r);
     const unsigned long long mMax = choose(n, r);
     for (unsigned long long m = 0; m < mMax; ++m)
     {
     GetMthElement(n, r, m, result);
     std::cout << std::setw(10) << m+1 << ": " << result << std::endl;
     }
    }
}

int main()
{
    size_t n, r;
    std::cout << "Calculate nCr" << std::endl;
    while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
    {
     combination::C(n, r);
    }
}
[/code: C++11]

[執行:]
Calculate nCr
Enter n r? 5 3
     1: { 1 2 3 }
     2: { 1 2 4 }
     3: { 1 2 5 }
     4: { 1 3 4 }
     5: { 1 3 5 }
     6: { 1 4 5 }
     7: { 2 3 4 }
     8: { 2 3 5 }
     9: { 2 4 5 }
     10: { 3 4 5 }
Enter n r?
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 上午 09:20:18
同樣程式, 不過是用 Python 寫的. Python 的整數的精確度理論上無限, 試過 c(100,50) 似乎沒有問題, 說「似乎」是因為沒有輸出所有的組合, 有興趣的可以把程式稍改一下, 用 GetMthElement() 的 'm' 來控制要輸出那一個組合.
[code: python 3.4.2]
def choose(n, r):
    if (n < r):
     return 0
    elif (n == r):
     return 1

    if (r < n - r):
     k2 = r
    else:
     k2 = n - r
    
    ans = n
    for i in range(2, k2+1):
     ans = (ans * (n - i + 1))//i
    
    return ans

def largestV(a, b, x):
    v = a - 1
    while (choose(v, b) > x):
     v = v-1
    return v

def GetMthElement(n, r, m):
    a = n
    b = r
    x = (choose(n, r) - 1) - m
    result = []
    for i in range(0, r):
     result.append(largestV(a, b, x))
     x = x - choose(result[i], b)
     a = result[i]
     b = b - 1
    for i in range(0, r):
     result[i] = n - result[i]
    return result

def c(n, r):
    nMax = int(choose(n, r))
    for m in range(nMax):
     print('{0:10d} {1} {2}'.format(m+1, ": ", GetMthElement(n, r, m)))
 [/code: python 3.4.2]

執行結果:
>>> import combination
>>> combination.c(5, 3)
     1 : [1, 2, 3]
     2 : [1, 2, 4]
     3 : [1, 2, 5]
     4 : [1, 3, 4]
     5 : [1, 3, 5]
     6 : [1, 4, 5]
     7 : [2, 3, 4]
     8 : [2, 3, 5]
     9 : [2, 4, 5]
     10 : [3, 4, 5]
>>>
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 下午 01:47:21
R大這招厲害,直接指定,經由計算直接定位,要得到全都就全指定就有了,也不必使用遞迴,我找時間排列的部份也改一改
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 下午 11:26:51
Permutation 的 C++ 程式碼, 配合之前的 combination, 就可以打出 nPr 所有組合的排列. NextPermutation() 的邏輯參考 http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order.
[code: C++]
#include <algorithm>
#include <iterator>
namespace permutation
{
    bool NextPermutation(std::vector<size_t>& result)
    {
     if (result.size() < 2)
     return false;

     size_t k = result.size() - 2;
     while (k != 0 && result[k] >= result[k+1])
     {
     --k;
     }
     if (k == 0 && result[k] >= result[k+1])
     return false;

     size_t l = result.size() - 1;
     while (l > k && result[k] >= result[l])
     {
     --l;
     }
     std::swap(result[k], result[l]);
     std::reverse(result.begin() + k + 1, result.end());
     return true;
    }

    void P(const size_t n, const size_t r)
    {
     std::vector<size_t> result(r);
     const unsigned long long mMax = combination::choose(n, r);
     for (unsigned long long line = 1, m = 0; m < mMax; ++m)
     {
     combination::GetMthElement(n, r, m, result);
     do
     {
     std::cout << std::setw(10) << line++ << ": " << result << std::endl;
     } while (NextPermutation(result));
     }
    }
}

int main()
{
    size_t n, r;
    std::cout << "Calculate nPr" << std::endl;
    while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
    {
     permutation::P(n, r);
    }
}
[/code: C++]

[執行:]
Enter n r? 4 3
     1: { 1 2 3 }
     2: { 1 3 2 }
     3: { 2 1 3 }
     4: { 2 3 1 }
     5: { 3 1 2 }
     6: { 3 2 1 }
     7: { 1 2 4 }
     8: { 1 4 2 }
     9: { 2 1 4 }
     10: { 2 4 1 }
     11: { 4 1 2 }
     12: { 4 2 1 }
     13: { 1 3 4 }
     14: { 1 4 3 }
     15: { 3 1 4 }
     16: { 3 4 1 }
     17: { 4 1 3 }
     18: { 4 3 1 }
     19: { 2 3 4 }
     20: { 2 4 3 }
     21: { 3 2 4 }
     22: { 3 4 2 }
     23: { 4 2 3 }
     24: { 4 3 2 }
Enter n r?

作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/14 下午 11:30:05
Python 的程式碼:
[Python 3.4.2]
import combination
def NextPermutation(ary):
    k = len(ary) - 2
    while k >= 0 and ary[k] >= ary[k+1]:
     k -= 1
    if k < 0:
     return false;

    l = len(ary) - 1
    while ary[k] >= ary[l]:
     l -= 1

    ary[k], ary[l] = ary[l], ary[k]
    ary[k+1:] = ary[len(ary)-1 : k : -1]
    return true

def p(n, r):
    nMax = int(combination.choose(n, r))
    line = 1
    for m in range(nMax):
     ary = combination.GetMthElement(n, r, m)
     while true:
     print('{0:10d} {1} {2}'.format(line, ": ", ary))
     line += 1
     if NextPermutation(ary) == false:
     break
 [/Python 3.4.2]

[執行結果]
>>> import permutation
>>> permutation.p(4, 3)
     1 : [1, 2, 3]
     2 : [1, 3, 2]
     3 : [2, 1, 3]
     4 : [2, 3, 1]
     5 : [3, 1, 2]
     6 : [3, 2, 1]
     7 : [1, 2, 4]
     8 : [1, 4, 2]
     9 : [2, 1, 4]
     10 : [2, 4, 1]
     11 : [4, 1, 2]
     12 : [4, 2, 1]
     13 : [1, 3, 4]
     14 : [1, 4, 3]
     15 : [3, 1, 4]
     16 : [3, 4, 1]
     17 : [4, 1, 3]
     18 : [4, 3, 1]
     19 : [2, 3, 4]
     20 : [2, 4, 3]
     21 : [3, 2, 4]
     22 : [3, 4, 2]
     23 : [4, 2, 3]
     24 : [4, 3, 2]
>>>
[/執行結果]
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/15 下午 10:37:25
感謝大大的分享!
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/16 上午 04:07:47
R大这招计算法有一个大的问题,因为没像递迴法会为每一个选取的位置準备一个计数,所以每次要得到一组组合都得为每一个位置计算一次,可以想见要选取的数量越大速度越慢,用时间换取空间,由一个问题换成另一个问题,还有第三种解决办法吗?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/16 上午 10:08:07
不过计算法因各组的求解可独立运算,因此很适合平行处理,可多个 CPU 或多台电脑加速运算,这算是这方法最大的优点
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/17 上午 10:56:49
要快的話 這樣最快了 一步也沒多走 只是寫死就是了

#define QUANTITY 5

int i, j, k;
for (i=0; i<(QUANTITY-2); i++)
{
  for (j=i+1; j<(QUANTITY-1); j++)
  {
    for (k=j+1; k<QUANTITY; k++)
    {
     cout << Num[i] << " " << Num[j] << " " << Num[k] << endl;
    }
  }
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/17 下午 05:03:27

>要快的話 這樣最快了 一步也沒多走 只是寫死就是了

100 萬選 1 萬來排,你要怎麼寫
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/17 下午 06:43:14

>
>>要快的話 這樣最快了 一步也沒多走 只是寫死就是了
>
>100 萬選 1 萬來排,你要怎麼寫

C++ 的巨集有沒有提供 loop 功能的?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/18 上午 09:33:40

>要快的話 這樣最快了 一步也沒多走 只是寫死就是了
>
>#define QUANTITY 5
>
>int i, j, k;
>for (i=0; i<(QUANTITY-2); i++)
>{
> for (j=i+1; j<(QUANTITY-1); j++)
> {
> for (k=j+1; k<QUANTITY; k++)
> {
> cout << Num[i] << ' ' << Num[j] << ' ' << Num[k] << endl;
> }
> }
>}
>


其實你這程式碼的效果和遞迴法差不多,若你真有耐心寫個一萬層,大概也許可能也能把堆疊給弄垮
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/18 上午 09:58:28
嗯 對呀 所以我說寫死是這樣
用遞迴當然也行 原理是一樣的
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/18 下午 03:00:32

>嗯 對呀 所以我說寫死是這樣
>用遞迴當然也行 原理是一樣的
我的意思是你的程式碼中的 I j k ,和我所寫的遞迴式中的 n 是一樣的,每多一層就會多一份在堆疊中,早晚會把堆疊用爆
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/18 下午 10:37:30
>>嗯 對呀 所以我說寫死是這樣
>>用遞迴當然也行 原理是一樣的
>我的意思是你的程式碼中的 I j k ,和我所寫的遞迴式中的 n 是一樣的,每多一層就會多一份在堆疊中,早晚會把堆疊用爆

recursion 邏輯裡存放到 stack 的可不只是區域變數, 也就是說, recursion 會用更多的 stack 資源. 另外如果區域物件的空間超出 stack 的侷限, 在編譯期就抓到了, 不會等到執行期才發生.

kagaya 大大的例子除了區域變數的局限外, 還有編譯器本身對 nesting level 的侷限及 identifier 數量的侷限這兩個問題. 把他例子裡的 i, j, k... 用 std::vector<size_t> 來包, v[0], v[1], ... 等當作 loop counter, 然後再設計一個更精簡的邏輯來取代多層的 nested loop.

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/19 下午 05:45:27
R大,你的 combination 計算法太夢幻了,看了老半天也看不懂(誰能解釋一下),我只好自己設計一套,希望旁人看來不會那麼夢幻

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>

template <typename T>
std::ostream& operator <<(std::ostream& os, std::vector<T>& vt)
{
 os << "{ ";
 for(std::vector<T>::iterator cit = vt.begin();
  cit != vt.end();
  ++cit)
 {
  os << *cit << ' ';
 }
 os << "}";
 return os;
}

unsigned long long choose(const size_t n, const size_t r)
{
 if (n < r)
  return 0;
 else if (n == r)
  return 1;

 // choose(100, 97) ==> choose(100, 3)
 size_t k2 = (r < n - r) ? r : n - r;

 // n * (n-1) * (n-2) ... (n-k2+1)
 // -------------------------------
 // 1 * 2 * ... k2
 unsigned long long ans = n;
 for (size_t i = 2; i <= k2; ++i)
 {
  ans = (ans * (n - i + 1))/i;
 }
 return ans;
}

size_t V(size_t a, size_t b, long long &m)
{
 if(b == 1)
  return (size_t)m+1;

 size_t l = 0;
 while(true)
 {
  long long z = choose(a-l-1,b-1);
  if(z < (m+1))
  {
   m = m - z;
   ++l;
  }
  else
   return l+1;
 }
}

void GetMthElement(const size_t n, const size_t r, unsigned long long mm, std::vector<size_t>& result)
{
 long long m = mm;
 result.resize(r);
 size_t a = n;
 size_t b = r;
 size_t c = 0;
 for(size_t i = 0; i < r; ++i)
 {
  result[i] = V(a, b, m) + c;
  c = result[i];
  a = n - c;
  --b;
 }
}

void C(const size_t n, const size_t r)
{
 std::vector<size_t> result(r);
 const unsigned long long mMax = choose(n, r);
 for (unsigned long long m = 0; m < mMax; ++m)
 {
  GetMthElement(n, r, m, result);
  std::cout << std::setw(10) << m+1 << ": " << result << std::endl;
 }
}

int main(int argc, char* argv[])
{
 size_t n, r;
 std::cout << "Calculate nCr" << std::endl;
 while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
 {
  C(n, r);
 }

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/19 下午 05:49:22
>
>kagaya 大大的例子除了區域變數的局限外, 還有編譯器本身對 nesting level 的侷限及 identifier 數量的侷限這兩個問題. 把他例子裡的 i, j, k... 用 std::vector<size_t> 來包, v[0], v[1], ... 等當作 loop counter, 然後再設計一個更精簡的邏輯來取代多層的 nested loop.
>

精簡的邏輯 +1,在有限度的使用下一定會比計算法有效率
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/19 下午 08:54:39

>>
>>kagaya 大大的例子除了區域變數的局限外, 還有編譯器本身對 nesting level 的侷限及 identifier 數量的侷限這兩個問題. 把他例子裡的 i, j, k... 用 std::vector<size_t> 來包, v[0], v[1], ... 等當作 loop counter, 然後再設計一個更精簡的邏輯來取代多層的 nested loop.
>>
>
>精簡的邏輯 +1,在有限度的使用下一定會比計算法有效率

勉強湊合一下,看有沒有人能寫得更精簡

#include <vector>
#include <iostream>
#include <iomanip>

template <typename T>
std::ostream& operator <<(std::ostream& os, std::vector<T>& vt)
{
 os << "{ ";
 for (std::vector<T>::iterator cit = vt.begin();
   cit != vt.end();
   ++cit)
 {
  os << *cit << ' ';
 }
 os << "}";
 return os;
}

void Combination(const size_t n, const size_t r,void (*pFn)(std::vector<size_t>& vt))
{
 if(n == 0 || n < r) return;

 std::vector<size_t> result(r);
 bool up = true;
 size_t Level = 0;

 while(Level < r)
 {
  result[Level] = Level + 1;
  ++Level;
 }

 size_t b = n-r+1;
 while(true)
 {
  if(Level == r)
  {
   pFn(result);
   --Level;
   up = false;
  }
  else if(Level == 0)
  {
   if(up == false)
   {
    if(result[0] < b)
    {
     up = true;
     ++result[0];
     ++Level;
    }
    else
     return;
   }
  }
  else
  {
   if(up == false)
   {
    if(result[Level] < (b+Level))
    {
     up = true;
     ++result[Level];
     ++Level;
    }
    else
     --Level;
   }
   else // if(up == true)
   {
    result[Level] = result[Level-1]+1;
    ++Level;
   }
  }
 }
}

unsigned long long m = 1;

// 回叫函數
void Fn(std::vector<size_t>& result)
{
 std::cout << std::setw(10) << m++ << ": " << result << std::endl;
}


int main(int argc, char* argv[])
{
 
 size_t n, r;
 std::cout << "Calculate nCr" << std::endl;
 while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
 {
  m = 1;
  Combination(n, r, Fn);
 }

 return 0;
}

作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/20 上午 11:24:41
good
g++的話要加上typename才能編譯

 for (typename std::vector<T>::iterator cit = vt.begin();
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/21 下午 06:20:16
Permutation 精簡版,不過和前面的遞迴模擬版做法差不多,因為樣本和 Index(前面的叫 n_stack) 都不能省去,不像 Combination 精簡版那麼精簡

#include <list>
#include <vector>
#include <iostream>
#include <iomanip>

template <typename T>
std::ostream& operator <<(std::ostream& os, std::vector<T>& vt)
{
 os << "{ ";
 for (std::vector<T>::iterator cit = vt.begin();
   cit != vt.end();
   ++cit)
 {
  os << *cit << ' ';
 }
 os << "}";
 return os;
}

void Permutation(const size_t n, const size_t r,void (*pFn)(std::vector<size_t>&))
{
 if(n == 0 || n < r) return;

 std::list<size_t> Samples; // 要排列的樣本
 std::vector<size_t> Index(r);
 for(size_t i = 0; i < n; ++i)
  Samples.push_back(i+1);

 std::vector<size_t> result(r);
 size_t Level = 1;
 bool up = true;

 while(true)
 {
  if(Level == r)
  {
   for(size_t i = Samples.size(); i > 0; --i)
   {
    result[Level-1] = Samples.front();
    Samples.pop_front();
    pFn(result);
    Samples.push_back(result[Level-1]);
   }
   --Level;
   up = false;
  }
  else if(Level == 0)
  {
   return;
  }
  else
  {
   if(up)
   {
    Index[Level-1] = Samples.size();
    result[Level-1] = Samples.front();
    Samples.pop_front();
    ++Level;
   }
   else
   {
    --Index[Level-1];
    Samples.push_back(result[Level-1]);
    if(Index[Level-1] > 0)
    {
     result[Level-1] = Samples.front();
     Samples.pop_front();
     ++Level;
     up = true;
    }
    else
     --Level;
   }
  }
 }
}

unsigned long long m = 1;

// 回叫函數
void Fn(std::vector<size_t>& result)
{
 std::cout << std::setw(10) << m++ << ": " << result << std::endl;
}

int main(int argc, char* argv[])
{
 size_t n, r;
 std::cout << "Permutation nPr" << std::endl;
 while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
 {
  m = 1;
  Permutation(n, r, Fn);
 }

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/21 下午 06:26:01

>[參考資料: https://msdn.microsoft.com/en-us/library/aa289166.aspx]
>組合程式. 程式用了一些 C++11 的語法如 auto, 編譯器如不支援自己轉成 std::vector<T>::const_iterator.
>因為用的是內建類型, 計算會有上限, unsigned long long 應該可以到 64C32, 再大就 overflow 了.
>

R大你的 Combination 計算法有問題,剛測試 n=1000 r=100 出來的數據不正確
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/21 下午 06:34:49

>good
>g++的話要加上typename才能編譯
>
> for (typename std::vector<T>::iterator cit = vt.begin();

大家腦力激盪的好處,總會擠出意想不到的東西
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/21 下午 11:00:04
>>[參考資料: https://msdn.microsoft.com/en-us/library/aa289166.aspx]
>>組合程式. 程式用了一些 C++11 的語法如 auto, 編譯器如不支援自己轉成 std::vector<T>::const_iterator.
>>因為用的是內建類型, 計算會有上限, unsigned long long 應該可以到 64C32, 再大就 overflow 了.
>>
>
>R大你的 Combination 計算法有問題,剛測試 n=1000 r=100 出來的數據不正確

Overflow 的關係. 程式裡面的 choose() 計算的就是 nCr 的數值, 1000C100 的精確值是63850511926305130236698511142022274281262900693853331776286816221524376994750901948920974351797699894319420811933446197797592213357065053890
這已遠遠超出了 unsigned long long 的最大值 (18446744073709551615).

用 Python 的程式碼可以得到正確的結果, 執行 combination.c(1000, 100) 的前 3 個輸出是 (本來想打 10 個的, 但會超出討論區的字數限制):

>>> combination.c(1000, 100)
     1 : [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, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]
     2 : [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, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 101]
     3 : [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, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 102]
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/22 下午 09:31:13

>Overflow 的關係. 程式裡面的 choose() 計算的就是 nCr 的數值, 1000C100 的精確值是

瞭解了,本來想用 gmp 這個大數函數庫來改寫,可惜函數庫 make 不出來,明天用我以前寫的大數函數庫來改寫
作者 : sflam(Raymond)討論區板主 Visual C++ .NET卓越專家VC++一代宗師新手入門優秀好手資訊類作業求救頂尖高手C++一代宗師貼文超過4000則
[ 貼文 4945 | 人氣 9172 | 評價 32290 | 評價/貼文 6.53 | 送出評價 142 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/23 上午 12:59:49
>瞭解了,本來想用 gmp 這個大數函數庫來改寫,可惜函數庫 make 不出來,明天用我以前寫的大數函數庫來改寫

CxxlMan 大打提醒了我, 這裡是用 boost 的 multiprecision 函式庫重寫的 combination:
[code: C++11]
#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;
namespace combination
{
    cpp_int choose(const size_t n, const size_t r)
    {
     if (n < r)
     return 0;
     else if (n == r)
     return 1;

     // choose(100, 97) ==> choose(100, 3)
     size_t k2 = (r < n - r) ? r : n - r;

     // n * (n-1) * (n-2) ... (n-k2+1)
     // -------------------------------
     // 1 * 2 * ... k2
     cpp_int ans = n;
     for (size_t i = 2; i <= k2; ++i)
     {
     ans = (ans * (n - i + 1))/i;
     }
     return ans;
    }

    size_t LargestV(size_t a, size_t b, cpp_int x)
    {
     size_t v = a - 1;
     while (choose(v, b) > x)
     --v;
     return v;
    }

    void GetMthElement(const size_t n, const size_t r, cpp_int m, std::vector<size_t>& result)
    {
     result.resize(r);
     size_t a = n;
     size_t b = r;
     cpp_int x = (choose(n, r) - 1) - m;
     for (size_t i = 0; i < r; ++i)
     {
     result[i] = LargestV(a, b, x);
     x = x - choose(result[i], b);
     a = result[i];
     b = b - 1;
     }
     for (size_t i = 0; i < r; ++i)
     {
     result[i] = n - result[i];
     }
    }

    void C(const size_t n, const size_t r)
    {
     std::vector<size_t> result(r);
     const cpp_int mMax = choose(n, r);
     for (cpp_int m = 0; m < mMax; ++m)
     {
     GetMthElement(n, r, m, result);
     std::cout << std::setw(10) << m+1 << ": " << result << std::endl;
     }
    }
}
[/code: C++11]

作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/23 下午 04:58:58

>>瞭解了,本來想用 gmp 這個大數函數庫來改寫,可惜函數庫 make 不出來,明天用我以前寫的大數函數庫來改寫
>
>CxxlMan 大打提醒了我, 這裡是用 boost 的 multiprecision 函式庫重寫的 combination:

原來 boost 有,這樣算得上是完美了,大數這東西應放入 C++ 的 stl,許多語言都有支援了,C++ 沒有實在很麻煩
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/28 下午 02:23:29
謝謝大大的分享 !
我原來PO的程式碼是可以調整到最大值是計算數字10階乘的結果,
不過目前我的電腦跑10階乘都要18天以上,
已經算是一個大型的計算程式,
所以目前我不會再增加這篇程式碼的篇幅了,
如果大家有更快的計算方式,
或是能很快算出結果的算法,
都歡迎繼續提供出來分享,
謝謝大家。
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/28 下午 05:55:38
補充一點:
由於PC電腦的硬體規格會持續進步,
新的程式語言規格也會不斷增加,
所以新的演算法理論上都會比舊的算法更快而且更好寫。
但是舊版的演算法是用來符合舊版的電腦,
所以在某些不能更新的電腦上面必須用舊版程式碼來撰寫新的程式,
這個過程叫做改良舊電腦。
為了達成改良舊電腦的自動化目標,
所以大型計算程式的程式碼不能隨便擴充,
需要經過長久的測試。
由於遞迴程式在不同的平台上面結果可能會有不同,
希望大家的電腦如果跑的動這個程式,
可以試著計算看看,
歡迎大家多多利用程式與討論程式,
最好是有一天可以改寫成Borland C++的舊版,
拿去裝到80286的電腦上面,
這樣就可以改良舊電腦了。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/30 下午 09:31:07

10! 跑 18 天,問題應不是在排列法本身,應該是在應用層費時太多,比如以上的例子大部份時間都花在文子顯示上,所以你應該分析清楚再見招拆招
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/31 上午 03:19:44
>10! 跑 18 天,
>問題應不是在排列法本身,
>應該是在應用層費時太多,
>比如以上的例子大部份時間都花在文字顯示上,
>所以你應該分析清楚再見招拆招

費時太多確實是Visual C++應用層的問題,
每一年的版本速度都有些微的不同,
我實測的時候,
2008和2010的Visual C++在顯示速度上面比2005版更慢。
建議大家在測試原始程式碼速度的時候,
就直接安裝使用Visual C++ 2005 Express來測試會比較快。
另外2013和2014年的Visual C++教科書已經出版了,
我也打算過幾個月拿這些版本來測試新功能,
幸好這幾年的版本在迴圈的部分沒有變動,
只要是用PC電腦都可以計算出結果。
至於Linux電腦跟Python程式語言的部分我沒法測試,
這部分改寫的程式碼就交給各位大大測試看看!
由於之前大大說過,
Visual C++遞迴程式出錯的時候,
無法預測也無法捕捉,
我把程式碼公布到論壇上面,
主要也希望新版PC電腦和筆電的硬體,
可以加速這部分的迴圈計算,
如果大家買了未來Windows 10新版PC電腦跟筆電,
發現遞迴程式的迴圈有計算異常的情形,
或是不支援舊版Visual C++,
都歡迎繼續回應到這個討論串文章裡面,
或是在我的部落格留言,謝謝。
作者 : kagaya(kagaya) VC++優秀好手C++優秀好手貼文超過1000則人氣指數超過30000點
[ 貼文 1599 | 人氣 38709 | 評價 4590 | 評價/貼文 2.87 | 送出評價 115 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/31 上午 10:45:09
人家在講I/O你可以扯到VC版本去
很神!
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/3/31 上午 11:35:22

> std::cout << std::setw(10) << m++ << ': ' << result << std::endl;

你試著把我寫的 Permutation 精簡版中以上這一段拿掉,用 release 模式編譯,在我的電腦 10! 大概 3 秒就跑完了,因此你的 18 天和 10! 的處理無關,而是你用 10! 來做什麼所花的時間要做分析
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/1 下午 06:58:46
不過就是排列組合,排列組合當然有它的應用。
但樓主一開頭說的好像是什麼神器,會不會太言過其實。

排列組合就回歸基本組合取法的觀念,就好了。
不重複組合為例,計算n取r的不重複組合的方法:
1.先取一個元素出來(稱為X),剩下的元素(n-1)取(r-1)的每種組合
 加上X就是n取r全部有X的組合方法。
2.因為不可重複,所以取出的X不能再放進去元素集合。
 因此從剩下的(n-1)元素,再拿一個元素出來(稱為Y)。
 剩下的元素(n-2)取(r-1)的每種組合加上Y就是全部有Y沒有X的組合方法。
3.重複以上的程序,直到只剩r-1個元素為止。
 因為C(r-1,r)已經無法再取出合法的組合了
(這組合取法看似有幾道手續,其實都一樣,取法只有一種。)

以公式表示,就是:
 C(n,r)= C(n-1, r-1)+C(n-2, r-1)...+C(r,r-1)
以C(5,3)為例,可以分解成:
C(5,3)
=C(4,2)+C(3,2)+C(2,2)
=[C(3,1)+C(2,1)+C(1,1)]+[C(2,1)+C(1,1)]+[C(1,1)]
因為C(3,1)=C(2,1)+C(1,1)=C(1,1)+C(1,1)+C(1,1)
所以最後C(5,3)可以分解成10個C(1,1)的和,也就是說C(5,3)=10

以上看起來囉嗦,其實邏輯很簡單,所以寫成程式也很簡單。
void C(size_t n, size_t r, std::vector<size_t> &Set)
{
if (Set.size()>=Set.capacity()){//The set has been collected completed. print it out.

std::cout<<'{';
for (std::vector<size_t>::iterator it = Set.begin(); it!=Set.end(); ++it)
std::cout<<' '<< *it;
std::cout<<" }"<<std::endl;
return;
}
size_t s= Set.size();
while (n>=r){
Set.push_back(n--);
C(n, r>1?r-1:r, Set);
Set.resize(s);
}
};

int main()
{
size_t n,r;
    std::cout << "To calculates C(n,r), Enter n r? " << std::flush, std::cin >> n >> r;
std::vector<size_t> Set;
Set.reserve(r);
C(n, r, Set);
::system("pause");
  return 0;
}

所有的邏輯,就在C函式裡的幾行:
while (n>=r){
Set.push_back(n--);
C(n, r>1?r-1:r, Set);
Set.resize(s);
}
因為是同一種方法去分解組合步驟,所以程式以遞迴來呈現會比較好。
以C(n,r)來說,最大的遞迴次數會是 (n-r+1),在以百萬計的 PC stack,
我覺得還好。
若是考慮stack會爆掉,也可以成loop的方式,但程式邏輯看起來較不容易。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/3 上午 03:34:35


>
>所有的邏輯,就在C函式裡的幾行:
> while (n>=r){
> Set.push_back(n--);
> C(n, r>1?r-1:r, Set);
> Set.resize(s);
> }
>
多虧你的程式碼,讓我搞懂 R大的Combination 計算法,
原來是以由大到小排序為基礎做構思,
再加上補數轉換搞得讓人眼花撩亂
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/4 上午 01:58:31
>原來是以由大到小排序為基礎做構思,
>再加上補數轉換搞得讓人眼花撩亂
組合的元素選取,並沒有順序要求。
只是依我前面的組合分解,C(n,r)的n一定會由大往小分解。
程式只是利用n來做為選取元素的ID而已。
因為只是ID,可以隨意轉換ID的。
例如選取元素是其它的pattern(不是{1,2,3,4...}),那麼就把ID當成pattern 的索引(index)。
想要索引是從0開始,而非1,那麼把Set.push_back(n--);改成Set.push_back(--n);就可以了。
我把程式改了一下,讓recursive時,耗用的的stack資源更少一點。
class CCombination{
std::vector<size_t> *m_pSet;
void recursiveC(size_t n, size_t r)
{
if (m_pSet->size()>=m_pSet->capacity()){//The set has been collected completed. print it out.

std::cout<<'{';
for (std::vector<size_t>::iterator it=m_pSet->begin(); it!=m_pSet->end(); ++it)
std::cout<<' '<< *it;
std::cout<<" }"<<std::endl;
return;
}
while (n>=r){
m_pSet->push_back(n--);
recursiveC(n, r>1?r-1:r);
m_pSet->pop_back();
}
}
public:
void C(size_t n, size_t r){
m_pSet= new std::vector<size_t>;
m_pSet->reserve(r);
recursiveC(n,r);
delete m_pSet;
}
};

int _tmain()
{
    size_t n,r;
    std::cout << "To calculates C(n,r), Enter n r? " << std::flush, std::cin >> n >> r;
    CCombination Combination;
    Combination.C(n,r);
    ::system("pause");
    return 0;
}

在32位元系統,recursiveC(size_t n, size_t r)每個遞迴,連同返回地址只會消耗12bytes。
如果,stack是1M,那麼可以組合8萬元素以上。
我的重點是,程式想要應用的範圍應是可以預期的,編譯器大都可以依需求調整stack大小。
而在預期之外的範圍(n-m超出預期)時,程式也可以檢知,不至於崩潰。
原邏輯是遞畗,改成loop很難不傷程式的可讀性。
例如上例程式,改以loop實現,我在儘量維持原邏輯改成loop會是這樣:
void LoopC(size_t n, size_t r){
std::vector<size_t> Set;
Set.reserve(r);
std::vector<SnCr> nCr;
nCr.push_back(SnCr(n,r));
do {
if (Set.size()>=Set.capacity()){//The set has been collected completed. print it out.
std::cout<<'{';
for (std::vector<size_t>::iterator it = Set.begin(); it!=Set.end(); ++it)
std::cout<<' '<< *it;
std::cout<<" }"<<std::endl;
}
else if (nCr.back().m_n >= nCr.back().m_r){
Set.push_back(nCr.back().m_n--);
nCr.push_back(SnCr(nCr.back().m_n, nCr.back().m_r>1?nCr.back().m_r-1:nCr.back().m_r));
continue;
}
if (!Set.empty()) Set.pop_back();
nCr.pop_back();
}while ( nCr.size()>0);
}

如果沒有前面的解說,加上recursive程式的理解,想要看懂LoopC的邏輯,是很不容易的。
就看程式員如何取捨。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/4 上午 08:42:26
啊,上面貼的那個遞迴程式,因為是class成員,所以呼叫時會多一個this區域變數,所以消耗的stack是16bytes。
本來是要改成如下的static(才會是12bytes)成員,結果忘了:P
class CCombination{
static std::vector<size_t> *m_pSet;
static void recursiveC(size_t n, size_t r){...}
public:
static void C(size_t n, size_t r){...}
};

int _tmain()
{
    size_t n,r;
    std::cout << "To calculates C(n,r), Enter n r? " << std::flush, std::cin >> n >> r;
    CCombination::C(n,r);
    ::system("pause");
    return 0;
}


另外,LoopC,因為r值不會被改變,就不必靠Set.capacity來記錄了:
void LoopC(size_t n, size_t r){
:::::::::::::::::::::::::::::::::::::::
do {
if (Set.size()>=r){//The set has been collected completed. print it out.
:::::::::::::::::::::::::::::::::::::::
}
::::::::::::::::::::::::::::::::::::::::
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/4 下午 06:33:22
loop 法在效能和安全都比遞迴好,沒有理由不用,但可讀性是差很多,解決辦法是兩樣都寫,但把遞迴法當註解用
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/4 下午 10:46:34
>loop 法在效能和安全都比遞迴好,沒有理由不用
安全,我不知道你指的什麼。
至於效能,那並不是所有case的首要追求的。
而且,loop並不見得其效能一定比recursive高。
應該是case by case吧。
以我上面的例子,使用loop來模擬recursive的邏輯。
recursive 基本上要做的是一個呼叫和返回指令,stack pointer的移動則平行處理可以忽略。
在loop裡要模擬呼叫和返回則必需在模擬的stack pointer的移動,在效能上並討不到便宜。
引數方面,rcursive需要(呼叫時)push,和(返回時)pop自stack(註)。
但在loop方式卻必需一連串的指令來移動區域變數,也是討不到便宜。
區域物件空間配置和收回,recursive只是移動stack指標,loop卻需要一連串的指令來配置和收回記憶體。
結論是,我我的例子裡,效能方面loop並討不好處。
它的優點,就是不用去煩惱stack夠不夠用(但還是要關心記憶體的容量)。
另一個優點是,一個函式解決整個排列組合運算。
recursive會需要函式外的初始化和一個共用物件。這個共用物件若用引數來傳遞勢必加重stack的消耗。
static來溝通,邏輯性較差,也有不能用在多緒程式的缺點。

當然,你可以反駁,loop方式不一定要模擬recursive。
這個我同意,但若解決問題的邏輯是rcursive,硬要以loop的想法去克服,還是不一定能討到便宜。
注意到,我說的是"不一定",並沒有定論一定是recursive或loop的效能好。
這要看問題是什麼和是否能找到好的loop設計。
(如果單純的以loop來模擬recursive如上面說明的,通常討不到便宜)


註:在大部份的編譯器,引數和區域物件是在stack配置的,這能運用CPU的硬體運算得到最好的效能和程式方便性。
但在有些用在stack記憶體很有限的CPU的編譯器,引數和區域變數並不是配置在stack。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/5 上午 03:58:07
你不如把 loop 也寫出來,做個測速大 pk。

還有這是不重複選取,選取間有關聯性,所以不管是遞迴法還是 loop 法,都不能做平行處理。
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/5 上午 11:55:08
>你不如把 loop 也寫出來,做個測速大 pk。
不是寫了嗎?上面的LoopC(...)就是!
但要注意,在dbug模式時,呼叫可能會加上額外一段和stack 偵錯有關的程式。
而loop的程式,多用了幾個STL 的容器物件,STL在debug模式也會有額外的開銷。
所以比較要在release模式下,才是正確的。

>還有這是不重複選取,選取間有關聯性,所以不管是遞迴法還是 loop 法,都不能做平行處理。
平行處理和是不是重複選取無關的。
我貼的LoopC很容易可以改成平行處理:
C(n,r)就是
取n加上C(n-1,r-1)組合,
取n-1加上C(n-2,r-1)組合,
取n-2加上C(n-3,r-1)組合,
::::::::::::::::::::::::::
取r加上C(r-1,r-1)組合。
以上做成一個for loop,是可以平行處理的。
至於recursive的那一個,問題在於Set物件是遞迴的共用的,本來就不能多緒執行。
要平行處理,就要把Set再於進去引數,分成幾個線程就要有幾個不同的Set。還是可以做平行處理。
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/5 下午 04:11:14

>>你不如把 loop 也寫出來,做個測速大 pk。
>不是寫了嗎?上面的LoopC(...)就是!
>但要注意,在dbug模式時,呼叫可能會加上額外一段和stack 偵錯有關的程式。
>而loop的程式,多用了幾個STL 的容器物件,STL在debug模式也會有額外的開銷。
>所以比較要在release模式下,才是正確的。

這以後再討論

>>還有這是不重複選取,選取間有關聯性,所以不管是遞迴法還是 loop 法,都不能做平行處理。
>平行處理和是不是重複選取無關的。
>我貼的LoopC很容易可以改成平行處理:
>C(n,r)就是
>取n加上C(n-1,r-1)組合,
>取n-1加上C(n-2,r-1)組合,
>取n-2加上C(n-3,r-1)組合,
>::::::::::::::::::::::::::
>取r加上C(r-1,r-1)組合。
>以上做成一個for loop,是可以平行處理的。
>至於recursive的那一個,問題在於Set物件是遞迴的共用的,本來就不能多緒執行。
>要平行處理,就要把Set再於進去引數,分成幾個線程就要有幾個不同的Set。還是可以做平行處理。

這是個大亮點,比 R大的計算法還要好,R大的計算法只能各組平行處理,選取單項還是得在同一個執行緒完成,你這招還可做得更細,可選取單項也能平行處理

以下我把它實作出來討論,但還是得用遞迴,你有辦法改成全 loop 嗎?

程式中的 for 指令是可以用 OpenMP 做到多 CPU 平行處理,但若要做到跨電腦就麻煩多了

這種做法很像走迷宮順間全部走完,很有價值





作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/5 下午 04:11:52
#include <iostream>
#include <iomanip>

struct resul_t
{
 resul_t(resul_t &previous_arg, size_t value_arg)
  :previous(previous_arg)
 {
  value = value_arg;
 }
 resul_t &previous;
 size_t value;
};

class Combination
{
 static void(*m_pFn)(const resul_t &);

 static void v(resul_t &pre, const size_t n, const size_t r)
 {
  if (r == 1)
  {
   for (size_t i = n; i > 0; --i)
    m_pFn(resul_t(pre, i - 1));
   return;
  }

  for (size_t i = n-1; i >= r-1; --i)
   v(resul_t(pre,i), i, r-1);
 }
public:
 static void C(const size_t n, const size_t r, void(*pFn)(const resul_t &))
 {
  m_pFn = pFn;
  v(*(resul_t*)NULL, n, r);
 }
};

void(*Combination::m_pFn)(const resul_t &);

unsigned long long m = 1;

void Fn(const resul_t &resul_arg)
{
 std::cout << std::setw(10) << m++ << '=' << '{';
 for (const resul_t *resul = &resul_arg; resul != (resul_t*)NULL; resul = &resul->previous)
  std::cout << resul->value << ' ';
 std::cout << '}' << std::endl;
}

int main(int argc, char* argv[])
{
 size_t n, r;
 std::cout << "Calculate nCr" << std::endl;
 while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
 {
  m = 1;
  Combination::C(n, r, Fn);
 }

 return 0;
}
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/6 上午 03:54:08
原來有這種寫法啊~~
謝謝各位大大的分享!
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/6 下午 10:11:25
修改為 OpenMP 版本,用 vs2013 編譯,因為了要用 lock_guard 同步控制,若不
在意畫面會亂掉,把同步控制拿掉用 vs2008 也能跑

比較在意的事用 omp_get_thread_num() 只會取得 0,若跑 Test() 是正常
的,不知道是不是有用多個 CPU 在跑

#include <mutex>
#include <iostream>
#include <iomanip>
#include <omp.h>

void Test(int n)
{
 static std::mutex io_mutex;
 std::lock_guard<std::mutex> lk(io_mutex);
 std::cout << "<T:" << omp_get_thread_num() << ">," << n << std::endl;
}

struct resul_t
{
 resul_t(const resul_t &previous_arg, size_t value_arg)
  :previous(previous_arg), value(value_arg)
 {}
 const resul_t &previous;
 const size_t value;
};

class Combination
{
 static void(*m_pFn)(const resul_t &);

 static void v(const resul_t &pre, const size_t n, const size_t r)
 {
  if (r == 1)
  {
#pragma omp parallel for
   for (int i = n; i > 0; --i) // 不能用 size_t i
    m_pFn(resul_t(pre, i - 1));
   return;
  }

#pragma omp parallel for ordered num_threads(100)
  for (int i = n - 1; i > 0 /*= (long)r - 1*/; --i) // 不能用 size_t i
   v(resul_t(pre, i), i, r - 1); // 要跑 Test() 須註解掉這行
  // Test(i); // 跑這 omp_get_thread_num() 正常
 }
public:
 static void C(const size_t n, const size_t r, void(*pFn)(const resul_t &))
 {
  m_pFn = pFn;
  v(*(resul_t*)NULL, n, r);
 }
};

void(*Combination::m_pFn)(const resul_t &);

unsigned long long m = 1;

void Fn(const resul_t &resul_arg)
{
 static std::mutex io_mutex;
 std::lock_guard<std::mutex> lk(io_mutex);

 std::cout << "<T:" << omp_get_thread_num() << '>';
 std::cout << std::setw(10) << m++ << '=' << '{';
 for (const resul_t *resul = &resul_arg; resul != (resul_t*)NULL; resul = &resul->previous)
  std::cout << resul->value << ' ';
 std::cout << '}' << std::endl;
}

int main(int argc, char* argv[])
{
 size_t n, r;
 std::cout << "Calculate nCr" << std::endl;
 while (std::cout << "Enter n r? " << std::flush, std::cin >> n >> r)
 {
  m = 1;
  Combination::C(n, r, Fn);
 }

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/7 下午 05:57:07
想為 coco 這方法取個名字,就叫量子演算法吧,因為我覺得若有量子電腦應該很容易實現,可惜可惜



作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/8 上午 11:55:48
免強用 c++11 的 std::thread 實現量子演算法,若用 RPC 替換 std::thread 應該也能跨電
腦,不過這些做法象徵意義大於實質意義,應該要用真正平行處理機制才能真正發揮出高效率

平行處理這種東西可能一輩子也用不上,我就不研究了,有興趣上網找找相關資料,當然能寫出來貼上來更好^^

#include <mutex>
#include <iostream>
#include <iomanip>
#include <memory>
#include <thread>

using namespace std;

struct result_t
{
 result_t(const shared_ptr<result_t> &previous_arg, const size_t value_arg)
  :previous_ptr(previous_arg), value(value_arg)
 {
 }
 const shared_ptr<result_t> previous_ptr;
 const size_t value;
};

class Combination
{
 static void(*m_pFn)(const shared_ptr<result_t> &);

 static void v_parallel(const shared_ptr<result_t> &result_arg, const size_t n, const size_t r)
 {
  thread m(v, result_arg, n, r);
  m.detach();
 }

 static void io_parallel(const shared_ptr<result_t> &result_arg)
 {
  thread m(m_pFn, result_arg);
  m.detach();
 }

 static void v(const shared_ptr<result_t> &pre, const size_t n, const size_t r)
 {
  if (r == 1)
  {
   for (size_t i = n; i > 0; --i)
    io_parallel(shared_ptr<result_t>(new result_t(pre, i - 1)));
   return;
  }

  for (size_t i = n - 1; i >= r - 1; --i)
   v_parallel(shared_ptr<result_t>(new result_t(pre, i)), i, r - 1);
 }
public:
 static void C(const size_t n, const size_t r, void(*pFn)(const shared_ptr<result_t> &))
 {
  m_pFn = pFn;
  v(shared_ptr<result_t>((result_t*)NULL), n, r);
 }
};

void(*Combination::m_pFn)(const shared_ptr<result_t> &);

unsigned long long m = 1;

void Fn(const shared_ptr<result_t> &result_arg)
{
 static mutex io_mutex;
 lock_guard<mutex> lk(io_mutex);

 cout << setw(10) << m++ << '=' << '{';
 for (shared_ptr<result_t> result_ptr = result_arg; result_ptr.get() != (result_t*)NULL; result_ptr = result_ptr->previous_ptr)
  cout << result_ptr->value << ' ';
 cout << '}' << endl;
}

int main(int argc, char* argv[])
{
 size_t n, r;
 cout << "Calculate nCr" << endl;
 cout << "Enter n r?" << endl ;
 while (cin >> n >> r)
 {
  m = 1;
  Combination::C(n, r, Fn);
 }

 return 0;
}
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2015/4/9 下午 09:36:23
上面用 std::thread 實現量子演算法雖然不完美,但可以看出一些有趣的東西,所以補充一下

1.因 thread 可同時產生的數量是有上限的,所以若超過上限,程式會被強制結束,因此面對這種大
 量吃 thread 的東西,應該先經過一層控管機制來產生 thread 才能確保安全

2.因 thread 有各自的 stack,所以遞迴最擔心的 overflow 就不再存在了,可以有遞迴的方便卻沒有遞
 迴的負擔,所以也就不用再用 loop 來代替遞迴

3.最有趣的來了,遞迴的觀念是由父呼叫子,由子呼叫孫,由孫返回子,再返回父,所以才叫遞迴,但上面
 的程式碼作用像遞迴,但父子孫的關係是鬆散的,父呼叫完子之後可以再去做其他的事,比如再去生其他
 的孩子,甚至可以先結束,不用再去等迴這個動作,對遞迴有新的觀點
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/6 下午 04:41:53
有了 http://www.programmer-club.com.tw/ShowSameTitleN/c/46838.html 這個小工具,現在不用擔心 thread 的數量有上限,以下用 ThreadLimit 來改寫量子演算法

#include <iostream>
#include <iomanip>

using namespace std;

struct result_t
{
 result_t(const shared_ptr<result_t> &previous_arg, const size_t value_arg)
  :previous_ptr(previous_arg), value(value_arg)
 {
 }
 const shared_ptr<result_t> previous_ptr;
 const size_t value;
};

class Combination
{
 static void(*m_pFn)(const shared_ptr<result_t> &);
 // 視自己電腦的 CPU 做修改,這裡假設是 4 核心,
 // 設定太大不會比較快
 static ThreadLimit<4> TL;

 static void v(const shared_ptr<result_t> &pre, const size_t n, const size_t r)
 {
  if (r == 1)
  {
   for (size_t i = n; i > 0; --i)
    TL.Thread(m_pFn, shared_ptr<result_t>(new result_t(pre, i - 1)));
   return;
  }

  for (size_t i = n - 1; i >= r - 1; --i)
   TL.Thread(v, shared_ptr<result_t>(new result_t(pre, i)), i, r - 1);
 }
public:
 static void C(const size_t n, const size_t r, void(*pFn)(const shared_ptr<result_t> &))
 {
  m_pFn = pFn;
  v(shared_ptr<result_t>((result_t*)NULL), n, r);
 }
};

void(*Combination::m_pFn)(const shared_ptr<result_t> &);
ThreadLimit<4> Combination::TL;

unsigned long long m = 1;

void Fn(const shared_ptr<result_t> &result_arg)
{
 static mutex io_mutex;
 lock_guard<mutex> lk(io_mutex);

 cout << setw(10) << m++ << '=' << '{';
 for (shared_ptr<result_t> result_ptr = result_arg;
  result_ptr.get() != (result_t*)NULL;
  result_ptr = result_ptr->previous_ptr
  )
  cout << result_ptr->value << ' ';

 cout << '}' << endl;

}

int main()
{
 size_t n, r;
 cout << "Calculate nCr" << endl;
 cout << "Enter n r?" << endl;
 while (cin >> n >> r)
 {
  m = 1;
  Combination::C(n, r, Fn);
 }

 return 0;
}
作者 : gmailjoey(建中) 貼文超過200則
[ 貼文 206 | 人氣 0 | 評價 190 | 評價/貼文 0.92 | 送出評價 13 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/7 上午 12:04:09
>現在不用擔心 thread 的數量有上限,
>以下用 ThreadLimit 來改寫量子演算法


Cxxlman大大你好,
還有幾個問題想請教:

1.要用哪一個版本的visual studio來跑大大的Fn函數?
我試過VC2005不能跑,請教大大有哪些新的免費版本可以跑Fn函數。

2.Combination裡面有很多static參數,
是不是應該把Combination的class類別改成公用的結構struct呢?
改成struct是不是有甚麼不好的後果?

3.我的自動號碼產生器不能算11階乘以上的數字,
目前因為自己技術力不足所以無法改寫。
徵求高手幫我改成BIG INT讓它可以算更多,
有興趣的網友請把連結網頁或是改寫好的程式碼,
寄到我的信箱:arkane0422@gmail.com
非常感謝!
作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4465 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/7 上午 08:53:30
try to find a version which supports c++ template (or template function) .
and 11! = 39916800 . you should use a big enough data type to store this factorial .
https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx


作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1003 | 人氣 3227 | 評價 1260 | 評價/貼文 1.26 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/7 下午 01:15:52

>
>1.要用哪一個版本的visual studio來跑大大的Fn函數?
>我試過VC2005不能跑,請教大大有哪些新的免費版本可以跑Fn函數。

我是用 vs2015 community update 3,這是免費的版本

>2.Combination裡面有很多static參數,
>是不是應該把Combination的class類別改成公用的結構struct呢?
>改成struct是不是有甚麼不好的後果?

這裡的 Combination 用 static 只是為了 scope,沒有特別的功能

>
>3.我的自動號碼產生器不能算11階乘以上的數字,
>目前因為自己技術力不足所以無法改寫。
>徵求高手幫我改成BIG INT讓它可以算更多,
>有興趣的網友請把連結網頁或是改寫好的程式碼,
>寄到我的信箱:arkane0422@gmail.com
>非常感謝!

目前 c++11 沒提供 biginteger,c++14 c++18 是不是有提供要查一查,boost 是有提供的
作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4465 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/7 下午 04:16:01
https://mattmccutchen.net/bigint/
it is available for vc++
check it out
作者 : ozzy123(ozzy) 資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4465 | 人氣 37262 | 評價 10860 | 評價/貼文 2.43 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2017/4/7 下午 05:02:01
http://gladman.plushost.co.uk/oldsite/computing/gmp4win.php
http://www.mpfr.org/#intro
https://msdn.microsoft.com/en-us/library/9yb4317s(VS.80).aspx >>> you should configure your VS
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2018 程式設計俱樂部 http://www.programmer-club.com.tw/
0.453125