前言

當(dāng)前所有算法都使用測試用例運行過，但是不保證100%的測試用例，如果存在問題務(wù)必聯(lián)系批評指正~

在此感謝左大神讓我對算法有了新的感悟認(rèn)識！

問題介紹

原問題
一張紙從下往上對折之后，出現(xiàn)一條折痕，該折痕凸起向下，所以叫“下折痕”，反之如果攤開之后，凸起向上，則叫上折痕。
如果一張紙從下往上對折兩次，則折痕為 [下，下，上]如下圖所示

問：
給定整數(shù)num，表示這張紙按照從下往上折疊的方式折疊num次，攤開之后，從上往下的折痕方向順序是什么？
如：
num = 2
結(jié)果為：下下上

解決方案

原問題：
1、首先想一個問題，如果當(dāng)前紙有一個向下的折痕，那么對于向下的折痕，我們再次對折時，在下面的紙張攤開后會形成向下的折痕，在上面的紙張會形成向上的折痕，因此我們能夠確定，對于每一個向下的折痕都有這個規(guī)律
2、同理我們也可以發(fā)現(xiàn)，對于折疊好的向上的折痕，如果我們再次折疊會出現(xiàn) 下上上
3、綜合上面，還有一個規(guī)律就是每一次的折疊都是對當(dāng)前折痕中的上上下下再次進(jìn)行折疊，所以通過當(dāng)前折痕是上和下即可判斷出折好之后的三元組是什么，如當(dāng)前折痕是下，那么折疊好攤開一定是 下下上三元組，如果是上，那么一定是下上上三元組。
4、理解了上面三條我們就很容易的可以使用完全二叉樹來進(jìn)行折紙問題的計算，下圖是折疊三次的示例

自己可以拿一張紙來折疊一下看看是不是這個規(guī)律，整體的就是這個完全二叉樹的中序遍歷！

代碼編寫

java語言版本

原問題：
方法一:

     /**
     * 二輪測試：紙張折疊num次之后，打印折痕
     * @param num
     */
    private static void printAllFoldersCp1(int num) {
        if (num <= 0) {
            return;
        }
        processCp1(num, null, null);
    }

    /**
     * 中序遍歷，遞歸打印折痕
     * @param num
     * @param parent 父節(jié)點是上還是下
     * @param isLeft 是否左子節(jié)點
     */
    private static void processCp1(int num, Boolean parent, Boolean isLeft) {
        if (num == 0) {
            // 已經(jīng)減到0了直接返回
            return;
        }
        Boolean cur = false;
        // 先判斷自己的是上還是下
        if (parent == null || isLeft == null) {
            // 根節(jié)點直接下
            cur = false;
        }else if (!parent && isLeft) {
            // 根節(jié)點是下并且自己是左子樹
            cur = false;
        }else if (!parent && !isLeft) {
            // 根節(jié)點是下，并且自己是右子樹
            cur = true;
        }else if (parent && isLeft) {
            // 上左子樹
            cur = false;
        }else if (parent && !isLeft) {
            cur = true;
        }
        // 判斷完成后開始下一輪
        processCp1(num - 1, cur, true);
        // 輸出自己
        System.out.println(cur ? "上" : "下");
        // 輸出右邊
        processCp1(num - 1, cur, false);
    }


    public static void main(String[] args) {
        printAllFolders(4);
    }

c語言版本

正在學(xué)習(xí)中

c++語言版本

正在學(xué)習(xí)中

思考感悟

發(fā)現(xiàn)規(guī)律是一個難點：這個規(guī)律文字其實解釋起來很麻煩，但是如果自己找一張紙折疊一下就會發(fā)現(xiàn)其實過程就是一個遞歸的過程，
對折這個動作就非常的“遞歸”，當(dāng)對折的時候折痕兩邊的紙片都會被折疊，同樣是折疊，只是下面的紙片向上折疊，而上面的紙片其實是一個向下折疊的過程，因為攤開的過程是一個翻轉(zhuǎn)的過程，這個需要自己去慢慢體會一下
構(gòu)造遍歷方式也是一個難點：第一想法是先構(gòu)造一個完全二叉樹再遍歷，如此一來，感覺有點憨憨
那么接下來如何能夠節(jié)省空間的中序遍歷呢？
首先num = 3， 我們認(rèn)為root節(jié)點高度為3，那么整體的順序為 左子樹 -> root -> 右子樹
其次，構(gòu)造遞歸函數(shù)的入?yún)?，第一個入?yún)ⅲ簄um不解釋，第二個入?yún)?，parent，第三個入?yún)?dāng)前是左子節(jié)點還是右子節(jié)點
因為只有知道自己的父節(jié)點和自己的位置是左邊還是右邊才能計算出來自己當(dāng)前應(yīng)該是上還是下。

寫在最后

方案和代碼僅提供學(xué)習(xí)和思考使用，切勿隨意濫用！如有錯誤和不合理的地方，務(wù)必批評指正~
如果需要git源碼可郵件給2260755767@qq.com
再次感謝左大神對我算法的指點迷津！文章來源地址http://www.zghlxwxcb.cn/news/detail-430149.html

到了這里，關(guān)于【算法】【算法雜談】折紙問題（完全二叉樹解法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！