Hỏi đáp

Chia sẻ kiến thức, cùng nhau phát triển

Thuật toán liên quan đến mảng

18:02 13-04-2018 800 lượt xem 2 bình luận 14:26 14-04-2018

Anh chị có thể giải đáp giúp em một thuật toán liên quan đến mảng được không ạ?:

Cho một mảng gồm n phần tử nguyên và một số nguyên m. Tìm cách xóa đi ít phần tử nhất để trong các phần tử còn lại, không có 2 phần tử bất kỳ nào có tổng chia hết cho m.

Em cảm ơn ạ.

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
C# learner đã bình luận 14:26 14-04-2018

Cách này có thể hơi dài nhưng phần nào giúp đc bạn. Mình dùng phương thức Crunch (nếu bạn đã từng brute force thì chắc bạn cũng biết đến Crunch là gì)

 

Đầu tiên cần những thư viện sau:

using System;
using System.Collections.Generic;

Tiếp  đến cần 1 class (cái này nó cx đc không có viết trực tiếp vô code

public class MatchCaseData
{
    public MatchCaseData(bool match, List<int> list)
    {
        isMatchCondition = match;
        ListCase = new List<int>();

        foreach (var item in list)
        {
            ListCase.Add(item);
        }
    }
    public bool isMatchCondition { get; set; }
    public List<int> ListCase { get; set; }
}

Và Method (Main Algo là Method gốc)

private void MainAlgo()
        {
            List<int> orginal = new List<int>() { 2,3,4,7};
            for (int i = 0; i < orginal.Count; i++)
            {
                var result = Crunch(orginal, i);
                string s;
                if (result.isMatchCondition)
                    s=String.Format("The Minimum is: {0}", orginal.Count - result.ListCase.Count);
            }
        }

        private MatchCaseData Crunch(List<int> lst, int crunchNo)
        {
            
            List<int> buffer = new List<int>();
            foreach (var item in lst)
            {
                buffer.Add(item);
            }
            for (int i = 0; i < buffer.Count; i++)
            {
                
                buffer.RemoveAt(i);
                if(crunchNo == 0)
                {
                    var resultCase = Check(buffer);
                    if (resultCase.isMatchCondition)
                        return resultCase;
                }
                else
                {
                    var resultCase = Crunch(buffer, crunchNo - 1);
                    if (resultCase.isMatchCondition)
                        return resultCase;
                }
            }
            return new MatchCaseData(false, buffer);
        }
        private MatchCaseData Check(List<int> lst)
        {
            for (int i = 0; i < lst.Count; i++)           
                for (int j = 0; j < lst.Count; j++)
                    if (i != j)
                        if (lst[i] + lst[j] % m == 0)
                            return new MatchCaseData(false, lst);

            return new MatchCaseData(true, lst);
        }

Mình mong có thể giúp bạn :D

K9 SuperAdmin, KquizAdmin, KquizAuthor đã bình luận 19:15 13-04-2018

thuật toán mệt đầu ak nha. tách nó ra

1. Lấy ra tất cả các trường hợp mà đã rút các ký tự ra thỏa mãn không có tổng chia hết cho m

2. Lấy ra thằng rút ít ký tự ra nhất

Câu hỏi mới nhất