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

[08520001]

@Tú: em có thể viết cụ thể hơn không?

[11520447]

Lúc trước có seri topic Mỗi ngày một bài toán của anh Thắng hay Hùng gì đó cũng vui, mà rồi cũng thất truyền :brick:
Cho em góp vui 2 bài nhé :funny:

Cho 1 dãy số nguyên, tìm dãy con có tổng lớn nhất (Dãy con là dãy gồm các phần tử liên tiếp trong dãy ban đầu). VD : 1 2 3 4 -1 thì dãy có tổng lớn nhất là 1 2 3 4.

Chỉ nghĩ được cách cho duyệt số chữ số của dãy con tăng dần

[09520019]

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

O_o Nghe đồn đội thuật toán có truyền nhân nên ghé forum coi thử..... comment của bạn Nguyên khá ấn tượng ...nhưng mà phải nói rõ cho bạn hiểu tại sao anh An lại nói bài này dễ rồi skip luôn. Hồi xưa mình cũng hơi hơi giống bạn, tức là cái gì cũng muốn tối ưu cả. Nhưng các Olympiad contest là có giới hạn về mặt thời gian. Đôi khi mình chấp nhận code O(n^3) hoặc O(n^4) chỉ với mục đích là chắc chắn pass test càng nhanh càng tốt. Nếu đang trong phòng thi thì mình chắc chắn sẽ theo code của bạn Dương vì tính đơn giản của nó. Với cái bài như thế này, thì mục tiêu bạn đặt ra không phải là tối ưu càng nhiều càng tốt, mà là code càng nhanh càng tốt, 1 phút nộp bài. Hiểu chứ ?

Sau đó, mới bắt đầu nghĩ tới chuyện tối ưu, và "hơi tối ưu" và đánh bạo nộp bài. Tối ưu là việc chuyển đoạn code trên từ O(n^3) xuống O(n^2), chỉ khi bí rồi (hoặc nhận thấy bất khả thi), hoặc cách hơi tối ưu của bạn code nhanh hơn với ít thời gian suy nghĩ và chắc chắn là khó xảy ra bug, thì mới dám code theo hướng đó.

Bây giờ là phần tối ưu O(n^2)

bài toán là gì ? a^3 + b^3 + c^3 = 100a + 10b + c
<-> c^3 - c + (a^3 + b^3 - 100a - 10b) = 0
<-> c^3 - c + (A) = 0 (I)

Đặt a,b là biến tự do, c là ẩn cần tìm, như vậy xem như cái cụm (A) là hằng số
phương trình (I) có thể giải bằng phương pháp tìm nghiệm phương trình bậc 3 theo phương pháp Vieta http://en.wikipedia.org/wiki/Cubic_f...n_of_the_roots

hoặc theo phương pháp dùng lượng giác với a = 1,b = 0 và c = -1, hoặc công thức nghiệm tổng quát. Nói chung là gì cũng được http://vi.wikipedia.org/wiki/Ph%C6%B...b%E1%BA%ADc_ba

vậy thì từ 3 vòng for, giảm còn 2 vòng for, tính c dựa theo phương trình bậc 3 còn lại. Nếu vô nghiệm thì chuyển tới vòng for tiếp theo.

[08520001]

Sau khi giải quyết bài toán của bạn Tín, Anh đề nghị ý kiến chúng ta sẽ thảo luận thuật toán theo chủ đề. Mỗi chủ đề lớn có nhiều chủ đề con, mỗi topic sẽ thảo luận 1 chủ đề con như vậy, các bài toán đưa ra sẽ thuộc chủ đề đó. Và đối với các bài toán đưa lên topic, tác giả sẽ phải cung cấp đầy đủ các thông tin về giới hạn dữ liệu (chúng ta mặc định thời gian chạy là 1 giây cho mỗi test). Vì có những bài, tùy vào giới hạn dữ liệu mà sẽ có những cách giải khác nhau. Ngoài ra, tác giả phải giải được bài toán đó, và sau khi các bạn khác thảo luận, tác giả phải đưa ra cách giải của mình, gồm đầy đủ thuật toán, cơ sở để chứng minh thuật toán đó là đúng, khuyến khích các bạn diễn đạt sao cho mọi người dễ hiểu.

[12520527]

Lúc trước có seri topic Mỗi ngày một bài toán của anh Thắng hay Hùng gì đó cũng vui, mà rồi cũng thất truyền :brick:
Cho em góp vui 2 bài nhé :funny:

Cho 1 dãy số nguyên, tìm dãy con có tổng lớn nhất (Dãy con là dãy gồm các phần tử liên tiếp trong dãy ban đầu). VD : 1 2 3 4 -1 thì dãy có tổng lớn nhất là 1 2 3 4.

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

[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

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

[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)

[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é.

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

[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?

[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ỗ đó

[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]

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