請問一下… 我想設計一個路徑的關聯… 例如： 第一層(沒有1)：００００ 第二層(有一個1)：１０００；０１００；００１０；０００１ 第三層(有二個1)：１１００；１０１０；１００１；０１１０；０１００;００１１ 第四層(有三個1)：１１１０；１１０１；１０１１；０１１１ 第五層(全部都為1)：１１１１ 上例是只有四個元素…我要設計二十三個元素… 我有用matlab寫過，不過跑了三天還沒產生出來… 不知道在bcb上有什麼好的方法可以解決我的問題…

jajolin 你好, 23個元素...所產生的排列組合2的23次方...... 建議你先利用小一點的數據來測試程式.. 等正確後在跑...

引言: jajolin 你好, 23個元素...所產生的排列組合2的23次方...... 建議你先利用小一點的數據來測試程式.. 等正確後在跑...

謝謝 pkdemon大大 … 我已經測試過8個元素…沒問題 不過23個元素真的太龐大了… 到現在還沒跑完… 希望大大能夠提供更好的方法…

jajolin 你好,    要處理那麼多的資料,我也不知道要怎麼處理比較快 我想你可以把程式中一些步驟再加以精簡,也許能快一點點..... 有一點要提的是,當你的程式在跑的時候,如果計算出一個結果就 >

jajolin 您好：    插個花！ 依各位的討論，有個約略可以使工作時程減半的建議： 依組合的特性知道，其實選與不選(或者是取 > 覺得這個問題很有意思，所以想了一下，發現可以試著將各次的結果存起來，再利用來算下一個的結果。不過時間的確是要花不少，粗略估計算>紅色為新增部分-依序排列。 < class="code"> //--------------------------------------------------------------------------- #include #pragma hdrstop #include "GenCombination0.h" #include //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- int coef[24]; // resize coef[.] to meet your need int coefficient(int n) // generate the binomial coefficients { int result; coef[0]=coef[1]= 1; for (int p=2; p<=n; p ) { coef[p] = 1; for (int t=p-1; t>0; t--) { coef[t] = coef[t] coef[t-1]; } } return(n 1); } //--------------------------------------------------------------------------- TStringList * combinationInOrder(TStringList *src) { TStringList *lst = new TStringList(); if ( src->Count==0 ) { lst->Add("0"); lst->Add("1"); } else { double value = ( log(src->Count)/log(2) ); // save result in double first int n = (int)(value); // OK //int n = (int)(log(src->Count)/log(2)); // >128, error occurs!!!??? coefficient(n); int index, idx; index = 0; Form1->ListBox2->Items->Clear(); Form1->ListBox2->Items->Add(IntToStr(n)); Form1->ListBox2->Items->Add("------"); for (int p=0; p<=n; p ) { Form1->ListBox2->Items->Add(IntToStr(coef[p])); for (int k=0; kAdd("0" src->Strings[index k]); } for (int k=0; kAdd("1" src->Strings[index k]); } index = coef[p]; } } return (lst); } TStringList * combination(TStringList *src) { TStringList *lst = new TStringList(); if ( src->Count==0 ) { lst->Add("0"); lst->Add("1"); } else { for (int k=0; kCount; k ) { lst->Add("0" src->Strings[k]); lst->Add("1" src->Strings[k]); } } return (lst); } void __fastcall TForm1::Button1Click(TObject *Sender) { AnsiString msg; TStringList *lst; Screen->Cursor = crHourGlass; time_t start = time(NULL); // get current system time lst = combinationInOrder((TStringList *)ListBox1->Items); //lst = combination((TStringList *)ListBox1->Items); ListBox1->Items->Assign(lst); msg.printf("(-):(%d) => (%.f) seconds", ListBox1->Items->Strings[0].Length(), ListBox1->Count, difftime(time(NULL), start) ); Label1->Caption = msg; Screen->Cursor = crDefault; } //--------------------------------------------------------------------------- RichTop 敬上 =====***** 把數學當工具，可以解決問題；將數學變能力，能夠發現並解決問題！ =====##### 發表人 - richtop 於 2004/10/27 12:15:54 發表人 - richtop 於 2004/10/27 17:16:10

重複post…! 發表人 - m8815010 於 2004/10/27 17:13:30

引言: 請問一下… 我想設計一個路徑的關聯… 例如： 第一層(沒有1)：００００ 第二層(有一個1)：１０００；０１００；００１０；０００１ 第三層(有二個1)：１１００；１０１０；１００１；０１１０；０１００;００１１ 第四層(有三個1)：１１１０；１１０１；１０１１；０１１１ 第五層(全部都為1)：１１１１ 上例是只有四個元素…我要設計二十三個元素… 我有用matlab寫過，不過跑了三天還沒產生出來… 不知道在bcb上有什麼好的方法可以解決我的問題…

jajolin你好： 你這個問題我個人覺得相當得大，因為要 class="code"> 1. 我的測試結果 2. 我的測試環境 3. 我的algorithm分析 4. 我的範例程式 5. 範例程式分析 I 測試結果 我測了 24 bits (取整數，剛好 3 bytes)，並只針對有12個1的情況(因為這是worst case， 共有 C(24,12)=2704156 種情況)，並且不在營幕show結果，直接將結果存檔(共存了7個檔， 每個檔約40萬行，每一行代表一種情況，每個檔約10MB)! 這個case約花了40分鐘! =======於是粗估了一下總時間=========== 總共的case有24種：有1個1、有2個1、有3個1、…… 所以最差情況共花 40*24=960分鐘 但有些case是quiet simple，幾乎不花時間的，如有1個1、有2個1、有23個1、有24個1… 所以應該總時間可以打折 960*1/2=480 分鐘=8小時 也就是應該不超過10小時可以完成24 bits的所有解(估計值) II 我的測試環境 環境應是得重要的，我的是： win2000 pro 512 ram P4 pure enviroment 沒有跑其它的東東 注意我的這隻程式在win xp測試時會掛 III Algorithm分析 比如現在要求4個 bits，有2個1的情況有幾種： 那假設求解的function為E(4,2)，4表示有4bits，2表示有2個1的情況 則E(4,2)=E(3,2)+E(3,1)……並可以一直遞迴拆解下去… 所以依這種精神可以將〝4個 bits，有2個1的情況〞的所有解建成一棵binary tree! 那從tree的root 走到任一leaf都是一種解，只要leaf不是Err即可! 圖例(紅色的travel即是一個解，其餘略)： 精神跟這題很像，無法解釋太清楚，就請自行參考吧： http://delphi.ktop.com.tw/topic.php?TOPIC_ID=53180 範例程式 以下是求24bits有12個1的所有情況： 注意 1. 先在 C: 下建一個try目錄 2. 可先測試較小的數，才不會一跑就數十分鐘 3. 當binary tree很大的時候展開會很久，所以不要輕易展開 TForm1 *Form1; const int SaveBound=200000; //每20萬個結果就存進檔案內一次 AnsiString RltFileName="C:\\Try\\RltFile1.txt"; //儲存的第一個檔名 void FindRlt(int bits_num,int num_1,TTreeNode* ParNode); //遞迴求解function void GetWholePath(TTreeNode* LeafNode,int LeafValue); //從binary tree求任一個解 void ChangeFileName(AnsiString& FileName); //更換儲存檔檔名 TStringList* rltlist; //儲存data元件 TStringList* filebuffer; //儲存data元件 int Count=0; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- void __fastcall TForm1::FormCreate(TObject *Sender) { this->Caption="開始時間 : "+Now(); //計算開始時間 TTreeNode* Root; //設binary tree的 root的text為〝Root〞 Root=TreeView1->Items->AddChild(NULL,"Root"); rltlist = new TStringList; //new物件 filebuffer = new TStringList; //new物件 FileClose(FileCreate(RltFileName)); //建立第一個儲存檔 FindRlt(24,12,Root); //建立binary tree，並且一邊建一邊求解 TStringList* filebuffer=new TStringList; //將最後不滿20萬筆的解直接存入最後一個檔中 filebuffer->LoadFromFile(RltFileName); filebuffer->AddStrings(rltlist); rltlist->Clear(); filebuffer->SaveToFile(RltFileName); delete filebuffer; this->Caption=this->Caption+" 結束時間 : "+Now(); //計算結束時間 } //--------------------------------------------------------------------------- void FindRlt(int bits_num,int num_1,TTreeNode* ParNode) { if ((bits_numTreeView1->Items->AddChild(ParNode,"ERR"); Form1->TreeView1->Items->AddChild(ParNode,"ERR"); return; } else if (bits_num==1 && num_1==0) { TTreeNode* Endchild; Endchild=Form1->TreeView1->Items->AddChild(ParNode,"0"); GetWholePath(Endchild,0); return; } else if (bits_num==1 && num_1==1) { TTreeNode* Endchild; Endchild=Form1->TreeView1->Items->AddChild(ParNode,"1"); GetWholePath(Endchild,1); return; } else { TTreeNode *Lchild,*Rchild; Lchild=Form1->TreeView1->Items->AddChild(ParNode,"0"); Rchild=Form1->TreeView1->Items->AddChild(ParNode,"1"); FindRlt(bits_num-1,num_1,Lchild); FindRlt(bits_num-1,num_1-1,Rchild); } if (rltlist->Count>=SaveBound) { Count++; if (Count>2) { ChangeFileName(RltFileName); FileClose(FileCreate(RltFileName)); Count=1; } filebuffer->LoadFromFile(RltFileName); filebuffer->AddStrings(rltlist); rltlist->Clear(); filebuffer->SaveToFile(RltFileName); filebuffer->Clear(); } } //--------------------------------------------------------------------------- void __fastcall TForm1::TreeView1DblClick(TObject *Sender) { TreeView1->FullExpand(); //將樹全部展開檢視 } //--------------------------------------------------------------------------- void GetWholePath(TTreeNode* LeafNode,int LeafValue) { AnsiString val=""; TTreeNode* ParNode=LeafNode->Parent; while (ParNode->Text!="Root"){ val=val+ParNode->Text; ParNode=ParNode->Parent; } val+=IntToStr(LeafValue); rltlist->Add(val); } //--------------------------------------------------------------------------- void ChangeFileName(AnsiString& FileName) { int Sqn_num=StrToInt(FileName.SubString(15,1))+1; FileName=FileName.SubString(1,14)+IntToStr(Sqn_num)+".txt"; } 程式分析 1.程式花在建binary tree的時間其時並不多，只要不展開的話!主要花的時間在由binary tree 求每一個解及存檔! 2.我也大量使用到TStringList元件，是不是理想，要再深入研究才知! 3.我的以收集20萬個解就存入檔中一次，並且每一個檔只存40萬個解! 這些conditions都是相當trade off的問題，要再深入研究才知優劣! (收集2萬個解就存入檔中一次，或是每一個檔只存10萬個解，這樣比做有比較快嗎？？？) Conclusion 1. 這種長時間的問題，演算法的好壞將是主要決勝處! 2. 尚未分析我的範例解法的time complexity是多少，單純比較花多少時間是沒意義的! 3. 光以不同程式語言來看的話，assembly應是最快，因為它最低階，正適合這種0、1的問題! Perl應該也可以試試，專門適合字串的處理! 4. 承最前說過，要考慮的東東實在很多，不得不堪!比如全部的解存成一個檔可能會有好幾百MB哦! 5. 本範例當然未必是最佳解，但總可以在一個上、下班解決之! All! 發表人 -

jajolin你好：     參考下面的碼，不知道是不是你要的？  

#include 
#include 
#include 
using namespace std;
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    int Size = 24;  // Input size
    vector > result;
    result.resize(Size+1);
    unsigned int num = 1 << Size;
    for(unsigned int i = 0; i < num;i++)
        result[std::bitset<32>(i).count()].push_back(i);        int Layer = 3;  // Layer
    for(unsigned int i = 0; i < result[Layer].size();++i)
        {
        string sa;
        std::bitset<32>(result[Layer][i])._M_copy_to_string(sa);
        string sb(sa.end()-Size,sa.end());
        Memo1->Lines->Add(sb.c_str());
        }
}
//---------------------------------------------------------------------------     

以上是執行後的部份結果， 速度應該還算可以，24元素大概需要用5秒... 另外，Compile這程式時，要把Linker中的dynamic RTL取消，不然編不過(BCB6 STL的bug)

忘了提一點，結果全部都在result中， 比如result[0]是第0層的解 result[1]是第1層的解 你再指定你要的Layer就可以輸出。 複雜度是O(2^Size)

謝謝 pkdemon，richtop，m8815010，pwipwi的回覆…    小弟已經知道如何下手了… 真的很感謝各位前輩的指導… 看來我程式的功力還是不夠… 只能跟各位大大學習囉…

引言: jajolin你好： 參考下面的碼，不知道是不是你要的？

#include 
#include 
#include 
using namespace std;
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    int Size = 24;  // Input size
    vector > result;
    result.resize(Size+1);
    unsigned int num = 1 << Size;
    for(unsigned int i = 0; i < num;i++)
        result[std::bitset<32>(i).count()].push_back(i);        int Layer = 3;  // Layer
    for(unsigned int i = 0; i < result[Layer].size();++i)
        {
        string sa;
        std::bitset<32>(result[Layer][i])._M_copy_to_string(sa);
        string sb(sa.end()-Size,sa.end());
        Memo1->Lines->Add(sb.c_str());
        }
}
//---------------------------------------------------------------------------     

以上是執行後的部份結果， 速度應該還算可以，24元素大概需要用5秒... 另外，Compile這程式時，要把Linker中的dynamic RTL取消，不然編不過(BCB6 STL的bug)

乍聞 >! 想說怎麼差這麼多，跟本是 >! 嗯，所以結論就是： >! 不過 >! 發表人 -