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).

         You don't have to write everything until the fourth row to find the fifth row. As I mentioned, each row of characters is symmetrically opposite. So the right side of each row is also symmetrically opposite. If you want to know the fifth row, you can make a table like the one below.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
															D								D				D		D	d

         After that, you can just plug in all the characters which are opposite to the right side of each D.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
															D	u	u	d	u	u	d	d	D	u	u	d	D	u	D	d

         You will ultimately get the same answer, which is (uuduudduuuddudd D uuduuddduuddudd).

         Please let me know if I made any mistakes, thanks a lot.