差異處

這裏顯示兩個版本的差異處。

--- programming:acm_temp [2007/04/11 19:08] – 10127 wenpei
+++ programming:acm_temp [2014/02/11 17:17] (目前版本) – sars
@@ 行 1: / 行 1: @@
-Hash、
+  * [[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 ======
@@ 行 17: / 行 27: @@
 利用長除法的原理，將每次的餘數乘以十加上一，然後再用 n 除一次，再取餘數，直到整除，算加了幾次 1 即可。
+或：
+<code>1
+≡ 3 (mod 7)
+≡ 30 ≡ 2
+≡ 20 ≡ 6
+≡ 60 ≡ 4
+^5 ≡ 40 ≡ 5
++ 3 + 2 + 6 + 4 + 5 = 0 (mod 7)
+</code>
+====== 10225 ======
+http://acm.uva.es/p/v102/10225.html
+  B^L ≡ N (mod P)
+Shank's Algorithm
+  m = ceiling( √(P-1) )
+<= i <= m-1
+<= j <= m-1
+  ......
 ====== 10745 ======
@@ 行 22: / 行 54: @@
 字串長度最大 10，依照字典排序印出不會被其他字串所包含(dominant)的字串，若 A 字串單字長度大於 B 字串，代表 B 絕對不可能 dominant A，同 642 方法試試。
+====== 陣列跟指標 ======
+http://www.ptt.cc/man/b93902xxx/D5FE/D814/DA6F/D1/M.1098330150.A.92B.html
+<code>
+        當我們宣告一個陣列時, 其實它的名稱就是一個指標, (或許說法不嚴謹)
+        那它指向哪裡呢? 它指到陣列第一個元素的位址。
+        以下面的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
+</code>
+====== 指標的資料型態 ======
+http://www.ptt.cc/man/b93902xxx/D5FE/D814/DA6F/D1/M.1098330154.A.188.html
+<code>
+        當我們在宣告一個指標(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 不色助教
+</code>