2017年5月29日 星期一
2017年5月22日 星期一
b547 巧克力口味
/*
b547-巧克力口味
*/
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int MaxR = 10;
set <string> rel[MaxR]; // 最多 10 種 關係
map <int , int> c2n;
string rs(8,'?');
string c6(6,' ');
int getn(int i)
{
int j=c2n[ c6[i] ];
j += c2n[ c6[i+1] ];
return j;
}
// 以遞迴 將某一關係的所有編號建立 存入 rel[si]中
string ss[]={"PBY","SCT"};
void setr(int si, int p, int q)
{
int i,j;
if(q==6) // 已 6個字元了
{
bool mk[10];
string one="";
memset(mk,0,sizeof(mk));
for(i=0; i<6; i+=2)
{
j= getn(i);
if( mk[j] ) return; // 出現過，不合
mk[j] = true;
one += char('0'+j);
}
rel[si].insert(one); // 可以的關係編號 加入 rel[si] 中
//// cout << si <<':' << one << endl; /////
}
else // 完成第 q 個字元，遞迴下一字元 q+1
{
if( rs[p+q]=='?' ) // 目前這個位置為 ? 偶則以 PBY各代1次、 奇則以 SCT各代1次
for(i=0; i<3; ++i)
{
c6[q] = ss[q%2][i]; setr(si, p, q+1);
}
else
{
c6[q] = rs[p+q]; setr(si, p, q+1);
}
}
}
string x,y,z; // 將nine切成3部份
int r; //共 r 個關係
bool ok() // 任一個關係 最少要有 某一列 3個巧克力 符合它
{
for(int si=0; si<r; ++si)
{
if( !( rel[si].find(x)!=rel[si].end() || rel[si].find(y)!=rel[si].end() || rel[si].find(z)!=rel[si].end() ) ) return false;
}
return true;
}
int main(void)
{
int i,j,k,t ,n;
char c;
c2n.clear();
c2n['P']=0; c2n['B']=3; c2n['Y']=6;
c2n['S']=1; c2n['C']=2; c2n['T']=3;
cin >> r;
for(i=0; i<r; ++i)
{
cin >> t;
for(j=0; j<t*2; ++j)
{
cin >> rs[j+2];/// >> rs[j+3];
}
/// cout << i <<':' << rs << endl; ////
if(t==3) setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
else // t=2 , 前?? 及後 ?? 各一次
{
setr(i,0,0); // 第i個關係，從第0字元、已轉了0個
rs[6] = rs[7] ='?';
setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
}
}
string nine="123456789";
// cout << nine << endl; 1~9 九位數，全排列 共 9! = 362880
int cnt=0;
do
{
x=nine.substr(0,3); y=nine.substr(3,3); z=nine.substr(6,3);
// cout << x <<',' << y <<',' << z <<'\n';
if( ok() ) ++cnt;
} while( next_permutation(nine.begin(),nine.end() ) );
cout << cnt << endl;
// system("pause");
return 0;
}
/*
3
3 B S Y S P C
3 P T B C Y T
3 P S B T Y C
3
3 B S Y ? ? C
2 B C Y T
3 P S ? ? Y C
==========
6
24
*/
b547-巧克力口味
*/
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int MaxR = 10;
set <string> rel[MaxR]; // 最多 10 種 關係
map <int , int> c2n;
string rs(8,'?');
string c6(6,' ');
int getn(int i)
{
int j=c2n[ c6[i] ];
j += c2n[ c6[i+1] ];
return j;
}
// 以遞迴 將某一關係的所有編號建立 存入 rel[si]中
string ss[]={"PBY","SCT"};
void setr(int si, int p, int q)
{
int i,j;
if(q==6) // 已 6個字元了
{
bool mk[10];
string one="";
memset(mk,0,sizeof(mk));
for(i=0; i<6; i+=2)
{
j= getn(i);
if( mk[j] ) return; // 出現過，不合
mk[j] = true;
one += char('0'+j);
}
rel[si].insert(one); // 可以的關係編號 加入 rel[si] 中
//// cout << si <<':' << one << endl; /////
}
else // 完成第 q 個字元，遞迴下一字元 q+1
{
if( rs[p+q]=='?' ) // 目前這個位置為 ? 偶則以 PBY各代1次、 奇則以 SCT各代1次
for(i=0; i<3; ++i)
{
c6[q] = ss[q%2][i]; setr(si, p, q+1);
}
else
{
c6[q] = rs[p+q]; setr(si, p, q+1);
}
}
}
string x,y,z; // 將nine切成3部份
int r; //共 r 個關係
bool ok() // 任一個關係 最少要有 某一列 3個巧克力 符合它
{
for(int si=0; si<r; ++si)
{
if( !( rel[si].find(x)!=rel[si].end() || rel[si].find(y)!=rel[si].end() || rel[si].find(z)!=rel[si].end() ) ) return false;
}
return true;
}
int main(void)
{
int i,j,k,t ,n;
char c;
c2n.clear();
c2n['P']=0; c2n['B']=3; c2n['Y']=6;
c2n['S']=1; c2n['C']=2; c2n['T']=3;
cin >> r;
for(i=0; i<r; ++i)
{
cin >> t;
for(j=0; j<t*2; ++j)
{
cin >> rs[j+2];/// >> rs[j+3];
}
/// cout << i <<':' << rs << endl; ////
if(t==3) setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
else // t=2 , 前?? 及後 ?? 各一次
{
setr(i,0,0); // 第i個關係，從第0字元、已轉了0個
rs[6] = rs[7] ='?';
setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
}
}
string nine="123456789";
// cout << nine << endl; 1~9 九位數，全排列 共 9! = 362880
int cnt=0;
do
{
x=nine.substr(0,3); y=nine.substr(3,3); z=nine.substr(6,3);
// cout << x <<',' << y <<',' << z <<'\n';
if( ok() ) ++cnt;
} while( next_permutation(nine.begin(),nine.end() ) );
cout << cnt << endl;
// system("pause");
return 0;
}
/*
3
3 B S Y S P C
3 P T B C Y T
3 P S B T Y C
3
3 B S Y ? ? C
2 B C Y T
3 P S ? ? Y C
==========
6
24
*/
2017年5月21日 星期日
vb版 BST建立及巡訪
一個TextBox1輸入5~30個皆不相同的整數以「,」隔開
一個Label1顯示輸出
一個按鈕，執行(1)建二元搜尋樹，(2)在Label1顯示{前序、中序、後序}巡訪結果
程式碼如下：
Public Class Form1
Class BT
Public data As Integer
Public lch As BT
Public rch As BT
Sub New()
lch = Nothing
rch = Nothing
End Sub
End Class
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim dat() = TextBox1.Text.Split(",") '依 , 分割為 陣列
Dim rt As BT = Nothing '一開始 樹根為 nothing
For i = 0 To UBound(dat)
Dim k As Integer = dat(i)
add(k, rt) '新增 1 node
Next
Dim s As String = "" : pre(s, rt) '前序
Label1.Text = "前序：" & s
s = "" : ino(s, rt) '中序
Label1.Text &= vbNewLine
Label1.Text &= "中序：" & s
s = "" : pos(s, rt) '後序
Label1.Text &= vbNewLine
Label1.Text &= "後序：" & s
End Sub
'將資料 k 新增至 樹根為 root 的 bst 樹中
Sub add(ByVal k As Integer, ByRef root As bt)
Dim node As New BT
node.data = k
If root Is Nothing Then
root = node
Return
End If
If k < root.data Then
add(k, root.lch)
Else
add(k, root.rch)
End If
End Sub
' 前序巡訪
Sub pre(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
If s <> "" Then s &= ","
s &= node.data
pre(s, node.lch)
pre(s, node.rch)
End Sub
' 中序巡訪
Sub ino(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
ino(s, node.lch)
If s <> "" Then s &= ","
s &= node.data
ino(s, node.rch)
End Sub
' 後序巡訪
Sub pos(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
pos(s, node.lch)
pos(s, node.rch)
If s <> "" Then s &= ","
s &= node.data
End Sub
End Class
一個Label1顯示輸出
一個按鈕，執行(1)建二元搜尋樹，(2)在Label1顯示{前序、中序、後序}巡訪結果
程式碼如下：
Public Class Form1
Class BT
Public data As Integer
Public lch As BT
Public rch As BT
Sub New()
lch = Nothing
rch = Nothing
End Sub
End Class
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim dat() = TextBox1.Text.Split(",") '依 , 分割為 陣列
Dim rt As BT = Nothing '一開始 樹根為 nothing
For i = 0 To UBound(dat)
Dim k As Integer = dat(i)
add(k, rt) '新增 1 node
Next
Dim s As String = "" : pre(s, rt) '前序
Label1.Text = "前序：" & s
s = "" : ino(s, rt) '中序
Label1.Text &= vbNewLine
Label1.Text &= "中序：" & s
s = "" : pos(s, rt) '後序
Label1.Text &= vbNewLine
Label1.Text &= "後序：" & s
End Sub
'將資料 k 新增至 樹根為 root 的 bst 樹中
Sub add(ByVal k As Integer, ByRef root As bt)
Dim node As New BT
node.data = k
If root Is Nothing Then
root = node
Return
End If
If k < root.data Then
add(k, root.lch)
Else
add(k, root.rch)
End If
End Sub
' 前序巡訪
Sub pre(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
If s <> "" Then s &= ","
s &= node.data
pre(s, node.lch)
pre(s, node.rch)
End Sub
' 中序巡訪
Sub ino(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
ino(s, node.lch)
If s <> "" Then s &= ","
s &= node.data
ino(s, node.rch)
End Sub
' 後序巡訪
Sub pos(ByRef s As String, ByVal node As bt)
If node Is Nothing Then Return
pos(s, node.lch)
pos(s, node.rch)
If s <> "" Then s &= ","
s &= node.data
End Sub
End Class
2017年5月20日 星期六
b549 數位相片檔名
/*
b549 nr102-5 北二區102年-5 數位相片檔名
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
map<int,int> used; // 已使用的 <時間 , 檔名>
map<int,int>::iterator mit;
map<int,int>::reverse_iterator rit;
bool can(int fn) // 傳入的檔名是否可用(符合雙遞增)
{
if(used.size()<2) return true; // 只有0或1個時，一定可以
int cnt=1; // 使用的 序列數，最多2個
mit=used.begin();
int fn1=mit->second, fn2=9999 ,fn3; //第1個使用 一個序列
// 若有兩個序列，維持 fn1<fn2
for(++mit; mit!=used.end() ; ++mit) // 從 第2個起與前一個比
{
fn3=mit->second; // 第2個起的檔案編號
if( fn3<fn1 )
{
if (cnt==2 ) return false; //已兩個再加1個 x
++cnt; fn2=fn1; fn1=fn3; //保持 fn1<fn2
}
else // fn3>fn1 可加入 fn1或fn2
{
if(fn3>fn2) fn2=fn3; //加至較大 的序列處，保留較小的序序編號
else fn1=fn3; // fn3<fn2無法加至 fn2，也保證 fn1=fn3<fn2
}
}
if( cnt==2 && fn<fn1 ) return false; //已兩個再加1個 x
else return true;
}
int main( )
{
int n , t ;
int fn[1000];
char c;
for( n=0; n<1000; ++n) fn[n] = n;
set <int>::iterator sit;
bool first=true;
while( cin >> n )
{
set <int> nuse(fn,fn+1000); //待用的檔號
used.clear();
while( n-- )
{
cin >> c >> t;
if( c == 'A' )
{
for( sit = nuse.begin(); sit != nuse.end(); ++sit )
{
int fn = *sit; //檢查檔名編號 fn 是否可用
if ( !can( fn ) ) continue; // 不能用，下一個
used[ t ] = fn; // t 時，加可用檔名 fn
nuse.erase( *sit );
break;
}
}
else
{
nuse.insert( used[t] ); // 未用的檔名，加一個
used.erase( t ); // 已用的 map <t,fn> 刪一個
}
}
// 印出，若不是第一組，則印出 --
if(first) first=false; else cout << "--\n";
rit = used.rbegin(); rit++; //先至倒數第2個
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
rit--;
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
}
return 0 ;
}
/* 輸入範例
10 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6 D 3 A 7 D 0 A 8
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 D 0 A 8 A 9
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9
15 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10
17 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11
19 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11 D 11 A 12
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 D 0 A 5
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 A 6
10 A 0 A 1 A 2 A 3 A 4 D 2 A 5 A 6 D 3 A 7
輸出範例-----------------
PIC004
PIC001
--
PIC002
PIC003
--
PIC006
PIC007
--
PIC006
PIC001
--
PIC001
PIC002
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC004
PIC005
--
PIC005
PIC003
*/
b549 nr102-5 北二區102年-5 數位相片檔名
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
map<int,int> used; // 已使用的 <時間 , 檔名>
map<int,int>::iterator mit;
map<int,int>::reverse_iterator rit;
bool can(int fn) // 傳入的檔名是否可用(符合雙遞增)
{
if(used.size()<2) return true; // 只有0或1個時，一定可以
int cnt=1; // 使用的 序列數，最多2個
mit=used.begin();
int fn1=mit->second, fn2=9999 ,fn3; //第1個使用 一個序列
// 若有兩個序列，維持 fn1<fn2
for(++mit; mit!=used.end() ; ++mit) // 從 第2個起與前一個比
{
fn3=mit->second; // 第2個起的檔案編號
if( fn3<fn1 )
{
if (cnt==2 ) return false; //已兩個再加1個 x
++cnt; fn2=fn1; fn1=fn3; //保持 fn1<fn2
}
else // fn3>fn1 可加入 fn1或fn2
{
if(fn3>fn2) fn2=fn3; //加至較大 的序列處，保留較小的序序編號
else fn1=fn3; // fn3<fn2無法加至 fn2，也保證 fn1=fn3<fn2
}
}
if( cnt==2 && fn<fn1 ) return false; //已兩個再加1個 x
else return true;
}
int main( )
{
int n , t ;
int fn[1000];
char c;
for( n=0; n<1000; ++n) fn[n] = n;
set <int>::iterator sit;
bool first=true;
while( cin >> n )
{
set <int> nuse(fn,fn+1000); //待用的檔號
used.clear();
while( n-- )
{
cin >> c >> t;
if( c == 'A' )
{
for( sit = nuse.begin(); sit != nuse.end(); ++sit )
{
int fn = *sit; //檢查檔名編號 fn 是否可用
if ( !can( fn ) ) continue; // 不能用，下一個
used[ t ] = fn; // t 時，加可用檔名 fn
nuse.erase( *sit );
break;
}
}
else
{
nuse.insert( used[t] ); // 未用的檔名，加一個
used.erase( t ); // 已用的 map <t,fn> 刪一個
}
}
// 印出，若不是第一組，則印出 --
if(first) first=false; else cout << "--\n";
rit = used.rbegin(); rit++; //先至倒數第2個
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
rit--;
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
}
return 0 ;
}
/* 輸入範例
10 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6 D 3 A 7 D 0 A 8
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 D 0 A 8 A 9
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9
15 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10
17 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11
19 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11 D 11 A 12
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 D 0 A 5
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 A 6
10 A 0 A 1 A 2 A 3 A 4 D 2 A 5 A 6 D 3 A 7
輸出範例-----------------
PIC004
PIC001
--
PIC002
PIC003
--
PIC006
PIC007
--
PIC006
PIC001
--
PIC001
PIC002
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC004
PIC005
--
PIC005
PIC003
*/
2017年5月2日 星期二
Z2A,Z1A求組合數
4/28中午及5/1晚上加強，Z2A三位、Z1A三位，共6位到課
Vb2010 -Windows Form專案： 四個按鈕、二個文字方塊(輸入m,n)，一個標籤(輸出)
M取N求組合數(二項係數) 0<=N<=M<=66，分四種解法
程式碼如下：
Dim c(66, 66) As Long '第4種解法使用
'解法一：呼叫函式 pk(k) 算出 k階乘 值， 0<=k<=66 ，但k=21 時溢位
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Label1.Text = pk(m) / pk(n) / pk(m - n)
End Sub
Function pk(ByVal k As Integer) As Long '函式
pk = 1
For i = 2 To k
pk *= i
Next
End Function
'解法二：先呼叫函式 pab(a,m):a*(a+1)*...*m ， a=max(n,m-n)+1
' 再除函式 pk(min(n,m-n)) ，但也在 m=30時溢位
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
If n > m - n Then n = m - n
' 先算 a*...M , a是？ 呼叫 pab(a,m)
Dim a As Integer = m - n + 1
'再除 pk(n)
Label1.Text = pab(a, m) / pk(n)
End Sub
Function pab(ByVal a As Integer, ByVal b As Integer) As Long
'a*a+1*a+2*...b
pab = 1
For i = a To b
pab *= i
Next
End Function
'解法三：純遞迴版呼叫 cmn(m,n)
' cmn(m,n)={0 for m=0, 1 for n=0 , cmn(m-1,n)+cmn(m-1,n-1) for other }
Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Dim t1 As Date = Now
Label1.Text = "純 C ( " & m & " , " & n & " ) = " & CMN(m, n) '呼叫純遞迴版
Label1.Text &= vbNewLine & DateDiff(DateInterval.Second, t1, Now) 'Cmn(29,14)約2秒，Cmn(30,15)約5秒
End Sub
Function CMN(ByVal m As Integer, ByVal n As Integer) As Long
If m = 0 Then Return 0
If n > m - n Then n = m - n '選 n, m-n 中較小的為 n
If n = 0 Then Return 1
c(m, n) = CMN(m - 1, n) + CMN(m - 1, n - 1)
Return c(m, n)
End Function
'解法四：動態規劃，建陣列C(66,66) 遞迴版呼叫 cmn2(m,n)
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
' vb宣告長整數 c(66,66) 初值預設為 0 , 另先設定 n=0時的初值為 1
For i = 0 To 66
c(i, 0) = 1
Next
End Sub
Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Dim t1 As Date = Now
Label1.Text = "陣列 C ( " & m & " , " & n & " ) = " & CMN2(m, n) '呼叫陣列遞迴版
Label1.Text &= vbNewLine & DateDiff(DateInterval.Second, t1, Now) 'Cmn2(66,33)<1秒
End Sub
Function CMN2(ByVal m As Integer, ByVal n As Integer) As Long
If m = 0 Then Return 0 ' m=0傳回 0
If n > m - n Then n = m - n
If c(m, n) <> 0 Then Return c(m, n) '不為0 表示算過
c(m, n) = CMN2(m - 1, n) + CMN2(m - 1, n - 1)
Return c(m, n)
End Function
Vb2010 -Windows Form專案： 四個按鈕、二個文字方塊(輸入m,n)，一個標籤(輸出)
M取N求組合數(二項係數) 0<=N<=M<=66，分四種解法
程式碼如下：
Dim c(66, 66) As Long '第4種解法使用
'解法一：呼叫函式 pk(k) 算出 k階乘 值， 0<=k<=66 ，但k=21 時溢位
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Label1.Text = pk(m) / pk(n) / pk(m - n)
End Sub
Function pk(ByVal k As Integer) As Long '函式
pk = 1
For i = 2 To k
pk *= i
Next
End Function
'解法二：先呼叫函式 pab(a,m):a*(a+1)*...*m ， a=max(n,m-n)+1
' 再除函式 pk(min(n,m-n)) ，但也在 m=30時溢位
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
If n > m - n Then n = m - n
' 先算 a*...M , a是？ 呼叫 pab(a,m)
Dim a As Integer = m - n + 1
'再除 pk(n)
Label1.Text = pab(a, m) / pk(n)
End Sub
Function pab(ByVal a As Integer, ByVal b As Integer) As Long
'a*a+1*a+2*...b
pab = 1
For i = a To b
pab *= i
Next
End Function
'解法三：純遞迴版呼叫 cmn(m,n)
' cmn(m,n)={0 for m=0, 1 for n=0 , cmn(m-1,n)+cmn(m-1,n-1) for other }
Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Dim t1 As Date = Now
Label1.Text = "純 C ( " & m & " , " & n & " ) = " & CMN(m, n) '呼叫純遞迴版
Label1.Text &= vbNewLine & DateDiff(DateInterval.Second, t1, Now) 'Cmn(29,14)約2秒，Cmn(30,15)約5秒
End Sub
Function CMN(ByVal m As Integer, ByVal n As Integer) As Long
If m = 0 Then Return 0
If n > m - n Then n = m - n '選 n, m-n 中較小的為 n
If n = 0 Then Return 1
c(m, n) = CMN(m - 1, n) + CMN(m - 1, n - 1)
Return c(m, n)
End Function
'解法四：動態規劃，建陣列C(66,66) 遞迴版呼叫 cmn2(m,n)
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
' vb宣告長整數 c(66,66) 初值預設為 0 , 另先設定 n=0時的初值為 1
For i = 0 To 66
c(i, 0) = 1
Next
End Sub
Private Sub Button4_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button4.Click
Dim m As Integer = TextBox1.Text
Dim n As Integer = TextBox2.Text
Dim t1 As Date = Now
Label1.Text = "陣列 C ( " & m & " , " & n & " ) = " & CMN2(m, n) '呼叫陣列遞迴版
Label1.Text &= vbNewLine & DateDiff(DateInterval.Second, t1, Now) 'Cmn2(66,33)<1秒
End Sub
Function CMN2(ByVal m As Integer, ByVal n As Integer) As Long
If m = 0 Then Return 0 ' m=0傳回 0
If n > m - n Then n = m - n
If c(m, n) <> 0 Then Return c(m, n) '不為0 表示算過
c(m, n) = CMN2(m - 1, n) + CMN2(m - 1, n - 1)
Return c(m, n)
End Function
Z2A河內塔範例
4/26中午加強，Z2A三位學生到課
Vb2010 -Windows Form專案： 一個按鈕、一個文字方塊，以debug.print輸出至即時運算視窗
程式碼如下：
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim n As Integer = TextBox1.Text
ho(n, "A", "B", "C")
End Sub
Sub ho(ByVal n As Integer, ByVal a As Char, ByVal b As Char, ByVal c As Char)
If n = 1 Then
Debug.Print(n & ":" & a & c)
Return
End If
ho(n - 1, a, c, b)
Debug.Print(n & ":" & a & c)
ho(n - 1, b, a, c)
End Sub
輸出範例：
輸入 4 的輸出如下
1:AB
2:AC
1:BC
3:AB
1:CA
2:CB
1:AB
4:AC
1:BC
2:BA
1:CA
3:BC
1:AB
2:AC
1:BC
輸入 5 的輸出如下
1:AC
2:AB
1:CB
3:AC
1:BA
2:BC
1:AC
4:AB
1:CB
2:CA
1:BA
3:CB
1:AC
2:AB
1:CB
5:AC
1:BA
2:BC
1:AC
3:BA
1:CB
2:CA
1:BA
4:BC
1:AC
2:AB
1:CB
3:AC
1:BA
2:BC
1:AC
Vb2010 -Windows Form專案： 一個按鈕、一個文字方塊，以debug.print輸出至即時運算視窗
程式碼如下：
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim n As Integer = TextBox1.Text
ho(n, "A", "B", "C")
End Sub
Sub ho(ByVal n As Integer, ByVal a As Char, ByVal b As Char, ByVal c As Char)
If n = 1 Then
Debug.Print(n & ":" & a & c)
Return
End If
ho(n - 1, a, c, b)
Debug.Print(n & ":" & a & c)
ho(n - 1, b, a, c)
End Sub
輸出範例：
輸入 4 的輸出如下
1:AB
2:AC
1:BC
3:AB
1:CA
2:CB
1:AB
4:AC
1:BC
2:BA
1:CA
3:BC
1:AB
2:AC
1:BC
1:AC
2:AB
1:CB
3:AC
1:BA
2:BC
1:AC
4:AB
1:CB
2:CA
1:BA
3:CB
1:AC
2:AB
1:CB
5:AC
1:BA
2:BC
1:AC
3:BA
1:CB
2:CA
1:BA
4:BC
1:AC
2:AB
1:CB
3:AC
1:BA
2:BC
1:AC
發表文章
