遞歸模型

將一個(gè)問(wèn)通過(guò)遞歸來(lái)解決的思路是：

　　1. 將原問(wèn)題不斷分解為相同模型的子問(wèn)題。

　　2. 尋找邊界條件，當(dāng)不滿足邊界條件則繼續(xù)分解問(wèn)題，滿足則開(kāi)始求解。

eg：

　　1.求和

　　　　　　模型：

　　　　　　　　　　1. 將原問(wèn)題不斷分解為相同模型的子問(wèn)題(前N項(xiàng)和可以分解為n加上n-1的前n-1項(xiàng)和 Sum(n) -> n + Sum(n-1))。

　　　　　　　　　　2. 尋找邊界條件，當(dāng)不滿足邊界條件則繼續(xù)分解問(wèn)題 (n > 1)，滿足則開(kāi)始求解 (n == 1)。

　　　　　　實(shí)現(xiàn)：

unsigned int sum(unsigned int n)
{
    if(n != 1)
    {
        return (n + sum(n -1));
    }
    else
    {
        return 1;
    }
}

　　2. 求斐波那契數(shù)

　　　　　　模型：

　　　　　　　　　　1. 將原問(wèn)題不斷分解為相同模型的子問(wèn)題（一個(gè)下標(biāo)對(duì)應(yīng)的斐波那契數(shù)為前兩個(gè)斐波那契數(shù)之和 fac(n) -> fac(n-1) + fac(n-2))。

　　　　　　　　　　2. 尋找邊界條件，當(dāng)不滿足邊界條件則繼續(xù)分解問(wèn)題，滿足則開(kāi)始求解 (n == 1 || n == 2)。

　　　　　　實(shí)現(xiàn)：

unsigned int fac(unsigned int n)
{
    if(n > 2)
    {
        return (fac(n - 1) + fac(n - 2));
    }
    else if((n == 1) || (n == 2))
    {
        return 1
    }
    return 0;
}

　　3. 求字符串長(zhǎng)度

　　　　　　模型：

　　　　　　　　　　1. 將原問(wèn)題不斷分解為相同模型的子問(wèn)題（一個(gè)字符串長(zhǎng)度分解為首字符加剩余字符長(zhǎng)度strlen(s) -> 1 + strlen(s-1) ）。

　　　　　　　　　　2. 尋找邊界條件，當(dāng)不滿足邊界條件則繼續(xù)分解問(wèn)題（沒(méi)有遍歷到'\0'），滿足則開(kāi)始求解 (遍歷到'\0')。

　　　　　　實(shí)現(xiàn)：

unsigned int strlen(unsigned char* str)
{
    unsigned int len = 0; 
    if(*str != '\0')
    {
        return (1 + strlen(str));        
    }
    else
    {
        return 0;
    }
}

unsigned int strlen(unsigned char* str)
{
    return str ? (*str ? (1 + strlen(str)) : 0) : 0;
}

反轉(zhuǎn)鏈表：

Node *list_reverse(Node *list)
{
    if(list == NULL && list->next == NULL)
    {
        return list;
    }
    else
    {
        Node *slide = list->next;
        Node *ret = list_reverse(list->next);
        list->next = NULL;
        slide->next =list;
        return ret;
    }
}

合并鏈表：

Node *list_merge(Node* list_1, Node* list_2)
{
    if(list_1 == NULL)
    {
        return list_2;
    }
    if(list_2 == NULL)
    {
        return list_1;
    }
    if(list_1->vlaue < list_2->value)
    {
        Node* list_1_slide = list_1->next;
        Node* ret = list_merge(list_1_slide, list_2);
        list_1->next = ret;
        return list_1;
        // return (list_1->next = list_merge(list_1->next, list_2), list_1);
    }
    else if(list_1->vlaue > list_2->value || list_1->vlaue == list_2->value)
    {
        Node* list_2_slide = list_2->next;
        Node* ret = list_merge(list_1, list_2_slide);
        list_2->next = ret;
        return list_2;
        // return (list_2->next = list_merge(list_1, list_2->next), list_2);
    }
}

漢諾塔

void HanoiTower(int n, char a, char b, char c)// a:src b:mid c:dest
{
    if(n == 1)
    {
        cout << a << --> << b << endl;
    }
    else
    {
        HanoiTower(n - 1, a, c, b);
        HanoiTower(1, a, b, c);
        HanoiTower(n - 1, b, a, c;)
    }
}

全排列：

八皇后：

　　1.創(chuàng)建9*9的邊界，邊界值為2，空白值為0，放置皇后值為1.

　　2. 每一個(gè)cell檢測(cè)其是否可以放置皇后的是檢測(cè)(-1,-1)(0,-1)(1,-1)三個(gè)方向是否有皇后

　　3. 以檢測(cè)一行哪個(gè)位置適合放置皇后為基礎(chǔ)，當(dāng)出現(xiàn)當(dāng)前行沒(méi)有皇后位則返回上一行重新尋找下一個(gè)皇后位。

template <int SIZE>
    class EightQueuen : public TopClass
{
protected:
    enum{ N = SIZE + 2};
    struct cell : public TopClass
    {
        cell(int x = 0, int y = 0) : px(x), py(y) {}
        int px;
        int py;
    };    

    int chessboard[N][N];
    LinkList<cell> m_solution;
    int m_count = 0;

    void init()
    {
        for(int x = 0; x < N; x += N - 1)
        {
            for(int y = 0; y < N ; y++)
            {
                chessboard[x][y] = 2;
                chessboard[y][x] = 2;
            }
        }
        for(int x = 1; x < N - 1; x++)
        {
            for(int y = 1; y < N - 1; y++)
            {
                chessboard[x][y] = 0;
            }
        }
    }
    
    void show_resolution()
    {
        for(m_solution.move(0); !m_solution.end(); m_solution.next())
        {
            cout << "(" << m_solution.current().px << "," << m_solution.current().py << ") " ;
        }
        cout << endl;

        for(int y = 0; y < N; y++)
        {
            for(int x = 0; x < N; x++)
            {
                cout << chessboard[x][y];
            }
            cout << endl;
        }
        cout << endl;
    }

    bool cell_check(int x, int y)
    {
        bool ret = 1, flag = 1,flag1,flag2,flag3;
        int temp_x = x, temp_y = y;
        int dir_1 = 0, dir_2 = 0, dir_3 = 0;

        do{
            temp_x = temp_x + (-1);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag1 = (chessboard[temp_x][temp_y] == 2);

        temp_x = x;
        temp_y = y;
        do{
            temp_x = temp_x + (0);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag2 = (chessboard[temp_x][temp_y] == 2);

        temp_x = x;
        temp_y = y;
        do{
            temp_x = temp_x + (1);
            temp_y = temp_y + (-1);
            flag = (chessboard[temp_x][temp_y] == 0);
        }while(flag);
        flag3 = (chessboard[temp_x][temp_y] == 2);

        return (flag1 && flag2 && flag3);
    }

    bool line_check(int y)
    {
        if(y <= SIZE)
        {
            for(int x = 1; x <= SIZE; x++)
            {
                if(cell_check(x,y))
                {
                    chessboard[x][y] = 1;
                    m_solution.insert(cell(x,y));
                    line_check(y + 1);
                    chessboard[x][y] = 0;
                    m_solution.remove(m_solution.length() - 1);
                }
            }
        }
        else
        {
            show_resolution();
            m_count++;
        }
    }

public:
    EightQueuen()
    {
        init();
    }

    void process()
    {
        line_check(1);
        cout << "Total Solution = " << m_count << endl;
    }
};


int main(void)
{
    EightQueuen<8> eq;
    eq.process();
    return 0;
}

posted @ 2020-02-22 23:01 張不源 Views(1162) Comments(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

張不源

遞歸模型

公告