左神算法基础班4_5折纸问题-白红宇

左神算法基础班4_5折纸问题

阅读量：7078 次

发布时间：2019-06-28

本文共 2074 字，大约阅读时间需要 6 分钟。

Problem:

　　【题目】请把一段纸条竖着放在桌子上，然后从纸条的下边向

　　上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕

　　突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折

　　2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折

　　痕、下折痕和上折痕。

　　给定一个输入参数N，代表纸条都从下边向上方连续对折N次，

　　请从上到下打印所有折痕的方向。例如：N = 1时，打印： down

　　N = 2时，打印： down down up

Solution:

　　首先，计算折痕次数是很好算的，一共是2^0 + 2^1 + ...+ 2^N

　　上下折痕次数也很好算，第一次是下折痕，然后上下折横次数平分总折横次数，下折痕多一次

　　但是不知道怎么使用递归

　　但是找到规律了，就是在上一次折痕的间隙依次插入下、上n次

　　比如：

　　　　第2次折痕为：下下上

　　　　第3次折痕为下上下上

　　　　即：下下上下下上上

Code:

1 #pragma once 2 #include 
     
       3 #include 
      
        4 #include 
       
         5  6 using namespace std; 7  8 struct Node 9 {10     string str;11     Node* next;12     Node(string s = "") :str(s), next(NULL) {}13 };14 15 16 Node* ZheZhi01(const int N)//非递归方式,使用链表插入更方便17 {18     Node* head = new Node("");19     Node* p;20     for (int i = 1; i <= N; ++i)21     {22         p = head;23         if (i == 1)//第一次折横24         {25             Node* q = new Node("down");26             q->next = p->next;27             p->next = q;28             p = p->next->next;29         }        30         while(p)31         {32             Node* q1 = new Node("down");33             q1->next = p->next;34             p->next = q1;35             p = p->next->next;36 37             Node* q2 = new Node("up");38             q2->next = p->next;39             p->next = q2;40             p = p->next->next;41         }42 43     }44     return head;45 }46 47 void ZheZhi02(const int N, int i, bool down)//使用递归方式48 {49     if (i > N)50         return;51     ZheZhi02(N, i + 1, true);52     if (down)53         cout << "down" << '\t';54     else55         cout << "up" << '\t';56     ZheZhi02(N, i + 1, false);57 }58 59 60 void Test()61 {62     int N;63     cout << "请输入折纸次数 N: ";64     cin >> N;65 66     ZheZhi02(N, 1, true);67 68 69     Node* head = NULL;70     head = ZheZhi01(N);71     Node* p = head->next;72     cout << "折纸痕为：" << endl;73     while (p)74     {75         cout << p->str << "\t";76         p = p->next;77     }78     cout << endl;79 80 }