Sars' History

本頁是唯讀的，您可以看到原始碼，但不能更動它。您如果覺得它不應被鎖上，請詢問管理員。
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 即可。

或：
<code>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)
</code>

====== 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>
        當我們宣告一個陣列時, 其實它的名稱就是一個指標, (或許說法不嚴謹)
        那它指向哪裡呢? 它指到陣列第一個元素的位址。
        以下面的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>
Sars' History

使用者工具

網站工具

頁面工具
