双向Josephus问题中的分形图形

    Daisuke Minematsu和他的同学们发现,Josephus问题中也隐藏着分形图形。Josephus问题是初学编程的人必然会接触到的一个问题——n个人围成一圈进行1到k报数,每次报到k的人退出游戏(离开这个圆圈),那么最后剩下的那个人是谁。在这里,我们考虑一个Josephus问题的变种:双向Josephus问题。双向Josephus问题中有两个交替进行的报数进程,其中一个按顺时针方向踢出每第k个人,另一个进程则逆时针踢出每第k个人。两个进程交替进行,直到最后只剩一人为止。假如n=10, k=3的话,第一个退出的人是#3,第二个退出的人是#8,第三个退出的人是#6,以后分别是4, 10, 9, 5, 1, 7,最后剩下的人是2。我们用S(n,k)来表示在相应的n值和k值的情况下最后剩下的那个人的编号,对于每个固定的k值,函数S的图象竟然都是一个分形图形。右图是S(n,4)所对应的图象,你可以非常清楚地看到这个图象的自相似性。你可以自己用Mathematica来验证一下。

Read more…

矩阵、随机化与分形图形

    Stetson大学的一个非常可爱的MM(以后本Blog将简称她为Stetson MM)和我分享了一个很神奇的东西。她们正在做一个线性代数的课题研究,题目的大致意思是“用矩阵来构造分形图形”。Stetson MM叫我试着做下面这个实验:对于一个坐标点(x,y),定义下面4个矩阵变换:
    
    然后,初始时令(x,y)等于(0,0),按照 T1 – 85%, T2 – 6%, T3 – 8%, T4 – 1% 的概率,随机选择一个变换对该点进行操作,生成的点就是新的(x,y);把它画在图上后,再重复刚才的操作,并一直这样做下去。我心里觉得奇怪,这为什么会得到分形图形呢?于是我写了一个简单的Mathematica程序:
list = {{0, 0}};
last = {{0}, {0}};
For[i = 0, i < 50000, i++, r = Random[];    If[r < 0.85, last = {{0.83, 0.03}, {-0.03, 0.86}}.last + {{0}, {1.5}},      If[r < 0.91, last = {{0.2, -0.25}, {0.21, 0.23}}.last + {{0}, {1.5}},        If[r < 0.99, last = {{-0.15, 0.27}, {0.25, 0.26}}.last + {{0}, {0.45}},          last = {{0, 0}, {0, 0.17}}.last + {{0}, {0}}        ]      ]    ];    list = Append[list, First[Transpose[last]]]; ] ListPlot[list, PlotStyle -> PointSize[0.002]]

    程序运行的结果真的是令我大吃一惊:竟然真的是一个分形图形!!我不禁再次对数学产生了一种崇敬和畏惧感!!

   

Read more…