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

[tara95]

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

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

[tara95]

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?

[12520332]

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é !

[14520214]

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);
}
}
}

[11520132]

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)

[11520327]

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.

[11520348]

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:

[11520327]

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ự.

var arr = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1];
for (i = 0; i < arr.length; ++i)
    if (arr.indexOf(arr[i]) == 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.

[11520132]

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ự.

var arr = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1];
for (i = 0; i < arr.length; ++i)
    if (arr.indexOf(arr[i]) == i && arr.indexOf(arr[i],i+1) > 0)
        console.log(arr[i]); 

[11520148]

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

[11520327]

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:

[11520132]

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?

var arr = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1];
for (i = 0; i < arr.length; ++i) {
    for (j = 0; j < i && arr[i] != arr[j]; ++j);
    if (i == j) {
        for (++j; j < arr.length && arr[i] != arr[j]; ++j);
        if (j != arr.length) console.log(arr[i]);
    }
} 

[11520537]

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.

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

[11520348]

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.

#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:

[11520327]

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.

#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;
}