Week 6: Algorithm Questions

Algorithm Questions

         Before this week's lecture, I attempted to solve the problem of folding paper, but I failed. After the lecture, I tried it again, and applied what our professor taught us in lecture. I created a plan, and I was ready to accept that it would be wrong. To my surprise, it works. I checked this way several times to make sure it is correct. However, if you find I am wrong, please leave me a comment to inform me that. Here is my way of solving this problem. (It is a little bit long.)

         First of all, I want to know how many creases the paper contains corresponding to how many times I fold it. I made a table for these numbers.

         #Time #Creases

   1       1

         2       3

         3       8

         4       15

         Then I found that the number of creases is (2^n)-1, where n is the nth time of folding the paper.

         So

         #Time #Creases

   1       2^1-1=1

         2       2^2-1=3

         3       2^3-1=8

         4       2^4-1=15

         Secondly, I want to find the pattern of creases. I made another table.

         #Time #Pattern

         1       D

         2       uDd

         3       uudDudd

         4       uuduuddDuuddudd

         Each row of characters is symmetrically opposite due to the way of folding the paper (Every time you fold the paper from left to right). Each row has a central character which must be D. The last character of each row must be d. Besides that, I discovered that the right side of nth row's D is exactly the entire row of n-1.

         I applied the rules which I discovered to find the 5^th row.

         It should be (uuduudduuuddudd D uuduuddduuddudd).