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

  • #31
    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],' ');
    thế trường hợp có phần từ 0 trong mảng thì sao? Vấn đề xuất hiện

    Comment


    • #32
      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.
      Code đó của bạn 14520674, không phải của em, em chỉ đánh giá thoi.

      Comment


      • #33
        [MENTION=12722]11520537[/MENTION]
        @All

        Mình có cách này, mọi người xem thử.

        Ý tưởng của giải thuật sử dụng 1 mảng để đánh dấu số nào xuất hiện hay chưa. Tuy nhiên, thay vì cấp phát mảng, ta sử dụng một số nguyên. Khi nhìn nó dưới dạng một chuỗi bit 10101010010000 ta sẽ có được cách đánh dấu mảng dựa vào 1 số.

        Giới hạn của đoạn code này là các số giới hạn trong khoảng [-32, 32]. Nếu muốn thuật toán làm việc với số lớn hơn thì phải extend kiểu dữ liệu.

        PHP Code:
        #include <iostream>
        #include <cstdlib>
        using namespace std;

        bool isDuplicated(int sumint x){
            
        //
            // Dieu kien sum >= 0 va x >= 0
            // Kiem tra xem, bit thu x co duoc bat hay chua
            // Neu bit thu x da duoc bat thi tra ve true
            // Neu bit thu x chua duoc bat thi tra ve false
            //
            
        return (sum & ( << ) );
        }

        int main(){

            
        //
            // Khoi tao
            //
            
        int arr[19] = {12341, -2, -36237171841, -2, -3};
            
        int length sizeof(arr) / sizeof(*arr);
            
        int positiveSum 0;
            
        int negativeSum 0;
            
            
            
        //
            // Duyet va in ket qua
            //
            
        for(int counter counter length ; ++ counter )
                if( 
        arr[counter] > ){
                    
        //
                    // Neu arr[counter] la so duong
                    // Ta se dung positiveSum de kiem tra xem arr[counter] da xuat hien hay chua
                    // Neu da xuat hien thi bo qua
                    // Neu chua thi cong vao sum, va in ra man hinh
                    //
                    
        if(isDuplicated(positiveSumarr[counter]) == false){
                        
        positiveSum positiveSum + (<< arr[counter]);
                        
        cout << arr[counter] << endl;
                    }
                }
                else{
                    
        //
                    // Neu arr[counter] la so am
                    // Ta se su dung negativeSum de kiem tra
                    // Hoan toan tuong tu voi positiveSum, nhung danh cho so am
                    //
                    
        if(isDuplicated(negativeSum, - arr[counter]) == false){
                        
        negativeSum negativeSum + (<< (- arr[counter]) );
                        
        cout << arr[counter] << endl;
                    }
                }
            
            
            
        //
            // Tra ve ket qua chuong trinh chay thanh cong
            //
            
        return 0;

        nguyendauit@gmail.com

        Comment


        • #34
          Originally posted by 10520100 View Post
          [MENTION=12722]11520537[/MENTION]
          @All

          Mình có cách này, mọi người xem thử.

          Ý tưởng của giải thuật sử dụng 1 mảng để đánh dấu số nào xuất hiện hay chưa. Tuy nhiên, thay vì cấp phát mảng, ta sử dụng một số nguyên. Khi nhìn nó dưới dạng một chuỗi bit 10101010010000 ta sẽ có được cách đánh dấu mảng dựa vào 1 số.

          Giới hạn của đoạn code này là các số giới hạn trong khoảng [-32, 32]. Nếu muốn thuật toán làm việc với số lớn hơn thì phải extend kiểu dữ liệu.

          PHP Code:
          #include <iostream>
          #include <cstdlib>
          using namespace std;

          bool isDuplicated(int sumint x){
              
          //
              // Dieu kien sum >= 0 va x >= 0
              // Kiem tra xem, bit thu x co duoc bat hay chua
              // Neu bit thu x da duoc bat thi tra ve true
              // Neu bit thu x chua duoc bat thi tra ve false
              //
              
          return (sum & ( << ) );
          }

          int main(){

              
          //
              // Khoi tao
              //
              
          int arr[19] = {12341, -2, -36237171841, -2, -3};
              
          int length sizeof(arr) / sizeof(*arr);
              
          int positiveSum 0;
              
          int negativeSum 0;
              
              
              
          //
              // Duyet va in ket qua
              //
              
          for(int counter counter length ; ++ counter )
                  if( 
          arr[counter] > ){
                      
          //
                      // Neu arr[counter] la so duong
                      // Ta se dung positiveSum de kiem tra xem arr[counter] da xuat hien hay chua
                      // Neu da xuat hien thi bo qua
                      // Neu chua thi cong vao sum, va in ra man hinh
                      //
                      
          if(isDuplicated(positiveSumarr[counter]) == false){
                          
          positiveSum positiveSum + (<< arr[counter]);
                          
          cout << arr[counter] << endl;
                      }
                  }
                  else{
                      
          //
                      // Neu arr[counter] la so am
                      // Ta se su dung negativeSum de kiem tra
                      // Hoan toan tuong tu voi positiveSum, nhung danh cho so am
                      //
                      
          if(isDuplicated(negativeSum, - arr[counter]) == false){
                          
          negativeSum negativeSum + (<< (- arr[counter]) );
                          
          cout << arr[counter] << endl;
                      }
                  }
              
              
              
          //
              // Tra ve ket qua chuong trinh chay thanh cong
              //
              
          return 0;

          Sau 1 hồi nghiền ngẫm thì đã hiểu ra cách giải. Mỗi số trong mảng sẽ được đánh dấu bằng 1 bit trong positiveSum hoặc negativeSum. Do chỉ dùng 1 bit để đánh dấu 1 số và đảm bảo 2 số khác nhau không trùng bit đánh dấu, ta cần chuyển số cần đánh dấu về dạng lũy thừa của 2. Giả sử số cần đánh dấu là 3: ta sẽ chuyển 3 thành 2 mũ 3 = 8 và số 8 là lũy thừa của 2 nên có thể sử dụng 1 bit để dánh dấu trong positiveSum bằng cách lấy positiveSum + 8....

          Comment


          • #35
            ý anh là tìm cách tối ưu mà không cần phải dùng thêm bất cứ mảng phụ nào hay sao.
            - nếu dùng thêm mảng phụ. chỉ cần một mảng đánh dấu. sẽ duyệt được trong 2*O(n) với điều kiện các phần tử trong dãy đủ nhỏ(không quá 10^6)
            -còn nếu ko cùng bất cứ mảng phụ nào thì duyệt trong O(n^2). với mỗi phần tử đã duyệt thì loại bỏ phần tử đó bằng cách gán cho nó một giá trị chắc chắc ko thuộc trong dãy.

            Comment


            • #36
              Originally posted by 13520211 View Post
              ý anh là tìm cách tối ưu mà không cần phải dùng thêm bất cứ mảng phụ nào hay sao.
              - nếu dùng thêm mảng phụ. chỉ cần một mảng đánh dấu. sẽ duyệt được trong 2*O(n) với điều kiện các phần tử trong dãy đủ nhỏ(không quá 10^6)
              -còn nếu ko cùng bất cứ mảng phụ nào thì duyệt trong O(n^2). với mỗi phần tử đã duyệt thì loại bỏ phần tử đó bằng cách gán cho nó một giá trị chắc chắc ko thuộc trong dãy.
              Không dùng mảng phụ --> Loại cách 1.
              Cách 2: đã có lời giải trong những # trước.
              Bài của 10520100 khá hay, e nên tham khảo.

              Comment


              • #37
                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);
                }
                }
                }
                Cái "int dem=0;" bạn để trong vòng for (int i = 0; i < n;i++) thì ok

                Comment


                • #38
                  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
                  PHP Code:
                  void HoanVi(int &aint &b)
                  {
                      
                  int temp a;
                      
                  b;
                      
                  temp;
                  }
                  void BubleSort(int A[], int n)
                  {
                      for (
                  int i 0i<1i++)
                      for (
                  int j 1j>ij--)
                      if (
                  A[j]<A[1])
                          
                  HoanVi(A[j], A[1]);
                  }
                  void tansuat(int a[], int n)
                  {
                      
                  int dem 0;
                      
                  int tam ;
                      
                  BubleSort(an);
                      for (
                  int i 0n;i++)
                      {
                          if (
                  a[i] < a[1])
                          {
                              
                  tam a[i];
                              for (
                  int j 0nj++)
                              if (
                  a[j] == tam)
                                  
                  dem++;
                              
                  printf("%d\t"tam);
                              
                  printf("%d\n"dem);
                          }
                      }

                  Cái này anh viết bằng js em có thể tham khảo thuật toán, không cần sắp xếp lại. Chỉ chạy 2 vòng lặp lồng nhau. C vs JS cú pháp cũng không khác lắm đâu. Anh lấy luôn cái mảng của thread.

                  PHP Code:
                  var arr = [123416237171841];
                  for (
                  0arr.length; ++i) {
                      for (
                  0i; ++j){ //Kiểm tra xem phần tử thứ i có phải là lần đầu tiên xuất hiện hay không
                          
                  if (arr[i] == arr[j]) break;  //Kiểm tra xem phần tử trước phần tử thứ i có phần tử nào = phần tử thứ i không
                      
                  }
                      if (
                  == j) { //Nếu không có phần tử nào trước phần tử thứ i có giá trị bằng phần tử thứ i -> lần đầu tiên xuất hiện trong mảng
                          
                  var count 1// Khai báo bộ đếm ban đầu bằng 1
                          
                  for (++jarr.length; ++j){ // Đếm từ phần tử thứ i+1 trở đi những phần thử bằng phần tử thứ i
                              
                  if (arr[i] == arr[j]) ++count// Tăng bộ đếm
                          
                  }
                          
                  console.log(arr[i] + ' - ' count); // Print
                      
                  }

                  Hoặc viết ngắn gọn lại thành:
                  PHP Code:
                  var arr = [123416237171841];
                  for (
                  0arr.length; ++i) {
                      for (
                  0&& arr[i] != arr[j]; ++j);
                      if (
                  == j) {
                          var 
                  count 1;
                          for (++
                  jarr.length && (arr[i] != arr[j] || ++count); ++j);
                          
                  console.log(arr[i] + ' - ' count);
                      }

                  Kết quả:
                  1 - 5
                  2 - 2
                  3 - 2
                  4 - 2
                  6 - 1
                  7 - 2
                  8 - 1
                  Last edited by 11520132; 07-12-2014, 02:35.

                  Comment

                  LHQC

                  Collapse
                  Working...
                  X