台灣最大程式設計社群網站
線上人數
2223
 
會員總數:245979
討論主題:189557
歡迎您免費加入會員
討論區列表 >> C/C++ >> 數字的排列組合
[]  
[我要回覆]
1
回應主題 加入我的關注話題 檢舉此篇討論 將提問者加入個人黑名單
數字的排列組合
價值 : 100 QP  點閱數:1346 回應數:5
樓主

陳德錡
門外漢
0 1
8 0
發送站內信

如題
我想要可以例如輸入3
就可以跑出1~3的所有組合
123 132 213 231 312 321
可是不能用遞迴 老師給我這個題目可是我只會用遞迴做




搜尋相關Tags的文章: [ 排列組合 ] ,
本篇文章發表於2016-09-24 15:31
1樓
回應

詹宗運
檢舉此回應
這是我做好的自動號碼產生器,
可以自動產生1-10個數字之間的排列解法,
並且將所有排列解法,
輸出到一個檔案叫做:
AutoNumberGeneratorElectronicList.txt。
注意:如果你要輸出這個檔案,
就必須用系統管理員身分執行程式。

下面就是我的自動號碼產生器的程式網址:
http://joeymovieyoutube.blogspot.tw/2014/11/visual-c-2005auto-number-generator.html

這個程式有一部分用到遞迴,
最多可以計算到10階乘就是10個數字的排列,
顯示所有結果需要好幾個星期,
歡迎你有多餘時間的時候參考使用看看哦。

我的部落格還有其他一些應用範例,
像是宅男買星際大戰公仔,
工廠送咖啡到機台,
或是如何搭捷運到基隆等等,
歡迎你參考使用。
本篇文章回覆於2017-08-20 21:48
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
2樓
回應

淺水員
檢舉此回應
提供純 C 語言寫法
試著輸出10個數字的排列到檔案,時間約13秒,產生檔案大小約80M
11個數字約160秒,檔案大小約1G

遞迴改成非遞迴的要點:
1. 了解函式呼叫是 stack(堆疊) 的方式在處理
2. 改成非遞迴就是自己處理這些 stack(堆疊)

本篇文章回覆於2017-08-21 15:04
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
3樓
回應

詹宗運
檢舉此回應
淺水員 大大你好:

我今天上線得到你的程式碼,
初步測試在VC++6 就可以跑,
跑程式碼的初步結果是:
有算出所有的正確解法,
而且跑到10階乘的時候一樣電腦變慢。
感謝淺水員大大分享舊版的C語言程式碼!
終於遇到專業人員,十分感謝。

這個程式有一個特點是:
跑到一半的時候,
他會把data[j]變成負值。
想請問變成負值是有甚麼特殊的運算嗎。

我個人的想法是,
雖然排列組合可以存在stack裡面,
但是堆疊並不容易查詢資料,
也不能做push 或是pop 的功能。
如果可以的話應該繼續增加程式,
把運算出來的資料存到大型的資料結構,
在push pop 的運算上才會變得更方便。
這也就是為什麼我的部落格堶情A
提供的程式碼篇幅比較長的原因。

新加入的網友你好,
如果你對這個計算排列組合的主題有興趣,
歡迎2017路過的新網友改寫看看我和淺水員的程式碼,
這個改寫程式碼的任務就交給路過的網友了,
有多餘時間的網友都可以試著研究看看!感恩。

本篇文章回覆於2017-08-22 01:06
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
4樓
回應

淺水員
檢舉此回應
我想說明一下,VC++6 或 Visual C++ 2005那些不是C++版本
那是整合開發環境(IDE)版本
也就是僅僅只是開發軟體的版本而已

C/C++有標準
凡是正常的C/C++編譯器都應該能夠編譯出標準的程式碼
儘管C/C++的標準有更新過
但新標準大體上都是相容先前標準
只是增加一些新特性
以及刪除一些真的很糟糕的函式
(容易出現地雷的函式)

所以,我前面寫的那個,照理說不管是VC++6 或 Visual C++ 2005 或更新版本
應該都要能夠編譯
只是如果對編譯器設定不熟悉
有可能找不到編譯標準程式碼的設定
例如這邊就有教人如何用Visual Studio 2015 編譯C原始碼的教學:
How to compile and run C program in Visual Studio 2015
我相信我上面寫的那個應該也是可以在 Visual Studio 2015 編譯的

關於跑到10!變慢的問題,這取決於演算法
依我目前所知也差不多是如此了
不過不顯示在螢幕上而直接輸出時間會節省很多
(我給的執行時間也是輸出成文字文件,無螢幕輸出的時間)

負號的部分,沒甚麼特別的
我只是以負號標記為「這個數字已經被取用」
所以後面不能重複取用而已

至於stack部分
我其實沒有完全遵照 stack 的定義
所以在22~23行那邊,完全把他當作陣列在用
正常的stack一定都是「後進先出」的
而且一定有push跟pop

雖然我沒有明確的寫 push 跟 pop 函式
但我在操作變數 k 的時候,那本質就是 push 與 pop 了
(25~26行、32~33行、38~42行)

至於「堆疊並不容易查詢資料」這句話我不是很了解你的意思
「大型的資料結構」也不是很懂你要的是什麼
在我學習C/C++的標準函式庫中
看到官方的函式庫都會盡可能抽象化他們的物件
方便使用者使用在不同的地方
因此,與其預設使用者需要 push pop
不如單純的只做排列這件事情
而物件內容可以讓使用者自行選擇

例如我下面的程式碼,我只需要使用者:
1. 選擇資料型態
2. 實作 index 與 value 的映射函式
3. 實作輸出函式

接下來就只呼叫函式:Permutation_資料型態名稱
就可以對不同的東西去排列

下面以 int 跟 char 為例
這用起來很像是 C++ 的 template
(其實應該用template寫比較乾淨,只是當練習)


而其相關的 Permutations.h :


本篇文章回覆於2017-08-22 18:36
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
5樓
回應

淺水員
檢舉此回應
補充一下,像這類題目。
(包含騎士旅行、八皇后、暴力破解法、井字遊戲AI…)
大致上就是深度優先搜索廣度優先搜索這些概念。
有興趣可以了解一下。
本篇文章回覆於2017-08-22 18:44
== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--
   
1

回覆
如要回應,請先登入.