【アルゴリズム】第一課学習ノート

一、ハーバード大学の知能指数テスト(離散数学)
1.テーマ
皇帝は貧乏人ではなく、守財奴の中にも貧乏人がいるので、そうではないものもあります.

A.皇帝、皇帝

B.守財奴、守財奴

C.守財奴、皇帝

D.皇帝、守財奴

2.解答
この問題は離散数学の論理推理を用いて行うことができ、まず、以下の命題を真と仮定する.

p:この人は皇帝

です

q:この人は貧乏人

です.

r:この人は守財奴

です

皇帝は貧乏人ではありません:p → ¬q

守財奴の中にも貧乏人がいます:∃x(x∈r ⋀ x∈q)

そして、p → ¬qによってその逆否命題q → ¬pを得ることも真であり、
このとき,∃x(x∈r ⋀ x∈q)とq → ¬pにより,仮説三段論から∃x(x∈r ⋀ x∈¬p)が推定され,
一部の人は守财奴で皇帝ではない.
だからこの問題はCを選んで、いくつかの守財奴は皇帝ではありません.
3.関連知識:仮説三段論
仮説三段論は仮説推理とも呼ばれる.仮説推理は常に仮説判断を前提に推理を行う.論理演算子記号には次のように表示されます.

p → q

q → r

だからp → r

古典的な例:
人はみな死ぬ.
ソクラテスは人間で、
だからソクラテスは死ぬ.
参照:Hypothetical syllogism-Wikipedia
二、天秤とコイン
1.テーマ
現在、同じ形の硬貨が16枚あり、そのうちの1枚は偽札であり、偽札は本物より軽量であることが知られている.まず分銅のない天秤を与えて、 に何回秤量してこの偽札を見つけることができますか?
思考:秤量案を与えるのは簡単だが、この方法で使われる秤量回数が最も少ないことをどのように証明するか.
2.解答
コインを3つに分けるには、3つの方法があります.

A:5枚

B:5枚

C:6枚

AとBを先に秤量し、A(またはB)が軽い場合は、5枚の硬貨をさらに2枚、2枚、1枚の3つの山に分けることで秤量することができ、最大2回の秤量で偽札を見つける必要がある.
AとBがバランスをとると、偽札は残りの6枚の硬貨のうち2枚、2枚、2枚の3つの山に分けられ、天秤の両端に2枚ずつ置かれ、平や不平にかかわらず、せいぜい2回の秤量で偽札を見つけることができる.
以上、偽札を見つけるには少なくとも3回秤量する必要があります.
3.理論の下界
1回の天秤秤量で左傾、右傾、バランスの3つが得られる以上、1回の秤量を1ビット符号化とすれば、この符号化は3進数であるが、この問題は、何ビット符号化で16を表すことができるのか.
解答:nビットが必要と仮定すると、3^n >= 16は、両側に対数を取ってn >= 2.52を得、この軽質な偽札を見つけるには少なくとも3回かかることを示している.
三、チェーンテーブル加算
1.テーマ
2つのチェーンテーブルが与えられ、それぞれ2つの非負の整数を表し、それらの数字は逆順序でチェーンテーブルに格納され、各ノードは1つの数字しか格納されず、2つの数の和を計算し、和のチェーンテーブルヘッダポインタを返す.
例:
入力:
2 -> 4 -> 3
5 -> 6 -> 4
出力:
7 -> 0 -> 8
2.分析
両方の数が逆順に格納されているため、ちょうど先頭から後ろに順番に増加することができ、キャリーと2つの数の桁数が異なる場合を考慮することに注意してください.
3.コード

/**
 *       
 */
LinkList add(LinkList L1, LinkList L2){
    LinkList sum = new LNode(0);
    int carry = 0; //   
    LNode *p = sum, *q, *k;
    LNode *p1 = L1->next, *p2 = L2->next;
    while (p1 && p2)
    {
        //        
        q = new LNode(0);
        q->value = (p1->value + p2->value + carry) % 10;
        carry = (p1->value + p2->value + carry) / 10;
        //     
        p->next = q;
        p = q;
        //        
        p1 = p1->next;
        p2 = p2->next;
    }
    //          
    q = p1 ? p1 : p2;
    while(q){
        //        
        k = new LNode(0);
        k->value = (q->value + carry) % 10;
        carry = (q->value + carry) / 10;
        //     
        p->next = k;
        p = k;
        //        
        q = q->next;
    }
    //          
    if(carry)
        p->next = new LNode(carry);
    return sum;
}

四、チェーンテーブルの部分反転
1.テーマ
チェーンテーブルを指定し、チェーンテーブルのmからnの位置の要素を反転させ、直接反転する必要があり、新しい空間を申請できません.(パラメータの範囲が1 <= m <= n <= を満たすと仮定)
たとえば
入力:
1 -> 2 -> 3 -> 4 -> 5, m=2, n=4
出力:
1 -> 4 -> 3 -> 2 -> 5
2.分析
m-1回空転し、m-1番目のノード、すなわち反転を開始した最初のノードの前駆体をheadとし、headを開始ノードとしてn-m回遍歴し、i番目の遍歴したノードをヘッド挿入法でheadのnextに挿入し、最後に反転後のチェーンテーブルを得る.
3.コード
概略図:

/**
 *    m n    
 */
LinkList reverse(LinkList &L, int m, int n){
    LNode* p = L->next, *pre, *phead, *pnext;
    int i = 0;
    for(; i < m-1; i++){
        phead = p;
        p = p->next;    
    }  
    pre = p;
    p = p->next;
    for(; i < n; i++){
       pnext = p->next;
       p->next = phead->next;
       phead->next = p;
       pre->next = pnext;
       p = pnext; 
    }
    return L;
}

五、チェーンテーブルの区分
1.テーマ
1つのチェーンテーブルと1つの数xを与え、チェーンテーブルを2つの部分に分割し、分割後のxより小さいノードが前にあり、xと大きいノードが後ろにあるようにする.この2つのセクションでは、要素は元のチェーンテーブルの出現順序を維持します.
たとえば
与えられたチェーンテーブル1->4->3->2->5->2およびx=3
1->2->2->4->3->5を返します
2.分析
2つのポインタp 1とp 2をそれぞれ申請し、xより小さいものをキューp 1に追加し、xと等しいものをp 2に追加し、最後にp 2をp 1の末端にリンクすればよい.このアルゴリズムの時間的複雑度はO(N)であり,空間的複雑度はO(1)であり,このアルゴリズムは実際に 。を説明している.
3.コード

/**
 *     
 */
LinkList divide(LinkList &L, int x){
    // p_left_head   x   
    // p_right_head     x   
    LNode* p_left_head = new LNode(-1);
    LNode* p_right_head = new LNode(-1);
    //                  
    LNode* left = p_left_head;
    LNode* right = p_right_head;
    LNode* p = L->next;
    while(p){
        if(p->value < x){
            left->next = p;
            left = p;
        } else {
            right->next = p;
            right = p;
        }
        p = p->next;
    }
    //  right   left  
    left->next = p_right_head->next;
    right->next = NULL;
    //       L
    L->next = p_left_head->next;
    //           
    delete p_left_head;
    delete p_right_head; 
    return L;
}

六、並べ替えチェーンテーブルの重量除去
1.テーマ
順序付けされたチェーンテーブルを指定し、その重複要素を削除し、重複要素が初めて現れたノードだけを保持します.さらに、重複要素をすべて削除するとしたら?
2.コード

/**
 *        (           )
 */
LinkList remove_repeat_item_1(LinkList& L){
    LNode *p = L, *q = p->next;
    while (q){
        if(q->value == p->value){
            p->next = q->next;
            delete q;
        } else 
            p = q;
        q = p->next;
    }
    return L;
}

/**
 *        (        )
 */
LinkList remove_repeat_item_2(LinkList& L){
    LNode *pre = L, *cur = L->next, *next;
    bool isDup;
    while (cur)
    {
        next = cur->next;
        isDup = false;
        while (next && (cur->value == next->value))
        {
            pre->next = next;
            delete cur;
            cur = next;
            next = cur->next;
            isDup = true;
        }
        if(isDup){
            //   cur      ，  
            pre->next = next;
            delete cur;
        } else {
            pre = cur;
        }
        cur = next;
    }
    return L;
}