فرض کنید قطعه زمین مربعی شکل با ابعادی از توان عدد دو داریم. مثلا با ابعاد 16 متر:
هدف فرش کردن این قطعه زمین با استفاده از موزاییکهایی با شکلهای زیر است:
به قسمی که یکی از خانههای زمین شطرنجی شده فوق پوشیده نشود. میتوان فرض کرد از این خانه برای احداث باغچه یا حوضچه کوچکی استفاده خواهد شد. توجه داشته باشید که اندازه اضلاع مربعهای کوچک موزاییکها نیز همانند صفحه شطرنجی فوق یک متر است. در ضمن حق شکستن این موزاییکها به تکههای کوچکتر را نداریم.
به عنوان مثال، فرض کنید زمینی با ابعاد چهار متر داریم، که میخواهیم خانه مشخص شده زیر پوشیده نشود:
میتوان این زمین را به صورت زیر فرش کرد:
اما راه حل کلی مساله چیست؟
با توجه به اینکه ابعاد زمین توانی از عدد دو است، روش تقسیم و حل را برای پوشانیدن این قطعه زمین امتحان میکنیم.
بر اساس تعریف روش تقسیم و حل، باید بتوان مساله را به زیرمسائلی از نوع خود مساله تقسیم کرد، و با ادغام نتایج حاصل از آنها، به نتیجه اصلی دست پیدا کرد. چون ابعاد این قطعه زمین توانی از عدد دو است، پس میتوان آن را به دو قسمت تقسیم کرد. با تقسیم طول و عرض زمین به دو قسمت، چهار قطعه زمین کوچکتر به دست میآید:
اما همه این چهار قطعه زمین شرایط مساله اصلی را دارا نیستند. در صورت مساله عنوان شده است که باید از پوشانیدن یکی از خانههای قطعه زمین صرف نظر کرد. از چهار قطعه زمین کوچکتر تنها یکی از آنها این شرط را برآورده میکند و بقیه قطعه زمینها باید به طور کامل پوشانیده شوند.
این نقص را میتوان با به کار بردن یک موزاییک حل کرد:
این موزاییک در مرکز قطعه زمین به قسمی قرار داده شده است که هر کدام از سه قسمت مربعی شکل آن، داخل یکی از قطعه زمینهای کوچکتری قرار گرفته است که شرط مساله را برآورده نمیکردند. با این کار، داخل این قطعه زمینها نیز خانهای وجود دارد که نباید پوشانیده شود. چرا که از قبل توسط موزاییکی پوشیده شده است. به این ترتیب همه چهار قطعه زمین کوچکتر خانهای دارند که نیاز به پوشش ندارد. در نتیجه میتوان بر روی حل مساله در قطعه زمینهای کوچکتر تمرکز کرد:
اگر قطعه زمینهای کوچکتر از ابعاد دو باشند، به سادگی با قرار دادن یک موزاییک میتوان آن را پوشانید:
پس به طور خلاصه، برای حل مساله باید به این صورت عمل کنیم:
قطعه زمین را از طول و عرض به دو قسمت تقسیم میکنیم. با این تقسیمات چهار قطعه زمین کوچکتر حاصل میشود. تکه مربعی شکل کوچکی که نباید پوشانیده شود داخل یکی از این قطعه زمینهای کوچکتر قرار خواهد گرفت. یک موزاییک را در مرکز قطعه زمین طوری قرار میدهیم که هر کدام از سه قطعه زمین کوچکتر دیگر یک قسمت از موزاییک را در خود داشته باشند. به این ترتیب چهار قطعه زمین کوچکتر به دست میآید که در هر کدام از آنها خانهای وجود دارد که نباید پوشانیده شود. ابعاد آنها نیز به طور حتم عددی از توان دو است. در نتیجه میتوان از همین روش برای پوشانیدن آنها استفاده کرد. تقسیمات متوالی قطعه زمینها به تکههای کوچکتر تا زمانی ادامه پیدا میکند که به قطعه زمینهایی با ابعاد دو متر برسیم. در این حالت به سادگی میتوان با یک موزاییک زمین را به طور کامل پوشش داد.
تعداد موزاییکها:
یکی از سوالات مهم این است که برای پوشانیدن قطعه زمین با توجه به شرایط مساله چند موزاییک لازم است؟
فرض کنید ( T( n تعداد موزاییکهای لازم برای پوشانیدن زمینی با ابعاد n باشد. با توجه به استفاده از روش تقسیم و حل، هر قطعه زمین به چهار قطعه زمین با ابعاد نصف تبدیل میشود. اما برای این تبدیل از یک موزاییک استفاده میکنیم. پس میتوان نوشت:
T( n ) = 4 T( n / 2 ) + 1
اگر ابعاد قطعه زمین دو متر باشد، تنها یک موزاییک برای پوشانیدن آن کافی است:
T( 2 ) = 1
پس میتوان گفت تعداد موزاییکهای لازم برای پوشش زمینی با ابعاد n از رابطه بازگشتی زیر به دست میآید:
T( n ) = 4 T( n / 2 ) + 1 , T( 2 ) = 1
با حل این رابطه بازگشتی با استفاده از روشهای متعارف ریاضی نتیجه زیر حاصل میشود:
T( n ) = ( n2 – 1 ) / 3
اما راه سادهتری هم برای به دست آوردن این رابطه وجود دارد.
در داخل قطعه زمینی با ابعاد n، تعداد n2 خانه مربعی شکل وجود دارد. یکی از این خانهها نباید پوشانیده شود. پس n2 – 1 خانه مربعی شکل کوچک داریم که باید توسط موزاییکها پوشانیده شوند. هر موزاییک نیز سه خانه مربعی شکل کوچک را پوشش میدهد. پس در مجموع به n2 – 1 ) / 3 ) موزاییک نیاز خواهیم داشت.
function placeItems(sp:Point,ep:Point,pp:Point):void { var mp:Point = new Point(0,0); mp.x = Math.floor((ep.x+sp.x)/2); mp.y = Math.floor((ep.y+sp.y)/2); if(sp.x!= ep.x sp.y != ep.y) { if(pp.x <= mp.x && pp.y mp.x && pp.y <= mp.y) { chessMark2(new Point(mp.x,mp.y+1),4); placeItems(new Point(sp.x,sp.y),new Point(mp.x,mp.y),new Point(mp.x,mp.y)); placeItems(new Point(sp.x,mp.y+1),new Point(mp.x,ep.y),new Point(mp.x,mp.y+1)); placeItems(new Point(mp.x+1,mp.y+1),new Point(ep.x,ep.y),new Point(mp.x+1,mp.y+1));
placeItems(new Point(mp.x+1,sp.y),new Point(ep.x,mp.y),new Point(pp.x,pp.y)); } else if(pp.x mp.y) { chessMark2(new Point(mp.x+1,mp.y),2); placeItems(new Point(sp.x,sp.y),new Point(mp.x,mp.y),new Point(mp.x,mp.y)); placeItems(new Point(mp.x+1,sp.y),new Point(ep.x,mp.y),new Point(mp.x+1,mp.y)); placeItems(new Point(mp.x+1,mp.y+1),new Point(ep.x,ep.y),new Point(mp.x+1,mp.y+1));
placeItems(new Point(sp.x,mp.y+1),new Point(mp.x,ep.y),new Point(pp.x,pp.y)); } else if(pp.x > mp.x && pp.y > mp.y) { chessMark2(new Point(mp.x,mp.y),1); placeItems(new Point(sp.x,sp.y),new Point(mp.x,mp.y),new Point(mp.x,mp.y)); placeItems(new Point(mp.x+1,sp.y),new Point(ep.x,mp.y),new Point(mp.x+1,mp.y)); placeItems(new Point(sp.x,mp.y+1),new Point(mp.x,ep.y),new Point(mp.x,mp.y+1));
placeItems(new Point(mp.x+1,mp.y+1),new Point(ep.x,ep.y),new Point(pp.x,pp.y)); } } } *********************************************************** 1 // Fig. 17.22: DrawStarsForm.cs 2 // Using paths to draw stars on the form. 3 using System; 4 using System.Drawing; 5 using System.Drawing.Drawing2D; 6 using System.Windows.Forms; 7 8 // draws randomly colored stars 9 public partial class DrawStarsForm : Form 10 { 11 // default constructor 12 public DrawStarsForm() 13 { 14 InitializeComponent(); 15 } // end constructor 16 17 // create path and draw stars along it 18 private void DrawStarsForm_Paint(object sender, PaintEventArgs e) 19 { 20 Graphics graphicsObject = e.Graphics; 21 Random random = new Random(); 22 SolidBrush brush = 23 new SolidBrush( Color.DarkMagenta ); 24 25 // x and y points of the path 26 int[] xPoints = 27 { 55, 67, 109, 73, 83, 55, 27, 37, 1, 43 }; 28 int[] yPoints = 29 { 0, 36, 36, 54, 96, 72, 96, 54, 36, 36 }; 30 31 // create graphics path for star; 32 GraphicsPath star = new GraphicsPath(); 33 34 // create star from series of points 35 for ( int i = 0; i <= 8; i += 2 ) 36 star.AddLine( xPoints[ i ], yPoints[ i ], 37 xPoints[ i + 1 ], yPoints[ i + 1 ] ); 38 39 // close the shape 40 star.CloseFigure(); 41 42 // translate the origin to (150, 150) 43 graphicsObject.TranslateTransform( 150, 150 ); 44 45 // rotate the origin and draw stars in random colors 46 for ( int i = 1; i <= 18; i++ ) 47 { 48 graphicsObject.RotateTransform( 20 ); 49 50 brush.Color = Color.FromArgb( 51 random.Next( 200, 255 ), random.Next( 255 ), 52 random.Next( 255 ), random.Next( 255 ) ); 53 54 graphicsObject.FillPath( brush, star ); 55 } // end for 56 } // end method DrawStarsForm_Paint 57 } // end class DrawStarsForm ************************************************************************** 1 // Fig. 17.21: DrawShapes.cs 2 // Drawing various shapes on a Form. 3 using System; 4 using System.Drawing; 5 using System.Drawing.Drawing2D; 6 using System.Windows.Forms; 7 8 // draws shapes with different brushes 9 public partial class DrawShapesForm : Form 10 { 11 // default constructor 12 public DrawShapesForm() 13 { 14 InitializeComponent(); 15 } // end constructor 16 17 // draw various shapes on Form 18 private void DrawShapesForm_Paint( object sender, PaintEventArgs e ) 19 { 20 // references to object we will use 21 Graphics graphicsObject = e.Graphics; 22 23 // ellipse rectangle and gradient brush 24 Rectangle drawArea1 = new Rectangle( 5, 35, 30, 100 ); 25 LinearGradientBrush linearBrush = 26 new LinearGradientBrush ( drawArea1, Color.Blue, 27 Color.Yellow, LinearGradientMode.ForwardDiagonal ); 28 29 // draw ellipse filled with a blue-yellow gradient 30 graphicsObject.FillEllipse( linearBrush, 5, 30, 65, 100 ); 31 32 // pen and location for red outline rectangle 33 Pen thickRedPen = new Pen( Color.Red, 10 ); 34 Rectangle drawArea2 = new Rectangle( 80, 30, 65, 100 ); 35 36 // draw thick rectangle outline in red 37 graphicsObject.DrawRectangle( thickRedPen, drawArea2 ); 38 39 // bitmap texture 40 Bitmap textureBitmap = new Bitmap( 10, 10 ); 41 42 // get bitmap graphics 43 Graphics graphicsObject2 = 44 Graphics.FromImage( textureBitmap ); 45 46 // brush and pen used throughout program 47 SolidBrush solidColorBrush = 48 new SolidBrush( Color.Red ); 49 Pen coloredPen = new Pen( solidColorBrush ); 50 51 // fill textureBitmap with yellow 52 solidColorBrush.Color = Color.Yellow; 53 graphicsObject2.FillRectangle( solidColorBrush, 0, 0, 10, 10 ); 54 55 // draw small black rectangle in textureBitmap 56 coloredPen.Color = Color.Black; 57 graphicsObject2.DrawRectangle( coloredPen, 1, 1, 6, 6 ); 58 59 // draw small blue rectangle in textureBitmap 60 solidColorBrush.Color = Color.Blue; 61 graphicsObject2.FillRectangle( solidColorBrush, 1, 1, 3, 3 ); 62 63 // draw small red square in textureBitmap 64 solidColorBrush.Color = Color.Red; 65 graphicsObject2.FillRectangle( solidColorBrush, 4, 4, 3, 3 ); 66 67 // create textured brush and 68 // display textured rectangle 69 TextureBrush texturedBrush = 70 new TextureBrush( textureBitmap ); 71 graphicsObject.FillRectangle( texturedBrush, 155, 30, 75, 100 ); 72 73 // draw pie-shaped arc in white 74 coloredPen.Color = Color.White; 75 coloredPen.Width = 6; 76 graphicsObject.DrawPie( coloredPen, 240, 30, 75, 100, 0, 270 ); 77 78 // draw lines in green and yellow 79 coloredPen.Color = Color.Green; 80 coloredPen.Width = 5; 81 graphicsObject.DrawLine( coloredPen, 395, 30, 320, 150 ); 82 83 // draw a rounded, dashed yellow line 84 coloredPen.Color = Color.Yellow; 85 coloredPen.DashCap = DashCap.Round; 86 coloredPen.DashStyle = DashStyle.Dash; 87 graphicsObject.DrawLine( coloredPen, 320, 30, 395,v150 ); 88 } // end method DrawShapesForm_Paint 89 } // end class DrawShapesForm
برنامه بالا حاصل کار تلاش من و دوستانم بود امیدوارم به نحوه احسن ازش استفاده بشه این میل منه در خدمتتون هستم i.and.you.we@gmail.com
نشانی ایمیل شما منتشر نخواهد شد. بخشهای موردنیاز علامتگذاری شدهاند *
Current ye@r *
Leave this field empty
Copyright © 2010 Dlbook Team