Kteam Q&A Community

Cộng đồng hỏi đáp về các vấn đề trong lập trình, công nghệ thông tin.

0

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

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 ạ.

2 câu trả lời Thêm câu trả lời

0
K9 đã trả lời 2018-04-13 19:15:47

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

0
C# learner đã trả lời 2018-04-14 14:26:01

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

Câu trả lời của bạn

Bạn có thể trả lời câu hỏi này? Hãy chia sẻ nó cho mọi người.

Hủy bỏ hoặc

Thông tin

Đã hỏi 2018-04-13 18:02:09
Đã xem 90 lần
Hoạt động 2018-04-14 14:26:01

Chiến dịch

Kteam - Howkteam Free Education