[Thảo luận] Thuật toán

[08520001]

Xin chào các bạn, tình hình là đã giữa tháng 8, nhưng trường mình chưa có hoạt động gì về ôn luyện thuật toán. Để phụ giúp phần nào vào phong trào thuật toán của trường, mình lập topic này để các bạn giao lưu về lĩnh vực này giay nam.
Trước tiên mình đưa ra một số bài toán cơ bản để các bạn thảo luận.
1. Liệt kê các số có 3 chữ số abc sao cho tổng các lập phương của các chữ số bằng chính số đó
2. Cho một chuỗi chỉ gồm các chữ số từ 0 đến 9. Tìm chuỗi liên tiếp dài nhất chỉ gồm các chữ số giống nhau. Vd input: 122333 -

[12520808]

Em nghĩ 2 bài này chỉ cần duyệt đơn giản là xong.
P/s: Sao không tổ chức thi "Code đến 23h" nữa nhỉ?

[10520058]

Em nghĩ 2 bài này chỉ cần duyệt đơn giản là xong.
P/s: Sao không tổ chức thi "Code đến 23h" nữa nhỉ?

[OT] Nghĩ thôi sao, code đi, muốn thi cũng được nếu các bạn thích có thể đề nghị một buổi lên trường code tính giờ trong phòng lab cho nó máu hoặc ngồi hành lang cũng đựoc, tăng tính giao tiếp sẽ tốt hơn :-)

bài này đơn giản mà, khời động nào các bạn :-)

[11520537]

Cho em nộp trước bài 1 (C# code).

for (int a = 1; a < 10; a++)
                for (int b = 0; b < 10; b++)
                    for (int c = 0; c < 10; c++)
                        if (a * a * a + b * b * b + c * c * c == a * 100 + b * 10 + c)
                            Console.WriteLine("{0}{1}{2}", a, b, c);

[08520001]

Đúng là bài này chỉ duyệt đơn giản thôi. Nhưng kĩ thuật duyệt thế nào mới quan trọng giay cao nam.
Còn về kì thi thì anh thấy chưa cần. Theo kết quả lần trước, thầy Toàn chỉ chọn những bài đơn giản nhất có thể nhưng tỉ lệ làm bài được (ko xét trường hợp không thi) thì rất ít. Nên anh nghĩ hiện tại tổ chức những kì thi như vậy không hiệu quả lắm.

[08520001]

Bài 1 kết thúc với thuật toán của bạn Dương. Theo mình thấy thuật toán này OK rồi giay luoi nam.
Và tiếp theo là bài 2...

[10520100]

Cảm ơn anh An đã tạo topic hay cho mọi người trao đổi.

Tuy nhiên em xin được góp ý đến với anh An, bạn Huy và bạn Lân. Có lẽ mọi người không cố ý nhưng em nghĩ sau này không nên đánh giá độ dễ, khó của một bài nữa. Mục đích để tôn trọng người giải bài đó, tôn trọng những người không giải được và không để triệt tiêu những ý tưởng sáng tạo, mở rộng của bài toán.

Thời học phổ thông, em cũng đã từng rất buồn và hụt hẫng khi bài toán mình mất cả tuần mới giải được thì nhận được một câu từ người khác : "Bài này dễ ợt mà..."

Còn về bài thứ nhất, em nghĩ đó là bài hay. Nhất là đối với sinh viên thích toán. Vì nếu ta nghĩ nó khó, thì nó khó, để ra cả trăm vấn đề để giải.

Thử đặt vấn đề cho bài 1, nếu ta không duyệt từ 001 -> 999 để kiểm tra, thì ta phải làm gì để tối ưu, có cách nào nhanh hơn không ?

Giả sử, với code của bạn Trần Đại Dương, em sửa chút ít lại thế này để 2 số a,b luôn cùng tính chẵn lẻ.

for (int a = 1; a < 10; a++)
                for (int b = (a % 2) ; b < 10; b = b + 2)
                    for (int c = 0; c < 10; c++)
                        if (a * a * a + b * b * b + c * c * c == a * 100 + b * 10 + c)
                            Console.WriteLine("{0}{1}{2}", a, b, c); 

Cùng với đó là những modulo khác giúp bài toán vui hơn.

Em không thích dạy đời ai hết, nhưng thực sự, mong mọi người đặt bản thân mình vào vị trí của người khác để suy nghĩ.

[08520001]

Cám ơn Nguyên đã cung cấp một bài học kinh nghiệm. Anh thấy bài học này là đúng, và chắc là mọi người cũng thấy vậy và sẽ vui vẻ rút kinh nghiệm cho lần sau.
Còn về cách giải của em, khi cho a và b cùng tinh chẵn lẻ thì sẽ được gì? Anh chưa hiểu chỗ đó

[11520537]

Cám ơn Nguyên đã cung cấp một bài học kinh nghiệm. Anh thấy bài học này là đúng, và chắc là mọi người cũng thấy vậy và sẽ vui vẻ rút kinh nghiệm cho lần sau.
Còn về cách giải của em, khi cho a và b cùng tinh chẵn lẻ thì sẽ được gì? Anh chưa hiểu chỗ đó

Em cũng thắc mắc là sao với bài toán này thì anh Nguyên lại có thể đưa ra được a và b cùng tính chất?

[11520537]

Sau một hồi cầm bút thì em thấy abc chẵn hay lẻ thì phụ thuộc c chẵn hay lẻ tương ứng. Mà a*a*a + b*b*b + c*c*c = abc nên bắt buộc nếu c chẵn thì a*a*a + b*b*b + c*c*c cũng phải chẵn nên a, b cùng tính chất. Ngược lại nếu c lẻ thì a*a*a + b*b*b + c*c*c lẻ, nên a,b cũng phải cùng tính chất.

Em rất phục anh Nguyên khi anh có thể kết luận ngay được điều này.

[08520001]

Oh. Vậy mà Nguyên cũng phân tích ra được. Tính chất này giúp thuật toán tăng tốc độ lên 2 lần. Nguyên cứ vậy mà phát huy nhé.

[12520808]

Đây là cách em làm bài 2

        int maxl=0;
	char resc;
	for(int i=0;i<s.length();)
	{
		int j=i;
		while(j<s.length()) 
			if (s[i]==s[j]) j++;
			else break;
		if (j-i>maxl) 
		{
			maxl=j-i;
			resc=s[i];
		}
		i=j;
	} 
	for (int i=0;i<maxl;i++) cout<<resc;

Độ phức tạp bằng với độ dài chuỗi gốc O(n)

[10520100]

@ Dương : cảm ơn em nhiều.

@ Anh An : dạ cảm ơn anh. Nói về code thì cả e vs a đều biết a hơn e nhiều mà. Em nói vậy hi vọng a không để bụng. hì hì.
Cái topic a đặt ra làm e nhớ lại cái thời cấp 3. Thời chưa có facebook, laptop thì ngồi giải toán vui cực.
Hi vọng các bạn khác cũng tham gia và phát huy khả năng.

[10520322]

Già rồi nhưng cũng góp vui giải bài 2 :love:

        str = "[Chuỗi nhập vào]";
        char first_char = str.charAt(0);
        int n = str.length();
        int count = 0;
        int index = 0;
        int length = 1;
        int start_index = 0;
        for(int i = 0; i < n; i++)
        {
            if(str.charAt(i) == first_char)
            {
                count++;

            }
            else
            {
                first_char = str.charAt(i);
                if(length < count)
                {
                    index = start_index;
                    length = count;
                }
                start_index = i;
                count = 1;
            }
        }

        String result = str.substring(index, index + length);

Mới tập code Java nên hơi dài

[08520001]

@Nguyên: Hì, anh chỉ được cái thi nhiều rồi nên biết nhiều chút thôi em.
Tình hình là thuật toán bài 2 của Hoàng và Lân ổn rồi á. Nhưng các bạn rút kinh nghiệm nên ghi kèm thuật toán, chứ gặp mấy bài phức tạp mà chỉ có code chắc hết hiểu nổi luôn.