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
    11520132
    Nguyễn Phi Hùng

  • 11520132
    replied
    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
    11520132
    Nguyễn Phi Hùng
    Last edited by 11520132; 07-12-2014, 02:35.

    Leave a comment:

  • 14520769
    Lã Hoàng Thái Sơn

  • 14520769
    replied
    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

    Leave a comment:

  • 11520327
    Lăng Hoài Sang

  • 11520327
    replied
    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.

    Leave a comment:

  • 13520211
    Nguyễn Trung Đức

  • 13520211
    replied
    ý 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.

    Leave a comment:

  • 11520327
    Lăng Hoài Sang

  • 11520327
    replied
    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....

    Leave a comment:

  • 10520100
    Đào Anh Nguyên

  • 10520100
    replied
    [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;

    Leave a comment:

  • 11520327
    Lăng Hoài Sang

  • 11520327
    replied
    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.

    Leave a comment:

  • 13520939
    Lê Văn Hiếu Trọng

  • 13520939
    replied
    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

    Leave a comment:

  • 14520183
    Nguyễn Hoàng Đức

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

    Leave a comment:

  • 14520183
    Nguyễn Hoàng Đức

  • 14520183
    replied
    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();
    }

    Leave a comment:

  • 08520021
    Đỗ Trọng Ân

  • 08520021
    replied
    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
    08520021
    Đỗ Trọng Ân
    Last edited by 08520021; 21-11-2014, 16:28.

    Leave a comment:

  • truonganpn
    Campus staff

  • truonganpn
    replied
    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.

    Leave a comment:

  • 10520355
    Cao Văn Nhàn

  • 10520355
    replied
    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.

    Leave a comment:

  • 11520327
    Lăng Hoài Sang

  • 11520327
    replied
    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.

    Leave a comment:

  • 14520674
    Thái Viết Phong

  • 14520674
    replied
    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] <<" ";
    }

    }
    14520674
    Thái Viết Phong
    Last edited by 14520674; 21-11-2014, 11:06.

    Leave a comment:

LHQC

Collapse
Working...
X