tft每日頭條

 > 科技

 > 大學生算法設計與編程挑戰賽題目

大學生算法設計與編程挑戰賽題目

科技 更新时间:2024-07-23 19:30:40
一、在正方形中填充圓形

前面提到過mtaplotlib支持創建其他幾何圖形。Polygon塊特别有趣,因為我們可以用它繪制具有不同邊數的多邊形。以下是我們繪制一個正方形(每條邊的長度為4的)方式:


''' Draw a square ''' from Matplotlib import pyplot as plt def draw_square(): ax = plt.axes(xlim=(0, 6), ylim=(0, 6)) square = plt.Polygon([(1,1), (5,1), (5,5), (1, 5), closed=True]) ax.add_patch(square) ax.axis('equal') plt.show() if __name__ == '__main__': draw_square()


Polygon對象是通過将頂點左邊編排作為第一個輸入參數來傳入的,因為我們要繪制一個正方形,所以修要傳入四個點的坐标:(1,1), (5,1), (5,5), (1, 5),令closed=True,告訴matplotlib我們要繪制一個封閉的正方形,即起點和終點是相同的。

在這個挑戰中,你将嘗試一個“在正方形中填充圓形”問題的簡化版本。在上述代碼生成的正方形中,可以放入多少個半徑為0.5的圓形?畫出來看一看!下圖展示了最終的輸出結果。

大學生算法設計與編程挑戰賽題目(第六章編程挑戰)1

在5*5的正方形中填充半徑為0.5的圓

這裡的技巧是從正方形的左下角開始,即(1,1)點,然後持續添加圓形到正方形被填滿。以下代碼片段顯示了如何創建一個圓并将其添加到圖形中:


y = 1.5 while y < 5: x = 1.5 while x < 1.5: c = draw_circle(x, y) ax.add_patch(c) # ax.set_gc('r') x = 1.0 y = 1.0


這并不是在正方形中填充圓形的唯一辦法,大家可以自行探讨。

代碼實現:


''' circle_in_square.py Circles in a square ''' from matplotlib import pyplot as plt def draw_square(): square = plt.Polygon([(1, 1), (5, 1), (5, 5), (1, 5)], closed=True) return square def draw_circle(x, y): circle = plt.Circle((x, y), radius=0.5, fc='y') return circle if __name__ == '__main__': ax = plt.gca() s = draw_square() ax.add_patch(s) y = 1.5 while y < 5: x = 1.5 while x < 5: c = draw_circle(x, y) ax.add_patch(c) x = 1.0 y = 1.0 plt.axis('scaled') plt.show()


二、繪制Siperpinski三角

繪制Siperpinski三角(名字來源于波蘭數學家Waclaw Siperpinski)是一個有内嵌其中的較小等邊三角形組成的等邊三角形分形。下圖展示了由10000個點構成的Siperpinski三角。

大學生算法設計與編程挑戰賽題目(第六章編程挑戰)2

由10000個點構成的Siperpinski三角

有趣的是,我們使用繪制蕨類植物的程序在這裡可以同樣繪制繪制Siperpinski三角,隻需要改變變換規則及其概率。以下程序可以用來繪制繪制Siperpinski三角:從點(0,0)開始,并應用以下變換之一。

(1)變換1:

(2)變換2:

(3)變換3:

每個變換被選中地概率相同,均為1/3,這裡的挑戰是編寫一個程序繪制由輸入的指定點數構成的繪制Siperpinski三角。

代碼實現:


''' Draw a Siperpinski ''' from matplotlib import pyplot as plt import random def transformations_1(p): x = p[0] y = p[1] x1 = 0.5*x y1 = 0.5*y return x1, y1 def transformations_2(p): x = p[0] y = p[1] x1 = 0.5*x 0.5 y1 = 0.5*y 0.5 return x1, y1 def transformations_3(p): x = p[0] y = p[1] x1 = 0.5*x 1 y1 = 0.5*y return x1, y1 def get_x_y(n,p): transformations = [transformations_1, transformations_2, transformations_3] x = [0] y = [0] x1, y1 = 0, 0 for i in range(n): t = random.choice(transformations) x1, y1 = t((x1, y1)) x.append(x1) y.append(y1) return x, y if __name__ == '__main__': p = (0, 0) n = int(input('Enter the number of Siperpinski\'s dots: ' )) x, y = get_x_y(n, p) plt.plot(x, y,'o') plt.title('Siperpinski with {0} dots'.format(n)) plt.show()


三、探索Henon函數

1976年,Michel Henon提出了Henon函數,該函數描述了一個點P(x,y)的變換規則:

無論初始點在哪裡(假設它離原點不遠),你将看到随着點的增多,它們開始沿着曲線分布,如下圖:

大學生算法設計與編程挑戰賽題目(第六章編程挑戰)3

Henon函數

這裡的挑戰是編寫一個程序,創建一個以(1,1)為初始點,經20000次該變換規則疊代後的圖形。

這是一個關于動力系統的例子,被所有點所吸引的曲線稱為吸引子。更多關于此函數、動力系統和分形的基本信息,可以參考Kenneth Falconer的著作Fractals:A Very Short Introduction(牛津大學出版社,2013)。

代碼實現(Henon 分形):


import matplotlib.pyplot as plt def transformation(p): x = p[0] y = p[1] x1 = y 1 - 1.4 * x**2 y1 = 0.3*x return x1, y1 def draw_Henon(n, p): x = [1] y = [1] x1, y1 = 1, 1 for i in range(n): x1, y1 = transformation((x1, y1)) x.append(x1) y.append(y1) return x, y if __name__ == '__main__': n = int(input('Enter the numbers of Henon points: ')) p = (1, 1) x, y = draw_Henon(n, p) plt.plot(x, y, 'o') plt.title('Henon with {0} points'.format(n)) plt.show()


四、繪制Mandelbrot集

這裡的挑戰是編寫一個程序繪制Mandelbrot集,這是引用加單規則導出複雜形狀的另一案例(如下圖)。在讨論實現它的具體步驟之前,我們先來了解matplotlib中的imshow()函數。

大學生算法設計與編程挑戰賽題目(第六章編程挑戰)4

Mandelbrot集

imshow()函數

imshow()函數通常用來顯示外部圖像,如JPEFG或PNG圖像。可以參考網址Image tutorial — Matplotlib 2.0.2 documentation中的例子。這裡,我們使用這個函數通過matplotlib來繪制我們新創建的圖像。

考慮笛卡爾平面的一部分,其中x和y’的坐标都位于0到5之間。現在,考慮沿每個軸的6個等距離點:x坐标和y坐标的取值均為0,1,2,3,4,5.如果我們取這些點的笛卡爾積,将得到x-y平面上的36個等距點。坐标分别為(0,0),(0,1), ... ,(0,5),(1,0),(1,1),... ,(1,5),...,(5,5)。現在假設我們要用灰色陰影給每個點上色,也就是說,随機選擇呢一些點為黑色、一些點為白色以及一些點為黑白之間的顔色。下圖就展示了這種情形。

為創建這個圖形,我們必須定義一個包含6個列表的列表,6個列表中的每一個都依次包含着0-10之間的6個整數,每個數字對應于每個點的顔色:0表示黑色,10表示白色。然後我們将這個列表和其他必要的參數一起傳遞給inshow()函數。

創建一個包含多個列表的列表

一個列表可以包含其他列表作為其元素:


>>> l1 = [1,2,3] >>> l2 = [4,5,6] >>> l = [l1, l2]


大學生算法設計與編程挑戰賽題目(第六章編程挑戰)5

6*6的等間距點陰影上色

這裡我們創建一個列表l,它包含了列表l1和列表l2。列表1的第一個元素l[0]與列表l1相同,第二個元素l[1]與列表l2相同。


>>> l[0] [1, 2, 3] >>> l[1] [4, 5, 6]


為引用這兩個列表中的單個元素,我們必須指定兩個索引,l[0][1]指代第一個列表的第二個元素,l[1][2]指代第二個列表的第三個元素,以此類推。

既然我們已經知道如何處理包含多個列表的列表,我們可以擺寫一個程序創建一個類似于上圖的圖形。


import matplotlib.pyplot as plt import matplotlib.cm as cm import random def initialize_image(x_p, y_p): # ① image = [] for i in range(y_p): x_colors = [] for i in range(x_p): x_colors.append(0) image.append(x_colors) return image def color_points(): x_p = 6 y_p = 6 image = initialize_image(x_p, y_p) for i in range(y_p): for j in range(x_p): image[i][j] = random.randint(0,10) # ② plt.imshow(image, origin='lower', extent=(0, 5, 0, 5), cmap=cm.Greys_r, interpolation='nearest') # ③ plt.colorbar() plt.show() if __name__ == '__main__': color_points()


①處的initialize_image()函數創建了一個包含多個列表的列表,其中每一個元素都初始化為0,該函數有兩個輸入參數x_p和y_p,分别對應于x軸和y軸上的點的個數,這實際上意味着初始列表圖像包含x_p個列表,其中每個列表包含y_p個0。

在color_points()函數中,一旦從initialize_image()函數返回一個圖像列表,在②處就給元素image[i][j]分配一個0-10之間的随機整數。當給元素分配随機整數時,我們也給笛卡爾平面上的點(從原點出發沿y軸第i步,沿x軸第j步的點)指定了顔色。這裡很重要的一點就是imshow()函數從image列表中的位置推導點的顔色,而不是依賴于具體的x坐标和y坐标。

然後,在③處調用imshow(函數,并将image作為第一個參數輸入,關鍵字參數origin='lower指定image[0][0]的數字對應于點(0, 0)的顔色,關鍵字參數extent=(0,5, 0, 5)分别将圖像的左下角和右上角的坐标設置為(0, 0)和(5, 5),關鍵字參數cmap=cm.Greys_ r說明我們要創建一個灰度圖像。

最後一個關鍵字參數interpolation='nearest'設定matplotlib 應該給那些沒有指定顔色的點用與其最近的點的顔色上色。這是什麼意思呢?注意我們僅考慮并指定了坐标區域(0, 0)和(5,5)内36個點的顔色,因為該區域内有無窮多個點,所以我們應該告訴matplotlib對那些沒有設定顔色的點如何上色,這就是你在圖中的 每個點周圍看到顔色"框”的原因。

調用colorbar()函數将在圖中顯示一個顔色條, 顯示哪個整 數對應哪個顔色。最後調用show()函數展示圖像。需要注意的是由于使用了random.randint()函數,你的圖像可能會與圖6-15展示的有所不同。

如果你通過在color_points()函數中将x_ p和y_ p設置為20來增加每個軸上的點數,你将會看到一個與圖6-16所示類似的圖像,注意顔色框的尺寸變小了。如果你增加更多的點數,你将看到顔色框的尺寸進一步縮小, 給人的錯覺是每個點都有不同的顔色。

Mandelbrot集的繪制

我們考慮x-y平面上位于點(-2.5,-1.0)和(1.0,1.0)之間的區域,并把每個軸劃分為400個等間距的點,這些點的笛卡爾積将給出該區域内的1600個等間距點,我們把這些點記為。

大學生算法設計與編程挑戰賽題目(第六章編程挑戰)6

20*20的等間距點陰影上色

通過調用之前用到的initialize_ image(函數創建一個 列表image,并将函數中的x_ p和y_ p都設置為400。 然後,為每個生成的點(x, y)執行下述步驟:

(1) 首先,創建兩個複數,和。(我們用j表示 )

(2)創建一個疊代标簽,并将其設置為0,即iteration=0。

(3)創建一個複數

(4)以1為單位增加iteration的值,即iteration= iteration 1。

(5)若abs(z1) < 2 且iteration < max_ iteration, 則返回第(3)步;否則進入第(6)步。max iteration 的值越大,繪制的圖像越詳細,當然花費的時間也就越長。這裡設置max iteration=1000。 (6)将點的顔色設置為iteration 的值,即image[k][i] = iteration。一旦有了完整的image列表,調用imshow()函數,并将extent關鍵字參數設置為(-2.5, -1.0)和(1.0,1.0) 之間的區域。

這個算法通常稱為時間逃逸算法。當一個點達到最大疊代次數時仍在區域内(即複數的模小于2),則該點屬于Mandelbrot 集,将其塗成白色。那些在未達到最大疊代次數就超出區域的點稱為“逃逸”,它們不屬于Mandelbrot集,将其塗成黑色。你可以通過減少和增加每一個軸上點的個數來進行實驗,減少點的個數會導 緻顆粒圖像,而增加點的個數則會産生更加細緻的圖像。

代碼實現:


import matplotlib.pyplot as plt import matplotlib.cm as cm import random x0, x1 = -2.5, 1 y0, y1 = -1.0, 1 def initialize_image(x_p, y_p): image = [] for i in range(y_p): x_colors = [] for i in range(x_p): x_colors.append(0) image.append(x_colors) return image def color_points(): n = 400 max_iteration = 1000 z1 = complex(0, 0) image = initialize_image(n, n) dx = (x1-x0)/(n-1) dy = (y1-y0)/(n-1) x_coords = [x0 i * dx for i in range(n)] y_coords = [y0 i * dy for i in range(n)] for i,x in enumerate(x_coords): for k, y in enumerate(y_coords): z1 = complex(0, 0) iteration = 0 c = complex(x,y) while abs(z1) < 2 and iteration < max_iteration: z1 = z1 ** 2 c iteration = 1 image[k][i] = iteration print(image) plt.imshow(image, origin='lower', extent=(-2.5, -1.0, -1.0, 1.0), cmap=cm.Greys_r, interpolation='nearest') plt.colorbar() plt.show() if __name__ == '__main__': color_points()


,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关科技资讯推荐

热门科技资讯推荐

网友关注

Copyright 2023-2024 - www.tftnews.com All Rights Reserved