Bài toán chia danh sách số theo điều kiện …

Đề bài

Chúng ta sẽ có danh sách những con số (có âm và dương) và tổng của những con số này luôn lớn hơn 0. Chúng ta cần phải chia danh sách những con số này thành những nhóm nhỏ và thỏa mãn những điều kiện như sau:

  1. Mỗi nhóm nhỏ chỉ chứa tối đa là 7 con số.
  2. Tổng các con số trong nhóm phải lớn hơn 0.

Ví dụ:
– Danh sách những con số: (-12, -2, 1, 2, 4, 5, 6, -7, -8, 10, 11, 3)
– Kết quả:
+ Nhóm 1: (-12, 11, 10, -8, 6, 5, 7)
+ Nhóm 2: (-2, 1, 2, 3, 4)

Giải nào

Ở đây mình mặc định các bạn đã có các khái niệm cơ bản về tạo một dự án (project) bằng Visual Studio rồi nhé! Trường hợp này mình tạo một project – Console App (.NET Framework).

Dưới đây là hàm main, mình có ghi chú cho từng dòng code bên dưới.

 static void Main(string[] args)
        {
            // Danh sách đầu vào
            List<int> list = new List<int>() { -12, -2, 1, 2, 4, 5, 6, -7, -8, 10, 11, 3 };

            // Sắp xếp danh sách theo thứ tự tăng dần
            list = list.OrderBy(i => i).ToList();

            // In ra danh sách để quan sát trong console
            Console.WriteLine("List is sorted: ");
            foreach (var item in list)
            {
                Console.WriteLine(item);
            }
            Console.WriteLine("====================");

            // Khởi tạo một danh sách để chứa những nhóm đã được chia
            List<List<int>> groups = new List<List<int>>();

            // Hàm chia danh sách
            SplitList(groups, list);

            // Chạy vòng lập để đọc từng nhóm trong danh sách 
            for (int i = 0; i < groups.Count; i++)
            {
                Console.WriteLine("Group " + (i + 1) + ":");

                // Chạy vòng lặp của từng nhóm để biểu diễn từng phần tử trong nhóm ra màn hình console
                foreach (var item in groups[i])
                {
                    Console.WriteLine(item);
                }
                Console.WriteLine("====================");
            }

            // Màu mè để báo cho người dùng biết là nhấn đại phím nào đi để kết thúc chứ còn chờ gì nữa?
            Console.WriteLine("Nhấn đại phím nào để kết thúc!");
            Console.ReadKey();
        }

Đây là code cho toàn bộ hàm chia danh sách.

private static void SplitList(List<List<int>> groups, List<int> list)
        {
            // Khởi tạo một biến có kiểu danh sách chứa các phần tử kiểu integer (số nguyên) để chứa các phần tử của một nhóm
            List<int> group = new List<int>();

            // Nếu danh sách chúng ta đưa vào có số phần từ lớn hơn 7 chúng ta sẽ vô đây để chạy một cái đệ quy
            if (list.Count > 7)
            {
                // Khởi tạo một biến để chứa tổng số duyệt từ đầu đến cuối của danh sách 
                int totalMax = 0;

                // Vòng lặp để duyệt qua toàn bộ danh sách từ đầu tới cuối
                for (int i = 0; i < list.Count; i++)
                {
                    // Nếu cái nhóm mà chưa đủ 7 phần tử thì vô đây.
                    if (group.Count < 7)
                    {
                        // Bắt đầu lấy phần tử trong danh sách ở index (vị trí) thứ 0 gán vào biến và cộng tiếp tục biến lên
                        totalMax += list[0];

                        // Thêm cái phần tử đó vào nhóm mình vừa tạo ở trên
                        group.Add(list[0]);

                        // Đồng thời xóa phần tử đó trong danh sách được cho vào.
                        list.Remove(list[0]);

                        // Tạo một biến chứa tổng các số duyệt từ cuối lên đầu của danh sách
                        int totalTemp = 0;

                        // Vòng lặp để duyệt qua toàn bộ danh sách từ cuối lên đầu
                        for (int j = list.Count - 1; j >= 0; j--)
                        {
                            // Nếu cái nhóm mà chưa đủ 7 phần tử thì vô đây.
                            if (group.Count < 7)
                            {
                                // Bắt đầu lấy phần tử trong danh sách ở index (vị trí) thứ cuối cùng danh sách gán vào biến và cộng tiếp tục biến lên.
                                totalTemp += list[j];

                                // So sánh nếu tổng của mấy thằng cuối được cho vào lớn hơn tổng đối số của mấy thằng đầu
                                if (totalTemp > Math.Abs(totalMax))
                                {
                                    // Cho cái vị trí thứ i của vòng lặp duyệt từ đầu tới cuối quay lại 0 để duyệt lại
                                    i = 0;

                                    // Thêm phần tử cuối vào trong nhóm
                                    group.Add(list[j]);

                                    // Xóa phần tử trong danh sách
                                    list.Remove(list[j]);

                                    // Cho cái tổng của các số từ đầu tới cuối về vị trí 0 để tạo lại cái tổng mới.
                                    totalMax = 0;

                                    // Dừng vòng lặp duyệt từ cuối lên đầu nếu không nó mà bự thì ngồi chờ mọt gong....
                                    break;
                                }
                                // Nếu không thỏa 1 trong 2 điều kiện trên thì vô đây
                                else
                                {
                                    // Vẫn phải thêm phần tử vị trí thứ j đó vào nhóm
                                    group.Add(list[j]);
                                    // Xóa phần từ tại vị trí thứ j đó ra khỏi danh sách
                                    list.Remove(list[j]);
                                }
                            }
                            // Còn không thì văng ra ngoài nếu không nó cứ duyệt tiếp, danh sách mà lớn thì ngủ một giấc nha! Chừng nào chạy xong thì xem kết quả.
                            else
                            {
                                break;
                            }
                        }
                    }
                    // Còn không thì văng ra ngoài nếu không nó cứ duyệt tiếp, danh sách mà lớn thì ngủ một giấc nha! Chừng nào chạy xong thì xem kết quả.
                    else
                    {
                        break;
                    }
                }

                // Nếu nhóm mình thấy đủ 7 phần tử phản động rồi thì add nó vào nhóm bự mình đã tạo sẵn ở hàm main.
                groups.Add(group);

                // Đây là bước quan trọng bỏ cái danh sách còn lại vào trong cái hàm này, đây là đệ quy (recursion).
                SplitList(groups, list);
            }
            // Còn nếu danh sách không lớn hơn 7 thì lấy hết nó chứ còn suy nghĩ gì chứ?
            else
            {
                groups.Add(list);
            }
        }

Bên trên là những gì mình code bừa để giải cho phù hợp với đề bài được giao cho, nếu các bạn có cách nào hay và tối ưu hơn xin vui lòng để lại bình luận bên dưới để cùng nhau phát triển cho ngành lập trình nhé! Thân chào!

Trả lời

Điền thông tin vào ô dưới đây hoặc nhấn vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s