Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

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

    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 -
    Last edited by 08520001; 18-04-2015, 23:47.

  • #2
    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ỉ?

    Comment


    • #3
      Originally posted by 12520808 View Post
      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 :-)
      Last edited by 10520058; 18-08-2013, 22:21. Reason: OT
      Be different and always different
      http://archlinuxvn.org/
      http://theslinux.org
      http://lab.infosec.xyz

      Comment


      • #4
        Cho em nộp trước bài 1 (C# code).
        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);
        Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!

        Comment


        • #5
          Đú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.
          Last edited by 08520001; 18-04-2015, 23:47.

          Comment


          • #6
            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...
            Last edited by 08520001; 18-04-2015, 23:48.

            Comment


            • #7
              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ẻ.

              PHP Code:
              for (int a 110a++)
                              for (
              int b = (2) ; 102)
                                  for (
              int c 010c++)
                                      if (
              == 100 10 c)
                                          
              Console.WriteLine("{0}{1}{2}"abc); 
              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ĩ.
              nguyendauit@gmail.com

              Comment


              • #8
                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ỗ đó
                Last edited by 08520001; 07-11-2014, 10:25.

                Comment


                • #9
                  Originally posted by 08520001 View Post
                  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?
                  Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!

                  Comment


                  • #10
                    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.
                    Tôi không hối tiếc những gì mình đã làm. Tôi chỉ hối tiếc những gì đã không làm khi có cơ hội!

                    Comment


                    • #11
                      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é.
                      Last edited by 08520001; 07-11-2014, 10:25.

                      Comment


                      • #12
                        Đây là cách em làm bài 2
                        Code:
                                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)

                        Comment


                        • #13
                          @ 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.
                          nguyendauit@gmail.com

                          Comment


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

                            Code:
                                    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
                            --Contact me--
                            + Gmail: dthoang92@gmail.com
                            + Skype: hoang.doan212
                            Life is a Series of Choices. Life is a Series of Experiences

                            Comment


                            • #15
                              @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.
                              Last edited by 08520001; 07-11-2014, 10:25.

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X