Announcement

Collapse
No announcement yet.

[Thuật toán] Cần tìm cách giải khác cho một nài toán cũ rích

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

  • [Thuật toán] Cần tìm cách giải khác cho một nài toán cũ rích

    Chào mọi người,

    Hôm nay một nhóc học CNTT (không phải trường mình) có hỏi mình một bài toán về duyệt mảng một chiều nhưng cách giải của em thì không vừa lòng nó. Bài toán như sau:
    "Cho một mảng số nguyên, in ra các phần tử (a) chỉ xuất hiện duy nhất một lần, (b) xuất hiện nhiều hơn 1 lần và không được in trùng."
    Vd: arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
    thì dòng 1 in ra là: 6, 8
    dòng 2 in ra là: 1, 2, 3, 4, 7

    Về cách giải quyết câu a thì không cần phải bàn. Vấn đề nằm ở câu b, vì không chuyên tâm vào cái này nên cách của mình là sử dụng thêm một mảng, và bắt đầu với việc duyệt mảng ban đầu, gặp phần tử nào chưa trùng thì lưu nó vào mảng, cuối cùng là in ra mảng này. Nhưng thằng nhóc không chịu vì nó nói không muốn dùng mảng để lưu, nó muốn duyệt mảng ban đầu trực tiếp rồi in ra luôn.

    Vì thế bạn nào có cách giải thỏa được lòng thằng nhóc thì đưa ra cùng thảo luận.
    Last edited by 11520537; 16-11-2014, 02:59.
    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!

  • #2
    Có thể dùng cách này thử xem
    Trước tiên loại 2 phần tử xuất hiện 1 lần duy nhất bằng cách cho nó về 0 luôn. Sau đó
    for (i=0,i++,i<15)
    for (j=0,j++,j<15)
    if (a[i]==a[j]) a[j]=0;
    for (i=0,i++,i<15)
    if (a[i]!=0) printf(a[i],' ');

    Comment


    • #3
      Originally posted by 11520031 View Post
      Có thể dùng cách này thử xem
      Trước tiên loại 2 phần tử xuất hiện 1 lần duy nhất bằng cách cho nó về 0 luôn. Sau đó
      for (i=0,i++,i<15)
      for (j=0,j++,j<15)
      if (a[i]==a[j]) a[j]=0;
      for (i=0,i++,i<15)
      if (a[i]!=0) printf(a[i],' ');
      Cái này được viết theo ngôn ngữ lập trình nào đâ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


      • #4
        Em nghĩ nếu bài này nếu không dùng mảng để lưu (giá trị chỉ xuất hiện 1 lần hoặc số lần xuất hiện của phần tử trong mảng) thì anh dùng 2 vòng lặp for, dùng biến đếm số phần tử giống nó xuất hiện trong mảng.
        I don't know the secret to success, but the secret to failure is trying to please everyone

        Comment


        • #5
          Originally posted by tara95 View Post
          Em nghĩ nếu bài này nếu không dùng mảng để lưu (giá trị chỉ xuất hiện 1 lần hoặc số lần xuất hiện của phần tử trong mảng) thì anh dùng 2 vòng lặp for, dùng biến đếm số phần tử giống nó xuất hiện trong mảng.
          Mình không hiểu đếm số phần tử nhau để làm gì? Bạn giải thích rõ hơn được không?
          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


          • #6
            Originally posted by 11520537 View Post
            Mình không hiểu đếm số phần tử nhau để làm gì? Bạn giải thích rõ hơn được không?
            Em hơi nhầm một tí.
            Anh thử cách này xem: Duyệt hết các phần tử của mảng, phần tử được in ra thỏa mãn: trước nó không có phần tử nào giống nó, và sau nó có ít nhất 1 phần tử giống nó, tức là sẽ in phần tử xuất hiện đầu tiên.
            I don't know the secret to success, but the secret to failure is trying to please everyone

            Comment


            • #7
              Originally posted by tara95 View Post
              Em hơi nhầm một tí.
              Anh thử cách này xem: Duyệt hết các phần tử của mảng, phần tử được in ra thỏa mãn: trước nó không có phần tử nào giống nó, và sau nó có ít nhất 1 phần tử giống nó, tức là sẽ in phần tử xuất hiện đầu tiên.
              Trường hợp này nó có thể có nhiều hơn 1 phần tử giống nó?
              When we are young, work to learn, NOT to earn.
              E: ninhho At outlook dot com
              M: +8490 3000 670

              Comment


              • #8
                for (i=0,i<n,i++)
                {
                for (j=i,j<n,j++)
                if (a[i]=a[j])
                for (k=i-1,k--,k<0)
                if (a[i]==a[k]) {check=false;break}
                else check=true;
                if (check=true) printf(a[i]);
                }

                Comment


                • #9
                  Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.
                  Code:
                  #include <iostream>
                   
                  using namespace std;
                   
                  int main()
                  {
                     int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                     int n=15;
                     int k=-1; // k is used to set for unchecked element
                     for(int i=0; i<n-1; ++i){
                         bool isExisted = false; // check if arr[i] appears more than 1
                         if(arr[i]!=-1){  // do not check if arr[i] == -1
                             for(int j=i+1; j<n; ++j){          
                                 if(arr[i]==arr[j]){
                                     isExisted=true; // arr[i] appears more than 1
                                     arr[j]=-1; // do not check arr[j] again in future
                                 }
                             }
                             if(isExisted==true){ // arr[i] appears more than 1
                                 cout<<arr[i]<<" ";
                             }
                         }
                     }
                     
                     return 0;
                  }
                  Last edited by 11520327; 20-11-2014, 07:49.

                  Comment


                  • #10
                    Originally posted by 11520327 View Post
                    Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.
                    Code:
                    #include <iostream>
                     
                    using namespace std;
                     
                    int main()
                    {
                       int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                       int n=15;
                       int k=-1; // k is used to set for unchecked element
                       for(int i=0; i<n-1; ++i){
                           bool isExisted = false; // check if arr[i] appears more than 1
                           if(arr[i]!=-1){  // do not check if arr[i] == -1
                               for(int j=i+1; j<n; ++j){          
                                   if(arr[i]==arr[j]){
                                       isExisted=true; // arr[i] appears more than 1
                                       arr[j]=-1; // do not check arr[j] again in future
                                   }
                               }
                               if(isExisted==true){ // arr[i] appears more than 1
                                   cout<<arr[i]<<" ";
                               }
                           }
                       }
                       
                       return 0;
                    }
                    Chủ thớt không muốn phá vỡ cái mảng. Muốn giữ nguyên hiện trạng ban đầu của mảng. :sogood:
                    Đảm bảo thế này thớt sẽ vào phản biện lại. :look_down:

                    Comment


                    • #11
                      Originally posted by 11520327 View Post
                      Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.
                      Code:
                      #include <iostream>
                       
                      using namespace std;
                       
                      int main()
                      {
                         int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                         int n=15;
                         int k=-1; // k is used to set for unchecked element
                         for(int i=0; i<n-1; ++i){
                             bool isExisted = false; // check if arr[i] appears more than 1
                             if(arr[i]!=-1){  // do not check if arr[i] == -1
                                 for(int j=i+1; j<n; ++j){          
                                     if(arr[i]==arr[j]){
                                         isExisted=true; // arr[i] appears more than 1
                                         arr[j]=-1; // do not check arr[j] again in future
                                     }
                                 }
                                 if(isExisted==true){ // arr[i] appears more than 1
                                     cout<<arr[i]<<" ";
                                 }
                             }
                         }
                         
                         return 0;
                      }
                      Về cách củ chuối này thì mình cũng đã áp dụng với cách tương tự của bạn đó là mình gán 0 cho phần tử bị trùng.
                      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


                      • #12
                        Mình làm như này, không thay đổi mảng, không dùng mảng tạm không biết đáp ứng được không?
                        PHP Code:
                        var arr = [123416237171841];
                        for (
                        0arr.length; ++i) {
                            for (
                        0&& arr[i] != arr[j]; ++j);
                            if (
                        == j) {
                                for (++
                        jarr.length && arr[i] != arr[j]; ++j);
                                if (
                        != arr.lengthconsole.log(arr[i]);
                            }

                        Last edited by 11520132; 20-11-2014, 11:20.

                        Comment


                        • #13
                          Originally posted by 11520348 View Post
                          Chủ thớt không muốn phá vỡ cái mảng. Muốn giữ nguyên hiện trạng ban đầu của mảng. :sogood:
                          Đảm bảo thế này thớt sẽ vào phản biện lại. :look_down:
                          Có t đây :love:. Có cách nào làm mà tối ưu k ta? Củ chuối nhưng dc cái chạy nhanh. Còn cái cách 3 vòng for thì không bàn ở đây. :doubt:
                          Last edited by 11520327; 20-11-2014, 15:16.

                          Comment


                          • #14
                            viết 2 hàm kiểm tra bool KiemTraTrung(int[] a, int n) và bool KiemTraDaIn(int[] a, int n, int index) là giải quết cả 2 câu
                            Last edited by 11520148; 20-11-2014, 15:57.

                            Comment


                            • #15
                              Originally posted by 11520327 View Post
                              Có t đây :love:. Có cách nào làm mà tối ưu k ta? Củ chuối nhưng dc cái chạy nhanh. Còn cái cách 3 vòng for thì không bàn ở đây. :doubt:
                              Của mình 2 vòng for lồng nhau thôi mà. Mình viết bằng js, có thể viết lại như thế này cho ngắn, nhưng ngôn ngữ khác thì có thể hàm indexOf không hoạt động tương tự.

                              PHP Code:
                              var arr = [123416237171841];
                              for (
                              0arr.length; ++i)
                                  if (
                              arr.indexOf(arr[i]) == && arr.indexOf(arr[i],i+1) > 0)
                                      
                              console.log(arr[i]); 
                              Last edited by 11520132; 20-11-2014, 17:23.

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X