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

  • #16
    Originally posted by 11520132 View Post
    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]); 
    arr.IndexOf nó hoạt động bên dưới như thế nào chắc b cũng biết mà. Cơ bản thì cũng như b viết vòng for thôi. Tính ra thì cũng 3 for.

    Comment


    • #17
      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:
      Sort mảng xong là thấy cách làm rồi. :shy:

      Comment


      • #18
        Originally posted by 11520348 View Post
        Sort mảng xong là thấy cách làm rồi. :shy:
        Sort xong phải duyệt thêm lần nữa mà thánh.

        Comment


        • #19
          Originally posted by 11520327 View Post
          arr.IndexOf nó hoạt động bên dưới như thế nào chắc b cũng biết mà. Cơ bản thì cũng như b viết vòng for thôi. Tính ra thì cũng 3 for.
          Làm sao ra ba vòng lồng nhau được nhỉ, cái index đầu nó chỉ chạy tới i, cái index sau nó chạy từ i+1 tới length, vậy maximum là 2 vòng lồng nhau thôi chứ, nó tương đương với
          for (i=0;i<arr.length;++i) for (j=0;j<arr.lenght;++j) thôi => O(n2)
          Last edited by 11520132; 22-11-2014, 00:55.

          Comment


          • #20
            Em năm nhất, đang học mảng, bon chen tý, đang bí bài " nhhập vào mảng, liệt kê tần suất xuất hiện các phần tử trong mảng, moi phần tử liêt kê 1 lần", dự là sẽ xắp xếp tăng dần trước nếu a[i]<[ai+1] thì mới sử lý đếm vậy là ko bị trùng.....em viết code bị lặp vô tận, anh nào giúp voi, thân
            void HoanVi(int &a, int &b)
            {
            int temp = a;
            a = b;
            b = temp;
            }
            void BubleSort(int A[], int n)
            {
            for (int i = 0; i<n - 1; i++)
            for (int j = n - 1; j>i; j--)
            if (A[j]<A[j - 1])
            HoanVi(A[j], A[j - 1]);
            }
            void tansuat(int a[], int n)
            {
            int dem = 0;
            int tam ;
            BubleSort(a, n);
            for (int i = 0; i < n;i++)
            {
            if (a[i] < a[i + 1])
            {
            tam = a[i];
            for (int j = 0; j < n; j++)
            if (a[j] == tam)
            dem++;
            printf("%d\t", tam);
            printf("%d\n", dem);
            }
            }
            }

            Comment


            • #21
              Originally posted by 14520214 View Post
              Em năm nhất, đang học mảng, bon chen tý, đang bí bài " nhhập vào mảng, liệt kê tần suất xuất hiện các phần tử trong mảng, moi phần tử liêt kê 1 lần", dự là sẽ xắp xếp tăng dần trước nếu a[i]<[ai+1] thì mới sử lý đếm vậy là ko bị trùng.....em viết code bị lặp vô tận, anh nào giúp voi, thân
              void HoanVi(int &a, int &b)
              {
              int temp = a;
              a = b;
              b = temp;
              }
              void BubleSort(int A[], int n)
              {
              for (int i = 0; i<n - 1; i++)
              for (int j = n - 1; j>i; j--)
              if (A[j]<A[j - 1])
              HoanVi(A[j], A[j - 1]);
              }
              void tansuat(int a[], int n)
              {
              int dem = 0;
              int tam ;
              BubleSort(a, n);
              for (int i = 0; i < n;i++)
              {
              if (a[i] < a[i + 1])
              {
              tam = a[i];
              for (int j = 0; j < n; j++)
              if (a[j] == tam)
              dem++;
              printf("%d\t", tam);
              printf("%d\n", dem);
              }
              }
              }
              Bạn để code trong thẻ thì mọi người mới giúp được nhé !

              Comment


              • #22
                Originally posted by 11520272 View Post
                Trường hợp này nó có thể có nhiều hơn 1 phần tử giống nó?
                Em đang nêu ra điều kiện để phần tử được in ra thỏa "Xuất hiện nhiều hơn 1 lần và không được in trùng". "Có ít nhất 1 phần tử giống nó (>=1)" thì đã bao gồm "có nhiều hơn 1 phần tử giống nó (>1)". Em không hiểu ý anh lắm?
                Last edited by tara95; 21-11-2014, 09:28.
                I don't know the secret to success, but the secret to failure is trying to please everyone

                Comment


                • #23
                  Originally posted by 14520214 View Post
                  Em năm nhất, đang học mảng, bon chen tý, đang bí bài " nhhập vào mảng, liệt kê tần suất xuất hiện các phần tử trong mảng, moi phần tử liêt kê 1 lần", dự là sẽ xắp xếp tăng dần trước nếu a[i]<[ai+1] thì mới sử lý đếm vậy là ko bị trùng.....em viết code bị lặp vô tận, anh nào giúp voi, thân
                  Code:
                  #include <stdio.h>
                  
                  void HoanVi(int &a, int &b)
                  {
                      int temp = a;
                      a = b;
                      b = temp;
                  }
                  void BubleSort(int A[], int n)
                  {
                      for (int i = 0; i < n - 1; i++)
                          for (int j = n - 1; j > i; j--)
                      if (A[j] < A[j - 1])
                          HoanVi(A[j], A[j - 1]);
                  }
                  void tansuat(int a[], int n)
                  {
                      int dem = 0;
                      int tam ;
                      BubleSort(a, n);
                      for (int i = 0; i < n;i++)
                      {
                          if (a[i] < a[i + 1])
                          {
                              tam = a[i];
                              for (int j = 0; j < n; j++)
                                  if (a[j] == tam)
                                      dem++;
                              printf("%d\t", tam);
                              printf("%d\n", dem);
                          }
                      }
                  }
                  
                  int main()
                  {
                      int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                      tansuat(arr,15);
                      return 0;
                  }
                  Anh chạy tốt mà, nhưng sai kết quả. Em chạy lại và xem kết quả thử xem.
                  Last edited by tara95; 21-11-2014, 09:29.
                  I don't know the secret to success, but the secret to failure is trying to please everyone

                  Comment


                  • #24
                    Mọi người thử thuật toán củ chuối với 2 vòng for này của mình xem
                    #include <iostream>
                    using namespace std;
                    int main()
                    {
                    int a[100],n,i,j,mark;
                    {
                    // Nhap mang ...
                    }
                    // Xử lí
                    for(i=0;i<n;i++)
                    {
                    mark
                    =-1;
                    for(j=0;j<n;j++)
                    if (a[i]==a[j]&& i!=j) mark=j;
                    if(mark<i && mark !=-1)
                    cout<< a[i] <<" ";
                    }

                    }
                    Last edited by 14520674; 21-11-2014, 11:06.
                    PHP Code:
                    Full nameThai Viet Phong
                    Facebook
                    www.facebook.com/ThaiVietPhong.ITM
                    Email
                    thaivietphong.net@gmail.com 
                    Tìm trước khi hỏi bạn sẽ giỏi hơn mỗi khi tìm

                    Comment


                    • #25
                      Originally posted by 14520674 View Post
                      Mọi người thử thuật toán củ chuối với 2 vòng for này của mình xem
                      Code:
                      #include <iostream>
                       
                      using namespace std;
                       
                      int main()
                      {
                         int a[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                         int n=15;
                         for(int i=0;i<n;i++)
                          {
                              int mark=-1;
                              for(int j=0;j<n;j++)
                                  if (a[i]==a[j]&& i!=j) 
                                      mark=j;
                              if(mark<i && mark !=-1)
                                  cout<< a[i] <<" ";
                          }
                         
                         return 0;
                      }
                      2 for, cho kết quả đúng, không thay đổi cấu trúc mảng. O(n2). Có lẽ là lời giải hợp lí tới hiện tại.

                      Comment


                      • #26
                        Originally posted by 11520327 View Post
                        Code:
                        #include <iostream>
                         
                        using namespace std;
                         
                        int main()
                        {
                           int a[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
                           int n=15;
                           for(int i=0;i<n;i++)
                            {
                                int mark=-1;
                                for(int j=0;j<n;j++)
                                    if (a[i]==a[j]&& i!=j) 
                                        mark=j;
                                if(mark<i && mark !=-1)
                                    cout<< a[i] <<" ";
                            }
                           
                           return 0;
                        }
                        2 for, cho kết quả đúng, không thay đổi cấu trúc mảng. O(n2). Có lẽ là lời giải hợp lí tới hiện tại.
                        Lâu lâu dạo forum, anh có cách này chia sẻ chứ không em cứ nghĩ cách của em là tối ưu nữa.
                        Với trường hợp này, nếu các phần tử ai giới hạn bé hơn khoảng 10^8 (vì lớn hơn có thể mảng không chứa nổi) thì mình có thể tạo một mảng đánh dấu. Các phần tử sẽ có 3 trạng thái là đã in, xuất hiện lần đầu, và trạng thái còn lại. Như vậy độ phức tạp chỉ là O(n) thôi.

                        PHP Code:
                        nội dung file input.txt:
                        15
                        1 2 3 4 1 6 2 3 7 1 7 1 8 4 1

                        source
                        #include <iostream>
                        #include <cstdio>
                        using namespace std;
                        char arr[100000001];
                        int n,x;
                        int main() {
                            
                        freopen("input.txt","r",stdin);
                            
                        memset(arr,0,sizeof(arr));
                            
                        cin>>n;
                            while(
                        n--){
                                
                        cin>>x;
                                
                        arr[x]++;
                                if(
                        arr[x]==0arr[x]--;
                                else if(
                        arr[x]>1arr[x]=-1cout<<x<<" ";
                            }
                            return 
                        0;

                        Nếu ai lớn hơn 10^8 thì các bạn có thể sử dụng cấu dữ liệu vào để giảm độ phức tạp, ví dụ cây nhị phân, hoặc đại loại nhị phân để giảm còn O(nLog) Trong C++ có cấu trúc map, các bạn có thể dùng.

                        PHP Code:
                        nội dung file input.txt:
                        15
                        1 2 3 4 1 6 2 3 7 1 7 1 8 4 1

                        source code với ai trong kiểu long long int 
                        (2^63 -1)
                        #include <iostream>
                        #include <cstdio>
                        #include <map>
                        using namespace std;
                        typedef long long int ll;
                        int n,x;
                        map<llintmm;
                        int main() {
                            
                        freopen("input.txt","r",stdin);
                            
                        cin>>n;
                            while(
                        n--){
                                
                        cin>>x;
                                
                        mm[x]++;
                                if(
                        mm[x]==0mm[x]--;
                                else if(
                        mm[x]>1mm[x]=-1,cout<<x<<" ";
                            }
                            return 
                        0;

                        code trên anh dùng nhập xuất từ file muốn nhập xuất từ console thì bỏ dòng freopen("input.txt","r",stdin); đi nha.
                        University of Information Technology
                        Cao Văn Nhàn _ CE10520355
                        SĐT: 0188 403 4943

                        Email: caovannhan2002@gmail.com

                        Comment


                        • #27
                          Originally posted by 10520355 View Post
                          Lâu lâu dạo forum, anh có cách này chia sẻ chứ không em cứ nghĩ cách của em là tối ưu nữa.
                          Với trường hợp này, nếu các phần tử ai giới hạn bé hơn khoảng 10^8 (vì lớn hơn có thể mảng không chứa nổi) thì mình có thể tạo một mảng đánh dấu. Các phần tử sẽ có 3 trạng thái là đã in, xuất hiện lần đầu, và trạng thái còn lại. Như vậy độ phức tạp chỉ là O(n) thôi.

                          Nếu ai lớn hơn 10^8 thì các bạn có thể sử dụng cấu dữ liệu vào để giảm độ phức tạp, ví dụ cây nhị phân, hoặc đại loại nhị phân để giảm còn O(nLog) Trong C++ có cấu trúc map, các bạn có thể dùng.
                          Ban đầu bạn chủ thớt nói là không muốn dùng thêm mảng phụ mà Có thể bạn ấy không nghĩ đến mảng đánh dấu hay một cấu trúc dữ liệu khác nhưng tui nghĩ về bản chất thì chữ "mảng phụ" nó cũng ám chỉ đến vấn đề space/time trade-off thôi. Không dùng thêm bộ nhớ (dù là ở dạng mảng phụ, mảng đánh dấu hay một cấu trúc dữ liệu khác) thì chắc chắn thuật toán sẽ phải chạy lâu hơn.

                          Comment


                          • #28
                            Ngồi buồn cắn móng tay
                            Code:
                            ex = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1]
                            
                            def unduplicate(arr):
                                checker = 0
                                occurred = 0
                                length = len(arr)
                                
                                for i in range(length):
                                    checker |= 1 << i
                                    
                                    for l in range(i + 1, length):
                                        if (not(checker >> l) % 2) and (arr[l] == arr[i]):
                                            checker |= 1 << l
                                            if not occurred:
                                                print arr[i]
                                                occurred = 1
                                                
                                    occurred = 0
                            
                            unduplicate(ex)
                            Array lớn thì đành chịu
                            Last edited by 08520021; 21-11-2014, 16:28.

                            Comment


                            • #29
                              Mọi người ngó qua đoạn code của em phát. Em năm 1 trình độ nhập môn lập trình ạ ^^

                              #include <stdio.h>
                              #include <conio.h>

                              void main()
                              {
                              int a[15] = { 1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1 };
                              for (int i = 0; i <= 14; i++)
                              {
                              int out = 0;
                              for (int j = 0; (j <= 14); j++)
                              {
                              if (j == i)
                              continue;
                              else
                              if (a[j] == a[i])
                              if (j < i)
                              break;
                              else
                              out = 1;

                              }
                              if (out == 1)
                              printf("%3d", a[i]);
                              }
                              getch();
                              }

                              Comment


                              • #30
                                xem cái picture cho dễ nha mọi người
                                code.jpg

                                Comment

                                LHQC

                                Collapse
                                Working...
                                X