Mảng _ bài 32

Lúc chiều đọc đề bài này thấy hay hay nên ngồi làm, giờ về post lên để thảo luận hén:

Đề: Cho mảng n số nguyên và nhập vào 1 số m. Cho biết có tồn tại 1 tập các phần tử thuộc mảng sao cho tổng của chúng bằng m

Đây là hướng giải của em: đầu tiên sắp xếp mảng a lại thành 1 mảng tăng dần. Tiếp tục xác định các phần tử nhỏ hơn.

Ví dụ mảng a gồm (2,4,5,13,10,8) và m = 9 thì ta chỉ cần xét các phần tử sau của a: (2,4,5,8)

Cuối cùng ta xét các tập này: nếu phần tử nhỏ hơn hoặc bằng m thì đưa nó vào b, rồi trừ m cho phần tử này. Cứ làm như thế đến khi m = 0 là được. Nếu m <> 0 thì giảm số phần tử lại....

Xét ví dụ trên nhé:

Step 1: có các phần tử (2,4,5,8)
8 < 9 ==> OK, chọn 8, m = 9 - 8 = 1
5 > 1 ==> loại
4 > 1 ==> loại
2 > 1 ==> loại

Step 2: bỏ bớt phần tử 8. Còn lại (2,4,5)
5 < 9 ==> OK, chọn 5, m = 9 -5 = 4
4 = 4 ==> OK, chọn 4, m = 4 - 4 = 0

m = 0 ==> thoát khỏi vòng lặp, thông báo là có 2 phần tử thỏa là (4,5)


Và đây là code hoàn chỉnh:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace mang_32
{
    class Program
    {
        static void Main(string[] args)
        {
            // nhập vào mảng có n phần tử
            Console.WriteLine("Nhap n: ");
            int n = int.Parse(Console.ReadLine());

            int[] a = new int[n];

            for (int i = 0; i < n; i++)
            {
                Console.Write("A[{0}] = ", i + 1);
                a[i] = int.Parse(Console.ReadLine());
            }

            // sắp xếp mảng a thành mảng tăng dần để tiện so sánh

            for (int i = 0; i < n - 1; i++)
                for (int j = i + 1; j < n; j++)
                    if (a[i] > a[j])
                    {
                        int tam = a[j];
                        a[j] = a[i];
                        a[i] = tam;
                    }

            // nhập vào số M để so sánh
            Console.WriteLine("Nhap m: ");
            int m = int.Parse(Console.ReadLine());

            // xác định vị trí của phần từ lớn nhất và nhỏ hơn m
            int vitri = 0;
            // nếu m lớn hơn tất cả các phần tử của mảng a thì đặt vitri = vị trí của phần tử cuối cùng
            if (m > a[n - 1])
                vitri = n - 1;
            else
                // ngược lại thì cần dùng vòng lặp để tìm
                for (int i = 0; i < n && vitri == 0; i++)
                    if (a[i] > m)
                        vitri = i - 1;

            for (int j = vitri; j >= 0; j--)
            {
                int temp = m; // đặt biến temp để biến m không bị thay đổi
                int[] b = new int[j + 1];
                int fantu_b = 0;

                for (int i = j; i >= 0 && temp > 0; i--)
                    // nếu a[i] nhỏ hơn thì thêm a[i] vào mảng b và giảm temp đi một lượng bằng a[i]
                    // cứ làm như thế đến khi temp = 0 hoặc duyệt hết các phần tử của mảng a
                    if (a[i] <= temp)
                    {
                        b[fantu_b] = a[i];
                        fantu_b++;
                        temp = temp - a[i];
                    }
               
                // nếu tồn tại một tập hợp mà tổng bằng m ==> in ra kết quả và thoát
                if (temp == 0)
                {
                    Console.WriteLine("Co ton tai cac fan tu");
                    for (int i = 0; i < j + 1; i++)
                        if (b[i] > 0) Console.WriteLine(b[i]);
                    break;
                }

                // nếu không tồn tại tập hợp trên thì quay lại (giảm j) và tiếp tục xét các phần tử nhỏ hơn.

                if (j == 0)
                    Console.WriteLine("Khong ton tai");
            }
           
            Console.ReadLine();
        }
    }
}


Bài của mình dùng giải thuật sinh ra các tập hợp con của tập hợp, rùi cộng chúng lại xem =m thi in ra.
(code sinh ra tập hợp con lấy của Zero);

Code:

using System;
using System.Collections.Generic;
using System.Text;
public class AI
{
   static void Main(string[] args)
   {
      //------Nhap cac phan tu cua tap hop---------
      Console.WriteLine("Ban dinh nhap bao nhieu phan tu? ");
      int n=int.Parse(Console.ReadLine());
      int []a=new int[n];
      Console.WriteLine("Nhap cac phan tu cua tap hop");
      int i;
      for(i=0;i<=n-1;i++)
      {
         Console.Write("Phan tu {0}=",i+1);
         a[i]=int.Parse(Console.ReadLine());
      }
      Console.Write("Nhap M:");int m=int.Parse(Console.ReadLine());
      //--------tao ra cac bit nhi phan--------
      string chuoinhap="";
      for(i=1;i<=n;i++) chuoinhap=chuoinhap+"0";//Tao ra chuoi co n so "0"
      lap:
        for (i = n; i >= 1; i--)
        {
            string kt = chuoinhap.Substring(i - 1, 1);
            if (kt == "0") break;
        }
        string chuoitrc = chuoinhap.Substring(0, i - 1);
      string chuoiin=chuoitrc+"1";
      for(int j=0;j<n-i;j++) chuoiin=chuoiin+"0";
      chuoinhap=chuoiin;
        //--------tinh cac tong cua cac tap hop neu=m thi in ra-----------
      int tong=0;
      for(i=0;i<=n-1;i++) if(chuoiin.Substring(i,1)=="1") tong=tong+a[i];
      if(tong==m) // Neu =m thi in ra
      {   
         for(i=0;i<=n-1;i++) if(chuoiin.Substring(i,1)=="1") Console.Write(a[i]+",");
         Console.WriteLine("");
      }
      //-----------------------------------------------------------------
      for(i=0;i<chuoiin.Length;i++) if(chuoiin.Substring(i,1)=="0") goto lap;
        Console.ReadLine();
   }
}