仔細想了一下
觀察Stanford排列解法與演算法筆記排列解法異同是比較花時間的
因此還是先解出UVa online上的題目比較能讓人安心去想
排序 part 1在
以這篇幅,也許會有part 3
part 3內容應該是Stanford解法與演算法筆記解法異同
其實那兩個做法可以簡單的劃分為C++實作法與純C語言做法
由於不確定寫不寫得出東西,所以還不太確定是否會有part 3
要解的題目是:
102 - Ecological Bin Packing
資源回收裝箱問題(我沒照著翻,題目底下英文敘述給人的感覺)
會挑這題是因為這題看起來很簡單
而解這題意外引出排列這個還蠻有意思的項目就挑這題了
(其實其它題也沒仔細看過)
問題簡述如下
輸入是九個數字
三個三個一組
每三個一組的三個數字
分別代表的是棕色瓶子(Brown)數量,綠色(Green)瓶子數量,透明(Clear)瓶子數量
程式所要做的是
顯示出怎樣分類所需移動的瓶子數量最小
當最小的分法不只一種時,以英文字母順序為主
補充:九個瓶子數量總和不會超過2³¹
也就是可以用int或unsigned int存總瓶子數來減的意思
(如果英文沒看錯的話)
此外,因為每個回收分類箱都只出現一次,所以三個回收分類箱是排列關係
例如
BGC BGC BGC
1 2 3 4 5 6 7 8 9 這九個是輸入內容
輸出
BCG 30
也就是第一組固定棕色瓶子,要移動綠色瓶子2個+透明瓶子3個=5
第二組固定透明瓶子,要移動棕色瓶子4個+綠色瓶子5個 = 9
第三組固定綠色瓶子,要移動棕色瓶子7個+透明瓶子9個=16
16+9+5= 30,共30個瓶子要移動
理論上要印六種排列法中最小移動瓶子數量
由於是範例,所以這保證是對的
但還是稍微檢查一下吧
B G C的話是 5 + (4+6) + (7+8) = 30
雖然移動瓶子所需數量相同
但因為BCG符合英文字母順序,就以BCG為主
(理論上還要檢查四種狀況比較才能斷定)
嗯...突然有些好奇
在解題前我先想一下
為什麼
B G C B G C B G C
1 2 3 4 5 6 7 8 9
這好像不管怎麼取,所需要移動的瓶子都是30這問題好了
雖然解題不用想這個
想到17:00還想不出來的話就先跳過
(後來想到20:20左右
想的結果更新於留言)
--------------------------------------------------
(思考、晚些寫程式丟UVa online驗證
我想用排列做法會慢一些,但應該不至於超時錯誤(TLE)吧!
3秒才超時,聽說有種簡單估計方法是,1秒約10億次操作=10⁹
IO本身佔些時間,若用scanf,printf等通常問題不大
雖然不知道測試資料共有多少組
但這程式全部運算總和要超過30億次感覺很困難
3個元素全排列遞迴解只要呼叫16次即可完成
這題運算也大多是常數時間
要是真的超過的話
研究、改良過後還是不行的話-像用C++ std::next_permutation或它的實作方法
就跳過這題不解好了
反正現有硬解解答蠻多的)
6/12補充
1秒約10億次操作=10⁹這估計原理應該是
現在CPU時脈頻率大多是或者說是可以到3.3GHz
也就是0與1變換的速度(波產生的速度)
(3.3GHz已經幾乎觸頂了,現在是靠平行運算提速)
(所以命令式語言就...而函數式語言或特性復活)
(其實邏輯式語言也有跟函數式語言易於平行運算的特性,所以才會被人工智慧所採用)
(但邏輯式語言寫一般的程式,概念可能比函數式語言還難)
G=2³⁰ 約略等於 = 10⁹,如果是硬碟容量的話,就是直接用10的次方來算了
那是否代表一秒鐘能執行3.3*10⁹指令呢?
呃,假如每個指令都只需要1個時脈的話,這是成立的
精簡指令集好像就是指令都在1時脈內完成
而現在的電腦幾乎內在都是精簡指令集的概念
但精簡指令集的一個指令,不是以加減乘除函式為單位
而是讀(load),存(store),加(add)之類的
所以做兩個數的加法,可能需要3個指令,最好的狀況也許只要3時脈可完成
這邊其實我也不是很確定
不過我想我們可藉此簡單的把1秒當作是10億次操作這個數量級的
理論依據可能就是從這來的
每秒鐘執行多少指令其實有另個指標,IPS(instruction per second)
關於時脈頻率再多扯一下好了
很多人喜歡說電腦就是由0跟1組成,0低電壓,1高電壓
其實有時候碰上這種說法要微笑面對
以組合邏輯電路、TTL(電晶體)元件、CMOS元件單個來看的話這大概是對的
有個相關的專有名詞是(Threshold voltage,電壓閾(玉)值)
TTL是根據材料品質,電壓超過或小於固定值就確定是低電壓或高電壓
(TTL供電大多是5V,似乎是壓到0.8V以下就確定是低電壓,2V以上就確定是高電壓)
而CMOS大多看%數(因為CMOS供電可以把電壓壓得很小(主要應用),雖然也可以很大)
不過用組合邏輯電路是做不出個人電腦的
一定需要時序邏輯(正反器元件)或功能能取代時序邏輯的
而時序邏輯就需要時脈(或者說波形)了
所以做電路設計時才需要示波器
若然,那嚴格上來說其實我們不見得能確定各電腦的0與1編碼方式
常見的編碼方式,除了高電壓1,低電壓0受限於元件的自然情況之外
有正(前)緣觸發(positive-edge-triggered,有低電壓變高電壓時才更改01狀態)
、負(後)緣觸發(negative-edge-triggered,有高電壓變低電壓時才更改01狀態)
哦,還有主從式觸發(master-slave-triggered,不過這我好像沒學過就僅提名詞)
前三者是正反器(filp-flop)相關的
後面再提供些電信相關編碼(也就是臺灣網路概論相關教科書時常提到的內容)
不歸零(NRZ,Non-Return to Zero)編碼(這編碼有些變種形式,像反轉Inverted,見wiki圖)
講這些只是想說,0跟1其實有時也不是那麼簡單
有很多時候,一些說法只是把某一領域壓縮到常人能理解的地步而已
但通常不代表那領域真的那麼簡單
(我的文章類型大多是打一長串來裝逼(這詞意思就好像自己懂很多、很會),請容忍下)
夏知饋:沒關係啦!大概習慣了
--------------------------------------------------
先貼程式碼
吃飯完後再講詳細些
(決定採註解形式)
submit(交答案)給UVa online時
記得程式語言選
C++ 5.3.0 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
C++ 11應該也行
程式最上方註解可去掉
那是比較有體系的處理權重問題的兩種解法示範
#include <stdio.h>
//本來是想全用C來寫,這主要是printf()、scanf()也就是基本std 輸入輸出io用的.h檔
#include <limits.h>
//為了使用INT_MAX 也就是2147483647這常數所引入
#include <string>
#include <algorithm>
//這是C++的部份
//上述兩個是為了用std::string與std::next_permutation而引入
#include <iostream>
//這也是C++的部分
//同樣顧名思義,io處理輸入輸出用的
//stream是因為<<,>>叫串流(stream)輸入(insertion)輸出(extraction)運算子
//主要是用cin,cout,我是只有用cout
//因為cin我還不太清楚要怎麼處理EOF判斷
using namespace std;
//為了少打些std::string之類的std::而寫的
int main(void)
{
/*
int weight[3] = {0,1,2};
char ascii_weight[128];
char alphanumic_table[3] = {'B','C','G'};
int temp_number;
for(int i=0;i<128;i++)
{
ascii_weight[i]=-1;
}
for(int i=0;i<3;i++)
{
temp_number = alphanumic_table[i];
ascii_weight[temp_number] = weight[i];
}
char temp;
scanf("%c",&temp);
printf("%d",ascii_weight[temp]);
*/
/*
for(int i=0; i<3;i++)
{
if(alphanumic_table[i] == temp)
{
printf("%d",weight[i]);
}
}
*/
#define N 3
int all_number[N][N];
//3組輸入,分別三個元素,長得像 [1,2,3] [4,5,6] [7,8,9]
int total=0;
int temp_total;
//我的程式是先加總再減去三個固定的瓶子,所以這麼寫
int min_total=INT_MAX;
//記錄哪個最小,一開始先設為最大整數,確保第一個結果被接收
//其實也可以把迴圈分成 "第一次"跟 "其餘次"兩段寫來解決這問題
string target_s = "BCG";
//這邊是手動將BCG排序好,這樣使用next_permutation時就會照字典順序排序了
string end_s;
//最小值時的字串排列狀況
while(scanf("%d %d %d",&all_number[0][0],&all_number[0][1],&all_number[0][2]) != EOF)
{
total=0;
min_total = INT_MAX;
//每處理完一行,就要將些運算數字清回預設值
//不然很可能會出問題
//忘記給預設值或迴圈中沒設回預設值這狀況
//算是寫C語言、C++超常犯錯誤之一
//當發現程式不合預期時,可以朝這方向來偵錯
for(int i=1;i<N;i++) //接收餘下兩組輸入,所以i從1開始
{
scanf("%d %d %d",&all_number[i][0],&all_number[i][1],&all_number[i][2]);
}
//這段加總用
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
total+=all_number[i][j];
}
}
do {
temp_total = total;
for(int i=0;i<N;i++)
{
//這寫法↓也算是硬解的一種
//減掉對應的三個元素後,就得到所需移動的瓶子數量
switch(target_s[i])
{
case 'B':
temp_total-= all_number[i][0];
break;
case 'C':
temp_total-= all_number[i][2];
break;
case 'G':
temp_total-= all_number[i][1];
break;
}
if(temp_total < min_total)
{
min_total = temp_total;
end_s = target_s;
}
}
} while(std::next_permutation(target_s.begin(), target_s.end()));
cout << end_s << " " << min_total << endl;
//題目輸出要求,記得中間要空一格,因為string是個物件所以不能用printf();
}
return 0;
}
沒意外的話
結果應該是(點左側My Submissions進入)
102 Ecological Bin Packing Accepted C++ 0.040 2016-06-12 05:20:17
↑交題時間
這解法算有些作弊
老實說我寫C語言出身的人,不應該依靠C++的功能來完成的
但想了一下不管是實作遞迴、非遞迴解法
我原則上也是用複製貼上的方式來改
那就用C++的功能讓程式碼看起來簡潔好懂些吧
而且C++ STD next_permutation之前有說過
根據些網站推測應該是用非遞迴解法
運作起來很快
結果有些神奇
在這網站上的人是硬解的
但時間卻是0.048s
我以為應該會比較快才對
也許是因為那人的程式碼解法是用加的
而我是用減的
對了,還有一個原因可能是
那人交題的時間很早
而那時的編譯器版本與機器狀況跟現在不同
啊,想到了,那再交一次好了
結果是
102 Ecological Bin Packing Accepted C++ 0.010 2016-06-12 05:31:16
硬解果然還是比較快!!
不過我還是比較喜歡個人這種也許能解出其它相同題型的解法
這邊就貼個採硬解網站僅供參考比較
(雖然我之前試了找了下,幾乎都是硬解,有個貌似不是硬解的,但程式碼連結掛掉了)
----------------------------------------------------
最後講一下權重賦予的程式解法部份
權重的意思在這邊是
這題題目的輸入順序是 棕色瓶子 綠色瓶子 透明瓶子(BGC)
但運算順序是按照字母順序(BCG)最先運算
那程式要怎麼處理這類輸入順序跟運算順序不同的狀況
我覺得這其實概念上跟權重差不多就稱為權重了
其實也不清楚正式稱呼
我這程式碼示範了三種解法(雖然三個都差不多鳥)
其中為了求快與簡潔
最後用的方法其實也算是種硬解
因為其它兩種解法較耗資源,但擴展性或說彈性是較強的
也就是當題目變,而題型不變時,要改的地方比較少或比較好改
(雖然我覺得題目改時,三者要修改工作量其實差不多
而且另外兩種解法是假設只處理英文或ASCII的狀況下才能順利運作)
在介紹三種解法前
先講下三種解法的思路
各解法就像是玩RTS(即時策略遊戲,世紀帝國、魔獸爭霸等)的兵種
各兵種所消耗的資源比重或種類是不太一樣的
像輕騎兵只需要消耗食物(雖然通常也只有食物的戰鬥力)
不過比RTS好或說乏味的地方是在於,我們不用海(大量生產)一或多兵種
通常電腦(計算機)資源就是時間與空間
然後還有個資源是隱性的
那就是修改彈性、適用問題範圍
現在先來看第一種解法
第一種解法需要權重、順序
像
char alphanumic_table[3] = {'B','C','G'};
int weight[3] = {0,1,2};
這要怎麼使用呢?
這代表的意思是B對應到第1個元素,C對應到第三個元素,G對應到第二個元素
(一般的權重通常是乘上比例,所以較學術、正確的稱呼很可能是對應關係吧)
使用上會像
for(int i=0; i<3;i++)
{
if(alphanumic_table[i] == 輸入值)
{
printf("%d",weight[i]);
}
}
示範用所以僅顯示權重或者說對應關係
由於一個做法的優缺點,大多需要別的做法比較才能得出
所以再看第二種解法吧
第二種解法是替ASCII表建權重(或說對應關係)
因此程式寫
char ascii_weight[128];
for(int i=0;i<128;i++)
{
ascii_weight[i]=-1;
}
這邊替沒用到(雖然程式是對所有)的字碼設個預設值
避免被誤用或者說誤用時辨識的出來
然後第二種解法可以自由決定要不要權重、順序
若要的話可以
for(int i=0;i<3;i++)
{
temp_number = alphanumic_table[i];
ascii_weight[temp_number] = weight[i];
}
temp_number用來記錄字母順序表的ASCII碼
再用那ASCII碼當索引決定對應到第幾個元素
不然其實可以直接
ascii_weight[B的ASCII碼,也就是66] = 對應元素的索引值;
C跟G當然也要寫,就不特別列出來了
第二種解法也用權重(對應關係)與字母順序表的好處就是
題目變成輸入16個數字,4個4個一組,需要多個新的英文字時還算好改
或者是輸入順序改採BGC外的,只要改權重(對應關係)表即可
第三種解法,這解法是有名稱的:「見招拆招」
好啦,我不知道正確名稱
就是當碰到B時,就取相對第1個元素運算
碰到G時,就取相對第2個元素運算這樣
也就是最後解法中switch (target_s[i]) { case 'B': ... break; ...}那邊
這方法表面上比較蠢
實際上我也不覺得能稱為聰明
但這可能是因為我們處理的是"單"個英文字
(第二種解法是針對ASCII表,若單個中文字的話,難不成要Unicode表或BIG5或GBK嗎?)
當然這方法在處理大量對應關係時不好用(case太多了,不易修改)
可是...這種一一對應關係的題目能大到哪邊去?
(但這種說詞就是要幫自己用硬解來找理由的!!)
好吧!要是真的有對應表很龐大的時候之應用,我大概也是不知道的!!
第一種解法缺陷是
就我所想到的實作方法,每次使用時都必須跑迴圈
第二種解法的缺陷是
會消耗一些記憶體空間,但這算比較能接受的做法
第三種解法的缺陷是
相對最不易修改,由於本質上是硬解,所以可能有較佳效能(performance)
可能啦!!畢竟沒實質上測試過
嗯,大概就這樣
我們為什麼要學程式設計呢?
嗯,首先我們根本不必學程式設計
但若說學程式設計會有好處的話
就是有某些程式
運作需要參數調校或原始碼小片段修改才擁有較佳的效能(performance)時
也許用得上程式設計,也許啦!!
雖然通常真得要用程式設計時
處理的不是效能(performance)問題
是do the right things(做對的事,亦稱為effectiveness,像網路爬蟲爬自己所需要的)
上述三種處理對應關係的程式解法
若要做成應用程式
只有第一種或第二種是可被接受的(當然第四種以後可能是個人沒想到)
至於第二種比較適合用英文、數字的情況
若碰上其它情形怎麼辦?
這時候我們可以說這程式的規格就是這樣
(可能會被戲稱為Bug寫入規格
但這是無可避免的
像用std::next_permutation就是要升冪排序啊!!)
但若是允許修改程式的話
第三種,也就是硬解就是能被接受的
這就有些像是工廠大量生產與手工製作的差異啦!!
這篇就此結束!!
後記:
sorry,後來想了一下
其實中文字、或超過一個英文字的情形
只要情形不超過127個(標準ASCII表)
還是可以用第二種解法
但是是靠代號的方式解決
也就是說有第三個陣列(可能會是二維字元陣列)
用索引值對應ASCII再對應到第幾個元素
運算後得到一組ASCII順序再還原成各情形
只是若ASCII全用上的話
根據之前XOR加密程式經驗
可能在26,也就是Substitute character
相當於按下Ctrl-Z
那邊大概會有問題
可能要特別處理
所以能處理的情形應該只有127個
(其實這題目一一對應且不重複,情形超過127個的話,輸入輸出應該也不太好看)
創作內容
程式語言建立自信系列-排列 part 2 解題說明與電壓、編碼、時脈頻率(完成,留言、後記更新)
單機版網頁遊戲系列相關 (20)
