Thảo luận - Giải bài toán nhặt đậu của Tấm | VN-Zoom | Cộng đồng Chia Sẻ Kiến Thức Công Nghệ và Phần Mềm Máy Tính

Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add https://vn-z.vn to your ad blocking whitelist or disable your adblocking software.

×

Thảo luận Giải bài toán nhặt đậu của Tấm

malemkhoang

Rìu Chiến
Tam.jpg

Hôm nay dì lại bắt Tấm đi nhặt đậu. Tấm lại phải nhờ đến tôi. Lần này dì bắt Tấm phải nhặt các dòng không trùng lặp giá trị trong một tệp text ra. Tôi phân vân quá. Nhờ 500 chim sẻ vn-z giúp nhé.​
Cam.jpg

Mã:
M
A
L
E
M
K
H
O
A
N
G

Tôi nghĩ, cứ so sánh giá trị các dòng, giá trị nào là duy nhất thì nhặt ra. Không biết 500 chim sẻ vn-z có ưng ý không?​
Tamcam.jpg
 

bbkim

Mỗi người một câu chuyện
Không hiểu bác muốn làm gì. Nhưng nếu để so sánh 2 đoạn văn bản đơn giản thì có thể dùng Diffchecker hoặc Text Compare online hoặc nhiều thì thêm plugin Compare cho notepad++ để so sánh.

Tôi nghĩ, cứ so sánh giá trị các dòng, giá trị nào là duy nhất thì nhặt ra.
Còn lấy duy nhất thì làm thế này thôi chứ có cách nào khác đâu. Khác nhau cái thuật toán để tăng tốc độ so sánh thôi à.
vd: chuỗi MALEMKHOANG đi. so sánh bình thường thì là M so với A L ... G, trùng > so sánh tiếp A với A L ... G. so từng cái từng M trở đi. Lâu vì trùng nhiều lần.
Sửa lại thuật toán so sánh M từ A > G trùng thì bỏ các giá trị trùng luôn còn ALEKHOANG so sánh tiếp chuỗi mới ALEKHOANG. Nó sẽ chạy ít hơn cách từ đầu đến cuối nên nhanh hơn 1 tí.
 

lvt491

Rìu Vàng Đôi
Phải kiểu này không bác thớt

C#:
using System;
using System.Collections.Generic;
using System.IO;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            try
            {
                //Ví dụ nội dung cần kiểm tra tại file C:\\file.txt
                var duyNhat = Checking("C:\\file.txt");

                if (duyNhat.Count == 0)
                    Console.WriteLine("Khong co duy nhat");
                else
                {
                    Console.WriteLine("Cac dong duy nhat la:");
                    foreach (var item in duyNhat)
                    {
                        Console.WriteLine(item);
                    }
                }   
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
            }
            Console.ReadKey();
        }

        static List<string> Checking(string filePath)
        {
            //Dùng để lưu nội dung dòng làm Key và số lần xuất hiện làm Value
            var listCount = new Dictionary<string, int>();

            //Dùng để lưu các dòng là Duy nhất (xuất hiện 1 lần)
            var listUnique = new List<string>();

            //Đọc nội dung tệp tin ở filePath
            using (var reader = new StreamReader(filePath))
            {
                string line;

                //Duyệt từng dòng cho đến hết
                while ((line = reader.ReadLine()) != null)
                {
                    //Bỏ qua dòng trống không có dữ liệu
                    if (string.IsNullOrEmpty(line))
                        continue;

                    if (listCount.ContainsKey(line))
                        listCount[line]++;
                    else
                        listCount[line] = 1;
                }

                //Duyệt và lưu những dòng có Value = 1
                foreach (var item in listCount)
                {
                    if (item.Value == 1)
                        listUnique.Add(item.Key);
                }

                return listUnique;
            }
        }
    }
}
 

malemkhoang

Rìu Chiến
@bbkim
@lvt491
Ban đầu, tôi cũng suy nghĩ như vậy. Phải so sánh từng dòng với tất cả các dòng còn lại. Dĩ nhiên, càng về sau thì các bước so sánh càng giảm đi. Thuật toán này tôi nhớ là đã có từ lâu trong Pascal, C... Nhưng không hiệu quả, tức là mất thời gian.
Tôi thực hành với mảng (list), có thể giới hạn số lượng dòng đọc vào, list có phương thức đếm (count) giá trị, vậy là xong, Tấm chỉ việc tra vào đẫy.
NotePad++ dùng chức năng "Line Operations - Remove Duplicate Lines", nhưng trong trường hợp này thì không hiệu quả vì nó còn giữ lại 1 giá trị trùng lặp. Dùng Regex trong NotePad++ thì còn phải qua vài bước trung gian khá loằng ngoằng.​
 

bbkim

Mỗi người một câu chuyện
Bản chất vẫn là so sánh từng dòng thôi. Nhưng mà đổi thuật toán để rút ngắn các bước so sánh lại thôi à. count, remove duplicate,... hay bất kỳ cái gì khác thì nó cũng làm những bước đó. Máy tính bây giờ khả năng tính toán mạnh nên nó thực hiện quá nhanh nên mình nghĩ nó nhanh thôi.

Giống như bài toán sắp xếp thấp đến cao á.

Vẫn phải so sánh nhưng mỗi thuật toán thực hiện một cách khác nhau nên thời gian sắp xếp sẽ nhanh chậm khác nhau.
 

AnNTH

🔫 Súng Lục Nhựa
Bài toán này khá hay.
Việc so sánh từng dòng với nhau thì em nghĩ là giải quyết được khá triệt để rồi. Nhưng để tối ưu thời gian chạy thì hướng đi của em sẽ khác, em sẽ dùng một cái hashmap hoặc dictionary để đếm tần suất của các dòng xuất hiện, ví dụ: {"M":2, "E":1,...}. Sau đó chỉ cần duyệt lại danh sách thêm 1 lần nữa để in ra thôi. Tóm gọn là từ so sánh -> đếm. Độ phức tạp sẽ chỉ còn là 2n. Thay vì dùng so sánh thì sẽ phải duyệt danh sách lồng nhau -> n^2.

C++:
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
    ifstream infile("input.txt");
    if (!infile.is_open()) {
        cerr << "Unable to open file" << endl;
        return 1;
    }

    int n;
    infile >> n;
    infile.ignore();

    vector<char> lines(n);
    unordered_map<char, int> frequency;

    // Đọc tất cả các dòng và đếm tần suất xuất hiện của từng ký tự
    for (int i = 0; i < n; ++i) {
        infile.get(lines[i]);
        infile.ignore();
        frequency[lines[i]]++;
    }

    infile.close();

    // In ra các ký tự chỉ xuất hiện một lần
    ofstream outfile("output.txt");
    for (int i = 0; i < n; ++i) {
        if (frequency[lines[i]] == 1) {
            outfile << lines[i] << endl;
        }
    }

    outfile.close();

    return 0;
}

P/s: phương pháp này đã là phương pháp tối ưu nhất mà em nghĩ ra về cả mặt phức tạp và không gian lưu trữ. Tuy nhiên vẫn còn có thể tối ưu thêm 1 chút nữa nhưng em nghĩ là nên giữ lại 1 chút để mấy anh em đồng đạo vào bàn.

P/s2: mới đọc lại thì thấy hình như bác @malemkhoang đang nói về dùng tool, mà em bàn qua tới lập trình luôn rồi kk. Nhưng mà code này có thể sửa 1 chút để chuyển qua tool cmd, và tốc độ xử lý đảm bảo nhanh hơn bất kỳ tool không chuyên nào cho vấn đề này kk
 
Sửa lần cuối:

malemkhoang

Rìu Chiến
@AnNTH
Tui cũng có đi mượn của hàng xóm, nhưng nó không cho, nên đành về lấy của nhà ra dùng. Tui thấy trong Python, khi sử dụng mảng (list), nó có sẵn phương thức đếm, thì dùng thôi. Trước tiên về mặt viết câu lệnh là ngắn gọn. Còn về mức độ tối ưu, thời gian, tài nguyên thì phải so sánh. Và còn một số vấn đề khác nữa...​
 

AnNTH

🔫 Súng Lục Nhựa
@AnNTH
Tui cũng có đi mượn của hàng xóm, nhưng nó không cho, nên đành về lấy của nhà ra dùng. Tui thấy trong Python, khi sử dụng mảng (list), nó có sẵn phương thức đếm, thì dùng thôi. Trước tiên về mặt viết câu lệnh là ngắn gọn. Còn về mức độ tối ưu, thời gian, tài nguyên thì phải so sánh. Và còn một số vấn đề khác nữa...​
Về mặt source code trong thuộc tính count của đối tượng list trong Python, thì cách hoạt động của nó sẽ duyệt qua từng phần tử trong list và so sánh với giá trị mà người dùng truyền vào:

Mã:
a = [1,2,3,2]

print(a.count(2))

# source code của count
# tạo 1 biến đếm count = 0
# duyệt qua 1 -> 1 != 2 -> bỏ qua
# duyệt qua 2 -> 2 == 2 -> count + 1
# ...
# cuối cùng trả về count
# source code của function này tại dòng 3218-3242 trong https://github.com/python/cpython/blob/main/Objects/listobject.c

Nên bác dùng count của list thì nó hoàn toàn tương tự như việc duyệt mảng chồng duyệt mảng, so sánh từng dòng -> độ phức tạp vẫn là 2n phép tính (với n là số lượng phần tử).

=>Kết luận: Dùng python chỉ để tối ưu cú pháp :v vì các thư viện của python được hỗ trợ quá mạnh
 

malemkhoang

Rìu Chiến
Đơn giản thì là vài dòng lệnh:
Python:
tentep = 'filename.txt'
with open(tentep, 'r', encoding='utf-8') as fp:
    noidung = fp.readlines()
ketqua = []
for i in range(0, len(noidung)):
    if noidung.count(noidung[i]) == 1: ketqua.append(noidung[i])

Để tối ưu xử lý thì thêm vài dòng lệnh xoá giá trị đã duyệt ra khỏi mảng.
 

malemkhoang

Rìu Chiến
@AnNTH
Đúng thật là: để thì buồn, cắt thì đau.
Phương án xoá phần tử mảng trong khi duyệt:
Python:
tentep = 'filename.txt'
with open(tentep, 'r', encoding='utf-8') as fp:
    noidung = fp.readlines()
for x in noidung:
    while noidung.count(x) > 1:
        for y in noidung:
            if noidung.count(y) > 1:
                for i in range(0, noidung.count(y)):
                    noidung.remove(y) # xoá phần tử mảng
 


Top