這個語法可以驗證一個身分證字號是不是合法的
function out = checkId(id)
first = [10:17 34 18:22 35 23:29 32 30 31 33];
a = uint8(upper(id));
b = zeros(1,11);
b(1:2) = uint8(num2str(first(a(1)-64)));
b(3:11) = uint8(a(2:10))-48;
out = mod([1 9 8 7 6 5 4 3 2 1 1]*b',10);
2012年12月11日 星期二
2012年10月31日 星期三
2012年3月3日 星期六
大地遊戲分配
前幾天學姐叫我安排大地遊戲的分組
數學營有8個小隊，有5個大地遊戲要玩，每個大地遊戲由2個小隊互相對抗
假設每個遊戲花的時間都一樣是T，那麼在同一個時間內可以進行4個遊戲，而且只要5T的時間就可以把整個流程走完
不過安排上有一些規則：
學姐的安排模式是這樣的：
ABCDE表示5個不同的遊戲，T1~T5表示5個時間T，1~8表示第1~第8小隊
作表格如下
為了簡化討論，我們可以不考慮對角線
每個格子裡面放2個小隊，如以上範例
此時安排就比較能找規律了，3個規則也等價於：
我和其他人也是不管怎麼安排，就是會因為規則限制而排不出來
這時候我當然就萌生了一個想法：該不會這個問題無解吧
要證明這題無解，我目前還沒想到方法，不過倒是想嘗試看看寫程式下去跑窮舉
於是決定用MATLAB寫底稿
因為矩陣每一格只能放一個元素，但是這個表格每一格都要放一組數對，所以我想到了一個解決辦法，那就是「質因數法」
現在我們不使用[1 2 3 4 5 6 7 8]代表各小隊，我們改用[2 3 5 7 11 13 17 19]這8個質數
原先的對抗組合，例如第2和第6小隊原本記為(2,6)，現在記為3*13=39(第2和第6個質數)
於是上面3個規則又有等價的敘述了：
現在寫程式的思維是這個樣子的：
我們先製造所有可能的組合，共有C(8,2)=28種，舉例來說，數對記法就是(1,2) (1,3) (1,4) ... (7,8)，質因數法就是2*3=6、2*5=10、2*7=14、...、17*19=323
因為我們將使用質因數法作為此程式的main idea，所以將這28個數字由小排到大，令為w向量，則w=[6 10 14 15 21 ...... 323]
由於規則1和2需要用到互質的條件，現在要建立一個全部元素為1的5*5矩陣，如此一來，接下來的判定基本上就沒什麼問題了
再來是放置數字的規則(註：MATLAB的矩陣是column major，因此A(9)是代表a_42元素)
如果遇到w(k)不符合規則時，則換放入w(k+1)
由A(2)開始放入w(1)，再來移動到A(3)，由w(1)開始嘗試，因為w(1)上一格放過了，違反規則，因此換成w(2)。如此不斷的進行檢查再放入
如果一直換到w(28)都不符合規則時，將數字改回1，檢討上一格A(i-1)的數字，若上一格放入w(m)，則改為w(m+1)，再移回來A(i)，從w(1)開始再試一遍，試到數字放得進去為止
如此不斷重複，直到試出來或是跑完所有可能仍無解為止
於是，MATLAB表示：無解
一開始在猜測有沒有解的時候，有考慮過6個小隊玩4種遊戲的情況，結果一下子就被我排出解來了。另外，4個小隊玩3個遊戲也很容易就發現無解
這是6個小隊要玩4種遊戲的情況(底稿)
v = [2 3 5 7 11 13]; %六個質因數代表六小隊
%把這六個質因數兩兩相乘的組合全部列出來
p = v'*v;
for i = 1:6
for j = 1:6
if (i>=j)
p(i,j) = 0; %把重複的數字去掉
end
end
end
%把這些組合排成列向量w，並去掉0
for i = 1:36
w(i) = p(i);
end
w = sort(w);
w([1:21]) = [];
A = ones(4,4); %建立4*4表格放入數字
i = 1; %A矩陣的位置(column major)，例如A(7)即為第3列第2行的元素
while i<16
if (mod(i,5)==1), i = i + 1; end %逢對角線即跳至下一個數(為了簡化討論，不將元素放至對角線)
I = i - 4*ceil(i/4) + 4; %將i轉換為第I列第J行
J = ceil(i/4);
k = 1; %w(k)即為w向量中第k個元素
while k<=15
%判定若將w(k)放入A(I,J)，是否會與同一列、同一行其他數互質，以及是否重複選取A(i)以前的元素
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
%符合條件者就放入表格中，並且準備判定下一個
A(i) = w(k);
if (mod(i,5)==0) %跳過對角線
i = i + 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i + 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
break;
else
k = k + 1; %不符合條件就換w(k+1)，並且再執行一次上面的判定
end
while (k==16) %當所有w(k)都試過一遍卻沒有符合的條件，就把這一格改成1，並且回頭將上一格的w(k)改成w(k+1)
A(i) = 1;
if (mod(i,5)==2)
i = i - 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i - 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
if (i==0), break; end %所有可能都試過了，但是都不符合條件，才會退到i=0。此時跳出所有迴圈，並宣布"No solution."
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=16), disp(A); end %所有數字都排進去，並且都符合規則，就把結果列出來，並結束迴圈
end
這是n個小隊要玩n/2+1種遊戲的情況(函數)
function out = team(n)
p = 2; s = 1; v = []; m = n/2 + 1;
while s<=n
if isprime(p)==1
v = [v p];
s = s + 1;
end
p = p + 1;
end
P = v'*v;
for i = 1:n
for j = 1:n
if (i>=j)
P(i,j) = 0;
end
end
end
for i = 1:n^2
w(i) = P(i);
end
w = sort(w);
w([1:n*(n+1)/2]) = [];
A = ones(m);
i = 1;
while i<m^2
if (mod(i,m+1)==1), i = i + 1; end
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
k = 1;
while k<=n*(n-1)/2
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
A(i) = w(k)
if (mod(i,m+1)==0)
i = i + 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i + 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
break;
else
k = k + 1;
end
while (k>n*(n-1)/2)
A(i) = 1
if (mod(i,m+1)==2)
i = i - 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i - 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
if (i==0), break; end
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=m^2), disp(A); end
end
數學營有8個小隊，有5個大地遊戲要玩，每個大地遊戲由2個小隊互相對抗
假設每個遊戲花的時間都一樣是T，那麼在同一個時間內可以進行4個遊戲，而且只要5T的時間就可以把整個流程走完
不過安排上有一些規則：
- 同一個遊戲，每小隊都要恰好玩一次
- 同一個時間內，每小隊都要恰好玩一個遊戲(雖然是廢話，不過還是個重要的條件)
- 對抗過的兩小隊，不要再對抗第二次
學姐的安排模式是這樣的：
ABCDE表示5個不同的遊戲，T1~T5表示5個時間T，1~8表示第1~第8小隊
作表格如下
| A | B | C | D | E | |
| T1 | X | 12 | 34 | 56 | 78 |
| T2 | X | ||||
| T3 | X | ||||
| T4 | X | ||||
| T5 | X |
為了簡化討論，我們可以不考慮對角線
每個格子裡面放2個小隊，如以上範例
此時安排就比較能找規律了，3個規則也等價於：
- 每個數字在每一直行恰出現一次
- 每個數字在每一橫列恰出現一次
- 每個格子包含的數對只能出現一次
我和其他人也是不管怎麼安排，就是會因為規則限制而排不出來
這時候我當然就萌生了一個想法：該不會這個問題無解吧
要證明這題無解，我目前還沒想到方法，不過倒是想嘗試看看寫程式下去跑窮舉
於是決定用MATLAB寫底稿
因為矩陣每一格只能放一個元素，但是這個表格每一格都要放一組數對，所以我想到了一個解決辦法，那就是「質因數法」
現在我們不使用[1 2 3 4 5 6 7 8]代表各小隊，我們改用[2 3 5 7 11 13 17 19]這8個質數
原先的對抗組合，例如第2和第6小隊原本記為(2,6)，現在記為3*13=39(第2和第6個質數)
於是上面3個規則又有等價的敘述了：
- 每一直行的數字兩兩互質
- 每一橫列的數字兩兩互質
- 每個格子所裝的數字都不相同
| A | B | C | D | E | |
| T1 | X | 6 | 35 | 143 | 323 |
| T2 | X | ||||
| T3 | X | ||||
| T4 | X | ||||
| T5 | X |
現在寫程式的思維是這個樣子的：
我們先製造所有可能的組合，共有C(8,2)=28種，舉例來說，數對記法就是(1,2) (1,3) (1,4) ... (7,8)，質因數法就是2*3=6、2*5=10、2*7=14、...、17*19=323
因為我們將使用質因數法作為此程式的main idea，所以將這28個數字由小排到大，令為w向量，則w=[6 10 14 15 21 ...... 323]
由於規則1和2需要用到互質的條件，現在要建立一個全部元素為1的5*5矩陣，如此一來，接下來的判定基本上就沒什麼問題了
再來是放置數字的規則(註：MATLAB的矩陣是column major，因此A(9)是代表a_42元素)
如果遇到w(k)不符合規則時，則換放入w(k+1)
由A(2)開始放入w(1)，再來移動到A(3)，由w(1)開始嘗試，因為w(1)上一格放過了，違反規則，因此換成w(2)。如此不斷的進行檢查再放入
如果一直換到w(28)都不符合規則時，將數字改回1，檢討上一格A(i-1)的數字，若上一格放入w(m)，則改為w(m+1)，再移回來A(i)，從w(1)開始再試一遍，試到數字放得進去為止
如此不斷重複，直到試出來或是跑完所有可能仍無解為止
於是，MATLAB表示：無解
一開始在猜測有沒有解的時候，有考慮過6個小隊玩4種遊戲的情況，結果一下子就被我排出解來了。另外，4個小隊玩3個遊戲也很容易就發現無解
這是6個小隊要玩4種遊戲的情況(底稿)
v = [2 3 5 7 11 13]; %六個質因數代表六小隊
%把這六個質因數兩兩相乘的組合全部列出來
p = v'*v;
for i = 1:6
for j = 1:6
if (i>=j)
p(i,j) = 0; %把重複的數字去掉
end
end
end
%把這些組合排成列向量w，並去掉0
for i = 1:36
w(i) = p(i);
end
w = sort(w);
w([1:21]) = [];
A = ones(4,4); %建立4*4表格放入數字
i = 1; %A矩陣的位置(column major)，例如A(7)即為第3列第2行的元素
while i<16
if (mod(i,5)==1), i = i + 1; end %逢對角線即跳至下一個數(為了簡化討論，不將元素放至對角線)
I = i - 4*ceil(i/4) + 4; %將i轉換為第I列第J行
J = ceil(i/4);
k = 1; %w(k)即為w向量中第k個元素
while k<=15
%判定若將w(k)放入A(I,J)，是否會與同一列、同一行其他數互質，以及是否重複選取A(i)以前的元素
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
%符合條件者就放入表格中，並且準備判定下一個
A(i) = w(k);
if (mod(i,5)==0) %跳過對角線
i = i + 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i + 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
break;
else
k = k + 1; %不符合條件就換w(k+1)，並且再執行一次上面的判定
end
while (k==16) %當所有w(k)都試過一遍卻沒有符合的條件，就把這一格改成1，並且回頭將上一格的w(k)改成w(k+1)
A(i) = 1;
if (mod(i,5)==2)
i = i - 2;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
else
i = i - 1;
I = i - 4*ceil(i/4) + 4;
J = ceil(i/4);
end
if (i==0), break; end %所有可能都試過了，但是都不符合條件，才會退到i=0。此時跳出所有迴圈，並宣布"No solution."
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=16), disp(A); end %所有數字都排進去，並且都符合規則，就把結果列出來，並結束迴圈
end
這是n個小隊要玩n/2+1種遊戲的情況(函數)
function out = team(n)
p = 2; s = 1; v = []; m = n/2 + 1;
while s<=n
if isprime(p)==1
v = [v p];
s = s + 1;
end
p = p + 1;
end
P = v'*v;
for i = 1:n
for j = 1:n
if (i>=j)
P(i,j) = 0;
end
end
end
for i = 1:n^2
w(i) = P(i);
end
w = sort(w);
w([1:n*(n+1)/2]) = [];
A = ones(m);
i = 1;
while i<m^2
if (mod(i,m+1)==1), i = i + 1; end
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
k = 1;
while k<=n*(n-1)/2
if (prod(gcd(A(I,:),w(k)))==1 && prod(gcd(A(:,J),w(k)))==1 && sum(sum(A==w(k)))==0)
A(i) = w(k)
if (mod(i,m+1)==0)
i = i + 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i + 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
break;
else
k = k + 1;
end
while (k>n*(n-1)/2)
A(i) = 1
if (mod(i,m+1)==2)
i = i - 2;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
else
i = i - 1;
I = i - m*ceil(i/m) + m;
J = ceil(i/m);
end
if (i==0), break; end
k = find(A(i)==w) + 1;
end
if (i==0), break; end
end
if (i==0), disp('No solution.'); break; end
if (i>=m^2), disp(A); end
end
2012年1月26日 星期四
MATLAB處理最小平方法
之前線代教了最小平方法的算法，用了$A^\mathrm{T}A\mathbf{\hat{x}}=A^\mathrm{T}\textbf{b}$
於是把這個方法丟給MATLAB算，馬上就跑出方程式的係數了
學以致用，很好XD
剛剛不小心找到了更簡單的方法...使用POLYFIT函數
p = polyfit(x,y,n)
##ReadMore##
其中x是所有點的x坐標，y是所有點的y坐標，n是插值多項式次數
輸出值p為一向量(其中的元素為多項式的係數以降冪排列)
其實這個函數本來是要計算多項式插值函數的，不過只要令n=1就是最小平方法了
如果要畫圖的話，再配合POLYVAL函數即可
POLYVAL函數的用法為polyval(p,x)，其中p是多項式，x是要代入的數
兩個函數結合在一起就可以畫出最小平方法的圖了
例如：
心得：那我之前做結報那麼辛苦的用$A^\mathrm{T}A\mathbf{\hat{x}}=A^\mathrm{T}\textbf{b}$幹嘛OTZ
於是把這個方法丟給MATLAB算，馬上就跑出方程式的係數了
學以致用，很好XD
剛剛不小心找到了更簡單的方法...使用POLYFIT函數
p = polyfit(x,y,n)
##ReadMore##
其中x是所有點的x坐標，y是所有點的y坐標，n是插值多項式次數
輸出值p為一向量(其中的元素為多項式的係數以降冪排列)
其實這個函數本來是要計算多項式插值函數的，不過只要令n=1就是最小平方法了
如果要畫圖的話，再配合POLYVAL函數即可
POLYVAL函數的用法為polyval(p,x)，其中p是多項式，x是要代入的數
兩個函數結合在一起就可以畫出最小平方法的圖了
例如：
x = [1 2 3 4 5];
y = [1 2.1 3.1 3.9 4.8];
p = polyfit(x,y,1);
xx = 0:.1:6;
yy = polyval(p,xx);
plot(x,y,'o',xx,yy);
心得：那我之前做結報那麼辛苦的用$A^\mathrm{T}A\mathbf{\hat{x}}=A^\mathrm{T}\textbf{b}$幹嘛OTZ
2012年1月25日 星期三
不動點定理
定理：設函數$f$是從$[0,1]$映到$[0,1]$，且$f\in C[0,1]$，則必存在一個$c\in [0,1]$使得\[f(c)=c\]
##ReadMore##
證明：令$g(x)=f(x)-x$，則\[\begin{align}g(0)&=f(0)\\ g(1)&=f(1)-1\end{align}\]
採用反證法，假設$g(0)g(1)>0$，則表示$f(0)f(1)>f(0)$，由於$0<f(0)\leq 1$，所以左右消去$f(0)$，得\[f(1)>1\]
顯然與命題不符，矛盾，得\[g(0)g(1)\leq 0\]
若$g(0)g(1)=0$，則表示$g(0)=0$或$g(1)=0$，也就是\[f(0)=0\text{ or }f(1)-1=0\]
命題成立
若$g(0)g(1)<0$，則根據中間值定理，存在$c\in [0,1]$使得$g(c)=0$，也就是\[f(c)-c=0\]
證畢
##ReadMore##
證明：令$g(x)=f(x)-x$，則\[\begin{align}g(0)&=f(0)\\ g(1)&=f(1)-1\end{align}\]
採用反證法，假設$g(0)g(1)>0$，則表示$f(0)f(1)>f(0)$，由於$0<f(0)\leq 1$，所以左右消去$f(0)$，得\[f(1)>1\]
顯然與命題不符，矛盾，得\[g(0)g(1)\leq 0\]
若$g(0)g(1)=0$，則表示$g(0)=0$或$g(1)=0$，也就是\[f(0)=0\text{ or }f(1)-1=0\]
命題成立
若$g(0)g(1)<0$，則根據中間值定理，存在$c\in [0,1]$使得$g(c)=0$，也就是\[f(c)-c=0\]
證畢
2012年1月6日 星期五
偉哉，行列式
這學期線代課印象最深刻的部分大概就是行列式吧
只需要三個看似基本的要求，就「唯一」決定行列式的運算規則，並且推導出許多有用的性質
1. $\text{det}(I)=1$
2. 兩列交換，行列式值變號
3. 行列式對第一列是線性的
就是這三條，實在是太酷了
想到以前高中學的行列式性質，其實都是從這三條導出來的，甚至連$\begin{vmatrix}a & b \\ c & d\end{vmatrix}=ad-bc$也可以導，明明在高中當作定義...
訂閱：
文章 (Atom)