Tortoise and Hare tournament | Bài toán rùa và thỏ trong lập trình C#

[nhc1987]

ĐỀ BÀI

Ở bài tập này chúng ta sẽ viết 1 chương trình mô phỏng lại quá trình chạy đua của Rùa và Thỏ với những quy luật sau đâu : Cả 2 con vật sẽ bắt đầu từ điểm xuất phát tại ô 1 trong 70 ô. Mỗi ô sẽ biểu diễn cho 1 vị trí trong suốt chặng đua này. Vị trí ô thứ 70 sẽ là đích đến. Con nào tới được ô 70 trước sẽ là winner hì hì. Nhưng sẽ có những chướng ngại giữa đường đi và làm tăng thêm hấp dẫn cho cuộc đua, chúng ta sẽ có những quy luật sau theo phần trăm của thời gian và những bước di chuyển. Chúng ta sẽ điều khiển 2 chú rùa và thỏ theo quy luật ở trong các box dưới đây.



Chương trình của chúng ta sẽ có 2 biến để theo vết vị trí của rùa và thỏ. Chúng ta sẽ cho random 1 số từ nguyên x ( 0 < x < 10 ).
Đối với rùa thì : nếu 1 <= x <= 5 thì là fast plod, khi 6 <= x <= 7 thì là slip còn khi 8 <= x <= 10 thì là slow pod.
Đối với thỏ thì ta có 5 TH : sleep, big hop, big slip, small hop, và small slip, ta sẽ tự quyết định giá trị của x cho thỏ tương tự như Rùa.
In ra màn hình chữ T tương trưng cho Thỏ và R tượng trưng cho rùa, mô phỏng lại chặng đua thú vị này.
Nếu trường hợp 2 con trùng ô thì in ra “Ouch !!”.
Nếu tại điểm xuất phát mà con nào lùi lại thì đưa nó lên lại vị trí xuất phát.

-------------------------------------------------------------------------

[HƯỚNG GIẢI QUYẾT]

Đối với bài này, có nhiều hướng suy nghĩ cho bạn :

- Thứ nhất, bạn có thể suy nghĩ đơn giản. Đây chỉ là một bài toán đơn giản, rèn luyện khả năng tư duy, khả năng lập trình ... Cho tất cả vào một file Program.cs là xong.

- Thứ hai, bạn suy nghĩ theo hướng phức tạp hơn một chút. Tại sao lai không đóng gói thành class nhỉ ? An toàn và dễ sử dụng hơn nhiều ... Vậy là (có thể) bạn tạo các class như sau


(Chú ý là ko có Animal và Move nhe mọi người, tại tui chỉnh sửa từ cái sơ đồ cũ nên nó vẫn còn :">)

- Thứ ba, suy nghĩ theo hướng cao hơn nữa.
+ Sao lại chỉ đua có thỏ và rùa ? Sao ko cho thành cuộc đua tập thể luôn ?
+ Sao lại có ít kiểu di chuyển vậy ? Sao ko cho thêm vào, kiểu move Hiphop chẳng hạn
+ Sao lại chỉ làm trên console ? Tui làm thêm GUI ko đc à ?

Vậy là (có thể) bạn tạo kiến trúc chương trình như sau :


Xin chú ý với các bạn một điều, phải tùy tình huống mà làm cho phù hợp. Giả dụ bài này cho thi HK thời gian 60' mà bạn thiết kế lớp cho chi tiết thì bạn nắm chắc ... điểm thấp . Do ở đây tui căn cứ vào thời gian cho phép giải quyết bài này là 1 ngày (hoặc hơn) nên đề ra phương án như trên.

Tạm thời tui mới chỉ có "suy nghĩ " đến mức như vậy à. Tui vẫn mong muốn vẫn còn chỗ nào đó có thể chia nhỏ hơn được nữa.

Bạn nào có ý kiến xin ko ngần ngại đưa lên. Xin cám ơn các ý kiến tuyệt vời của các bạn (câu này chôm của Dr )

(Còn tiếp)

Xem thêm tại đây : Bài toán Rùa và Thỏ

[nhc1987]

Hông thấy ai có ý kiến hết vậy chài. Oke, vậy tui sẽ code dựa trên bản phân tích thứ 3 :

Chúng ta sẽ bắt đầu với core của game : đó là 3 lớp : Animal, Move và Game

Thứ nhất, Animal.cs

/*********************************************************************    File    :   Animal.cs    Date    :   23/1/2008   0:48----------------------------------------------------------------------*   Name    :   Nguyen Hung Cuong*   Class   :   TH2005*   MSSV    :   0512085*   Mail    :   nhc.hcmuns@gmail.com----------------------------------------------------------------------    Purpose :   **********************************************************************/using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public abstract class Animal    {        protected int _CurrentPosition = 0;        public int CurrentPosition        {            get { return _CurrentPosition; }            set { _CurrentPosition = value; }        }         public abstract String Name        {            get;        }         protected List<Move> _MoveTypes;         public Animal()        {         }         public Move MakeRandomMove()        {            int index = new Random().Next(_MoveTypes.Count);            return _MoveTypes[index];        }         public Move Run()        {            Move move = MakeRandomMove();            move.CurrentPosition = _CurrentPosition;     // set current            move.GoGo();                                          // go             _CurrentPosition = move.CurrentPosition;     // update current             return move;        }    }}

Thứ hai, Move.cs

/*********************************************************************    File    :   Move.cs    Date    :   23/1/2008   0:50----------------------------------------------------------------------*   Name    :   Nguyen Hung Cuong*   Class   :   TH2005*   MSSV    :   0512085*   Mail    :   nhc.hcmuns@gmail.com----------------------------------------------------------------------    Purpose :   **********************************************************************/using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public abstract class Move    {        protected int _CurrentPosition;        public int CurrentPosition        {            get { return _CurrentPosition; }            set { _CurrentPosition = value; }        }         protected abstract int _PercentageOfTime        {            get;        }         protected abstract int _ActualMove        {            get;        }         public Move()        {         }         public void GoGo()        {            _CurrentPosition = _CurrentPosition + _ActualMove;             if (_CurrentPosition < Game.MIN_WIDTH)                _CurrentPosition = Game.MIN_WIDTH;             else if (_CurrentPosition > Game.MAX_WIDTH)                _CurrentPosition = Game.MAX_WIDTH;        }         public override string ToString()        {            return "Position = " + _CurrentPosition;        }        }}

Thứ ba, Game.cs

/*********************************************************************    File    :   Game.cs    Date    :   23/1/2008   11:46----------------------------------------------------------------------*   Name    :   Nguyen Hung Cuong*   Class   :   TH2005*   MSSV    :   0512085*   Mail    :   nhc.hcmuns@gmail.com----------------------------------------------------------------------    Purpose :   **********************************************************************/using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public abstract class Game    {        public static int MIN_WIDTH = 0;        public static int MAX_WIDTH = 0;         /// <summary>        /// Set up game        /// </summary>        public abstract void Setup();         /// <summary>        /// Play game        /// </summary>        public abstract void Play();    }}

Sau khi có được 3 class này xem như ta đã giải quyết xong bài toán ở trên. Đặc biệt bạn có thể thấy được khả năng mở rộng của game này là rất cao ... Sau khi code cho bài nhỏ xíu ở trên, bạn có thể phát triển nó thành game bán kiếm tiền được đó ... Từ từ sẽ thấy rõ hơn

Bạn nào có ý kiến xin ko ngần ngại đưa lên. Xin cám ơn các ý kiến tuyệt vời của các bạn (câu này chôm của Dr)

Lưu ý : vẫn có thể còn bug do tui chưa test kĩ. Bạn nào thấy vui lòng thông báo nhé

(Còn tiếp)

Xem thêm tại đây : Bài toán Rùa và Thỏ

[bete]

Thân gửi bạn nhc,

Tui nghĩ như vầy:

1) nếu làm như bạn thì:
- mỗi lần move là phải tạo và hủy 1 thực thể (instance) của lớp Move (nếu move 100 bước thì phải tạo và hủy 100 lần); và thời gian tồn tại của các thực thể này rất là ngắn (chỉ 1 bước move mà thôi)
- để thay đổi thuộc tính position của lớp Thỏ và lớp Rùa => phải tạo 1 thực thể của lớp Move và truyền position của Thỏ/Rùa vô cho Move rồi Move thay đổi thuộc tính position (của Move) và trả ngược lại về thuộc tính position của Rùa/Thỏ => có vẻ không hợp lý cho lắm (chỉ cần thay đổi 1 thuộc tính của Thỏ/Rùa mà phải làm gián tiếp qua 1 thực thể Move; và các thuộc tính của thực thể Move thực chất chỉ là bản sao y chang của các thuộc tính của Thỏ/Rùa => tại sao không thay đổi trực tiếp ngay trong Thỏ/Rùa ???)

2) có nên chăng làm như sau: thỏ và rùa có thuộc tính position. Thông thường thuộc tính được thay đổi thông qua các phương thức (method) => nên cài đặt thẳng các cách move vô lớp Thỏ và lớp Rùa (không cần các lớp Move/Hop/Slip/Sleep/.....)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[nhc1987]

1) nếu làm như bạn thì:
- mỗi lần move là phải tạo và hủy 1 thực thể (instance) của lớp Move (nếu move 100 bước thì phải tạo và hủy 100 lần); và thời gian tồn tại của các thực thể này rất là ngắn (chỉ 1 bước move mà thôi)
???)

Thật ra, cách làm của mình đã tính tới chuyện sẽ lưu lại các bước di chuyển của các animals để cho user có thể replay, undo, redo, .... Do đó thực sự các bước move đó tồn tại trong suốt quá trình sống của object Hare, Tortoise

- để thay đổi thuộc tính position của lớp Thỏ và lớp Rùa => phải tạo 1 thực thể của lớp Move và truyền position của Thỏ/Rùa vô cho Move rồi Move thay đổi thuộc tính position (của Move) và trả ngược lại về thuộc tính position của Rùa/Thỏ => có vẻ không hợp lý cho lắm (chỉ cần thay đổi 1 thuộc tính của Thỏ/Rùa mà phải làm gián tiếp qua 1 thực thể Move; và các thuộc tính của thực thể Move thực chất chỉ là bản sao y chang của các thuộc tính của Thỏ/Rùa => tại sao không thay đổi trực tiếp ngay trong Thỏ/Rùa

Ở đây do chỉ là đơn giản nên tạm thời bạn chỉ thấy thay đổi ở position, thực tế nó còn percentageOfTime mình vẫn chưa xét tới. Và có thể thêm vào một số thông tin khác nữa mà sau này phát sinh.

2) có nên chăng làm như sau: thỏ và rùa có thuộc tính position. Thông thường thuộc tính được thay đổi thông qua các phương thức (method) => nên cài đặt thẳng các cách move vô lớp Thỏ và lớp Rùa (không cần các lớp Move/Hop/Slip/Sleep/.....)

Cách làm của bạn gây khó khăn rất nhiều cho việc bảo trì. Khi code như vậy bạn hoàn toàn ko tái sử dụng được gì cả .... Cách làm của bạn tương đương với suy nghĩ 1.

Bạn có thể xem thêm bài trả lời cuối cùng của nhc tại thread : Bài toán rùa và thỏ

Cám ơn bạn đã cho ý kiến :cheers:

[Kevin Hoang]

Dr cũng có ý như Bete đó. OOP tức là nó giống với thực tế. Ở đây sẽ có 2 lớp Thỏ và Rùa, 2 lớp này có tất cả các thuộc tính như là Move, Hop, Slip, Sleep, ... Và một lớp để điều khiển cuộc chơi. Mọi người cho ý kiến nhé!

Dr cũng đang nghiên cứu làm cái này trên C#, nhưng mà trình độ còn yếu quá, kèm theo bận bịu nhiều thứ. Thành thử làm hoài không được.

[nhc1987]

Oke, tiếp tục sẽ là các lớp inherit từ các lớp cha ở trên :

Thứ nhất, chúng ta xét về Animal, bạn có thể dễ dàng nhận ra trong game này cần 2 con là Rùa và Thỏ. Vậy thì tạo 2 classes đi còn chờ gì nữa

Hare.cs

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    /// <summary>    /// Hare : Thỏ rừng # Rabbit : Thỏ nhà :D    /// </summary>    public class Hare : Animal    {        public override string Name        {            get { return "Hare"; }        }         public override string ToString()        {            return "H";        }         public Hare(int fieldWidth)        {            _CurrentPosition = new Random(DateTime.Now.GetHashCode()).Next(fieldWidth);             _MoveTypes = new List<Move>();             _MoveTypes.Add(new Sleep());      // sleep            _MoveTypes.Add(new BigHop());     // big hop            _MoveTypes.Add(new BigSlip());    // big slip            _MoveTypes.Add(new SmallHop());   // small hop        }    }}

Tortoise.cs

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    /// <summary>    /// Tortoise : Rùa nước ngọt #  Turtle : Rùa biển :D    /// </summary>    public class Tortoise : Animal    {        public override string Name        {            get { return "Tortoise"; }        }         public override string ToString()        {            return "T";        }         public Tortoise(int fieldWidth)        {            _CurrentPosition = new Random().Next(fieldWidth);             _MoveTypes = new List<Move>();             _MoveTypes.Add(new FastFlod());      // fast flod            _MoveTypes.Add(new Slip());          // slip            _MoveTypes.Add(new SlowPlod());      // slow flod        }     }}

Thứ hai, thêm các kiểu move vào ... và việc code các lớp này thực sự rất đơn giản, chỉ cần override lại 2 properties là PercentageOfTime và ActualMove

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class BigHop : Move    {        public BigHop()        {         }         protected override int _PercentageOfTime        {            get { return 20; }        }         protected override int _ActualMove        {            get { return 9; }        }    }}

 using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class BigSlip : Move    {        public BigSlip()        {         }         protected override int _PercentageOfTime        {            get { return 10; }        }         protected override int _ActualMove        {            get { return -12; }        }    }}

 using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class FastFlod : Move    {        public FastFlod()        {         }         protected override int _PercentageOfTime        {            get { return 50; }        }         protected override int _ActualMove        {            get { return 3; }        }    }}

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class Sleep : Move    {        public Sleep()        {         }         protected override int _PercentageOfTime        {            get { return 20; }        }         protected override int _ActualMove        {            get { return 0; }        }    } }

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class Slip : Move    {        public Slip()        {         }         protected override int _PercentageOfTime        {            get { return 20; }        }         protected override int _ActualMove        {            get { return -6; }        }    }}

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class SlowPlod : Move    {        public SlowPlod()        {         }         protected override int _PercentageOfTime        {            get { return 30; }        }         protected override int _ActualMove        {            get { return 1; }        }    }}

using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class SmallSlip : Move    {        public SmallSlip()        {         }         protected override int _PercentageOfTime        {            get { return 20; }        }         protected override int _ActualMove        {            get { return -2; }        }    }}

[bete]

Thân gửi bạn nhc,

Xin được thảo luận với bạn thêm 1 chút:

1) Trước hết tui xin nhìn nhận là nếu cài đặt thẳng các cách move vô ở lớp Rùa và lớp Thỏ là rất dở vì không mở rộng được (tui đã đọc phần trả lời cuối cùng của bạn ở cái thread kia)

2) Cách lập các lớp cho các cách move như bạn là mở rộng được (thêm 1 kiểu move mới, 2 con vật nào đó có thể có cùng 1 kiểu move nào đó)

3) percentageOfTime không nên để ở trong lớp Move/Hop/Slip/.... mà nên để ở trong lớp Rùa và lớp Thỏ: con vật A có thể có cách move X với percentageOfTime là y% và con vật B khác có thể có cùng cách move X nhưng với z% (khác với y%)

3) Để mở rộng được (thêm 1 kiểu move mới, 2 con vật nào đó có thể có cùng 1 kiểu move nào đó) mình có thể làm cách khác:

a) định nghĩa enum MoveType = HOP (0), SLIP (1), Sleep (2), ....
b) định nghĩa lớp Animal với thuộc tính validMoves, phương thức ActualMove và Move:

Animal::validMoves: list hoặc mảng (các phần tử là kiểu enum MoveType)
Animal::ActualMove(move_type) {
  switch (move_type) { 
    case HOP: position = .....
   ....... 
  }
}
Animal::Move {
  idx = random(1 .. nValidMoves);
  move_type = ValidMoves[idx];
  ActualMove(move_type);
}

c) Lớp Rùa và lớp Thỏ thừa kế từ lớp Animal
Rùa::validMoves = (SLIP, ...); (đặt dòng này trong constructor của lớp Rùa)
Thỏ::validMoves = (HOP, ...); (đặt dòng này trong constructor của lớp Thỏ)

Như vậy:
- lớp Animal/Rùa/Thỏ có thuộc tính position
- thuộc tính position được thay đổi bởi phương thức Move (move là 1 hành xử (behavior) tác động lên thuộc tính position: theo tinh thần của OOP)
- dễ dàng thêm 1 loại Animal mới (thêm lớp Gà; khởi tạo Gà::validMoves trong constructor của lớp Gà), dễ dàng thêm 1 loại move mới (thêm phần tử HIPHOP vô enum MoveType; thêm "case HIPHOP" vô switch (chỉ thêm ở 1 chỗ trong Animal::ActualMove)), dễ dàng cho 2 loại animal xài chung 1 loại move nào đó (thêm loại move này khi khởi tạo validMoves trong 2 lớp ứng với 2 loại animal này)

(enum MoveType chỉ được xài ở 2 chỗ: định nghĩa của enum & switch trong Animal::ActualMove()
=> dễ sửa code

cài đặt cho các loại move khác nhau nằm tập trung ở 1 cái switch => dễ kiểm tra & dễ sửa)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân

[nhc1987]

3) percentageOfTime không nên để ở trong lớp Move/Hop/Slip/.... mà nên để ở trong lớp Rùa và lớp Thỏ: con vật A có thể có cách move X với percentageOfTime là y% và con vật B khác có thể có cùng cách move X nhưng với z% (khác với y%)

Cũng là một hướng phát triển hay

3) Để mở rộng được (thêm 1 kiểu move mới, 2 con vật nào đó có thể có cùng 1 kiểu move nào đó) mình có thể làm cách khác:

a) định nghĩa enum MoveType = HOP (0), SLIP (1), Sleep (2), ....
b) định nghĩa lớp Animal với thuộc tính validMoves, phương thức ActualMove và Move:
.............

Oke, đó cũng là một cách làm. Nhưng tui vẫn thấy tiếc ở chỗ

+ phải duyệt qua nguyên một list các move types để có thể đến được move type đúng của nó 8-}

+ Bây giờ tui phát triển game, hỗ trợ save game, load game, undo, redo ... Bạn sẽ thêm vào một cái list các move để ghi nhớ lại vị trí ? Bạn sẽ thêm switch ... case trong save game, thêm switch ... case trong undo, trong redo, trong loadgame ? ... Lúc này thì ko đơn giản đâu à nha

Mong bạn đưa ra cách giải quyết :cheers:

[code]

[nhc1987]

Bây giờ tới Game nhe bà con, món chính yếu đây :

/*********************************************************************    File    :   Game.cs    Date    :   23/1/2008   0:49----------------------------------------------------------------------*   Name    :   Nguyen Hung Cuong*   Class   :   TH2005*   MSSV    :   0512085*   Mail    :   nhc.hcmuns@gmail.com----------------------------------------------------------------------    Purpose :   **********************************************************************/using System;using System.Collections.Generic;using System.Text; namespace RunningGame{    public class GameConsole : Game    {        private const int _MAX_CONSOLE = 300;         private List<Animal> _Competitors = new List<Animal>();         public GameConsole()        {            _Competitors.Add(new Tortoise(MAX_WIDTH));  // tortoise            _Competitors.Add(new Hare(MAX_WIDTH));      // hare             MIN_WIDTH = 0;            MAX_WIDTH = 70;        }         public override void Setup()        {             for (int i = 0; i < _MAX_CONSOLE; ++i )            {                Utilities.GoToXY(i, MAX_WIDTH);                Utilities.Out("|");                            }             foreach (Animal animal in _Competitors)            {                Utilities.GoToXY(0, animal.CurrentPosition);                Utilities.Out(animal.ToString());            }        }         public override void Play()        {            int index = 0;   // for display only            List<Animal> movedAnimals = new List<Animal>();             while(true)            {                foreach (Animal animal in _Competitors)                {                    Move move = animal.Run();                       // animal move                    Utilities.GoToXY(index, move.CurrentPosition);  // move the cursor                     if (movedAnimals.Count != 0)                    {                        SolveCollisionProblem(animal, movedAnimals); // collision ?                    }                    else                    {                        Utilities.Out(animal.ToString());                    }                     movedAnimals.Add(animal);   // add to list contains moved animals                     if (IsWin(animal))  // check for winning                    {                        Utilities.OutLine();                        Utilities.OutLine(animal.Name + " win !!!");                        return;                    }                }                 movedAnimals = new List<Animal>();  // renew list                ++index;                 if (index == _MAX_CONSOLE)   // check for draw situation                {                    Utilities.OutLine("Draw");                    return;                }                 System.Threading.Thread.Sleep(300); // move slowly :D            }        }         private Boolean IsWin(Animal animal)        {            if (animal.CurrentPosition == MAX_WIDTH)                return true;             return false;        }         private void SolveCollisionProblem(Animal animal, List<Animal> list)        {            foreach (Animal movedAnimal in list)            {                if(animal.CurrentPosition == movedAnimal.CurrentPosition)                {                    Utilities.Out("OUCH!");                }                else                {                    Utilities.Out(animal.ToString());                }            }        }    }}

Cái này thì tùy mọi ngừoi chỉnh. Xuất mấy câu thông báo yêu cầu gì gì đóa cũng được. Tui viết đơn giản vậy thoai

[rox_rook]

Ngưỡng mộ nhc ghê T_T ! Mặc dù không hiểu C# như description và design thật là ấn tượng . Rất bài bản và logic, all I have to say is awesome T_T! Nhìn thích ghê đó he he !
@ : Làm sao vẽ được mấy cái UML đó đẹp quá vậy chỉ tui với hì hì !