* [[http://www.csie.ntnu.edu.tw/~u91029/index.html|演算法筆記]]
Hash、大數、質因數分解、質數
====== 146 ======
給一個字串，找出下一個權重的字串。可用 algorithm.h 中的 bool next_permutation(iterator_start, iterator_end);
abaacb -> ababac
cbbaa -> no solution(lastest one)
另解：從最右邊開始往左找，直到找不到遞增關係停止，前面一樣，然後找下一個即可。如 abaacb 中，最右邊 cb 為遞增，但到 acb 即非遞增，因此可找 acb 的下一個 bac，然後前面一樣。
====== 642 ======
http://acm.uva.es/p/v6/642.html
將字典中的每個字都放到一個 1~26 的陣列中，代表字母出現的次數
====== 719 ======
http://acm.uva.es/p/v7/719.html
頭尾相連，哪個位置開始會是最小字串
====== 10127 ======
http://acm.uva.es/p/v101/10127.html
要有多少 1 可以讓 n 整除。ex: 111111 / 7 = 15873 Ans: 6
利用長除法的原理，將每次的餘數乘以十加上一，然後再用 n 除一次，再取餘數，直到整除，算加了幾次 1 即可。
或：
1
10 ≡ 3 (mod 7)
100 ≡ 30 ≡ 2
1000 ≡ 20 ≡ 6
10000 ≡ 60 ≡ 4
10^5 ≡ 40 ≡ 5
1 + 3 + 2 + 6 + 4 + 5 = 0 (mod 7)
====== 10225 ======
http://acm.uva.es/p/v102/10225.html
B^L ≡ N (mod P)
Shank's Algorithm
m = ceiling( √(P-1) )
0 <= i <= m-1
0 <= j <= m-1
......
====== 10745 ======
http://acm.uva.es/p/v107/10745.html
字串長度最大 10，依照字典排序印出不會被其他字串所包含(dominant)的字串，若 A 字串單字長度大於 B 字串，代表 B 絕對不可能 dominant A，同 642 方法試試。
====== 陣列跟指標 ======
http://www.ptt.cc/man/b93902xxx/D5FE/D814/DA6F/D1/M.1098330150.A.92B.html
當我們宣告一個陣列時, 其實它的名稱就是一個指標, (或許說法不嚴謹)
那它指向哪裡呢? 它指到陣列第一個元素的位址。
以下面的code為例:
int a[5];
這宣告了一個陣列, 名為 a, 大小為 5 個 int.
我假設它在記憶體裡長這樣:
─┬──┬──┬──┬──┬──┬─
...│a[0]│a[1]│a[2]│a[3]│a[4]│...
─┴──┴──┴──┴──┴──┴─
我們知道可以用 name[index] 這樣的形式來取值, 這正
是陣列天生的性質 -- 連續的記憶體位置, 所以才能直接
透過 index 算出來..(超秘: index[name] 也是一樣的效果唷!!)
而前面提到的, 陣列的名稱是一個指標, 所以呢, 下面的
等式是成立的:
a == &a[0] == &(0[a])
*a == a[0] == 0[a]
我們都知道 & 當作一元運算子(unary operator, 也就是只有
一個運算元的運算子)時, 在 C 裡是作為 "取位址" 的用途,
所以 &a[0] 自然是解釋作 取第一個元素的位址, 也就等於 a
的值了。而 * 作一元運算子時, 就是 "從這個位址取值" 的
意思, 所以 *a 就是取第一個元素的值, 當然就等於 a[0] 囉
既然 name[index] 幫我們作了記憶體計算的工作, 我們當然
也可以用指標來做類似的動作, 像上面的例子, 如果我有了 a
的值, 要怎麼算出 a[1] 的位址呢? 很簡單:
a + 1
咦? 不是說 int 佔 4 bytes嗎?, 為什麼 +1 就好了而不是 +4 ?
因為 compiler 看得出來左邊的運算元是一個 int *, 所以它在
做加法時, 會自動對應 sizeof(int) 的值來作 offset, 所以
a 和 a+1 的值, 你輸出後其實是相差4的 (可以自己實驗..)
所以導出下列等式:
a + i == &a[i] == &i[a];
*(a+i) == a[i] == i[a];
所以我們在函式間傳遞陣列時, 可以把它當成 int * 來傳,
就是這個道理 (多維陣列下面會講)
至於多維陣列呢? 我以一個二維陣列來做說明
int b[3][2];
這樣我們該怎麼解讀呢? 其實可以一步步來, 好比一維陣列的解
讀一樣: b[3] 是一個 int[2] 的陣列, 所以在記憶體中是長這樣:
← b[0] →← b[1] →← b[2] →
┬────┬────┬────┬────┬────┬────┬─
... │ b[0][0]│ b[0][1]│ b[1][0]│ b[1][1]│ b[2][0]│ b[2][1]│...
┴────┴────┴────┴────┴────┴────┴─
而其記憶體計算的方式跟上述一維陣列的例子相仿:
b == b[0] == &b[0][0]
*(*(b+1)) == b[1][0] == *(b[0] + 2)
// 你可以看得懂上面這行就表示你懂了
因為這樣, 所以在函數傳遞時, 除了第一維以外, 其它維度的大小
都必須宣告清楚, 否則compiler根本不知道該怎麼計算像 b[0] + 1
的結果 (以此例而言, 它一定要知道 b[3] 是一個 int[2], 才知道
b[0] + 1 是要加 8啊)
所以本來我們都會這樣做:
void foo(int array[][2])
{
....
}
int b[3][2];
foo(b);
但是學會指標後我們可以這麼做:
void foo(int** array, int size1, size2)
{
.....
}
int b[3][2];
foo( (int **)b);
不過這樣的話, 在 foo 裡面就要自己計算記憶體位址了,
再更高維的就以此類推吧...
[ Pointer array / Pointer to array]
這裡開始進入火星文區
以下兩個例子:
int* a[3];
int (*b)[3];
你知道它們差別在哪裡嗎? 用文字敘述的話就是:
int* a[3]; 是一個陣列名為 a, 有三個元素, 每個元素的資料型態是 int*
int (*b)[3]; 則是一個指標名為 b, 它指向一個 int[3] 的陣列
用圖形來看就是:
int data[3];
int* a[3]; int (*b)[3]; b = data;
a → ├─┤ b → data → ├────────┤
│ → │data[0]==(*b)[0]│
├─┤ ├────────┤
│ → │data[1]==(*b)[1]│
├─┤ ├────────┤
│ → │data[2]==(*b)[2]│
├─┤ ├────────┤
我想看圖之後就會非常了解了吧 :)
如果這個圖沒有問題的話, 那麼你陣列跟指標的觀念應該是算及格了 :p
====== 指標的資料型態 ======
http://www.ptt.cc/man/b93902xxx/D5FE/D814/DA6F/D1/M.1098330154.A.188.html
當我們在宣告一個指標(pointer)時, 這個指標本身也是一個變數,
它存著某個記憶體位址, 所以我們可以利用這個位址來取值或是做
其它的記憶體上的運算。那這個變數在記憶體中佔幾個 byte 呢?
這個答案跟 int 一樣: machine-dependent, 以現在32-bit的系統
及 compiler 而言, 指標變數也是佔32bits == 4 bytes的大小,
而它內容, 也是用2進位表示的整數(unsigned)。所以以下的每一個
指標都是 4bytes 的變數:
char* a; short* b; int* c; double* d;
它們的差異, 就在透過它們來取值時, 依照它指向的資料型態, 來
取出 n bytes 來取值。比方說 *d 就是從 d 開始抓 8bytes 出來
並且照 IEEE 754 的表示法來得到這個浮點數的值。
陣列的話, 陣列指標(陣列名)就是第一個元素的位址。
就算以後教到 struct 也是同樣的道理。
[函數指標]
既然, 基本型態的變數, 陣列 等等都有其對應的指標, 那為什麼
函式會沒有呢? 它一樣要在記憶體中佔個位子, 所以當然也會有
指標指到它的位址呀, 不然你要怎麼呼叫它??? <---- 對! 重點來
了, 你呼叫函數的時候, 不就是用它的名字來呼叫嗎? 它就像陣列
一般, 函數的名稱就是它的pointer, 而一個函數如果像這樣:
char foo(short a, int b, float c, double d, int f[]);
那麼 foo 就是這個函數的指標, 那它指到什麼資料型態呢? 它指到
char (short, int, float, double, int [])
這個資料型態, 也許你會覺得很奇怪, 但回想一下上集中陣列的例子
int **a;
int data[3];
int (*b)[3];
b = &data; /* 注意: 跟函數指標有點出入的地方! */
a = &((int *) data); /* 補充範例 */
b 就是一個指到 int [3] 的指標呀, 同樣的精神就可以套用在 foo
上面啦。而如果我們要宣告一個這樣資料型態的指標, 就可以如下所示:
char (*p2f)(short, int, float, double, int []);
p2f = foo; /* 注意: 跟陣列的例子有出入 */
/* p2f = &foo 也可以, 你可以想想為什麼 */
這樣一來我們就可以用 p2f 指到 foo 這個函式了, 所以也就可以
char ch;
ch = p2f(a, b, c, d, e, f);
/* 同上 ch = (*p2f)(a, b, c, d, e, f); 也一樣*/
就好像真的去使用 foo 一樣, 雖然我們是用 p2f。
所以呢, 利用這樣的觀念, 就可以輕易解決掉使徒五最關鍵的部分
-- functions 的宣告及設定。(再說下去就要變答案了....orz)
[typedef]
typedef 關鍵字是用來替資料型態取個「別名」(alias), 好比說
你叫出 「上官林傑」、「ericsk」、「無敵親切超級帥氣助教」
都可以指到我, 除了上官林傑是我的本名之外, 其它的就是我的別名 (挺)
比方說我們可以
typedef long long INT64;
typedef int INT32;
這樣表示幫 int 型態取了個別名 INT32, 之後我們就可以用它來
宣告變數。(也幫 long long 取了個別名叫 INT64)
為什麼要介紹這個呢？這樣便可以幫我們簡化一些東西, 像之前
的例子: int (*b)[3]; 我們知道 b 是一個指標指向 int[3]
可是我們卻不能用 int[3] *b; 來宣告 b, 這樣實在不是很直覺,
但若是用了typedef
typedef int (*P2I3)[3];
P2I3 b;
b = &data;
如此一來, 這個例子中的 b 就跟 int (*b)[3]; 的 b 是一樣的
資料型態, 而函式指標也可以這麼做: (引上述例子)
typedef char (*PF)(short, int, float, double, int[]);
PF p2f;
p2f = foo;
所以用這樣的表示法, 是不是就直覺多了呢?
[後記]
其實打這兩篇, 除了賺P幣之外, 就是一次回答多數同學的疑問 (FAQ)
除了能讓大家輕鬆解決使徒五之外, 也能再多多練習暴走的指標..
希望大家都能快樂學習 迅速成長 :D
by 不色助教