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.
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*==a[j]) a[j]=0;
for (i=0,i++,i<15)
if (a*!=0) printf(a*,’ ');
[QUOTE=11520031;307185]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*==a[j]) a[j]=0;
for (i=0,i++,i<15)
if (a*!=0) printf(a*,’ ');[/QUOTE]
Cái này được viết theo ngôn ngữ lập trình nào đây?
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.
[QUOTE=tara95;307208]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.[/QUOTE]
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?
[QUOTE=11520537;307209]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?[/QUOTE]
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.
[QUOTE=tara95;307224]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.[/QUOTE]
Trường hợp này nó có thể có nhiều hơn 1 phần tử giống nó?
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* appears more than 1
if(arr*!=-1){ // do not check if arr* == -1
for(int j=i+1; j<n; ++j){
if(arr*==arr[j]){
isExisted=true; // arr* appears more than 1
arr[j]=-1; // do not check arr[j] again in future
}
}
if(isExisted==true){ // arr* appears more than 1
cout<<arr*<<" ";
}
}
}
return 0;
}
[QUOTE=11520327;307636]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* appears more than 1
if(arr*!=-1){ // do not check if arr* == -1
for(int j=i+1; j<n; ++j){
if(arr*==arr[j]){
isExisted=true; // arr* appears more than 1
arr[j]=-1; // do not check arr[j] again in future
}
}
if(isExisted==true){ // arr* appears more than 1
cout<<arr*<<" ";
}
}
}
return 0;
}
[/QUOTE]
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:
[QUOTE=11520327;307636]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* appears more than 1
if(arr*!=-1){ // do not check if arr* == -1
for(int j=i+1; j<n; ++j){
if(arr*==arr[j]){
isExisted=true; // arr* appears more than 1
arr[j]=-1; // do not check arr[j] again in future
}
}
if(isExisted==true){ // arr* appears more than 1
cout<<arr*<<" ";
}
}
}
return 0;
}
[/QUOTE]
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.
[QUOTE=11520348;307641]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:[/QUOTE]
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:
[QUOTE=11520327;307681]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:[/QUOTE]
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 && arr.indexOf(arr*,i+1) > 0)
console.log(arr*);
[QUOTE=11520132;307685]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 && arr.indexOf(arr*,i+1) > 0)
console.log(arr*);
[/QUOTE]
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.
[QUOTE=11520327;307681]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:[/QUOTE]
[QUOTE=11520327;307689]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.[/QUOTE]
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)
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*<[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* < a[i + 1])
{
tam = a*;
for (int j = 0; j < n; j++)
if (a[j] == tam)
dem++;
printf("%d “, tam);
printf(”%d
", dem);
}
}
}